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.

  • $\begingroup$ 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. $\endgroup$ Aug 6 '20 at 11:27
  • $\begingroup$ 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}$? $\endgroup$ Aug 6 '20 at 11:29
  • $\begingroup$ @Keen-ameteur Yes I am sure. Yes. $\mathcal{A}$ is any set of subsets of $\Omega$. $\endgroup$
    – thanhtang
    Aug 6 '20 at 11:30
  • $\begingroup$ @NickyLevering Yes, right. $\endgroup$
    – thanhtang
    Aug 6 '20 at 11:32
  • $\begingroup$ If $\mathcal{A}$ is not a sub-collection of $\mathcal{F}$, then this is not well defined. $\endgroup$ 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$.

  • $\begingroup$ 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? $\endgroup$
    – thanhtang
    Aug 6 '20 at 13:12
  • 1
    $\begingroup$ 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? $\endgroup$ Aug 6 '20 at 13:20
  • $\begingroup$ Nevermind. The last part is not obviously true. $\endgroup$ Aug 6 '20 at 13:21
  • $\begingroup$ 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 :-) $\endgroup$
    – thanhtang
    Aug 6 '20 at 13:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.