9  Convergence of random variables

Author

Affiliation

Aditya Mahajan

McGill University

Suppose we have an infinite sequence \(\{X_n\}_{n \ge 1}\) of random variables defined on a common probability space \((Ω, \ALPHABET F, \PR)\). Thus, for every \(ω \in Ω\), there is an infinite sequence \[ X_1(ω), X_2(ω), X_3(ω), \dots \] A sequence of random variables, also called a stochastic process, can be thought of as a generalization of random vectors. When does this sequence converge?

9.1 Almost sure convergence

1. Recall that a sequence \(\{x_n\}_{n \ge 1}\) of real numbers converges to a limit \(x\) if for every \(ε > 0\), there exists a \(N\) such that for all \(n \ge N\), we have that \[ \ABS{ x_n - x } < ε. \]

2. The simplest way to define convergence of a sequence of random variables as follows: a sequence \(\{X_n\}_{n \ge 1}\) of random variables converges to a limit \(X\) surely if for every \(ω \in Ω\), the sequence \(\{X_n(ω)\}_{n \ge 1}\) of real numbers converges to \(X(ω)\).

3. Sure convergence can be too strong, as is illustrated by the following example.

Example 9.1 Consider a probability space \((Ω, \ALPHABET F, \PR)\) where \(Ω = [0,1]\), \(\ALPHABET F = \mathscr{B}(0,1)\), and \(\PR\) is the uniform distribution on \(Ω\). Define \(X_n(ω) = \IND_{A_n}(ω)\) where \(A_n = [0, \frac 1n]\), i.e., \[ X_n(ω) = \begin{cases} 1, & ω \in [0, \frac{1}{n}] \\ 0, & ω \in (\frac{1}{n}, 1] \end{cases} \]

viewof ω_convergence_1 = Inputs.range([0.0, 1], {label: "ω", value:0.05, step: 0.01})

points_convergence_1 = {
    const N = 120
    var points = new Array(N)

    for(var n=1; n <= N; n++) {
      var val = (ω_convergence_1*n <= 1) ? 1 : 0 ;
      points[n-1] = { n: n, X_n: val }
    }
    return points
}

Plot.plot({
  grid: true,
  y : {ticks: 1 },
  height: 100,
  marks: [
    // Axes
    Plot.ruleX([0]),
    Plot.ruleY([0]),
    // Data
    Plot.ruleX(points_convergence_1, {x: "n", y: "X_n", strokeWidth: 1}),
    Plot.dot(points_convergence_1, {x: "n", y: "X_n", fill: "currentColor", r: 2}),
  ]
})

Show that \(\{X_n\}_{n \ge 1}\) does not converge surely to the zero random variable.

NoteSolution

For any \(ω \in (0,1]\), \(X_n(ω) = 1\) for \(n \le \lfloor 1/ω \rfloor\), and \(0\) afterwards. Thus, \(X_n(ω) \to 0\).

However, for \(ω = 0\), \(X_n(ω) = 1\) for all \(n\). Therefore, \(\{X_n\}_{n \ge 1}\) does not converge surely to the zero random variable.

4. From a practical point of view, we do not care about not converging at \(ω = 0\), because that is an event of zero probability. Stated differently, the set \[ \{ ω : X_n(ω) \to 0 \} \] has probability 1.

5. Based on the previous discussion, we can relax the notion of sure convergence to almost sure convergence. A sequence \(\{X_n\}_{n \ge 1}\) of random variables converges to a random variable \(X\) almost surely if \[ \PR\left( \left\{ ω : \lim_{n \to ∞} X_n(ω) = X(ω) \right\} \right) = 1 \] Or, equivalently, for any \(ε > 0\), \[ \PR\left( \limsup_{n \to ∞} \{ ω : | X_n(ω) - X(ω) | > ε \} \right) = 0 \] We denote such convergence as \(X_n \xrightarrow{a.s.} X\).

6. Another way to generalize the definition of convergence of a sequence of real numbers to that of random variables is called convergence in probability. A sequence \(\{X_n\}_{n \ge 1}\) of random variables converges to a random variable \(X\) in probability if \[ \lim_{n \to ∞} \PR( \ABS{ X_n - X } > ε ) = 0. \] Or, equivalently, for any \(ε > 0\) and \(δ > 0\), there exists a \(N\) such that for all \(n \ge N\), we have \[ \PR( \ABS{ X_n - X} > ε ) \le δ. \] We denote such convergence as \(X_n \xrightarrow{p} X\).

9.2 Convergence in probability

