Law of Large Numbers

Empirical averages

Let $\set{X_n}_{n \in \N}$ be a sequence of i.i.d. random variables.

Definition 1. The empirical mean after $N$ trials is defined by $$\label{e:EM}\tag{EM} \mu_N \defeq \frac{1}{N} \sum_{n = 1}^N X_n \,. $$

From experience one expects $\mu_N \to \mu$ as $N \to \infty$. This is the content of the law of large numbers. Note however, $\mu_N$ is a random variable – convergence of $\mu_N \to \mu$ is a statement about the convergence of random variables. There are many different notions of convergence of random variables, and the various laws of large numbers study different notions of convergence of the empirical mean $\mu_N$ to the true mean $\mu$.

Theorem 2 (Mean Square Law of Large Numbers). Let $\set{X_n}_{n \in \N}$ be a sequence of i.i.d. random variables with finite variance. Let $\mu = \E X_1$, $\sigma^2 = \var(X_1)$. Then $$ \E (\mu_N - \mu)^2 = \frac{\sigma^2}{N} \xrightarrow{N \to \infty} 0 \,. $$

Theorem 3 (Weak Law of Large Numbers). Let $\set{X_n}_{n \in \N}$ be a sequence of i.i.d. random variables with finite variance. Let $\mu = \E X_1$, $\sigma^2 = \var(X_1)$. Then for any $\epsilon > 0$, $$ \P \paren[\big]{ \abs{\mu_N - \mu} > \epsilon } \leq \frac{\sigma^2}{\epsilon^2 N} \xrightarrow{N \to \infty} 0 \,. $$

Remark 4. There are random variables for which the mean is not defined. There are also random variables for which the mean is defined by the variance is not.

Theorem 5 (Strong Law of Large Numbers). Let $\set{X_n}_{n \in \N}$ be a sequence of i.i.d. random variables with finite fourth moment (i.e. $\E \abs{X_1}^4$ is defined and finite), and let $\mu = \E X_1$. Then $\mu_N \to \mu$ almost surely. That is, $$ \P \paren[\Big]{ \lim_{n \to \infty} \mu_N = \mu } = 1 \,. $$

Remark 6. The mean square law of large numbers of course requires the random variables to have finite variance. The weak and strong law of large numbers don’t, and are in fact true without any hypothesis other than requiring $\mu$ to be defined.

Problem 7. Find a random variable $X$ for which the mean is defined by the variance is not.

Problem 8. Let $X$ be a random variable and $0 < p < q < \infty$.

  1. If $\E |X|^p$ is must $\E |X|^q$ be defined? Prove it, or find a counter example.
  2. If $\E |X|^q$ is must $\E |X|^p$ be defined? Prove it, or find a counter example.

Products of independent random variables

Theorem 9. Let $\set{X_n}_{n \leq N}$ be (discrete) random variables. The collection $\set{X_n}_{n \leq N}$ is independent if and only if for every collection of functions $\set{f_n}_{n \leq N}$ $$\label{e:P}\tag{P} \E \paren[\Big]{\prod_{n = 1}^N f_n(X_n)} = \prod_{n = 1}^N \E f_n(X_n) \,, $$ provided the functions $f_n$ are such that both the left hand side and right hand side are defined.

Remark 10. The sequence of random variables $\set{X_n}_{n \in \N}$ are independent if and only if \eqref{e:P} holds for every finite $N$.

Corollary 11. Independent random variables are uncorrelated.

Problem 12. Let $X, Y$ be two (discrete) random variables for which $\E X$, $\E Y$, $\E (XY)$ are all defined.

  1. True or false: If $X$ and $Y$ are independent, then $\E (XY) = \E X \E Y$.
  2. True or false: If $\E (XY) = \E X \E Y$, then $X$ and $Y$ are independent.

When the random variables are not discrete, one can prove the following analog of Theorem 9.

