The Glivenko Cantelli Theorem and its Generalizations Thomas Kahle August 21,2006 In this note we will study upper bounds of random variables of the type sup vn(A)-v(A)川： AEA where A is a class of sets that needs to fulfill certain assumptions.These bounds are important tools in the analysis of learning processes and probabilistic theories of pattern recognition. The presentation given here is based on [DGL96]. 1 Hoeffdings inequality Lemma 1 (Cheby shev inequality).Lete>0 and X E C2 then VX PIX-EXI≥≤ Theorem 2 (Hoeffdings inequality).Let X1,...,Xn,be independent bounded random vari- ables such that Xi fall in the interval ai,bi]with probability one.Denote their sum by Sn=Xi.Then for any e>0 we have P{S-E5n≥≤e-21∑，6-a)2 d P{Sn-ESn≤-e}≤e-2E1∑6-a)P Proof.Use convexity of the exponential function to prove that for a random variable X with EX=0anda≤X≤b for any s>0 we have E{ex}≤e2b-a2/s The proof is now based on Chernoff's bounding method:Use the Markov inequality to see that for a nonnegative random variable X and e>0 we have P(X≥sX Therefore if s>0 and X an arbitrary random variable P{X≥e}=P{ex≥ese}≤ Eesx ese 1The Glivenko Cantelli Theorem and its Generalizations Thomas Kahle August 21, 2006 In this note we will study upper bounds of random variables of the type sup A∈A |νn(A) − ν(A)| , where A is a class of sets that needs to fulll certain assumptions. These bounds are important tools in the analysis of learning processes and probabilistic theories of pattern recognition. The presentation given here is based on [DGL96]. 1 Hoedings inequality Lemma 1 (Chebyshev inequality). Let ² > 0 and X ∈ L2 then P {|X − EX| ≥ ²} ≤ VX ² 2 . Theorem 2 (Hoedings inequality). Let X1, . . . , Xn, be independent bounded random vari￾ables such that Xi fall in the interval [ai , bi ] with probability one. Denote their sum by Sn = Pn i=1 Xi . Then for any ² > 0 we have P {Sn − ESn ≥ ²} ≤ e −2² 2/ Pn i=1(bi−ai) 2 and P {Sn − ESn ≤ −²} ≤ e −2² 2/ Pn i=1(bi−ai) 2 Proof. Use convexity of the exponential function to prove that for a random variable X with EX = 0 and a ≤ X ≤ b for any s > 0 we have E © e sXª ≤ e s 2 (b−a) 2/8 . The proof is now based on Cherno 's bounding method: Use the Markov inequality to see that for a nonnegative random variable X and ² > 0 we have P {X ≥ ²} ≤ EX ² Therefore if s > 0 and X an arbitrary random variable P {X ≥ ²} = P © e sX ≥ e s²ª ≤ Ee sX e s² . 1