## 7.2.7 Almost Sure Convergence

Consider a sequence of random variables $X_1$, $X_2$, $X_3$, $\cdots$ that is defined on an underlying sample space $S$. For simplicity, let us assume that $S$ is a finite set, so we can write

\begin{align}%\label{} S=\{s_1,s_2,\cdots, s_{\large k}\}. \end{align} Remember that each $X_n$ is a function from $S$ to the set of real numbers. Thus, we may write \begin{align}%\label{} X_n(s_i)=x_{{\large ni}}, \qquad \textrm{ for }i=1,2,\cdots, k. \end{align} After this random experiment is performed, one of the $s_i$'s will be the outcome of the experiment, and the values of the $X_n$'s are known. If $s_{\large j}$ is the outcome of the experiment, we observe the following sequence: \begin{align}%\label{} x_{{\large 1j}}, x_{{\large 2j}}, x_{{\large 3j}}, \cdots. \end{align} Since this is a sequence of real numbers, we can talk about its convergence. Does it converge? If yes, what does it converge to? Almost sure convergence is defined based on the convergence of such sequences. Before introducing almost sure convergence let us look at an example.

Example

Consider the following random experiment: A fair coin is tossed once. Here, the sample space has only two elements $S=\{H,T\}$. We define a sequence of random variables $X_1$, $X_2$, $X_3$, $\cdots$ on this sample space as follows:

