# symmetrization in glivenko-cantelli proof

In this proof of the Glivenko-Cantelli theorem, page 2 of these notes, two types of symmetrization are used. The first transforms the sup of the centered empirical cdf $$P(\sup_{z\in\mathbb{R}}|(1/n)\sum_{i=1}^n(I(Z_i\le z)-P(Z\le z))|>\epsilon)$$ into a sup involving a ghost copy $$P(\sup_{z\in\mathbb{R}}|(1/n)\sum_{i=1}^nI(Z_i\le z)-(1/n)\sum_{i=1}^nI(Z'_i\le z)|>\epsilon).$$ The second symmetrization adds iid rademacher variables to transform the last expression into $$P(\sup_{z\in\mathbb{R}}|(1/n)\sum_{i=1}^n\sigma_iI(Z_i\le z)|>\epsilon).$$ I don't fully understand the purpose of the second symmetrization and want to know if it can be avoided. The end goal of the symmetrizations is I believe to get the sup from inside the expectation to the outside. This can be done because the symmetrized argument only takes on a finite number of values, whereas, the original process $$(1/n)\sum_{i=1}^n(I(Z_i\le z)-P(Z\le z))$$ can take on infinitely many. But you only need the first symmetrization to get an argument $$(1/n)\sum_{i=1}^nI(Z_i\le z)-(1/n)\sum_{i=1}^nI(Z'_i\le z)$$ that only takes on a finite number of values. Say that those values are to be found at $$z_1,\ldots,z_m$$. These values would be random but $$m$$ wouldn't be. Is the following argument sound?

\begin{align} P(\sup_{z\in\mathbb{R}}|(1/n)\sum_{i=1}^nI(Z_i\le z)-(1/n)\sum_{i=1}^nI(Z'_i\le z)|>\epsilon)\\ =P(\max_{z_1,\ldots,z_m}|(1/n)\sum_{i=1}^nI(Z_i\le z)-(1/n)\sum_{i=1}^nI(Z'_i\le z)|>\epsilon)\\ \le P(\sum_{j=1}^m|(1/n)\sum_{i=1}^nI(Z_i\le z_j)-(1/n)\sum_{i=1}^nI(Z'_i\le z_j)|>\epsilon)\\ = \sum_{j=1}^mP(|(1/n)\sum_{i=1}^nI(Z_i\le z_j)-(1/n)\sum_{i=1}^nI(Z'_i\le z_j)|>\epsilon)\\ \le m\sup_{z\in\mathbb{R}}P(|(1/n)\sum_{i=1}^nI(Z_i\le z_j)-(1/n)\sum_{i=1}^nI(Z'_i\le z_j)|>\epsilon). \end{align}

Then the argument to the sup is centered and bounded and hoeffding's inequality can be applied as before.

## 1 Answer

Bottom line : To get the union bound, we need to condition on the random variables $$Z_i$$. However, conditional on the $$Z_i$$, the quantity of interest is not random anymore and the probability of interest can not be bounded. The Rademacher random variables are thus introduced to get a random quantity that behaves similarly to the quantity of interest and whose probability can be bounded with (conditional) Hoeffding's inequality.

Notice that in the expression $$\mathbb P(\sup_{z\in\mathbb{R}}|(1/n)\sum_{i=1}^n(I(Z_i\le z)-P(Z\le z))|>\epsilon)\tag1$$ The function $$\varphi:z\mapsto(1/n)\sum_{i=1}^n(I(Z_i\le z)-P(Z\le z))$$ is piecewise continuous on $$\mathbb R$$ and bounded between $$-1$$ and $$1$$. It thus follows that $$|\varphi(z)|$$ attains its supremum for zome $$z^*\in\mathbb R\cup\{\pm\infty\}$$. Expression $$(1)$$ is thus equal to $$\mathbb P(|\sum_{i=1}^n(I(Z_i\le z^*)-P(Z\le z^*))|>n\epsilon)\tag2$$ It is clear that the sum inside the probability is a sum of i.i.d. bounded and centered random variables. So we could just apply Hoeffding's inequality to upper bound $$(2)$$ and we'd be done, right ? Right, except we can't because the behavior of $$\varphi$$ (the values it takes and hence its maximum) is conditional on the values of $$\mathbf Z_i$$. Therefore, the inequality only holds conditional on the $$Z_i$$'s, but conditional on the $$Z_i$$, $$\varphi$$ is only a function of $$Z$$, and Hoeffding's inequality can't be applied anymore.

Exact same thing happens if you consider $$\varphi:z\mapsto (1/n)\sum_{i=1}^n(I(Z_i\le z)-I(Z'_i\le z))$$ : the behavior of the function (the finite number of values it takes, where...) is conditional on the $$Z_i,Z'_i$$, but conditional on the $$Z_i,Z_i'$$, $$\varphi$$ is not even random anymore and the probability becomes degenerate, hence Hoeffding can't be applied either.

To bypass that difficulty, a nice solution is to introduce an "extra randomness" term through the Rademacher variables $$\sigma_i$$, that leaves the conditional behavior of $$\varphi$$ unchanged but still allows to get nice upper bounds of our probability of interest.

By the way, the desired upper bound can be obtained by directly applying (conditional) Hoeffding's inequality to $$\sum_{i=1}^n\sigma_i(I(Z_i\le z)-I(Z'_i\le z))$$, which is a sum of i.i.d. centred random variables bounded between $$-1$$ and $$1$$. You get the following : \begin{align} &\mathbb P\left(\sup_{z\in\mathbb R}\left\vert\sum_{i=1}^n(I(Z_i\le z)-I(Z'_i\le z))\right\vert>\epsilon/2\,\bigg|\, (Z_i,Z_i')_{1\le i\le n}\right)\\ &\mathbb P\left(\sup_{z\in\mathbb R}\left\vert\sum_{i=1}^n\sigma_i(I(Z_i\le z)-I(Z'_i\le z))\right\vert>\epsilon/2\,\bigg|\, (Z_i,Z_i')_{1\le i\le n}\right)\\ &\le (n+1)\\ &\times\sup_{z\in\mathbb R} \mathbb P\left(\left\vert\sum_{i=1}^n\sigma_i(I(Z_i\le z)-I(Z'_i\le z))\right\vert>\epsilon/2\,\bigg|\, (Z_i,Z_i')_{1\le i\le n}\right)\\ &\le 2(n+1)\exp\left(\frac{-2n\epsilon^2}{8}\right)\end{align} Which yields a better bound than the one given in the theorem (which maybe means I made a mistake somewhere...).

• why does your function $\phi(z)$ only take finitely many values? If the $P(Z<z)$ could be continuous. Commented Mar 26, 2022 at 19:58
• Thank you for pointing it out, @sayda. I fixed the argument. Hopefully it's not too confusing, but the bottom line is that because we need to condition on the $Z_i$'s, we need an "extra source of randomness" to measure the probability of interest, and the Rademacher variables fulfil that role. Commented Mar 28, 2022 at 4:03