Convergence of random variables

Author

Affiliation

Aditya Mahajan

McGill University

Suppose we have an infinite sequence of random variables $\{X_n{\}}_{n\ge 1}$ defined on a common probability space $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$. A sequence of random variables, also called a stochastic process, can be thought of a generalization of random vectors. When does this sequence converge?

1 Different notions of convergence

Recall that a sequence $\{x_n{\}}_{n\ge 1}$ of real numbers converges to a limit $x^{\ast }$ if for every $\epsilon >0$, there exists a $N$ such that for all $n\ge N$, we have that $$|\phantom{(}{x}_n-x^{\ast }|<\epsilon .$$

Convergence of a sequence of random variables is much different. We have already seen one form of convergence: convergence in distribution

There are two ways in which this notion can be extended to sequence of random variables:

• Convergence in probability. A sequence $\{X_n{\}}_{n\ge 1}$ of random variables converges to a random variale $X$ in probability if $$\underset{n\to \infty }{lim}\mathbb{P}(|\phantom{(}{X}_n-X|>\epsilon )=0.$$ Or, equivalently, for any $\epsilon >0$ and $\delta >0$, there exists a $N$ such that for all $n\ge N$, we have $$\mathbb{P}(|\phantom{(}{X}_n-X|>\epsilon )\le \delta .$$ We denote such convergence as $X_n\stackrel{p}{\to }X$.

• Almost sure convergence. A sequence $\{X_n{\}}_{n\ge 1}$ of random variables converges to a random variable $X$ almost surely if $$\mathbb{P}\left(\{\omega :\underset{n\to \infty }{lim}{X}_n(\omega )=X(\omega )\}\right)=1$$ Or, equivalently, for any $\epsilon >0$, $$\mathbb{P}(\underset{n\to \infty }{lim sup}\{\omega :|X_n(\omega )-X(\omega )|>\epsilon \})=0$$ We denote such convergence as $X_n\stackrel{a.s.}{\to }X$.

Lim inf and lim sup of sets

Explanation adapted from math.stackexchange [1] and [2]

Limits of sets is easy to describe when we have weakly increasing or weakly decreasing sequence of sets. In particular, if $\{I_n{\}}_{n\ge 1}$ is a weakly increasing sequence of sets, then $$\underset{n\to \infty }{lim}{C}_n=\bigcup _{n=1}^{\infty }{C}_n.$$ Thus, the limit is the union of all sets. Moreover, if $\{D_n{\}}_{n\ge 1}$ is weakly decreasing sequence of sets, then $$\underset{n\to \infty }{lim}{D}_n=\bigcap _{n=1}^{\infty }{D}_n.$$ Thus, the limit is the intersection of all sets.

What happens when a sequence $\{A_n{\}}_{n\ge 1}$ is neither increasing nor decreasing? We can sandwitch it between an increasing sequence $\{C_n{\}}_{n\ge 1}$ and a decreasing sequence $\{D_n\}$ as follows:

$$\begin{array}{lcl}{C}_1=A_1\cap A_2\cap A_3\cap \cdots & \subseteq A_1& \subseteq D_1=A_1\cup A_2\cup A_3\cup \cdots \\ C_2=\phantom{A_1\cap }{A}_2\cap A_3\cap \cdots & \subseteq A_2& \subseteq D_2=\phantom{A_1\cup }{A}_2\cup A_3\cup \cdots \\ C_3=\phantom{A_1\cap A_2\cap }{A}_3\cap \cdots & \subseteq A_3& \subseteq D_3=\phantom{A_1\cup A_2\cup }{A}_3\cup \cdots \\ & ⋮& \end{array}$$

The limit of $\{C_n{\}}_{n\ge 1}$ is called the lim inf of $\{A_n{\}}_{n\ge 1}$, i.e., $$\underset{n\to \infty }{lim inf}{A}_n=\underset{n\to \infty }{lim}{C}_n=\bigcup _{n=1}^{\infty }{C}_n=\bigcup _{n=1}^{\infty }\bigcap _{i=n}^{\infty }{A}_i.$$ Similarly, the limit of $\{D_n{\}}_{n\ge 1}$ is call the lim sup of $\{A_n{\}}_{n\ge 1}$, i.e., $$\underset{n\to \infty }{lim sup}{A}_n=\underset{n\to \infty }{lim}{D}_n=\bigcap _{n=1}^{\infty }{D}_n=\bigcap _{n=1}^{\infty }\bigcup _{i=n}^{\infty }{A}_i.$$ When the two limits are equal, we say that the sequence $\{A_n{\}}_{n\ge 1}$ has a limit.

---

Another way to think about these definitions is as follows. $$\omega \in \underset{n\to \infty }{lim sup}{A}_n⟺\underset{n\to \infty }{lim sup}{\mathbb{1}}_{A_n}(\omega )=1$$ which holds if and only if the binary sequence $\{{\mathbb{1}}_{A_n}(\omega )\}$ has infinitely many ones, i.e., $\omega$ is a member of infinitely many $A_n$.

Similarly, $$\omega \in \underset{n\to \infty }{lim inf}{A}_n⟺\underset{n\to \infty }{lim inf}{\mathbb{1}}_{A_n}(\omega )=1$$ which holds if and only if the binary sequence $\{{\mathbb{1}}_{A_n}(\omega )\}$ eventually becomes $1$ forever, i.e., $\omega$ is eventually a member of $A_n$ forever.

2 Examples of convergence in probability

Example 1 Consider a probability space $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$ where $\mathrm{\Omega }=[0,1]$, $\mathcal{F}=\mathcal{B}(0,1)$, and $\mathbb{P}$ is the uniform distribution on $\mathrm{\Omega }$. Define $$X_n(\omega )=\{\begin{array}{ll}1,& \omega \in [0,\frac{1}{n^2})\\ 0,& \omega \in [\frac{1}{n^2},1]\end{array}$$ Show that $X_n\stackrel{p}{\to }0$.

Solution

Note that $$X_n=\{\begin{array}{ll}1& \text{with probability }\frac{1}{n^2}\\ 0& \text{with probability }1-\frac{1}{n^2}\end{array}$$ Pick any $\epsilon >0$. If $\epsilon >1$, then $\mathbb{P}(X_n>\epsilon )=0$. So, we assume that $\epsilon \in (0,1)$. Then, $$\mathbb{P}(X_n>\epsilon )=\mathbb{P}(X_n=1)=\frac{1}{n^2}$$ which converges to $0$ as $n\to \infty$. Therefore, $X_n\stackrel{p}{\to }0$.

Example 2 Consider the same setup as Example 1, but the random variable $X_n$ defined as $$X_n(\omega )=\{\begin{array}{ll}1,& \omega \in [0,\frac{1}{n})\\ 0,& \omega \in [\frac{1}{n},1]\end{array}$$ Show that $X_n\stackrel{p}{\to }0$.

Solution

This can be solved in exactly the same manner as Example 1.

Example 3 Consider the same setup as Example 1, but the random variable $X_n$ defined as $$X_n(\omega )=\{\begin{array}{ll}n,& \omega \in [0,\frac{1}{n})\\ 0,& \omega \in [\frac{1}{n},1]\end{array}$$ Show that $X_n\stackrel{p}{\to }0$.

Solution

This can be solved in exactly the same manner as Example 1.

Example 4 Consider an i.i.d. sequence $\{X_n{\}}_{n\ge 1}$, where $X_n\sim \text{Uniform}(0,1)$. Define $$Y_n=min\{X_1,\dots ,X_n\}.$$ Show that $Y_n\stackrel{p}{\to }0$.

Solution

Pick any $\epsilon >0$. As in Example 1, if $\epsilon >1$, then $\mathbb{P}(Y_n>\epsilon )=0$. So, we assume that $\epsilon \in (0,1)$. Then, $$\begin{array}{rl}\mathbb{P}(Y_n>\epsilon )& =\mathbb{P}(min\{X_1,\dots ,X_n\}\ge \epsilon )\\ & =\mathbb{P}(X_1\ge \epsilon ,X_2\ge \epsilon ,\dots ,X_n\ge \epsilon )\\ & =(1-\epsilon {)}^n\end{array}$$ which goes to zero as $n\to \infty$. Thus, $Y_n\stackrel{p}{\to }0$.

3 Examples of almost sure convergence

We revisit the examples of previous section.

• In Example 1, for any $\omega \ne 0$, the sequence $\{X_n(\omega ){\}}_{n\ge 1}$ is a finite sequence of $1$’s followed by infinite sequence of $0$’s. Thus, $\underset{n\to \infty }{lim}{X}_n(\omega )=0$. Thus, $$\mathbb{P}(\{\omega :\underset{n\to \infty }{lim}{X}_n(\omega )=0\})=\mathbb{P}(\omega \in (0,1])=1.$$ Hence, $X_n\stackrel{a.s}{\to }0$.

• In Example 2, the same argument as above works.

• In Example 3, a slight variation of the above argument works.

• In Example 4, we proceed as follows. Fix $\omega$ and consider the sequence $\{Y_n(\omega ){\}}_{n\ge 1}$. Since this is a decreasing sequence, it must have a limit. Denote that limit by $Y(\omega )$, i.e., $$Y(\omega )=\underset{n\to \infty }{lim}{Y}_n(\omega ).$$

  Since $\{Y_n{\}}_{n\ge 1}$ is a decreasing sequence, we have that $Y(\omega )\le Y_n(\omega )$. Hence, for any $\epsilon >0$, $$\mathbb{P}(Y>\epsilon )\le \mathbb{P}(Y_n>\epsilon )=(1-\epsilon {)}^n$$ (where the last inequality follows from the calculation in the solution of Example 4).

  The above inequality holds for every $n$, so we have $$\mathbb{P}(Y>\epsilon )\le \underset{n\to \infty }{lim}(1-\epsilon {)}^n=0.$$ Recall that $\epsilon >0$ was arbitrary. Therefore, we have shown that $$\mathbb{P}(\underset{n\to \infty }{lim}{Y}_n>\epsilon )=0.$$ Thus, the only possibility is that $$\mathbb{P}(\underset{n\to \infty }{lim}{Y}_n=0)=1.$$ Hence $Y_n\stackrel{a.s.}{\to }0$.

4 Almost sure convergence from convergence in probability.

It is possible to infer almost sure convergence from convergence in probability. For that we need to state a result. The proof is not difficult, but is omitted due to time.

Lemma 1 (Borel Cantelli Lemma) Let $\{A_n{\}}_{n\ge 1}$ be a sequence of events defined on a common probability space $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$. If the sum of the probability of the events is finite, i.e., $$\sum _{n=1}^{\infty }\mathbb{P}(A_n)<\infty ,$$ then the probability that infinitely many of them occur is zero, i.e., $$\mathbb{P}(\underset{n\to \infty }{lim sup}{A}_n)=0.$$

There is a partial converse of Borel-Cantelli lemma.

Lemma 2 (Second Borel Cantelli Lemma) Let $\{A_n{\}}_{n\ge 1}$ be a sequence of independent events defined on a common probability space $(\mathrm{\Omega },\mathcal{F},\mathbb{P})$. If the sum of the probability of the events is infinite, i.e., $$\sum _{n=1}^{\infty }\mathbb{P}(A_n)=\infty ,$$ then the probability that infinitely many of them occur is one, i.e., $$\mathbb{P}(\underset{n\to \infty }{lim sup}{A}_n)=1.$$

An immediate implication of Borel-Cantelli lemma is the following:

Lemma 3 Suppose $X_n\stackrel{p}{\to }X$ and for any $\epsilon >0$, we have $$\sum _{n=1}^{\infty }\mathbb{P}(|\phantom{(}{X}_n-X|>\epsilon )<\infty$$ then $X_n\stackrel{a.s.}{\to }X$.

In light of the above result, we revisit some variations of the examples of the previous section.

• Consider a variation Example 1 where we no longer specify $X_n$ as a function of $\omega$ but simply assume that $$X_n=\{\begin{array}{ll}1& \text{with probability }\frac{1}{n^2}\\ 0& \text{with probability }1-\frac{1}{n^2}\end{array}$$ Then for any $\epsilon >0$, $\mathbb{P}(\left|\phantom{(}{X}_n\right|>\epsilon )=\mathbb{P}(X_n>\epsilon )=1/n^2$. Therefore, $\sum _{n\ge 1}\mathbb{P}(\left|\phantom{(}{X}_n\right|>\epsilon )<\infty$; hence by Lemma 3, $X_n\stackrel{a.s.}{\to }0$.

• Consider a variation Example 2 where we no longer specify $X_n$ as a function of $\omega$ but simply assume that $$X_n=\{\begin{array}{ll}1& \text{with probability }\frac{1}{n}\\ 0& \text{with probability }1-\frac{1}{n}\end{array}$$ and $\{X_n{\}}_{n\ge 1}$ are independent.

  Then for any $\epsilon >0$, $\mathbb{P}(\left|\phantom{(}{X}_n\right|>\epsilon )=\mathbb{P}(X_n>\epsilon )=1/n$. Therefore, $\sum _{n\ge 1}\mathbb{P}(\left|\phantom{(}{X}_n\right|>\epsilon )=\infty$; hence by the Second Borel-Cantelli lemma, $$\mathbb{P}(\underset{n\to \infty }{lim sup}\{\left|\phantom{(}{X}_n\right|>\epsilon \})=1.$$ So, $X_n$ does not converge almost surely!

• In Example 4, we can directly apply Lemma 3 to argue that $Y_n\stackrel{a.s.}{\to }0$.

A variation of Lemma 4 is the following:

Lemma 4 Let $\{X_n{\}}_{n\ge 1}$ be a sequence of random variables with finite expectations and let $X$ be another random variable. If $$\sum _{n=1}^{\infty }\mathbb{E}[|\phantom{(}{X}_n-X|]<\infty$$ then $$X_n\stackrel{a.s.}{\to }X.$$

Proof

To simplify the notation, we assume that $X=0$.

Pick any $\epsilon >0$ and define the sequence of events $$A_n=\{\omega :\left|\phantom{(}{X}_i\right|>\epsilon \},n\in \mathbb{N}.$$

From Markov inequality, we have $$\mathbb{P}(A_n)=\mathbb{P}(\left|\phantom{(}{X}_i\right|>\epsilon )\le {\displaystyle \frac{\mathbb{E}[\left|\phantom{(}{X}_i\right|]}{\epsilon }}.$$ Therefore, $$\sum _{n=1}^{\infty }\mathbb{P}(A_n)\le \frac{1}{\epsilon }\sum _{n=1}^{\infty }\mathbb{E}[\left|\phantom{(}{X}_i\right|]<\infty$$ by the hypothesis of the result. Therefore, by Borel-Cantelli lemma, we have $$\mathbb{P}(\underset{n\to \infty }{lim sup}{A}_n)=0.$$

5 Some properties of convergence of sequence of random variables

We now state some properties without proof.

1. The three notions of convergence that we have defined are related as follows: $$[X_n\stackrel{a.s.}{\to }X]⟹[X_n\stackrel{p}{\to }X]⟹[X_n\stackrel{D}{\to }X]$$

Proof that almost sure convergence implies convergence in probability

Fix $\epsilon >0$. Define $$A_n=\{\omega :\mathrm{\exists }m\ge n,|\phantom{(}{X}_m(\omega )-X|\ge \epsilon \}.$$ Then, $\{A_n{\}}_{n\ge 1}$ is a decreasing sequence of events. If $\omega \in \bigcap _{n\ge 1}{A}_n$, then $X_n(\omega )\text{⧸}\stackrel{a.s}{\to }X(\omega )$. This implies $$\mathbb{P}(\bigcap _{n\ge 1}{A}_n)\le \mathbb{P}(\{\omega :\underset{n\to \infty }{lim}{X}_n(\omega )\ne X(\omega )\})=0.$$ By continuity of probability, $$\underset{n\to \infty }{lim}\mathbb{P}(A_n)=\mathbb{P}(\underset{n\to \infty }{lim}{A}_n)=0.$$

Proof that convergence in probability implies convergence in distribution

Let $F_n$ and $F$ denote the CDFs of $X_n$ and $X$, respectively. Fix $\epsilon >0$, pick $x$ such that $F$ is continuous at $x$, and consider $$\begin{array}{rl}{F}_n(x)& =\mathbb{P}(X_n\le x)=\mathbb{P}(X_n\le x,X\le x+\epsilon )+\mathbb{P}(X_n\le x,X>x+\epsilon )\\ & \le \mathbb{P}(X\le x+\epsilon )+\mathbb{P}(X-X_n>\epsilon )\\ & \le F(x+\epsilon )+\mathbb{P}(|\phantom{(}{X}_n-X|>\epsilon ).\end{array}$$ Similarly, $$\begin{array}{rl}F(x-\epsilon )& =\mathbb{P}(X\le x-\epsilon )=\mathbb{P}(X\le x-\epsilon ,X_n\le x)+\mathbb{P}(X\le x-\epsilon ,X_n>x)\\ & \le \mathbb{P}(X_n\le x)+\mathbb{P}(X_n-X>\epsilon )\\ & \le F_n(x)+\mathbb{P}(|\phantom{(}{X}_n-X|>\epsilon ).\end{array}$$

Thus, $$F(x-\epsilon )-\mathbb{P}(|\phantom{(}{X}_n-X|>\epsilon )\le F_n(x)\le F(x+\epsilon )+\mathbb{P}(|\phantom{(}{X}_n-X|>\epsilon ).$$ Taking $n\to \infty$, we have $$F(x-\epsilon )\le \underset{x\to \infty }{lim inf}{F}_n(x)\le \underset{x\to \infty }{lim sup}{F}_n(x)\le F(x+\epsilon ).$$ The result is true for all $\epsilon >0$. Since $F$ is continuous at $x$, when we take $\epsilon \downarrow 0$, we have $$F(x-\epsilon )\uparrow F(x)\text{and}F(x+\epsilon )\downarrow F(x)$$ which implies that $F_n(x)\to F(x)$.

2. There are partial converss. For any constant $c$ $$[X_n\stackrel{D}{\to }c]⟹[X_n\stackrel{p}{\to }c].$$ If $\{X_n{\}}_{n\ge 1}$ is a strictly decreasing sequence then $$[X_n\stackrel{p}{\to }c]⟹[X_n\stackrel{a.s.}{\to }c].$$

3. If $X_n\stackrel{p}{\to }X$, then there exists a subsequence $\{n_k:k\in \mathbb{N}\}$ such that $\{X_{n_k}{\}}_{k\ge 1}$ converges almost surely to $X$.

4. $X_n\stackrel{p}{\to }X$ if and only if every subsequence $\{n_k:k\in \mathbb{N}\}$ has a sub-subsequence $\{n_{k_m}:m\in \mathbb{N}\}$ such that $\{X_{n_{k_m}}{\}}_{m\ge 1}$ that converges to $X$ almost surely.

5. Skorokhod’s representation theorem. If $X_n\stackrel{D}{\to }X$, then there exists a sequence $\{Y_n{\}}_{n\ge 1}$ that is identically distributed to $\{X_n{\}}_{n\ge 1}$ such that $Y_n\stackrel{Y}{\to }$, where $Y$ is identically distributed to $X$.

6. Continuous mapping theorems. Let $g:\mathbb{R}\to \mathbb{R}$ be a continuous function. Then,

   • $X_n\stackrel{a.s.}{\to }X$ implies $g(X_n)\stackrel{a.s.}{\to }g(X)$.
   • $X_n\stackrel{p}{\to }X$ implies $g(X_n)\stackrel{p}{\to }g(X)$.
   • $X_n\stackrel{D}{\to }X$ implies $g(X_n)\stackrel{D}{\to }g(X)$.

7. Convergence of sums.

   • If $X_n\stackrel{a.s.}{\to }X$ and $Y_n\stackrel{a.s.}{\to }Y$, then $X_n+Y_n\stackrel{a.s.}{\to }X+Y$.
   • If $X_n\stackrel{p}{\to }X$ and $Y_n\stackrel{p}{\to }Y$, then $X_n+Y_n\stackrel{p}{\to }X+Y$.
   • It is not true in general that $X_n+Y_n\stackrel{D}{\to }X+Y$ whenever $X_n\stackrel{p}{\to }X$ and $Y_n\stackrel{p}{\to }Y$. The result is true when $X$ or $Y$ is a constant.

If $X_n\stackrel{p}{\to }X$ and $Y_n\stackrel{p}{\to }Y$, then $X_n+Y_n\to X+Y$ and $X_n{Y}_n\stackrel{X}{\to }Y$.

6 Strong law of large numbers

Theorem 1 Let $\{X_n{\}}_{n\ge 1}$ be an i.i.d. sequence of random variables with mean $\mu$ and variance ${\sigma }^2$. Let $${\overline{X}}_n=\frac{1}{n}\sum _{i=1}^n{X}_i$$ be the sameple average. Then, ${\overline{X}}_n\stackrel{a.s}{\to }\mu$, i.e., $$\mathbb{P}(\omega :\underset{n\to \infty }{lim}{X}_n(\omega )=\mu )=1.$$

We provide a proof under the assumption that the fouth moment’s exist.

Proof

We assume that $\mu =0$ (this is just for notational simplicity) and $\mathbb{E}[X^4]=\gamma <\infty$ (this is a strong assumption).

Since we know that the forth moment exist, we can use a forth moment version of Chebyshev inequality: $$\mathbb{P}\left|\phantom{(}{\overline{X}}_n\right|\ge \epsilon )\le \frac{\mathbb{E}[{\overline{X}}_n^4]}{{\epsilon }^2}.$$

Then, by the multinomial theorem, we have $$\mathbb{E}{\overline{X}}_n^4=\frac{1}{4}\mathbb{E}[\sum _i{X}_i^4+(\genfrac{}{}{0ex}{}{4}{1,3})\sum _{i\ne j}{X}_i{X}_j^3+(\genfrac{}{}{0ex}{}{4}{2,2})\sum _{i\ne j}{X}_i^2{X}_j^2+(\genfrac{}{}{0ex}{}{4}{1,1,2})\sum _{i\ne j\ne k}{X}_i{X}_j{X}_k^2+\sum _{i\ne j\ne k\ne \ell }{X}_i{X}_j{X}_k{X}_{\ell }].$$

Since the $\{X_i{\}}_{i\ge 1}$ are independent and zero mean, we have

• $\mathbb{E}[X_i{X}_j^3]=\mathbb{E}[X_i]\mathbb{E}[X_j^3]=0$.
• = = 0$.

Therefore, $$\mathbb{E}[{\overline{X}}_n^4=\frac{1}{n^4}[n\mathbb{E}[X_i^4]+3n(n-1)\mathbb{E}[X_i^2{X}_j^2]]\le \frac{M_4}{n_3}+\frac{3{\sigma }^4}{n^2}$$ where $M_4$ is the forth moment. Now, from the forth moment version of Chebyshev inequality, we have $$\mathbb{P}\left|\phantom{(}{\overline{X}}_n\right|\ge \epsilon )\le \frac{\frac{M_4}{n_3}+\frac{3{\sigma }^4}{n^2}}{{\epsilon }^2}.$$ This implies that $$\sum _{n=1}^{\infty }\mathbb{P}(\left|\phantom{(}{X}_n\right|\ge \epsilon )<\infty .$$ Thus, from Lemma 3, we have that $X_n\stackrel{a.s.}{\to }0$.

7 There’s more

There’s another type of convergence commonly used in engineering: convergence in mean-squared sense. In the interest of time, we will not study this notion in class.