Theorem 13. Let $\set{X_n}_{n \leq N}$ be random variables. The collection $\set{X_n}_{n \leq N}$ is independent if and only if for every collection of bounded continuous functions $\set{f_n}_{n \leq N}$ $$\label{e:PC}\tag{PC} \E \paren[\Big]{\prod_{n = 1}^N f_n(X_n)} = \prod_{n = 1}^N \E f_n(X_n) \,. $$

Proof. The proof of this requires some measure theory / approximation arguments, and will be skipped.

Proposition 14. Suppose $\set{X_n}_{n \in \N}$ is a collection of pairwise uncorrelated random variables. That is, for $m \neq n$, suppose $\cov(X_m, X_n) = 0$. Then for every $N \in \N$ $$\label{e:V}\tag{V} \var\paren[\Big]{ \sum_{n=1}^N X_n } = \sum_{n=1}^N \var(X_n) \,. $$

Corollary 15. If $\set{X_n}_{n \in \N}$ is a collection of pairwise independent random variables, then \eqref{e:V} holds.

Mean square convergence

Definition 16. Let $Y$ be a random variable, $(Y_n)$ be a sequence of random variables. Let $p \in [1, \infty)$. We say $Y_n \to Y$ in $L^p$, if $$ \lim_{n \to \infty} \E \abs{Y_n - Y}^p = 0 \,. $$ When $p = 1$, we say $Y_n \to Y$ in mean. When $p = 2$, we say $Y_n \to Y$ in mean square.

Remark 17. While Definition 16 makes sense for any $p > 0$, it is often only used when $p \geq 1$. The reason for this is Minkowski’s inequality. Define $$ \norm{X}_p = (\E \abs{X}^p )^{1/p} \,. $$ For any $p \geq 1$, Minkowski’s inequality implies $\norm{X + Y}_p \leq \norm{X}_p + \norm{Y}_p$. That is $\norm{X - Y}_p$ can be used to measure the distance between the two random variables, and this notion of distance will satisfy the triangle inequality. For $p \in (0, 1)$ this is no longer true.

Proposition 18. If $1 \leq p \leq q$, then $\norm{X}_p \leq \norm{X}_q$. Consequently if $X_n \to X$ in $L^q$, then $X_n \to X$ in $L^p$.

Proof of the mean square LLN (Theorem 2). Note $$ \E(\mu_N - \mu)^2 = \frac{1}{N^2} \var\paren[\Big]{ \sum_{n=1}^N \var(X_n) } = \frac{\var(X_1)}{N} \,. $$

Remark 19. Note Theorem 2 is equivalent to showing $\mu_N \to \mu$ in $L^2$. Here $\mu_N$ is a random variable (the empirical mean), and $\mu$ is viewed as a constant random variable, which takes on the value $\mu$ with probability $1$.

Problem 20. Suppose $X_n$ is a sequence of random variables such that $$ \lim_{n \to \infty} \E X_n = \mu\,, \quad \max_{n \in \N} \sum_{k = 0}^\infty \abs{\cov(X_n, X_{n + k})} < \infty $$ Show that $\mu_N \to \mu$ in $L^2$, where $\mu_N$ is the empirical mean defined in \eqref{e:EM}.

Problem 21. Let $X$ be a random variable, and $X_n$ be a sequence of random variables.

  1. If $p \geq 1$ and $X_n \to X$ in $L^p$ as $n \to \infty$, then show that $\E X_n \to \E X$.
  2. If $p \geq 2$ and $X_n \to X$ in $L^p$ as $n \to \infty$, then show that $\var(X_n) \to \var(X)$.

Convergence in probability

Definition 22. Let $Y$ be a random variable, $(Y_n)$ be a sequence of random variables. We say $Y_n \to Y$ in probability if for any $\epsilon > 0$, $$ \lim_{n \to \infty} \P \paren[\big]{\abs{Y_n - Y} > \epsilon} = 0 \,. $$

Proposition 23. If for any $p \in [1, \infty)$, we have $Y_n \to Y$ in $L^p$. Then, $Y_n \to Y$ in probability.

Proof of the weak LLN (Theorem 3). Proposition 23 and Theorem 2 immediately imply Theorem 3.

