Chernoff's method now is to find an s>0 that minimizes the upper bound or at least makes it small.In our case we have =eⅡE{e-w} by independence 1 ≤e-eⅡea-aP/sby first line of proof =e-sees2∑-1(b:-a4)2/8 =e-2e2/∑-16-a4)2 chooses=4e/∑-a)2 i=l The second inequality is proved analogously. ▣ 2 The Glivenko Cantelli Theorem As a fir st step we study an alternative proof of the well known theorem Theorem 3 (Glivenko-Cantelli).Let Z1,...:Zn be i.i.d.real valued random variables with distribution function F(z)=P(Z1 2).Let 5▣1 be the standard empirical distribution function.Then P{supF(e)-Fn(a训>e}≤8(n+1)e-n/32 z∈R and in particular by the Borel-Cantelli lemma lim supF(z）-Fn(z川=0 with probability one n→0∞ze2 The proof we will give is not the simplest one possible,but it contains the ideas of the generalization we will consider later.The argument given here is due to symmetrization ideas of Dudley [Dud78]and Pollard Pol84]. Proof.Assume ne2>2,otherwise the bound is trivial.Introduce the following notation v(A=P{☑∈A}anda(A)=是∑=llZ,eA}where AR is a measurable st..Denote by A the class of sets of the form (-oo,2],zER.Then we have sup lF(2)-Fn(2)=sup Ivn(A)-v(A)I. zER AEA STEP 1.FIRST SYMMETRIZATION BY A GHOST SAMPLE Define random variables Zi,...,ZER such that Z1,...,Zn,Z1,...,Zn are all i.i.d.Denote by the empirical measure of the primed variables.For ne2 2 we have P{腮.(-(4训>s2P{腰.(-(A训≥引 2Cherno's method now is to nd an s > 0 that minimizes the upper bound or at least makes it small. In our case we have P {Sn − ESn ≥ ²} ≤ e −s²E ( exp à s Xn i=1 (Xi − EXi) !) = e−s² Yn i=1 E n e s(Xi−EXi) o by independence ≤ e −s² Yn i=1 e s 2 (bi−ai) 2/8 by rst line of proof = e−s²e s 2 Pn i=1(bi−ai) 2/8 = e−2² 2/ Pn i=1(bi−ai) 2 choose s = 4²/Xn i=1 (bi − ai) 2 The second inequality is proved analogously. 2 The Glivenko Cantelli Theorem As a rst step we study an alternative proof of the well known theorem Theorem 3 (Glivenko-Cantelli). Let Z1, . . . , Zn be i.i.d. real valued random variables with distribution function F(z) = P(Z1 ≤ z). Let Fn(z) = 1 n Xn i=1 1{Zi≤z} be the standard empirical distribution function. Then P ½ sup z∈R |F(z) − Fn(z)| > ²¾ ≤ 8 (n + 1) e−n²2/32 , and in particular by the Borel-Cantelli lemma limn→∞ sup z∈R |F(z) − Fn(z)| = 0 with probability one. The proof we will give is not the simplest one possible, but it contains the ideas of the generalization we will consider later. The argument given here is due to symmetrization ideas of Dudley [Dud78] and Pollard [Pol84]. Proof. Assume n²2 > 2, otherwise the bound is trivial. Introduce the following notation ν(A) = P {Z1 ∈ A} and νn(A) = 1 n Pn j=1 1{Zj∈A} where A ⊆ R is a measurable set. Denote by A the class of sets of the form (−∞, z], z ∈ R. Then we have sup z∈R |F(z) − Fn(z)| = sup A∈A |νn(A) − ν(A)| . Step 1. First symmetrization by a ghost sample Dene random variables Z 0 1 , . . . , Z0 n ∈ R such that Z1, . . . , Zn, Z0 1 , . . . , Z0 n are all i.i.d. Denote by ν 0 n the empirical measure of the primed variables. For n²2 ≥ 2 we have P ½ sup A∈A |νn(A) − ν(A)| > ²¾ ≤ 2P ½ sup A∈A |νn(A) − ν 0 n(A)| ≥ ² 2 ¾ 2