# Converging exponentially in probability implies convergence with probability one ?

When I read the paper On the Strong Universal Consistency of Nearest Neighbor Regression Function Estimate, the theorem 1 in it states something like

If for every $\epsilon > 0$ there exists some integer $n_0$ such that for $n>n_0$ $$\text{Pr}\{X_n>\epsilon\}\leq e^{-cn\epsilon^2}$$ then $$X_n\rightarrow 0$$ with probability one as $n\rightarrow\infty$

It looks like that when $X_n$ converges in probability sufficiently fast (i.e., exponentially), then it converges with probability one. But I don't know where could I get proof this result or it just follows from some theorem I don't know. Can someone help?

• Please provide a link to the paper you quote, thanks! Dec 27 '14 at 16:00
• @Xi'an the paper is here , but I think guy has given a nice answer below Dec 28 '14 at 0:30

This is a simple consequence of the Borel-Cantelli lemma. Before starting, I think we are missing the assumption that $X_1, X_2, \ldots$ are nonnegative. First, recall the following fact

$X_n \to 0$ almost surely if and only if $P(X_n > \epsilon \mbox{ infinitely often}) = 0$ holds for every $\epsilon > 0$.

This is a consequence of countable additivity. Next, recall that the Borel-Cantelli Lemma

If $A_1, A_2, \ldots$ are events such that $\sum_{n = 1} ^ \infty P(A_n) < \infty$ then $P(A_n \mbox{ happens infinitely often}) = 0$.

This is true because

$$P(A_n \mbox{ infinitely often}) = P\left(\bigcap_{n = 1} ^ \infty \bigcup_{j = n} ^ \infty A_j\right) \le P\left(\bigcup_{j = n'} ^ \infty A_j\right) \le \sum_{j = n'} ^ \infty P(A_j) \stackrel{n' \to\infty}\longrightarrow 0$$

with the limit being $0$ due to the fact that $\sum_j P(A_j) < \infty$.

So, we have established that what we really need for almost sure convergence is that $P(X_n > \epsilon)$ be summable for every $\epsilon$. Decaying exponentially is much stronger than being summable; we could get away with much less.