We observe that,having 21,...,2nER fixed,as z ranges over R the number of different vectors(lz≤}，，lzn≤e})is at most n+1.Therefore conditioned on Z1,,Zn the supremum in the probability above is just a maximum taken over the at most n+1 random variables.We apply the union bound to find sup aa(>.n A∈A ≤(m+1)sup Having the supremum outside the probability we are left with finding an exponential bound on the probability 店w12} STEP 4.HOEFFDINGS INEQUALITY As we have conditioned on the values of the Z1,...,Zn we can regard 21.....as fixed.Then )is the sum of n independent zero mean random variables between-1 and 1.We can therefore apply Hoeffdings inequality: 店a4>么2}s Thus we find ≤2(n+1)e-ne2/32 Take the expectation value on both sides to find ≤2(n+1)e-ne2/32 Altogether we have P{.④-以>s8u+ecm which finishes the proof. 口 3 Generalizations Next we want to prove the Vapnik Chervonenkis inequality,which is a mighty generalization of the Glivenko Cantelli Theorem.The proof we just studied is after a slight adjustment already proof of the stronger theorem. The aim of the generalization is to give the statement for arbitrary classes of measurable sets A.We then need to refine the argument in the proof were the sup is identified as a maximum. Definition 4.Let A be a collection of measurable sets in Rd.For z1,...,ERd we call NA(z1,...,zn):=Ifz1,...,2n}nA:AEA} 4We observe that, having z1, . . . , zn ∈ R xed, as z ranges over R the number of dierent vectors ¡ 1{z1≤z}, . . . , 1{zn≤z} ¢ is at most n + 1. Therefore conditioned on Z1, . . . , Zn the supremum in the probability above is just a maximum taken over the at most n + 1 random variables. We apply the union bound to nd P ( sup A∈A 1 n ¯ ¯ ¯ ¯ ¯ Xn i=1 σi1{A}(Zi) ¯ ¯ ¯ ¯ ¯ > ² 4 | Z1, . . . , Zn ) ≤ (n + 1) sup A∈A P ( 1 n ¯ ¯ ¯ ¯ ¯ Xn i=1 σi1{A}(Zi) ¯ ¯ ¯ ¯ ¯ > ² 4 | Z1, . . . , Zn ) . Having the supremum outside the probability we are left with nding an exponential bound on the probability P ( 1 n ¯ ¯ ¯ ¯ ¯ Xn i=1 σi1{A}(Zi) ¯ ¯ ¯ ¯ ¯ > ² 4 | Z1, . . . , Zn ) . Step 4. Hoeffdings inequality As we have conditioned on the values of the Z1, . . . , Zn we can regard z1, . . . , zn as xed. Then Pn i=1 σi1{A}(zi) is the sum of n independent zero mean random variables between −1 and 1. We can therefore apply Hoedings inequality: P ( 1 n ¯ ¯ ¯ ¯ ¯ Xn i=1 σi1{A}(Zi) ¯ ¯ ¯ ¯ ¯ > ² 4 | Z1, . . . , Zn ) ≤ 2e−n²2/32 . Thus we nd P ( sup A∈A 1 n ¯ ¯ ¯ ¯ ¯ Xn i=1 σi1{A}(Zi) ¯ ¯ ¯ ¯ ¯ > ² 4 | Z1, . . . , Zn ) ≤ 2(n + 1)e−n²2/32 . Take the expectation value on both sides to nd P ( sup A∈A 1 n ¯ ¯ ¯ ¯ ¯ Xn i=1 σi1{A}(Zi) ¯ ¯ ¯ ¯ ¯ > ² 4 ) ≤ 2(n + 1)e−n²2/32 . Altogether we have P ½ sup A∈A |νn(A) − ν(A)| > ²¾ ≤ 8(n + 1)e−n²2/32 . which nishes the proof. 3 Generalizations Next we want to prove the Vapnik Chervonenkis inequality, which is a mighty generalization of the Glivenko Cantelli Theorem. The proof we just studied is after a slight adjustment already proof of the stronger theorem. The aim of the generalization is to give the statement for arbitrary classes of measurable sets A. We then need to rene the argument in the proof were the sup is identied as a maximum. Denition 4. Let A be a collection of measurable sets in R d . For z1, . . . , zn ∈ R d we call NA(z1, . . . , zn) := |{{z1, . . . , zn} ∩ A : A ∈ A}| 4