Prove Glivenko-Cantelli (GC) by bracketing

41 Views Asked by At

Question: My question about the theorem Glivenko-Cantelli (GC) by bracketing is: if $N_{[]}(\varepsilon,\mathcal{F},L_{1}(P))=\infty$, which part of the above proof will fail, thus GC will fail.

Source: the theorem and the proof are directly from: Bodhisattva Sen, A Gentle Introduction to Empirical Process Theory and Applications, July 19, 2022, Subsection 3.1 GC by bracketing.

Theorem: Let $\mathcal{F}$ be a class of measurable functions such that $N_{[]}(\varepsilon,\mathcal{F},L_{1}(P))<\infty$ for every $\varepsilon$ > 0. Then $\mathcal{F}$ is Glivenko-Cantelli.

Proof: Fix $\epsilon>0$. Choose finitely many $\epsilon$-brackets $[l_{i},u_{i}]$ whose union contains $\mathcal{F}$ and such that $P(u_{i}-l_{i})<\epsilon$, for every $i$. Then, for every $f\in\mathcal{F}$, there is a bracket $i$ such that \begin{equation} (P_{n}-P)f=P_{n}f-Pf \end{equation} \begin{equation} =P_{n}f-Pu_{i}+Pu_{i}-Pf \end{equation} \begin{equation} \leq P_{n}u_{i}-Pu_{i}+Pu_{i}-Pf \end{equation} \begin{equation} \leq\left(P_{n}-P\right)u_{i}+\epsilon \end{equation} Consequently

\begin{equation} \sup_{f\in\mathcal{F}}(P_{n}-P)f\leq\max_{i}\left(P_{n}-P\right)u_{i}+\epsilon \end{equation}

Following the strong law of large numbers \begin{equation} \left(P_{n}-P\right)u_{i}\to^{as}0 \end{equation} \begin{equation} \max_{i}\left(P_{n}-P\right)u_{i}\to^{as}0 \end{equation} \begin{equation} \max_{i}\left(P_{n}-P\right)u_{i}+\epsilon\to^{as}\epsilon \end{equation} Thus $\sup_{f\in\mathcal{F}}(P_{n}-P)f$ is bounded above by $\epsilon$ almost surely.

A similar argument also yields

\begin{equation} (P_{n}-P)f=P_{n}f-Pf=P_{n}f-Pl_{i}+Pl_{i}-Pf \end{equation} \begin{equation} \geq P_{n}l_{i}-Pl_{i}+Pl_{i}-Pf \end{equation} \begin{equation} \geq\left(P_{n}-P\right)u_{i}-\epsilon \end{equation}

Consequently

\begin{equation} \inf_{f\in\mathcal{F}}(P_{n}-P)f\geq\min_{i}\left(P_{n}-P\right)l_{i}-\epsilon \end{equation} Following the strong law of large numbers \begin{equation} \min_{i}\left(P_{n}-P\right)l_{i}-\epsilon\to^{as}-\epsilon \end{equation} Thus $\inf_{f\in\mathcal{F}}(P_{n}-P)f$ is bounded below by $-\epsilon$ almost surely.

Thus we have \begin{equation} \sup_{f\in\mathcal{F}}\left|(P_{n}-P)f\right|=\max\left\{ \sup_{f\in\mathcal{F}}(P_{n}-P)f,-\inf_{f\in\mathcal{F}}(P_{n}-P)f\right\} \end{equation} Thus we \begin{equation} \limsup_{n\to\infty}\sup_{f\in\mathcal{F}}\left|(P_{n}-P)f\right|\leq\epsilon,\text{almost surely},\forall\epsilon>0 \end{equation}

As $\epsilon\downarrow0$, we have $\sup_{f\in\mathcal{F}}\left|(P_{n}-P)f\right|=\|P_{n}-P\|_{\mathcal{F}}\to0$ almost surely.

Note: $P_nf=\frac{1}{n}\sum_{i=1}^nf(X_i)$, $Pf=Ef(X)$