Problem 24. Find an example of a sequence of random variables $Y_n$, and a random variable $Y$ such that $Y_n \to Y$ in probability, $\E Y$, $\E Y_n$ are all defined, but $Y_n$ does not converge to $Y$ in mean.

Problem 25. Suppose $X_n \sim \Binom(n, p)$. Show that $\frac{1}{n} X_n \to p$ in probability, as $n \to \infty$.

Borel Cantelli Lemmas

Let $\set{A_n}_{n \in \N}$ be a sequence of events.

Definition 26. The event that $\set{A_n}$ occurs infinitely often (denoted by $\limsup A_n$, or $\set{A_n \text{ i.o}}$) is defined by $$ \limsup_{n \to \infty} A_n = \set{A_n \text{ i.o.}} \defeq \set{\omega \in \Omega \st \text{ there exist infinitely many } n \in \N \text{ such that } \omega \in A_n } \,. $$

Definition 27. The event that $\set{A_n}$ occurs eventually (denoted by $\liminf A_n$, or $\set{A_n \text{ ev.}}$) is defined by $$ \liminf_{n \to \infty} A_n = \set{A_n \text{ ev.}} \defeq \set{\omega \in \Omega \st \exists N = N(\omega) \in \N : \forall n \geq N, \omega \in A_n } \,. $$

Lemma 28 (Borel Cantelli). Let $\set{A_n}_{n \in \N}$ be a sequence of events.

  1. If $\sum_1^\infty \P(A_n) < \infty$, then almost surely, $A_n$ does not occur infinitely often. That is $$ \P( \limsup A_n ) = \P( A_n \text{ i.o.} ) = 0 $$

  2. If $\sum_1^\infty \P(A_n) = \infty$, and $\set{A_n}_{n \in \N}$ are independent, then almost surely, $A_n$ occurs infinitely often. That is $$ \P( \limsup A_n ) = \P( A_n \text{ i.o.} ) = 1 $$

Proof sketch. For the first part $$ \P( A_n \text{ i.o.} ) = \P\paren[\big]{ \bigcap_m \bigcup_{n \geq m} A_n } \leq \lim_{m \to \infty} \sum_{n \geq m} \P(A_n) = 0\,. $$ For the second part, $$ \P( \set{A_n \text{ i.o.}}^c ) = \P( A_n^c \text{ ev.} ) = \P\paren[\big]{ \bigcup_m \bigcap_{n \geq m} A_n^c } = \lim_{m \to \infty} \prod_{n \geq m} (1 - \P(A_n)) $$ Now note $$ \prod_{n \geq m} (1 - \P(A_n)) = \exp\paren[\Big]{\sum_{m \geq n}\log (1 - \P(A_n))} $$ and $$ \sum_{n \geq m} \log (1 - \P(A_n)) \leq -\sum_{n \geq m} \P(A_n) = -\infty $$ so $\prod_{n \geq m} (1 - \P(A_n)) \to 0$.

Example 29. Let $A \in \mathcal F$ be such that $\P(A) \in (0, 1)$. Let $A_n = A$ for every $n \in \N$. Then for sequence of events $\set{A_n}_{n \in \N}$ we have $\sum_n \P(A_n) = \infty$, but $\P(A_n \text{ i.o}) = \P(A) < 1$. (In other words, the converse of the first Borel Cantelli lemma is false.) This can easily be upgraded to obtain an example where $\sum_n \P(A_n) = \infty$ and $\P(A_n \text{ i.o.}) = 0$.

Example 30. Let $\set{p_n}_{n \in \N}$ be a sequence of numbers, $\set{X_n}$ be independent random variables, such that $X_n \sim \Bernoulli(p_n)$.

  1. If $\sum p_n < \infty$, then almost surely $X_n = 0$ eventually.
  2. If $\sum p_n = \infty$, then almost surely $X_1$ infinitely often