1. Almost sure convergence implies convergence in probability, i.e., \[ [X_n \xrightarrow{a.s.} X] \implies [X_n \xrightarrow{p} X] \]

   NoteProof

   Fix \(ε > 0\). Define \[ A_n = \{ ω : \exists m \ge n, \ABS{X_m(ω) - X(ω)} \ge ε \}. \] Then, \(\{A_n\}_{n \ge 1}\) is a decreasing sequence of events. If \(ω \in \bigcap_{n \ge 1} A_n\), then \(\ABS{X_n(ω)-X(ω)}\ge ε\) infinitely often, so \(X_n(ω)\) does not converge to \(X(ω)\). This implies \[\PR\Bigl( \bigcap_{n \ge 1} A_n \Bigr) \le \PR\Bigl( \Bigl\{ ω : \lim_{n \to ∞}X_n(ω) \neq X(ω) \Bigr\}\Bigr) = 0. \] By continuity of probability, \[ \lim_{n \to ∞} \PR(A_n) = \PR\Bigl( \lim_{n \to ∞} A_n \Bigr) = 0. \] Since \[ \{ω : \ABS{X_n(ω)-X(ω)}\ge ε\}\subseteq A_n, \] we have \[ \PR(\ABS{X_n-X}\ge ε)\le \PR(A_n)\longrightarrow 0. \] Hence, \(X_n\xrightarrow{p}X\).

2. However, the converse is not true. Convergence in probability does not imply almost sure convergence, as is illustrated by the following example. Another example is presented in Example 9.5, part (a).

Example 9.2 Consider a probability space as in Example 9.1. Let \[ q_n=2^{\lfloor\log_2 n\rfloor}, \] which is the largest power of two not exceeding \(n\), and define \[ A_n=\left[\frac{n-q_n}{q_n},\frac{n-q_n+1}{q_n}\right), \qquad X_n(ω)=\IND_{A_n}(ω). \] For the last interval at each level, include the endpoint \(1\). Thus, the sets are enumerated as \[ [0,1],\quad \left[0,\frac12\right),\left[\frac12,1\right],\quad \left[0,\frac14\right),\left[\frac14,\frac12\right), \left[\frac12,\frac34\right),\left[\frac34,1\right],\quad\ldots \]

viewof ω_convergence_2 = Inputs.range([0.0, 1], {label: "ω", value:0.05, step: 0.01})

points_convergence_2 = {
    const N = 120
    var points = new Array(N)

    for(var n=1; n <= N; n++) {
      const q_n = 2 ** Math.floor(Math.log2(n))
      const k = n - q_n
      const left = k / q_n
      const right = (k + 1) / q_n
      const val = (ω_convergence_2 >= left &&
                   (ω_convergence_2 < right || (k === q_n - 1 && ω_convergence_2 === 1))) ? 1 : 0
      points[n-1] = { n: n, X_n: val }
    }
    return points
}

Plot.plot({
  grid: true,
  y : {ticks: 1 },
  height: 100,
  marks: [
    // Axes
    Plot.ruleX([0]),
    Plot.ruleY([0]),
    // Data
    Plot.ruleX(points_convergence_2, {x: "n", y: "X_n", strokeWidth: 1}),
    Plot.dot(points_convergence_2, {x: "n", y: "X_n", fill: "currentColor", r: 2}),
  ]
})

Show that \(\{X_n\}_{n \ge 1}\) converges in probability but not almost surely.

NoteSolution

At each level \(m\), the intervals \(A_{2^m},\ldots,A_{2^{m+1}-1}\) partition \([0,1]\). Consequently, for every \(ω\in[0,1]\), exactly one of the corresponding random variables equals \(1\). As the levels continue indefinitely, \(X_n(ω)=1\) infinitely often. It also equals \(0\) infinitely often. Hence, \(X_n(ω)\) does not converge for any \(ω\), and the sequence does not converge almost surely.

Now fix an \(ε > 0\) and consider the set \[ E_n = \{ ω : |X_n(ω) - 0| > ε \}. \] If \(ε \ge 1\), then \(E_n = \emptyset\), and \(\PR(E_n) = 0\) for all \(n\). So, assume that \(0<ε<1\). Then, \[ E_n = \{ ω : X_n(ω) = 1 \}. \] The interval \(A_n\) has length \(1/q_n\). Therefore, \[ \PR(E_n) = \PR(X_n = 1) = \frac{1}{q_n}. \] As \(n\to∞\), we also have \(q_n\to∞\), and hence \[ \lim_{n \to ∞} \PR(E_n) = 0. \] Thus, \(X_n\xrightarrow{p}0\).

3. There is however a partial converse. If \(\{X_n\}_{n \ge 1}\) is a monotone sequence of random variables (i.e., either \(X_1 \le X_2 \le \cdots\) almost surely or \(X_1 \ge X_2 \ge \cdots\) almost surely) and \(c\) is a constant, then \[ [X_n \xrightarrow{p} c] \implies [X_n \xrightarrow{a.s.} c]. \]

