# Convergence in probability implies almost surely convergence for maximal empirical processes

For any $$n$$, let $$X_1, ..., X_n$$ be i.i.d. random variables on the probability space $$(\Omega, \mathcal{F}, Pr)$$ where $$\Omega = \mathbb{R}^d$$. Define $$\mu_n(A) = \frac{1}{n} \sum_{i=1}^n 1_{\{X_i \in A\}}, \\ \mu(A) = Pr(X_1 \in A).$$

Consider any $$\mathcal{A} \subset \mathcal{F}$$, and define

$$g(X_1, ..., X_n) := \sup_{A \in \mathcal{A}} |\mu_n(A) - \mu(A)|$$

Prove that $$g(X_1, ..., X_n)$$ converges in probability to $$0$$ implies that $$g(X_1, ..., X_n)$$ converges almost surely to $$0$$.

p/s: This problem is posed as an exercise in the book "Combinatorial methods in density estimation" by Luc Devroye and Gabor Lugosi (exercise 3.2 with a hint to use the bounded difference inequality). I have tried but could not solve it. Hopefully, someone could help. Thank you.

Edit: As noted by @NickyLevering, I change "iff" to "implies" because it is well-known that a.s. convergence implies convergence in probability (also changed the title to reflect this better). I also set $$\Omega = \mathbb{R}^d$$ to make it clearer.

• Per definition of a.s. convergence and convergence in probability the a.s. convergence implies convergence in probability, thus you only have to prove the 'only if' statement. Aug 6 '20 at 11:27
• Are you sure about the definitions of $\mu_n$ and $\mu$? One is a random variable and the other is a number? Also what is $\mathcal{A}$? Aug 6 '20 at 11:29
• @Keen-ameteur Yes I am sure. Yes. $\mathcal{A}$ is any set of subsets of $\Omega$. Aug 6 '20 at 11:30
• @NickyLevering Yes, right. Aug 6 '20 at 11:32
• If $\mathcal{A}$ is not a sub-collection of $\mathcal{F}$, then this is not well defined. Aug 6 '20 at 11:32

Abbreviate $$g_n=g(X_1,...,X_n)$$ and note, first of all, that for any $$A$$,

$$\left\|\sum_{i=1}^n 1_{X_i\in A}-\sum_{i=1}^n 1_{Y_i\in A}\right\|\leq |\{i|X_i\neq Y_i\}|$$ Hence, we can apply the bounded differences inequality with $$c_i=\frac{1}{n}$$ and get that

$$Pr(|g_n-\mathbb{E} g_n|\geq t)\leq 2\exp(-2tn)$$ for every $$t>0$$.

In particular, $$\sum_{n=1}^{\infty}Pr(|g_n-\mathbb{E} g_n|\geq \frac{1}{\sqrt{n}})\leq 2 \sum_{n=1}^{\infty}\exp(-2\sqrt{n})<\infty,$$ so by Borel Cantelli, $$g_n-\mathbb{E} g_n\to 0$$ almost surely.

Thus, if $$g_n\to 0$$ in probability, we want to prove that $$\mathbb{E}g_n$$ goes to $$0$$. This is equivalent to proving that every subsequence $$g_{n_k}$$ has a subsequence $$g_{n_{k_j}}$$ such that $$\mathbb{E} g_{n_{k_j}}\to 0$$. This follows since $$g_{n_k}\to 0$$ in probability and hence, has a subsequence $$g_{n_{k_j}}\to 0$$ almost surely. Then, since $$0\leq g_{n_{k_j}}\leq 1$$, we can apply Dominated Convergence to get $$\mathbb{E}g_{n_{k_j}}\to 0$$.

• Of course, you're right in using Borel Cantelli and then proving that $\mathbb{E} g_n \rightarrow 0$. For proving $\mathbb{E} g_n \rightarrow 0$, I am not sure if I fully understand it for now (but you are probably right there); I just need more time to really understand it and I will approve your answer once I fully understand it. One thing I wonder is that do we really need $g_n \rightarrow 0$ in prob. for $\mathbb{E} g_n \rightarrow 0$? We have $\mathbb{E} g_n = O(1/\sqrt{n})$ (proved in Luc's book), so it approaches $0$ regardless of whether $g_n \rightarrow 0$ in probability or not? Aug 6 '20 at 13:12
• I mean... you can definitely convince me that $g_n$ should go to $0$ under very mild conditions. You definitely need $X_1$ to have first moment, though, right? Aug 6 '20 at 13:20
• Nevermind. The last part is not obviously true. Aug 6 '20 at 13:21
• Yes, right. For the result $\mathbb{E}g_n = O(1/\sqrt{n})$ to hold, it needs some conditions about the boundedness of an integral related to the covering number of $\mathcal{A}$. The condition that $Z_n \rightarrow 0$ in prob. seems like also another mild condition for $E Z_n \rightarrow 0$. I think I got it now. Many thanks :-) Aug 6 '20 at 13:38