Remark 31. The above is a generalization of the infinite monkey theorem. Suppose you have an army of monkeys that type randomly into a typewriter. On day $n$, the probability they produce the complete collected works of Shakespeare is $p_n$. (If they typed more text than Shakespeare did, then the probability of succeeding is miniscule, but positive.) As time increases, the monkeys age and become slower, and so $p_n$ may become smaller as $n \to \infty$. If, $\sum p_n = \infty$, then the Borel Cantelli lemma guarantees that the monkeys will (almost surely) produce the complete collected works of Shakespeare, infinitely often. If $\sum p_n < \infty$, then they may produce the complete collected work sof Shakespeare finitely many times; but they will almost never (i.e. with probability $0$) produce the complete collected works of Shakespeare infinitely often.

Problem 32. Let $p \in (0, 1)$, and $\set{X_n}$ be a sequence of i.i.d. $\Geom(p)$ random variables.

  1. Is there a random variable $Y$ such that for all $n \in \N$, $X_n \leq Y$ almost surely? Prove or disprove it.
  2. Is there a random variable $Y$ such that for all $n \in \N$, $X_n \leq n Y$ almost surely? Prove or disprove it.
  3. More generally, let $(c_n)_{n \in \N}$ be a (deterministic) sequence of positive numbers. There exists a random variable $Y$ such that $X_n \leq c_n Y$ almost surely for all $n$, if and only if there exists $K > 0$ such that $$ \sum_{n = 1}^\infty (1 - p)^{K c_n} < \infty \,. $$

Almost sure convergence

Definition 33. Let $X$ be a random variable, $\set{X_n}$ be a sequence of random variables. We say $X_n \to X$ almost surely as $n \to \infty$ if $$ \P\paren[\Big]{ \omega \in \Omega \st \lim_{n \to \infty} X_n(\omega) = X(\omega) } = 1 \,. $$

Lemma 34. If  $X_n \to X$ almost surely as $n \to \infty$, then $X_n \to X$ in probability as $n \to \infty$.

The converse is false.

Problem 35. Let $\set{X_n}$ be a sequence of i.i.d. $\Bernoulli(p)$ random variables with $p \in (0, 1)$. Given $n \in \N$, write $n = (b_1, b_2, \dots, b_k)$ in binary, and define $Y_n = 1$ if $(X_1, \dots, X_k) = (b_1, \dots, b_k)$ and $0$ otherwise. Show that $Y_n \to 0$ in probability, but $Y_n \not \to 0$ almost surely.

Lemma 36. Let $X$ be a random variable, $\set{X_n}$ be a sequence of random variables. Suppose for every $\epsilon > 0$, we knew $\sum_1^\infty \P( \abs{X_n - X} > \epsilon ) < \infty$. Then $X_n \to X$ almost surely.

Lemma 37. Let $X_n$ be i.i.d. random variables, $\E X_1 = \mu$, $\var(X_1) = \sigma^2$, $\E(X_1 - \mu)^4 = \tau^4$. Then $$ \E( \mu_N - \mu)^4 = \frac{N \tau^4 + 3N (N-1) \sigma^4}{N^4} \,. $$

Proof of Theorem 5. Follows immediately from Lemma 36, Lemma 37 and Chebychev’s inequality.

Normal numbers

Definition 38 (Normal numbers). Let $b \in \N$, $b \geq 2$. Let $x \in [0, 1]$, and let $S$ be any finite sequence in $\set{0, \dots, b-1}$. Let $N_S(x, n)$ be the number of occurrences of $S$ in the first $n$ places of the base $b$ expansion of $x$. We say $x \in [0, 1)$ is normal in base $b$ if for every finite sequence of base $b$-digits $S$, $$ \lim_{n \to \infty} \frac{N_S(x, n)}{n} = \frac{1}{b^{\abs{S}}} \,. $$ We say $x \in [0, 1)$ is normal if it is normal in base $b$ for all $b \geq 2$.

It is not known whether $\pi - 3$ or $e - 2$ are normal. However, we will shortly show that almost every $x \in [0, 1]$ is a normal number.