4. If \(X_n \xrightarrow{p} X\), then there exists a subsequence \(\{n_k : k \in \naturalnumbers \}\) such that \(\{X_{n_k}\}_{k \ge 1}\) converges almost surely to \(X\).

5. \(X_n \xrightarrow{p} X\) if and only if every subsequence \(\{n_k : k \in \naturalnumbers \}\) has a sub-subsequence \(\{n_{k_m} : m \in \naturalnumbers \}\) such that \(\{X_{n_{k_m}} \}_{m \ge 1}\) that converges to \(X\) almost surely.

9.3 Convergence in Distribution

1. We have already seen the notion of convergence in distribution (also called weak-convergence). A sequence \(\{X_n\}_{n \ge 1}\) of random variables converges to a random variable \(X\) in distribution if \[ \lim_{n \to ∞} \PR(X_n \le x) = \PR(X \le x) \] for every \(x\) where \(F(x) = \PR(X \le x)\) is continuous.

2. Note that the limiting object \(\lim_{n \to ∞} \PR(X_n \le x)\) need not be a valid CDF. For example, consider the deterministic sequence, \(X_n = n\). The corresponding CDF is \[ F_{X_n}(x) = \begin{cases} 0 & x < n \\ 1 & x \ge n \end{cases} \] Thus, for any \(x\), we have \(\lim_{n \to ∞} F_{X_n}(x) = 0\) which is not a valid CDF.

3. Convergence in probability implies convergence in distribution. \[ [X_n \xrightarrow{p} X] \implies [X_n \xrightarrow{D} X] \]

   NoteProof

   Let \(F_n\) and \(F\) denote the CDFs of \(X_n\) and \(X\), respectively. Fix \(ε > 0\), pick \(x\) such that \(F\) is continuous at \(x\), and consider \[\begin{align*} F_n(x) &= \PR(X_n \le x) = \PR(X_n \le x, X \le x + ε) + \PR(X_n \le x, X > x + ε) \\ &\le \PR(X \le x + ε) + \PR(X - X_n > ε) \\ &\le F(x + ε) + \PR(\ABS{X_n - X} > ε). \end{align*}\] Similarly, \[\begin{align*} F(x-ε) &= \PR(X \le x-ε) = \PR(X \le x-ε, X_n \le x ) + \PR(X \le x - ε, X_n > x ) \\ &\le \PR(X_n \le x) + \PR(X_n - X > ε) \\ &\le F_n(x) + \PR(\ABS{X_n - X} > ε). \end{align*}\]

   Thus, \[ F(x-ε) - \PR(\ABS{X_n - X} > ε) \le F_n(x) \le F(x+ε) + \PR(\ABS{X_n - X} > ε). \] Taking \(n \to ∞\), we have \[ F(x-ε) \le \liminf_{n \to ∞} F_n(x) \le \limsup_{n \to ∞} F_n(x) \le F(x + ε). \] The result is true for all \(ε > 0\). Since \(F\) is continuous at \(x\), when we take \(ε \downarrow 0\), we have \[ F(x - ε) \uparrow F(x) \quad\text{and}\quad F(x + ε) \downarrow F(x) \] which implies that \(F_n(x) \to F(x)\).

4. The converse is not true. For example, let \(X_1,X_2,\ldots,X\) be independent \(\text{Uniform}(0,1)\) random variables. Clearly, \(X_n \xrightarrow{D} X\). However, for any \(ε \in (0,1)\), \[ \PR( \ABS{X_n - X} > ε ) = (1-ε)^2 \]

   [Think of the area of the unit square corresponding to the event \(|X_n - X| > ε\)]. Thus, \[ \lim_{n \to ∞} \PR(\ABS{X_n - X} > ε) \neq 0. \] So, \(X_n\) does not converge in probability to \(X\).

5. There is a partial converse. If \(c\) is a constant then \[ [X_n \xrightarrow{D} c] \implies [X_n \xrightarrow{p} c]. \]

6. Convergence in distribution does not imply convergence of moments! For example, consider the sequence of random variables where \[ X_n = \begin{cases} 0 & \text{w.p. } 1 - \frac 1n \\ n & \text{w.p. } \frac 1n \end{cases} \] Then, \[ F_{X_n}(x) = \begin{cases} 0, & x < 0 1 - \frac 1n, & 0 \le x < n \\ 1 & x \ge n \end{cases} \] Thus, we have \[ \lim_{n \to ∞} F_{X_n}(x) = \begin{cases} 0 & x < 0 \\ 1 & x \ge 0 \end{cases} \] which corresponds to a random variable \(X = 0\).

   However, for any \(k \ge 1\), we have \(\EXP[X_n^k] = n^{k-1}\) but \(\EXP[X^k] = 0\). Thus, the moments do not converge!

