# Convergence in probability does not imply almost sure convergence?

My textbook states the theorem that if a sequence of random variables converges almost surely, it also converges in probability, but that the opposite does not necessarily hold. It also states that if a random variable converges in probability, there is nevertheless a subsequence that converges almost surely.

Annoyingly, the book doesn't give proofs or explanations.

To me it seems that the two concepts are really the same thing, though convergence in probability is defined sequentially on individual elements of the sequence, while almost sure convergence is defined on an entire sequence at once.

Why aren't these definitions equivalent?

Consider the Lebesgue measure $P$ on $[0,1]$ and define a sequence of random variables $(X_n)$ by letting $X_n$ be the characteristic function of the interval $$\left[\frac{j}{2^k},\frac{j+1}{2^k}\right],$$ where $k:=\lfloor\log_2(n)\rfloor$ and $j\in\{0,\ldots,2^k-1\}$ satisfies $n=2^k+j$. This sequence converges in probability to zero but does not converge almost surely to zero.

We have $$X_1=1_{[0,1]},\, X_2=1_{[0,1/2]},\, X_3=1_{[1/2,1]},\, X_4=1_{[0,1/4]},\, X_5=1_{[1/4,1/2]},\, X_6=1_{[1/2,3/4]},\ldots.$$ From this it is easy to see that, for every $\varepsilon>0$, $$P(|X_n|>\varepsilon)\to 0.$$ Thus $(X_n)$ converges to zero in probability. However, given any $\omega\in[0,1]$, we have that $X_n(\omega)=1$ for infinitely many $n$. Therefore $(X_n)$ does not converge to zero almost surely.

This example is commonly called the typewriter sequence. Note that there are many subsequences of $(X_n)$ which converge almost surely to zero.

• I don't understand why you say "given any $\omega$". My problem with this statement is, that shouldn't be choosing one specific $\omega$ and then fixing that for the entire sequence. Instead, each $X_n$ should be the result from a new $\omega$ that is drawn. "Converge to zero almost surely" means that $P(\lim (X_n)=0)=1$, which means that we have to calculate the probability that $\lim(X_n)=0$ over the probability space that is a union of all the probability spaces of each $X_n$. (It would be an infinite dimensional Cartesian product of $[0,1]$ intervals I think). – user56834 Oct 20 '17 at 10:14
• @Programmer2134 To converge almost surely to zero does mean to have $P(\lim X_n=0)=1$. However, the notation $(\lim(X_n)=0)$ here means $$\{ \omega \in [0,1] : \lim X_n(\omega)=0\}.$$ Since for any $\omega\in[0,1]$ we have $X_n(\omega)=1$ for infinitely many $n$, we have $$P(\lim(X_n)=0) = P(\{ \omega \in [0,1] : \lim X_n(\omega)=0\}) = P(\emptyset) = 0.$$ This shows that $(X_n)$ does not converge almost surely to zero. – John Griffin Oct 20 '17 at 21:26
• Ah, I see. Then I misinterpreted the definition of almost sure convergence. This still leaves me confused: if we apply the same event $\omega$ from the sample space, then wouldn't all the random variables in the sequence become perfectly correlated? we would effectively only pick one value for the random variables, and derive the other variables in the sequence from the others. Or does this same principle also apply to convergence in probability? – user56834 Oct 25 '17 at 7:32
• @Programmer2134 $\omega$ is a point in our space, not an event. I'm not sure what you mean by perfectly correlated because I don't really know probability theory outside of measure theory. Convergence almost surely means that the points for which the random variables converge to another has probability one. Convergence in probability means that the probability of the events for which the random variables in the sequence differ from the limiting random variable by more than a fixed amount converges to zero. In either case, we can't say anything about the sequence knowing only a few of the RVs. – John Griffin Oct 25 '17 at 12:18
• What I mean is: say $X_n = \omega \cdot f(\omega)^n$ for some function $f$. If we then know $X_0$, we know $\omega$, because $X_0=\omega$. Since we know $\omega$, we know every $X_n$. In other words, if every random variable $X_n$ is a function of the same draw from the probability space $\Omega$, then we know all $X_n$ just by knowing $X_0$. It seems to me that the definitions of almost sure convergence, depends on taking one draw from $\Omega$, and then applying that to all members of the sequence $X_n$, rather than drawing a new $\omega$ for every $X_n$ (which makes more sense to me). – user56834 Oct 25 '17 at 13:20

Convergence in probability : $X_n \xrightarrow{p} X$ if for all $\epsilon > 0$, $\Pr[|X_n - X| > \epsilon] \to 0$ as $n \to \infty$.

Convergence almost surely : $X_n \xrightarrow{a.s} X$ if $\Pr[X_n(w) \nrightarrow X(w)] = 0$.

Convergence almost surely implies convergence in probability. However, the other way is not true, the most popular counterexample being the following.

Let the space in consideration be $[0,1]$. We will define our sequence with double indices, $X_{nk}$, where $0 \leq k < n$ and $n \geq 1$. Reindexing can be done later.

Let $X_{nk} = 1_{[\frac kn, \frac{k+1}{n}]}$, and let $X \equiv 0$. I claim that $X_{nk} \xrightarrow{p} X$. This is because, if we choose any $\epsilon > 0$, then for each $n$ and $k$, $X_{nk}$ is non-zero only in an interval of $\frac 1n$. If we choose $n > \frac 1\epsilon$, then you can see that the probability that $X_{nk}$ is non-zero (or different from zero) is less than $\epsilon$, as desired.

However, for each $w \in [0,1]$ and $n \in \mathbb N$, there exists $k$ such that $w \in [\frac kn, \frac{k+1}{n}]$. Therefore, the sequence ${X_{nk}}$ consists of infinitely many zeros and infinitely many ones, and therefore does not converge for any $w \in [0,1]$. Since $[0,1]$ has probability non-zero (infact, probability one), we conclude that $X_{nk} \nrightarrow X$ almost surely.

• What do you mean by "let $X_{nk} = 1_{[\frac kn, \frac{k+1}{n}]}$"? – user56834 Oct 19 '17 at 11:17
• This is an indicator random variable. That is, $1_{A}$, for any set $A$, is defined as $1_A(w) = 1$ if $w \in A$ and $0$ if $w \notin A$. – Teresa Lisbon Oct 19 '17 at 23:01
• So you mean $X_{nk}$ has the probability density function $1_{[\frac kn, \frac{k+1}{n}]}$, rather than $X_{nk} = 1_{[\frac kn, \frac{k+1}{n}]}$? – user56834 Oct 20 '17 at 8:14
• Yes, it turns out that is the case as well. However, $X_{nk}$, as a function from $[0,1] \to \mathbb R$, is defined to be $1$ on the interval $[\frac kn, \frac{k+1}{n}]$, and zero elsewhere. A random variable can be either defined in terms of it's probability density, or what values it takes where. – Teresa Lisbon Oct 20 '17 at 9:43
• so you're assuming a uniform density of some underlying probability space on $[0,1]$, and $X_{nk}$ is a random variable on that space? – user56834 Oct 20 '17 at 9:47