Almost sure convergence using exponential tail bound


I have a question about a theorem in the following set of lecture notes 'A Gentle Introduction to Empirical Process theory' ( In particular, I'm interested in Theorem 3.26. This theorem tells us the following:

Suppose that $X_1,\ldots, X_n$ are i.i.d. random variables on $\mathbb{R}$ with distribution $P$ and c.d.f. $F$. Let $\mathbb{F}_n$ be the empirical d.f. of the data. Then,
\begin{aligned}\mathbb{P}\left[\|\mathbb{F}_n-F\|_\infty\geq8\sqrt{\frac{\log(n+1)}n}+t\right]\leq e^{-nt^2/2},\quad&\quad\text{forall } t>0.\quad&\end{aligned}

Hence, $\|\mathbb{F}_n-F\|_\infty\overset{a.s.}{\operatorname*{\to}}0$.

Note that $\|\mathbb{F}_n-F\|_\infty = \sup_{x \in \mathbb{R}} |\mathbb{F}_n(x)-F(x)|$ denotes the sup-norm of the difference of the ecdf and the cdf. The first claim (the upper bound on the tail probability) is proven in the notes itself. They leave the implication that this tail bound implies almost sure convergence as an exercise to the reader. I am not able to figure it out and that's what my question is about.

One thing I looked at is using that the proof also establishes mean convergence by showing that $\mathbb{E}[\|\mathbb{F}_n-F\|_\infty] \to 0$ and this sequence of r.v.s is non-negative but this does not imply a.s. convergence as shown here (Does convergence in mean imply convergence almost surely if the limit is zero and the sequence is nonnegative?).

Does anyone have any other insights?

Best Answer

The result follows by Borel-Cantelli.

Fix $\varepsilon>0$. Notice, since $8\sqrt{\frac{\log(n+1)}{n}}\to 0$ as $n\to \infty$, there exists some $n_0\in \mathbb{N}$ and $\tilde{t}>0$ such that $$n>n_0 \implies 8\sqrt{\frac{\log(n+1)}{n}}+\tilde{t}<\varepsilon.$$

Therefore, $$\begin{align*}\sum_{n>n_0}\mathbb{P}(\Vert F_n-F\Vert_{\infty}>\varepsilon) & \leq \sum_{n>n_0}\mathbb{P}\left(\Vert F_n-F\Vert_{\infty}>8\sqrt{\frac{\log(n+1)}{n}}+\tilde{t}\right) \\ &\leq \sum_{n>n_0}e^{-n\tilde{t}^2/2} \\ &<\infty.\end{align*}$$ From which we can conclude, $\sum_{n=1}^{\infty}\mathbb{P}( \Vert F_n-F\Vert _{\infty}>\varepsilon)<\infty$. So, by Borel-Cantelli (since we can derive the same for all $\varepsilon>0$) we arrive at $\Vert F_n-F \Vert \xrightarrow{\textrm{a.s.}}0.$

Related Question