7. Skorokhod’s representation theorem. If \(X_n \xrightarrow{D} X\), then there exist random variables \(Y_1,Y_2,\ldots,Y\) on a common probability space such that \(Y_n\) has the same distribution as \(X_n\) for every \(n\), \(Y\) has the same distribution as \(X\), and \(Y_n \xrightarrow{a.s.} Y\).

9.4 Convergence in \(r\)-th mean

1. There is another form of convergence: convergence in the \(r\)-th mean. We say that a sequence \(\{X_n\}_{n \ge 1}\) of random variables converges to \(X\) in \(r\)-th mean, \(r \ge 1\), if \(\EXP[\ABS{X_n}^r] < ∞\) for all \(n\), \(\EXP[\ABS{X}^r] < ∞\), and \[ \lim_{n \to ∞} \EXP[ \ABS{X_n - X}^r ] = 0. \]

2. When \(r = 1\), we say that \(\{X_n\}_{n \ge 1}\) converges in mean. When \(r=2\), we say that \(\{X_n\}_{n \ge 1}\) converges in mean square. We will mainly focus on mean-square convergence and denote it by \(X_n \xrightarrow{m.s.} X\).

3. If \(\{X_n\}_{n \ge 1}\) converges to \(X\) in the \(r\)-th mean, then it also converges in the \(s\)-th mean, for all \(1\le s < r\).

4. Convergence in \(r\)-th mean implies convergence in probability.

   NoteProof

   By Markov inequality, we have (for any \(r \ge 1\)) \[ \PR(\ABS{X_n - X} > ε) = \PR(\ABS{X_n - X}^r > ε^r) \le \frac{ \EXP[ \ABS{X_n - X}^r ] }{ε^r}. \] So, if the RHS goes to zero as \(n \to ∞\), then so does the LHS.

5. However, the converse is not true as is illustrated by Example 9.3, part (c).

6. Mean-square convergence and almost-sure convergence are not comparable. Example 9.3, part (c) gives an example that converges almost surely but not in mean square. Example 9.5, part (a) gives an example that converges in mean square but not almost surely.

7. Mean-square Cauchy criterion: A sequence \(\{X_n\}_{n\ge1}\) of random variables with finite second moments converges in mean square to some random variable \(X\) if and only if \[ \lim_{m,n\to∞}\EXP[\ABS{X_n-X_m}^2]=0. \] Thus, mean-square convergence can be established without knowing the limiting random variable in advance.

   NoteProof

   Define the mean-square norm by \[ \lVert X\rVert_2=\sqrt{\EXP[\ABS{X}^2]}. \] If \(X_n\xrightarrow{m.s.}X\), then the triangle inequality gives \[ \lVert X_n-X_m\rVert_2 \le \lVert X_n-X\rVert_2+\lVert X_m-X\rVert_2 \longrightarrow0 \] as \(m,n\to∞\). Hence, \(\EXP[\ABS{X_n-X_m}^2]\to0\).

   Conversely, the space of random variables with finite second moments is complete under the mean-square norm. Therefore, if \(\{X_n\}_{n\ge1}\) satisfies the Cauchy condition above, there exists a random variable \(X\) with finite second moment such that \[ \lVert X_n-X\rVert_2\longrightarrow0. \] Equivalently, \(X_n\xrightarrow{m.s.}X\).

9.5 Continuity properties of convergence

1. Continuity preserves convergence almost surely, in probability, and in distribution. Thus, if \(X_n\) converges to \(X\) in any of these modes and \(g\) is a continuous function, then \(g(X_n)\) converges in the same mode to \(g(X)\).

2. This is not the case for mean-square convergence. For example, \(X_n = 0\) with probability \(1 - \frac 1{n^3}\) and \(X_n = n\) with probability \(\frac 1{n^3}\). Then, \[ \EXP[|X_n - 0|^2] = n^2 \frac{1}{n^3} \to 0. \] Thus, \(X_n \xrightarrow{m.s.} 0\). Now consider the function \(g(x) = x^2\). \[ \EXP[ | g(X_n) - g(0)|^2 ] = n^4 \frac{1}{n^3} = n \to ∞. \] Thus, \(g(X_n)\) does not converge in mean square to \(g(0)\).

3. If \(X_n \xrightarrow{a.s.} X\) and \(Y_n \xrightarrow{a.s.} Y\), then \((X_n, Y_n) \xrightarrow{a.s.} (X,Y)\). Therefore, for any continuous function \(g\), we have \(g(X_n, Y_n) \xrightarrow{a.s.} g(X,Y)\).

   NoteProof

   Define \[\begin{align*} Ω_X &= \{ ω : \lim_{n \to ∞} X_n(ω) = X(ω) \} \\ Ω_Y &= \{ ω : \lim_{n \to ∞} Y_n(ω) = Y(ω) \} \end{align*}\] We know that \(\PR(Ω_X) = 1\) and \(\PR(Ω_Y) = 1\). From Example 8.3, we have that \(\PR(Ω_X \cap Ω_Y) = 1\). Thus, \((X_n, Y_n) \xrightarrow{a.s} (X,Y)\).

   The second part follows from continuity property of convergence.

