Exercise 4.2: Failure of Glivenko–Cantelli

chapter 4

Given any two fixed \(\varepsilon = (\varepsilon_1, \ldots, \varepsilon_n)\) and \(x = (x_1, \ldots, x_n)\), we can define the set \(I(\varepsilon) = \lbrace i \in [n] \colon \varepsilon_i = +1 \rbrace\), and take \(S(x, \varepsilon) = \lbrace x_i \colon i \in I(\varepsilon) \rbrace\). By definition \(S(x, \varepsilon) \in \mathcal{S}\), implying the lower bound \begin{align} \radcomp_n(\mathcal{S}) \geq \frac{1}{n} \E_{X, \varepsilon} \left[ \sum_{i=1}^n \varepsilon_i \ind_{S(X, \varepsilon)} (X_i) \right] = \P (\varepsilon_1 = +1) = \frac{1}{2} \, . \end{align}

In other words \(\radcomp_n(\mathcal{S}) \neq o(1)\), and the upper bound from Theorem 4.10, \(2 \radcomp_n(\mathcal{S}) + \delta \geq 1\), is vacuous for all \(\delta \geq 0\).