I have a question about a theorem in the following set of lecture notes 'A Gentle Introduction to Empirical Process theory' (http://www.stat.columbia.edu/~bodhi/Talks/Emp-Proc-Lecture-Notes.pdf). 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?


1 Answer 1


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.$

  • $\begingroup$ Thank you for your solution. Can you also explain why is the last series convergent? $\endgroup$ Commented May 29 at 22:42
  • $\begingroup$ @Mondayisgood It is a geometric sequence. Since $e^{-\tilde{t}^2/2}<1$ for any $\tilde{t}>0$, it is convergent. $\endgroup$ Commented May 30 at 5:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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