4. The above property is also true for convergence in probability. The proof is left as a homework exercise.

5. However, this property is not true for convergence in distribution, as illustrated by the following example. Let \(X,X_1,X_2,\ldots\) be independent \(\text{Unif}(-1,1)\) random variables. Define \(Y_n=X_n\) and \(Y=-X\). Then, \(X_n\xrightarrow{D}X\) and \(Y_n\xrightarrow{D}Y\), but \[ X_n+Y_n=2X_n\xrightarrow{D}2X, \] whereas \(X+Y=0\). Thus, marginal convergence of \(X_n\) and \(Y_n\) does not imply joint convergence of \((X_n,Y_n)\).

6. Slutsky’s theorem: Suppose \(X_n \xrightarrow{D} X\) and \(Y_n \xrightarrow{D} c\), where \(c\) is a constant. Then, \((X_n, Y_n) \xrightarrow{D} (X, c)\). Therefore, for any continuous function \(g\), \[ g(X_n,Y_n)\xrightarrow{D}g(X,c). \] In particular, \(X_n + Y_n \xrightarrow{D} X + c\) and \(X_n Y_n \xrightarrow{D} cX\).

7. Note that we have already argued that \(Y_n \xrightarrow{D} c\) is equivalent to \(Y_n \xrightarrow{p} c\). So, one can replace \(Y_n \xrightarrow{D} c\) in Slutsky’s theorem by \(Y_n \xrightarrow{p} c\).

9.6 Some examples

Example 9.3 Consider the probability space \((Ω, \ALPHABET F, \PR)\) as in Example 9.1, and consider different choices of \(X_n\) shown below. For each case, determine whether \(X_n\) converges almost surely, in probability, or in mean square.

1. \(X_n(ω) = \IND_{A_n}(ω)\), where \(A_n = [0, \frac 1n]\).
2. \(X_n(ω) = \IND_{A_n}(ω)\), where \(A_n = [0, \frac 1{n^2}]\).
3. \(X_n(ω) = \textcolor{red}{n}\IND_{A_n}(ω)\), where \(A_n = [0, \frac 1n]\).

NoteSolution

For every \(ω\in(0,1]\), there exists an \(N(ω)\) such that \(ω>1/n\) and \(ω>1/n^2\) for all \(n\ge N(ω)\). Hence, in each of the three parts, \(X_n(ω)=0\) for all sufficiently large \(n\). At \(ω=0\), the sequence equals \(1\) in parts (a) and (b), and equals \(n\) in part (c). Since \(\PR(\{0\})=0\), all three sequences converge almost surely to zero: \[ X_n\xrightarrow{a.s.}0. \]

For convergence in probability, fix \(ε>0\). In parts (a) and (b), for \(0<ε<1\), \[\begin{align*} \PR(\ABS{X_n}>ε) &=\frac1n &&\text{in part (a)},\\ \PR(\ABS{X_n}>ε) &=\frac1{n^2} &&\text{in part (b)}. \end{align*}\] For \(ε\ge1\), both probabilities are zero. In part (c), once \(n>ε\), \[ \PR(\ABS{X_n}>ε) =\PR\left(ω\in\left[0,\frac1n\right]\right) =\frac1n. \] Thus, all three sequences also converge in probability to zero: \[ X_n\xrightarrow{p}0. \]

Finally, \[\begin{align*} \EXP[\ABS{X_n}^2] &=\frac1n &&\text{in part (a)},\\ \EXP[\ABS{X_n}^2] &=\frac1{n^2} &&\text{in part (b)},\\ \EXP[\ABS{X_n}^2] &=n^2\frac1n=n &&\text{in part (c)}. \end{align*}\] Therefore, the sequences in parts (a) and (b) converge in mean square to zero. The sequence in part (c) does not converge in mean square to zero. It cannot have a different mean-square limit because mean-square convergence implies convergence in probability, and a limit in probability is unique almost surely. Hence, the sequence in part (c) does not converge in mean square.

Example 9.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\}. \] Determine whether \(Y_n\) converges almost surely, in probability, or in mean square.

NoteSolution

Convergence in probability

Fix an \(ε > 0\) and consider the set \[ E_n = \{ ω : |Y_n(ω) - 0| > ε \}. \] As in Example 9.3, if \(ε > 1\), then \(\PR(E_n) = 0\). So, we assume that \(ε < 1\). Then, \[\begin{align*} \PR(E_n) &= \PR(Y_n > ε) = \PR\bigl( \min\{ X_1, \dots, X_n \} \ge ε ) \\ &= \PR( X_1 \ge ε, X_2 \ge ε, \dots, X_n \ge ε ) \\ &= (1-ε)^n \end{align*}\] which goes to zero as \(n \to ∞\). Thus, \(Y_n \xrightarrow{p} 0\).

