# Almost sure convergence

{Xn} is a sequence of independent random variables each with the same Sample Space {0,1} and Probability {1-1/$n^2$ ,1/$n^2$}
Does this sequence converge with probability one (Almost Sure) to the constant 0?

Essentially the {Xn} will look like this (its random,but just to show that the frequency of ones drops)
010010000100000000100000000000000001......

-

Yes, but how fast does the frequency drop ? The faster it does the more it is probable that (Xn) converges to 0.

Lemma : If (Xn) is a sequence of elements in {0,1}, Xn converges to 0 if and only if Xn has finitely many 1s :

If a sequence (Xn) converges to 0, then by definition of the limit, there exists some integer N such that for all n>=N, |Xn| <= 1/2. Now since Xn is 0 or 1, |Xn| <= 1/2 implies that Xn = 0. Thus, for all n >= N, Xn = 0. This means that the sequence (Xn) has finitely (in fact, less than N) many 1s.

Conversely, if a sequence (Xn) has finitely many 1s, there exist an integer N (the index of the last 1 of the sequence) such that Xn = 0 for all n > N. Then the sequence (Xn) converges to 0 because for any $\varepsilon$ > 0, we do have that for all n > N, $|X_n - 0| = 0 < \varepsilon$.

Here, define $Y_n = \Sigma_{k=1}^n X_n$ and $Y_\infty = \lim_{n \rightarrow \infty} Y_n$ = the number of 1s in the sequence (Xn). The lemma tells us that (Xn) converges to 0 if and only if $Y_\infty < \infty$.

You'll notice that $E[Y_\infty] = \lim E[Y_n] \lt \infty$ thanks to the fact that $\Sigma \frac{1}{n^2}$ is convergent.

This implies that $Y_\infty < \infty$ almost surely, which in turn shows that (Xn) does converge with probability 1.

If you have the frequency drop too slowly, this won't work. For example if P(Xn = 1) = 1/log(n) for n>=3, it will almost always diverge.

-
Xn is convergent if and only if Y∞ <∞ , I agree ...But why should it be? – AIB Feb 1 '11 at 10:18
@ AIB : The sequence Xn converges to 0 <=> The sequence Xn has finitely many 1s <=> The sum of the Xn is finite – mercio Feb 1 '11 at 10:27
So is it a sure convergence? Convergence in the classical sense(not probabilistic) ? – AIB Feb 1 '11 at 15:05
yes. P(Xn converges to 0) = P(Xn has finitely many 1) = P(Yn is finite) = 1. – mercio Feb 1 '11 at 15:26
@chandok As per my understanding of limit , the deterministic sequence 010010000100000000100000000000000001 ...does not have a limit... because it has 2 limit points 0 and 1... – AIB Feb 2 '11 at 7:51

Let's elaborate on the answers already given, by considering the more general case where $X_n = 1$ with probability $a_n$ and $X_n = 0$ with probability $1-a_n$, where $a_n \downarrow 0$ (the typical cases being $a_n = 1/n$ and $a_n = 1/n^2$) and the $X_n$ are not necessarily independent.

The most natural approach is to use Borel-Cantelli lemma, as follows. Denote by $E_n$ the event $\lbrace X_n = 1 \rbrace$. If $\sum\nolimits_{n = 1}^\infty {{\rm P}(E_n )} < \infty$, then the probability of $E_n$ occurring for infinitely many $n$ is $0$. Thus, if $\sum\nolimits_{n = 1}^\infty {a_n} < \infty$, then $X_n \to 0$ almost surely (that is, with probability $1$), since, almost surely, $X_n = 0$ for all $n$ sufficiently large. If, on the other hand, $\sum\nolimits_{n = 1}^\infty {{\rm P}(E_n )} = \infty$ and the events $E_n$ are independent, then the probability of $E_n$ occurring for infinitely many $n$ is $1$. Thus, if $\sum\nolimits_{n = 1}^\infty {a_n} = \infty$ and the $X_n$ are independent, then almost surely $X_n$ does not converge to $0$ (even though ${\rm P}(X_n = 0) \to 1$, which only gives that $X_n \to 0$ in probability).

As for chandok's approach, define $Y_n = \sum\nolimits_{k = 1}^n {X_k }$, so that $0 \leq Y_1 \leq Y_2 \leq \cdots$. Since the sequence $Y_n$ is monotone, it converges, say to $Y$ (which might be infinite). By the Monotone Convergence Theorem, ${\rm E}(Y_n) \to {\rm E}(Y)$ (to put it otherwise, $\int_\Omega {Y_n \,{\rm dP}} \to \int_\Omega {Y\,{\rm dP}}$), where the right-hand side might be infinite (and is obviously infinite if $Y$ is). Now, ${\rm E}(Y_n) = \sum\nolimits_{k = 1}^n {a_k }$. Hence, if $\sum\nolimits_{k = 1}^\infty {a_k }$ is finite, then so is ${\rm E}(Y)$, or $\int_\Omega {Y\,{\rm dP}}$. From measure theory (since $Y$ is nonnegative), it follows that $Y$ is almost everywhere finite, or, in our setting, $Y$ is almost surely finite. But $Y$ is finite if and only if $X_n = 0$ for all $n$ sufficiently large. So, $\sum\nolimits_{k = 1}^\infty {a_k } < \infty$ implies $X_n \to 0$. However, if $\sum\nolimits_{k = 1}^\infty {a_k } = \infty$, then one cannot a priori conclude from ${\rm E}(Y) = \infty$ that $Y$ is almost surely infinite (simply since a random variable can have infinite expectation).

EDIT: With the above notation and assuming that the $X_n$ are independent, the characteristic function $\varphi _{n } (u)$ of $Y_n$ is given by $$\varphi _{n } (u) = {\rm E}[e^{{\rm i}uY_n } ] = {\rm E}[e^{{\rm i}u(X_1 + \cdots + X_n )} ] = \prod\limits_{k = 1}^n {{\rm E}[e^{{\rm i}uX_k } ]} = \prod\limits_{k = 1}^n {[(1 - a_k ) + a_k e^{{\rm i}u} ]}.$$ Now, $X_n \to 0$ if and only if $Y := \lim _{n \to \infty } Y_n$ is finite. So it is instructive to note here the following (general) result. If $\varphi _{n } (u)$ converges to a function $\varphi(u)$ for every $u \in \mathbb{R}$ and $\varphi(u)$ is continuous at $u=0$, then $\varphi(u)$ is the characteristic function of some distribution.

-

Hint: The Borel-Cantelli lemma.

-