Problem 39. Let $\Omega = [0, 1]$, $\mathcal B$ be the Borel $\sigma$-algebra, and $\P$ be the Lebesgue measure (see this theorem). Let $b \geq 2$, and $X_n(\omega)$ be the $n$-th digit in the base-$b$ expansion of $\omega$.

  1. Show that $X_n$ are i.i.d. and uniformly distributed on $\set{0, \dots, b-1}$.
  2. Show that any  $\omega \in [0, 1]$ is almost surely a normal number in base $b$.

Lemma 40. If $\set{A_n}_{n \in \N}$ are a sequence of events such that $\P(A_n) = 1$ for every $n$, then $\P(\cap_{n \in \N} A_n) = 1$.

Proposition 41. Show that any  $\omega \in [0, 1]$ is almost surely a normal number (i.e. show that with probability $1$, any $\omega \in [0, 1)$ is normal with every base $b \geq 2$.

Random series

Recall the Lebesgue measure on $[0, 1]$ is a probability measure $\mu$ such that for every interval $[a, b] \subseteq [0, 1]$, we have $\mu([a, b]) = b - a$. As mentioned earlier, constructing the Lebesgue measure completely requires some work. It’s not enough to simply specify the value of the Lebesgue measure on intervals; you need to specify it’s value on all Borel sets – the smallest $\sigma$-algebra containing all open intervals. Arbitrary Borel sets aren’t nice countable disjoint unions of intervals, and so it isn’t easy to ensure the Lebesgue measure can be consistently defined on such sets, and satisfy our countable additivity requirement.

Using a random series, however, one can simply write down a formula for the Lebesgue measure on arbitrary Borel sets!

Proposition 42. Let $X_n$ be i.i.d. $\Bernoulli(1/2)$ random variables, define $$ X = \sum_1^\infty \frac{X_n}{2^n} \,. $$ Then for any Borel set $B \subseteq [0, 1]$, $\P(X \in B)$ is the Lebesgue measure of $B$.

The proof of this requires one calculation (below), and one measure theory lemma (which we state but don’t prove).

Lemma 43. Let $X$ be as in Proposition 42. For every interval $[a, b] \subseteq [0, 1]$, we have $\P(X \in [a, b]) = b -a$.

Proof sketch. Let $S_n = \sum_1^n X_n / 2^n$. Show that for any $b \in [0, 1]$, and any $n \in \N$, we have $$ \set{X < b} \subseteq S_n \leq \frac{\floor{2^n b}}{2^n} \,. $$

Proof of Proposition 42. While it may seem obvious that Lemma 43 implies Proposition 42, it requires a little work to prove. It’s usually done by the Doob Dynkin lemma; which we won’t go into the details of.

By tweaking the above a little, you can get $X$ to be uniformly distributed on the Cantor Set.

Proposition 44. Let $X_n$ be i.i.d. random variables which are uniformly distributed on $\set{0, 2}$. Define $$ X = \sum_{n = 1}^{\infty} \frac{X_n}{3^n} \,. $$ Then $X$ is “uniformly distributed” on the Cantor set. (More correctly, $\P_X$ is the $\log_3 2$-dimensional Hausdorff measure on the cantor set.)

Another notion you’re all familiar with is that the Harmonic series $\sum 1/n$ diverges, but the alternating Harmonic series $\sum (-1)^n / n$ converges. Suppose now we look at the random series $$ X = \sum_{n = 1}^\infty \frac{\xi_n}{n} \,, $$ where $\set{\xi_n}$ are i.i.d. Radamacher random variables (i.e. $\P(\xi_n = 1) = \P(\xi_n = -1) = 1/2$).

Problem 45. Show that the series defining $X$ converges almost surely.

The standard proof of this is to use a Tonelli theorem to show $$ \E X^2 = \sum_{n = 1}^\infty \frac{\E \xi_n^2 }{n^2} < \infty\,, $$ and then conclude $\P(X < \infty) = 1$. However, this involves tools from Lebesgue integration we haven’t yet learnt. Instead there’s a (slightly longer) proof using Borel Cantelli.

Hint. Define $ A_k = \sum_{n = 2^k + 1}^{2^{k+1}} \frac{\xi_n}{n} $, and show $\sum \P(A_k \geq 1/k^2) < \infty$