$$\nonumber X_n(s) = \left\{ \begin{array}{l l} {\large \frac{n}{n+1}} & \quad \textrm{ if }s=H \\ & \quad \\ (-1)^n & \quad \textrm{ if }s=T \end{array} \right.$$
1. For each of the possible outcomes ($H$ or $T$), determine whether the resulting sequence of real numbers converges or not.
2. Find \begin{align}%\label{} P\left( \left\{s_i \in S: \lim_{n\rightarrow \infty} X_n(s_i)=1\right\}\right). \end{align}
• Solution
1. If the outcome is $H$, then we have $X_n(H)=\frac{n}{n+1}$, so we obtain the following sequence \begin{align}%\label{} \frac{1}{2}, \frac{2}{3}, \frac{3}{4}, \frac{4}{5}, \cdots. \end{align} This sequence converges to $1$ as $n$ goes to infinity. If the outcome is $T$, then we have $X_n(T)=(-1)^n$, so we obtain the following sequence \begin{align}%\label{} -1, 1, -1, 1, -1, \cdots. \end{align} This sequence does not converge as it oscillates between $-1$ and $1$ forever.
2. By part (a), the event $\left\{s_i \in S: \lim_{n\rightarrow \infty} X_n(s_i)=1\right\}$ happens if and only if the outcome is $H$, so \begin{align}%\label{} P\left( \left\{s_i \in S: \lim_{n\rightarrow \infty} X_n(s_i)=1\right\}\right) &=P(H)\\ &=\frac{1}{2}. \end{align}

In the above example, we saw that the sequence $X_{n}(s)$ converged when $s=H$ and did not converge when $s=T$. In general, if the probability that the sequence $X_{n}(s)$ converges to $X(s)$ is equal to $1$, we say that $X_n$ converges to $X$ almost surely and write

\begin{align}%\label{} X_n \ \xrightarrow{a.s.}\ X. \end{align}

Almost Sure Convergence

A sequence of random variables $X_1$, $X_2$, $X_3$, $\cdots$ converges almost surely to a random variable $X$, shown by $X_n \ \xrightarrow{a.s.}\ X$, if \begin{align}%\label{eq:union-bound} P\left( \left\{s \in S: \lim_{n\rightarrow \infty} X_n(s)=X(s)\right\}\right)=1. \end{align}

Example

Consider the sample space $S=[0,1]$ with a probability measure that is uniform on this space, i.e.,

\begin{align}%\label{} P([a,b])=b-a, \qquad \textrm{ for all }0 \leq a \leq b \leq 1. \end{align} Define the sequence $\big\{X_n, n=1,2, \cdots \big \}$ as follows: $$\nonumber X_n(s) = \left\{ \begin{array}{l l} 1 & \quad 0 \leq s < {\large \frac{n+1}{2n}} \\ & \quad \\ 0 & \quad \text{otherwise} \end{array} \right.$$ Also, define the random variable $X$ on this sample space as follows: $$\nonumber X(s) = \left\{ \begin{array}{l l} 1 & \quad 0 \leq s < \frac{1}{2} \\ & \quad \\ 0 & \quad \text{otherwise} \end{array} \right.$$ Show that $X_n \ \xrightarrow{a.s.}\ X$.
• Solution
• Define the set $A$ as follows: \begin{align}%\label{eq:union-bound} A= \left\{s \in S: \lim_{n\rightarrow \infty} X_n(s)=X(s)\right\}. \end{align} We need to prove that $P(A)=1$. Let's first find $A$. Note that $\frac{n+1}{2n}>\frac{1}{2}$, so for any $s \in [0,\frac{1}{2})$, we have \begin{align}%\label{} X_n(s)=X(s)=1. \end{align} Therefore, we conclude that $[0,0.5) \subset A$. Now if $s> \frac{1}{2}$, then \begin{align}%\label{} X(s)=0. \end{align} Also, since $2s-1>0$, we can write \begin{align}%\label{} X_n(s)=0, \qquad \textrm{ for all }n>\frac{1}{2s-1}. \end{align} Therefore, \begin{align}%\label{eq:union-bound} \lim_{n\rightarrow \infty} X_n(s)=0=X(s), \qquad \textrm{ for all }s>\frac{1}{2}. \end{align} We conclude $(\frac{1}{2},1] \subset A$. You can check that $s=\frac{1}{2} \notin A$, since \begin{align}%\label{} X_n\left(\frac{1}{2}\right)=1, \qquad \textrm{ for all }n, \end{align} while $X\left(\frac{1}{2}\right)=0$. We conclude \begin{align}%\label{} A=\left[0,\frac{1}{2}\right) \cup \left(\frac{1}{2}, 1\right]=S-\left\{\frac{1}{2}\right\}. \end{align} Since $P(A)=1$, we conclude $X_n \ \xrightarrow{a.s.}\ X$.

In some problems, proving almost sure convergence directly can be difficult. Thus, it is desirable to know some sufficient conditions for almost sure convergence. Here is a result that is sometimes useful when we would like to prove almost sure convergence.

Theorem

Consider the sequence $X_1$, $X_2$, $X_3$, $\cdots$. If for all $\epsilon>0$, we have

\begin{align}%\label{} \sum_{n=1}^{\infty} P\big(|X_n-X| > \epsilon \big) < \infty, \end{align} then $X_n \ \xrightarrow{a.s.}\ X$.

Example

Consider a sequence $\{X_n, n=1,2,3, \cdots \}$ such that

$$\nonumber X_n = \left\{ \begin{array}{l l} -\frac{1}{n} & \quad \textrm{with probability } \frac{1}{2} \\ & \quad \\ \frac{1}{n} & \quad \textrm{with probability } \frac{1}{2} \end{array} \right.$$ Show that $X_n \ \xrightarrow{a.s.}\ 0$.
• Solution
• By the Theorem above, it suffices to show that \begin{align}%\label{} \sum_{n=1}^{\infty} P\big(|X_n| > \epsilon \big) < \infty. \end{align} Note that $|X_n|={\large \frac{1}{n}}$. Thus, $|X_n| > \epsilon$ if and only if $n < {\large \frac{1}{\epsilon}}$. Thus, we conclude \begin{align}%\label{} \sum_{n=1}^{\infty} P\big(|X_n| > \epsilon \big) & \leq \sum_{n=1}^{{\large \lfloor\frac{1}{{\large \epsilon}}\rfloor}} P\big(|X_n| > \epsilon \big)\\ & = {\large \lfloor\frac{1}{\epsilon}\rfloor} < \infty. \end{align}

Theorem 7.5 provides only a sufficient condition for almost sure convergence. In particular, if we obtain \begin{align}%\label{} \sum_{n=1}^{\infty} P\big(|X_n-X| > \epsilon \big) = \infty, \end{align} then we still don't know whether the $X_n$'s converge to $X$ almost surely or not. Here, we provide a condition that is both necessary and sufficient.

Theorem

Consider the sequence $X_1$, $X_2$, $X_3$, $\cdots$. For any $\epsilon>0$, define the set of events \begin{align}%\label{} A_m=\{|X_n-X|< \epsilon, \qquad \textrm{for all }n \geq m \}. \end{align} Then $X_n \ \xrightarrow{a.s.}\ X$ if and only if for any $\epsilon>0$, we have \begin{align}%\label{eq:union-bound} \lim_{m\rightarrow \infty} P(A_m) =1. \end{align}

Example

Let $X_1$, $X_2$, $X_3$, $\cdots$ be independent random variables, where $X_n \sim Bernoulli\left(\frac{1}{n} \right)$ for $n=2,3, \cdots$. The goal here is to check whether $X_n \ \xrightarrow{a.s.}\ 0$.

1. Check that $\sum_{n=1}^{\infty} P\big(|X_n| > \epsilon \big) = \infty$.
2. Show that the sequence $X_1$, $X_2$, $...$ does not converge to $0$ almost surely using Theorem 7.6
3. .
• Solution
1. We first note that for $0<\epsilon<1$, we have \begin{align}%\label{} \sum_{n=1}^{\infty} P\big(|X_n| > \epsilon \big)&= \sum_{n=1}^{\infty} P(X_n=1)\\ &= \sum_{n=1}^{\infty} \frac{1}{n} = \infty. \end{align}
2. To use Theorem 7.6, we define \begin{align}%\label{} A_m=\{|X_n|< \epsilon, \qquad \textrm{for all }n \geq m \}. \end{align} Note that for $0<\epsilon<1$, we have \begin{align}%\label{} A_m=\{X_n=0, \qquad \textrm{for all }n \geq m \}. \end{align} According to Theorem 7.6 , it suffices to show that \begin{align}%\label{eq:union-bound} \lim_{m\rightarrow \infty} P(A_m) <1. \end{align} We can in fact show that $\lim_{m\rightarrow \infty} P(A_m)=0$. To show this, we will prove $P(A_m)=0$, for every $m \geq 2$. For $0<\epsilon<1$, we have \begin{align}%\label{eq:union-bound} P(A_m) &=P \big(\{X_n=0, \qquad \textrm{for all }n \geq m \}\big)\\ &\leq P \big(\{X_n=0, \qquad \textrm{for } n=m, m+1, \cdots, N \}\big) \quad (\textrm{for every positive integer $N \geq m$})\\ &=P(X_m=0) P(X_{{\large m+1}}=0) \cdots P(X_{N}=0) \qquad (\textrm{since the $X_i$'s are independent})\\ &=\frac{m-1}{m} \cdot \frac{m}{m+1} \cdots \frac{N-1}{N}\\ &=\frac{m-1}{N}. \end{align} Thus, by choosing $N$ large enough, we can show that $P(A_m)$ is less than any positive number. Therefore, $P(A_m)=0$ for all $m \geq 2$. We conclude that $\lim_{m\rightarrow \infty} P(A_m)=0$. Thus, according to Theorem 7.6, the sequence $X_1$, $X_2$, $...$ does not converge to $0$ almost surely.

An important example for almost sure convergence is the strong law of large numbers (SLLN). Here, we state the SLLN without proof. The interested reader can find a proof of SLLN in [19]. A simpler proof can be obtained if we assume the finiteness of the fourth moment. (See [20] for example.)

The strong law of large numbers (SLLN)

Let $X_1$,$X_2$,...,$X_n$ be i.i.d. random variables with a finite expected value $EX_i=\mu < \infty$. Let also \begin{align}%\label{} M_n=\frac{X_1+X_2+...+X_n}{n}. \end{align} Then $M_n \ \xrightarrow{a.s.}\ \mu$.

We end this section by stating a version of the continuous mapping theorem. This theorem is sometimes useful when proving the convergence of random variables.

Theorem Let $X_1$, $X_2$, $X_3$, $\cdots$ be a sequence of random variables. Let also $h: \mathbb{R} \mapsto \mathbb{R}$ be a continuous function. Then, the following statements are true:
1. If $X_n \ \xrightarrow{d}\ X$, then $h(X_n) \ \xrightarrow{d}\ h(X)$.
2. If $X_n \ \xrightarrow{p}\ X$, then $h(X_n) \ \xrightarrow{p}\ h(X)$.
3. If $X_n \ \xrightarrow{a.s.}\ X$, then $h(X_n) \ \xrightarrow{a.s.}\ h(X)$.

The print version of the book is available through Amazon here.