Almost sure convergence

We now consider almost sure convergence. Note that for a fixed \(ω\), the sequence \(\{Y_n(ω)\}_{n \ge 1}\) is a decreasing sequence. Hence, it must have a limit. Denote that limit by \(Y(ω)\), i.e., \[ Y(ω) = \lim_{n \to ∞} Y_n(ω). \]

Since \(\{Y_n\}_{n \ge 1}\) is a decreasing sequence, we have that \(Y(ω) \le Y_n(ω)\). Hence, for any \(ε > 0\), \[ \PR(Y > ε) \le \PR(Y_n > ε) = (1 - ε)^n \] where the last inequality follows from the calculations done above.

The above inequality holds for every \(n\), so we have \[ \PR(Y > ε) \le \lim_{n \to ∞} (1-ε)^n = 0. \] Recall that \(ε > 0\) was arbitrary. Therefore, we have shown that \[ \PR\Bigl( \lim_{n\to ∞} Y_n > ε \Bigr) = 0. \] Thus, the only possibility is that \[ \PR\Bigl( \lim_{n\to ∞} Y_n = 0 \Bigr) = 1. \] Hence \(Y_n \xrightarrow{a.s.} 0\).

Mean square convergence

Let \(F_n\) denote the CDF of \(Y_n\) and \(f_n\) denote the PDF. As computed above, \[ F_n(y) = 1 - (1-y)^n, \quad y \in (0,1). \] Therefore, \[ f_n(y) = \frac{d F_n(y)}{dy} = n(1-y)^{n-1}, \quad y \in (0,1). \] Since \(Y_n \in [0, 1]\), we have \[ \EXP[ \ABS{Y_n - 0}^2 ] = \EXP[ Y_n^2 ] \le \EXP[ Y_n] \] where the last inequality uses the fact that \(y^2 \le y\) for \(y \in [0,1]\). We now compute \(\EXP[Y_n]\). \[\begin{align*} \EXP[Y_n] &= \int_{0}^{1} y f_n(y)\, dy \\ &= \int_{0}^1 y n (1-y)^{n-1}\, dy \\ &= n \int_{0}^1 y (1-y)^{n-1}\, dy. \end{align*}\] We could compute the integral using integration by parts, but here we simply use the fact that the above is a :Beta integral. Thus, \[ \EXP[Y_n] = n \int_{0}^1 y (1-y)^{n-1}\, dy = n B(2,n) = n\frac{1!(n-1)!}{(n+1)!} = \frac{1}{n+1}. \] Thus, \[ \lim_{n \to ∞} \EXP[Y_n^2 ] \le \lim_{n \to ∞} \EXP[Y_n ] = 0. \] Hence, \(Y_n \xrightarrow{m.s.} 0\).

9.7 Almost sure convergence from convergence in probability.

Example 9.4 shows that verifying almost sure convergence can be a bit tricky. In this section, we show that sometimes it is possible to infer almost sure convergence from convergence in probability.

WarningLim inf and lim sup of sets

We expand on the discussion of limits of sets presented earlier.

