2 THE GLIVENKO CANTELLI THEOREM 3 To see this let A*be a set for which vn(A*)-v(A*)I>e if existent or a fixed set in A otherwise.The measur ability of such a choice needs to be checked,using the technique of step 3 of the proof,showing that its actually a choice from finitely many sets only.Then P{.4-4训>分身≥P{(4)-(4I>} ≥P{(4)-4川>e,以4-4*I<} =E{L.-apP{(4)-41<2,Z} The conditional probability inside the expectation may be bounded by Chebyshey's inequality as follows: P{k4）-41<a,Z}≥1-4-4》 ne2/4 1 21-ne22 because the variance of the random variable vn(A)-v(A)equalsv(A)(1-v(A)).Altogether we find P{a理.()-A>分}≥.(a)-4训> 1 sup lun(A)-v(A)I>e ≥2P1 STEP 2.SECOND SYMMETRIZATION BY RANDOM SIGNS Let 01,...,on be i.i.d.sign variables that are also independent of all Zi,Z and satisfy P{o 1)=P{o =-1)=j.Then using step 1 (aw2-w2小>} 11 =2P E.a-2列>} We now apply the union bound to remove the auxiliary random variables Z1,...,Zn {2aa->引 s{☏容wa小}+{空网 STEP 3.CONDITIONING To find a bound on the probability r{空wa小}-假2小 we will condition on Z1,...,Zn.The conditional probability can be bounded and afterwards we will remove the conditioning by just taking the expectation value.2 THE GLIVENKO CANTELLI THEOREM 3 To see this let A∗ be a set for which |νn(A∗ ) − ν(A∗ )| > ² if existent or a xed set in A otherwise. The measurability of such a choice needs to be checked, using the technique of step 3 of the proof, showing that its actually a choice from nitely many sets only. Then P ½ sup A∈A |νn(A) − ν 0 n(A)| > ² 2 ¾ ≥ P n |νn(A ∗ ) − ν 0 n(A ∗ )| > ² 2 o ≥ P n |νn(A ∗ ) − ν(A ∗ )| > ², |ν 0 n(A ∗ ) − ν(A ∗ )| < ² 2 o = E n 1{|νn(A∗)−ν(A∗)|>²}P n |ν 0 n(A ∗ ) − ν(A ∗ )| < ² 2 |Z1, . . . , Zn oo . The conditional probability inside the expectation may be bounded by Chebyshev's inequality as follows: P n |ν 0 n(A ∗ ) − ν(A ∗ )| < ² 2 |Z1, . . . , Zn o ≥ 1 − ν(A∗ ) (1 − ν(A∗ )) n²2/4 ≥ 1 − 1 n²2 ≥ 1 2 , because the variance of the random variable νn(A)−ν(A) equals 1 n ν(A) (1 − ν(A)). Altogether we nd P ½ sup A∈A |νn(A) − ν 0 n(A)| > ² 2 ¾ ≥ 1 2 P {|νn(A ∗ ) − ν(A ∗ )| > ²} ≥ 1 2 P ½ sup A∈A |νn(A) − ν(A)| > ²¾ . Step 2. Second Symmetrization by random signs Let σ1, . . . , σn be i.i.d. sign variables that are also independent of all Zi , Z0 i and satisfy P {σ = 1} = P {σ = −1} = 1 2 . Then using step 1 P ½ sup A∈A |νn(A) − ν(A)| > ²¾ ≤ 2P ( sup A∈A 1 n ¯ ¯ ¯ ¯ ¯ Xn i=1 ¡ 1{A}(Zi) − 1{A}(Z 0 i ) ¢ ¯ ¯ ¯ ¯ ¯ > ² 2 ) = 2P ( sup A∈A 1 n ¯ ¯ ¯ ¯ ¯ Xn i=1 σi ¡ 1{A}(Zi) − 1{A}(Z 0 i ) ¢ ¯ ¯ ¯ ¯ ¯ > ² 2 ) . We now apply the union bound to remove the auxiliary random variables Z 0 1 , . . . , Z0 n. P ( sup A∈A 1 n ¯ ¯ ¯ ¯ ¯ Xn i=1 σi ¡ 1{A}(Zi) − 1{A}(Z 0 i ) ¢ ¯ ¯ ¯ ¯ ¯ > ² 2 ) ≤ P ( sup A∈A 1 n ¯ ¯ ¯ ¯ ¯ Xn i=1 σi1{A}(Zi) ¯ ¯ ¯ ¯ ¯ > ² 4 ) + P ( sup A∈A 1 n ¯ ¯ ¯ ¯ ¯ Xn i=1 σi1{A}(Z 0 i ) ¯ ¯ ¯ ¯ ¯ > ² 4 ) = 2P ( sup A∈A 1 n ¯ ¯ ¯ ¯ ¯ Xn i=1 σi1{A}(Zi) ¯ ¯ ¯ ¯ ¯ > ² 4 ) . Step 3. Conditioning To nd a bound on the probability P ( sup A∈A 1 n ¯ ¯ ¯ ¯ ¯ Xn i=1 σi1{A}(Zi) ¯ ¯ ¯ ¯ ¯ > ² 4 ) = P ( sup z∈R 1 n ¯ ¯ ¯ ¯ ¯ Xn i=1 σi1{Zi≤z} ¯ ¯ ¯ ¯ ¯ > ² 4 ) we will condition on Z1, . . . , Zn. The conditional probability can be bounded and afterwards we will remove the conditioning by just taking the expectation value