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?

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

1 Answer 1


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.


Your Answer

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

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