Limits of sets is easy to describe when we have weakly increasing or weakly decreasing sequence of sets. In particular, if \(\{C_n\}_{n \ge 1}\) is a weakly increasing sequence of sets, then \[ \lim_{n \to ∞} C_n = \bigcup_{n=1}^{∞} 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 \[ \lim_{n \to ∞} D_n = \bigcap_{n=1}^{∞} 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 sandwich 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 \dotsb &\quad\subseteq\qquad A_1 \qquad &\subseteq \qquad D_1 = A_1 \cup A_2 \cup A_3 \cup \dotsb \\ C_2 = \phantom{A_1 \cap{}} A_2 \cap A_3 \cap \dotsb &\quad\subseteq\qquad A_2 \qquad &\subseteq \qquad D_2 = \phantom{A_1 \cup{}} A_2 \cup A_3 \cup \dotsb \\ C_3 = \phantom{A_1 \cap A_2 \cap{}} A_3 \cap \dotsb &\quad\subseteq\qquad A_3 \qquad &\subseteq \qquad D_3 = \phantom{A_1 \cup A_2 \cup{}} A_3 \cup \dotsb \\ & \qquad\vdots & \end{array} \]

The limit of \(\{C_n\}_{n \ge 1}\) is called the lim inf of \(\{A_n\}_{n \ge 1}\), i.e., \[ \liminf_{n \to ∞} A_n = \lim_{n \to ∞} C_n = \bigcup_{n=1}^∞ C_n = \bigcup_{n=1}^{∞} \bigcap_{i=n}^{∞} A_i. \] Similarly, the limit of \(\{D_n\}_{n \ge 1}\) is called the lim sup of \(\{A_n\}_{n \ge 1}\), i.e., \[ \limsup_{n \to ∞} A_n = \lim_{n \to ∞} D_n = \bigcap_{n=1}^∞ D_n = \bigcap_{n=1}^{∞} \bigcup_{i=n}^{∞} 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. \[ ω \in \limsup_{n \to ∞} A_n \iff \limsup_{n \to ∞} \IND_{A_n}(ω) = 1 \] which holds if and only if the binary sequence \(\{\IND_{A_n}(ω)\}\) has infinitely many ones, i.e., \(ω\) is a member of infinitely many \(A_n\).

Similarly, \[ ω \in \liminf_{n \to ∞} A_n \iff \liminf_{n \to ∞} \IND_{A_n}(ω) = 1 \] which holds if and only if the binary sequence \(\{\IND_{A_n}(ω)\}\) eventually becomes \(1\) forever, i.e., \(ω\) is eventually a member of \(A_n\) forever.

For example, suppose we toss a coin infinitely many times. Let \((Ω, \ALPHABET F, \PR)\) denote the corresponding probability space, and let \(A_n\) denote the event that the \(n\)-th toss is heads. Then,

• \(\limsup_{n \to ∞} A_n\) is the event that there are infinitely many heads.
• \(\liminf_{n \to ∞} A_n\) is the event that all but a finite number of the coins were heads, i.e., there were only finitely many tails.

We now state two fundamental results. The proofs are not difficult but are omitted due to time.

Lemma 9.1 (Borel Cantelli Lemma) Let \(\{A_n\}_{n \ge 1}\) be a sequence of events defined on a common probability space \((Ω, \ALPHABET F, \PR)\). If the sum of the probability of the events is finite, i.e., \[ \sum_{n=1}^∞ \PR(A_n) < ∞, \] then the probability that infinitely many of them occur is zero, i.e., \[ \PR\Bigl(\limsup_{n \to ∞} A_n \Bigr) = 0. \]

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

There is a partial converse of Borel-Cantelli lemma.

Lemma 9.2 (Second Borel Cantelli Lemma) Let \(\{A_n\}_{n \ge 1}\) be a sequence of independent events defined on a common probability space \((Ω, \ALPHABET F, \PR)\). If the sum of the probability of the events is infinite, i.e., \[ \sum_{n=1}^∞ \PR(A_n) = ∞, \] then the probability that infinitely many of them occur is one, i.e., \[ \PR\Bigl(\limsup_{n \to ∞} A_n \Bigr) = 1. \]

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

Lemma 9.3 Suppose \(X_n \xrightarrow{p} X\) and for any \(ε > 0\), we have \[ \sum_{n=1}^{∞} \PR(\ABS{X_n - X} > ε) < ∞ \] then \(X_n \xrightarrow{a.s.} X\).

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

• Consider Example 9.3, part a, we have \[ \PR(E_n) = \frac 1n. \] Since \(\sum_{n \ge 1} \PR(E_n) = ∞\), we cannot use the above theorem to infer that \(X_n \xrightarrow{a.s.} 0\). This is not a contradiction because Lemma 9.3 is a sufficient condition, not a necessary condition.

• Consider Example 9.3, part b, we have \[ \PR(E_n) = \frac 1{n^2}. \] Since \(\sum_{n \ge 1} \PR(E_n) < ∞\), we can use Lemma 9.3 to infer that \(X_n \xrightarrow{a.s.} 0\).

• In Example 9.4, we have argued that \(\PR(Y_n > ε) = (1-ε)^n\). Therefore, \(\sum_{n \ge 1} \PR(Y_n > ε) = \sum_{n=1}^∞ (1-ε)^n = \frac{1-ε}{ε} < ∞\) (for \(0 < ε < 1\)). Hence, by Lemma 9.3, \(Y_n \xrightarrow{a.s.} 0\).

We can also consider a variation of the above.

Example 9.5 Consider a variation of Example 9.3, where we no longer specify \(X_n\) as a function of \(ω\) but simply assume that \[ X_n = \begin{cases} 0 & \text{with probability } 1 - p_n \\ 1 & \text{with probability } p_n \end{cases} \] and \(\{X_n\}_{n \ge 1}\) are independent.
Determine whether \(\{X_n\}_{n \ge 1}\) converges almost surely, in probability, or in mean square

1. \(p_n = \frac 1n\)
2. \(p_n = \frac 1{n^2}\).

NoteSolution

• Convergence in probability: Fix \(ε \in (0,1)\). As before define \(E_n = \{ ω : \ABS{X_n(ω)} > ε \} = \{ ω : X_n(ω) = 1 \}\). Thus, \(\PR(E_n) = p_n\) and for both cases, \(p_n \to 0\) as \(n \to ∞\). Therefore, \(X_n \xrightarrow{p} 0\).

• Almost sure convergence: For part (a), \(\sum_{n \ge 1} p_n = ∞\); hence by the Second Borel-Cantelli lemma, \[ \PR(\limsup_{n \to ∞} \{ \ABS{X_n} > ε \}) = 1. \] So, \(X_n\) does not converge almost surely!

  For part (b), \(\sum_{n \ge 1} p_n < ∞\); hence by Lemma 9.3, \(X_n \xrightarrow{a.s.} 0\).

• Mean square convergence: We have \(\EXP[\ABS{X_n}^2] = p_n\). For both cases \(p_n \to 0\). Hence, \(X_n \xrightarrow{m.s.} 0\).

Note that part (a) converges in probability and mean square but not almost surely.

A useful consequence of Lemma 9.3 is the following:

Lemma 9.4 Let \(\{X_n\}_{n \ge 1}\) be a sequence of random variables and let \(X\) be another random variable. If \[ \sum_{n=1}^{∞} \EXP[ \ABS{X_n - X} ] < ∞ \] then \[ X_n \xrightarrow{a.s.} X. \]

NoteProof

For every \(m\in\naturalnumbers\), define \[ A_n^{(m)}=\left\{ω:\ABS{X_n(ω)-X(ω)}>\frac1m\right\}. \]

By Markov’s inequality, \[ \sum_{n=1}^{∞}\PR\left(A_n^{(m)}\right) \le m\sum_{n=1}^{∞}\EXP[\ABS{X_n-X}]<∞. \] Therefore, the Borel-Cantelli lemma gives \[ \PR\left(\limsup_{n\to∞}A_n^{(m)}\right)=0 \qquad\text{for every }m\in\naturalnumbers. \] The countable union of these probability-zero events also has probability zero. Outside this union, for every \(m\) there exists an \(N_m(ω)\) such that \[ n\ge N_m(ω)\implies \ABS{X_n(ω)-X(ω)}\le\frac1m. \] Thus, \(X_n(ω)\to X(ω)\) outside a probability-zero set, and hence \(X_n\xrightarrow{a.s.}X\).

9.8 Strong law of large numbers

Theorem 9.1 Let \(\{X_n\}_{n \ge 1}\) be an i.i.d. sequence of random variables with mean \(μ\) and variance \(σ^2\). Let \[ \bar X_n = \frac 1n \sum_{i=1}^n X_i \] be the sample average. Then, \(\bar X_n \xrightarrow{a.s.} μ\), i.e., \[ \PR\Bigl( ω : \lim_{n \to ∞} \bar X_n(ω) = μ \Bigr) = 1. \]

We provide a proof under the assumption that the fourth moment exists.

NoteProof

We assume that \(μ = 0\) (this is just for notational simplicity) and let \(M_4=\EXP[X_1^4]<∞\) (this is a strong assumption).

Since we know that the fourth moment exists, we can use a fourth moment version of Markov inequality: \[ \PR(\ABS{\bar X_n} \ge ε) = \PR(\ABS{\bar X_n}^4 \ge ε^4) \le \frac{ \EXP[ \bar X_n^4]}{ε^4}. \]

When we expand \((X_1+\cdots+X_n)^4\), independence and the zero-mean assumption imply that every term containing an index exactly once has expectation zero. The only surviving terms are those in which all four indices are equal or there are two pairs of equal indices. Therefore, \[\begin{align*} \EXP\left[(X_1+\cdots+X_n)^4\right] &=\sum_{i=1}^n\EXP[X_i^4] +6\sum_{1\le i<j\le n}\EXP[X_i^2X_j^2]\\ &=nM_4+6\binom n2σ^4\\ &=nM_4+3n(n-1)σ^4. \end{align*}\] Consequently, \[ \EXP[\bar X_n^4] =\frac{M_4}{n^3}+\frac{3(n-1)σ^4}{n^3} \le \frac{M_4}{n^3}+\frac{3σ^4}{n^2}. \] Thus, the fourth-moment version of Markov’s inequality gives \[ \PR(\ABS{\bar X_n} \ge ε) \le \frac{ \frac{M_4}{n^3} + \frac{3 σ^4}{n^2} }{ε^4}. \] This implies that \[ \sum_{n=1}^{∞} \PR(\ABS{\bar X_n} \ge ε) < ∞. \] Thus, from Lemma 9.3, we have that \(\bar X_n \xrightarrow{a.s.} 0\).

9.9 Further Reading

• Gubner: Sec. 13.1, 14.1, 14.2, 14.3 (and corresponding problems at the end of the chapters)
• Grimmett and Stirzaker: Sec. 7.1, 7.2, 7.3, 7.4, 7.5 (and corresponding problems at the end of the sections and the end of the chapters)