Covariance, convergence of random variables, limit theorems

WarningDraft

This lecture note is still being edited: the text may contain typos, inaccuracies, and locally underdeveloped passages. If you find something, please let the author know (contact information on the course page).

1 Covariance, correlation

Definition 1 The covariance of random variables \(\xi , \eta\) is defined as

\[ \operatorname {Cov}\left[ \xi , \eta \right] = \mathbb {E}\left[\left(\xi - \mathbb {E}\left[\xi \right]\right) \cdot \left(\eta - \mathbb {E}\left[\eta \right]\right)\right] \]

Let us immediately expand it using linearity of expectation:

\[ \operatorname {Cov}\left[ \xi , \eta \right] = \mathbb {E}\left[\xi \eta \right] - \mathbb {E}\left[\xi \right] \cdot \mathbb {E}\left[\eta \right] - \mathbb {E}\left[\xi \right] \cdot \mathbb {E}\left[\eta \right] + \mathbb {E}\left[\xi \right] \cdot \mathbb {E}\left[\eta \right] = \mathbb {E}\left[\xi \eta \right]- \mathbb {E}\left[\xi \right] \cdot \mathbb {E}\left[\eta \right] \]

The covariance exists provided the first moments \(\mathbb {E}\left[\xi \right]\), \(\mathbb {E}\left[\eta \right]\) and \(\mathbb {E}\left[\xi \eta \right]\) exist.

The correlation of random variables \(\xi , \eta\) is the ratio

\[ \operatorname {Corr}\left[ \xi , \eta \right] = \frac{\operatorname {Cov}\left[ \xi , \eta \right]}{\sqrt{\operatorname {Var}\left[\xi \right] \operatorname {Var}\left[\eta \right]}} \]

It exists provided the corresponding variances exist.

Correlation is, in a certain sense, a measure of dependence between random variables \(\xi , \eta\). Namely, if the random variables \(\xi , \eta\) are independent, then \(\operatorname {Corr}\left[ \xi , \eta \right] =0\). Conversely, if \(\operatorname {Corr}\left[ \xi , \eta \right] = \pm 1\), then the random variables are linearly dependent.

Properties of covariance

• Covariance is symmetric: \(\operatorname {Cov}\left[ \xi , \eta \right] = \operatorname {Cov}\left[ \eta , \xi \right]\);

• Covariance is bilinear:

  \[ \begin{align} \operatorname {Cov}\left[ a_1\xi _1 + a_2\xi _2, \eta \right] & = a_1\operatorname {Cov}\left[ \xi _1, \eta \right] + a_2 \operatorname {Cov}\left[ \xi _2, \eta \right] \\ \operatorname {Cov}\left[ \xi , b_1\eta _1 + b_2\eta _2 \right] & = b_1\operatorname {Cov}\left[ \xi , \eta _1 \right] + b_2 \operatorname {Cov}\left[ \xi , \eta _2 \right] \end{align} \]

• \(\operatorname {Cov}\left[ \xi , \xi \right] = \operatorname {Var}\left[\xi \right]\);

• \(\operatorname {Cov}\left[ \xi , \eta \right] = \mathbb {E}\left[\xi \eta \right] - \mathbb {E}\left[\xi \right]\mathbb {E}\left[\eta \right]\);

• if \(\xi , \eta\) are independent, then \(\operatorname {Cov}\left[ \xi , \eta \right]=0\);

• if \(c\in \mathbb {R}\) is a constant, then \(\operatorname {Cov}\left[ \xi + c, \eta \right] = \operatorname {Cov}\left[ \xi , \eta \right]\);

• \(\operatorname {Var}\left[\xi_{1}+\ldots +\xi_{n}\right]=\operatorname {Var}\left[\xi_{1}\right]+\ldots +\operatorname {Var}\left[\xi_{n}\right]+\sum_{i \neq j} \operatorname {Cov}\left[ \xi_i, \xi_j \right]\).

ExampleExample 1

Give an example of two dependent random variables \(\xi , \eta\) whose covariance equals \(0\).

SolutionSolution

The point: covariance measures the degree of linear dependence. However, dependence can be nonlinear even while the linear-dependence coefficient equals \(0\).

Let \(\Omega =\left\{ \omega_{1}, \omega_{2}, \omega_{3}\right\}\) with probabilities \(1/3\) each. Define \(\xi\), \(\eta\) on the elementary outcomes as follows:

	\(\omega _1\)	\(\omega _2\)	\(\omega _3\)
\(\mathbb {P}\left(\omega _i\right)\)	\(1/3\)	\(1/3\)	\(1/3\)
\(\xi\)	\(1\)	\(1\)	\(0\)
\(\eta\)	\(1\)	\(-1\)	\(0\)

• Note that \(\xi \eta = \eta\) and \(\mathbb {E}\left[\eta \right] = 1 \cdot \frac{1}{3} - 1 \cdot \frac{1}{3} + 0 \cdot \frac{1}{3} = 0\), hence

  \[ \operatorname {Cov}\left[ \xi , \eta \right] = \mathbb {E}\left[\xi \eta \right] - \mathbb {E}\left[\xi \right]\mathbb {E}\left[\eta \right] = \mathbb {E}\left[\eta \right] - \mathbb {E}\left[\xi \right] \cdot \mathbb {E}\left[\eta \right] = 0 - \frac{2}{3} \cdot 0 = 0 \]

• The random variables are dependent. Indeed, \(\mathbb {P}\left(\xi = 0\right) = \mathbb {P}\left(\eta = 0\right) = \mathbb {P}\left(\omega_3\right) = \frac{1}{3}\), while

  \[ \mathbb {P}\left(\xi =0, \eta =0\right) = \mathbb {P}\left(\omega _3\right) =\frac{1}{3} \neq \frac{1}{3} \cdot \frac{1}{3} = \mathbb {P}\left(\xi = 0\right) \cdot \mathbb {P}\left(\eta = 0\right) \]

In this case there is dependence, but it is nonlinear: \(\xi = \eta^2\) or \(\xi = \left|\eta \right|\).

2 The indicator method

ExampleExample 2

Given a \(5 \times 4\) grid table. A spider wants to get from the bottom-left node to the top-right node, moving along the sides of the cells. It can only move right or up. Among all possible paths of length \(9\), the spider chooses its path uniformly at random. Compute

1. the expectation,

2. the variance and the standard deviation (the square root of the variance) of the number of turns it makes along the way.

Figure 1: A \(5\times 4\) grid: the spider moves only right or up. In this example path the spider made \(5\) turns.

SolutionSolution

Generally speaking, in problems like this one can dispense with the formalism of a probability triple and go straight to the computation, but for the sake of clarity we will construct the probability space explicitly.

The spider must make \(5\) horizontal moves and \(4\) vertical moves. We can formalize the corresponding experiment as follows:

\[ \Omega = \left\{ \omega = \left(\omega _1, \ldots , \omega _9\right) \quad : \quad \omega _i \in \left\{ 0,1\right\} , \; \sum _{1}^9 \omega _i = 4\right\} , \quad \mathcal{F} = 2^{\Omega }, \quad \mathbb {P}\left(B\right) = \frac{\left|B\right|}{\left|\Omega \right|} = \frac{\left|B\right|}{C_{9}^5}, \; B \in \mathcal{F} \]

Here \(0\) corresponds to a move to the right, and \(1\) to a move up.

Note that the number of turns \(X\) is exactly the number of subsequences of the form \(0,1\) or \(1,0\) in \(\omega \in \left\{ 0,1\right\}^9\). That is,

\[ \begin{align} X & = \; \mathbb {1}_{A_1} + \ldots + \; \mathbb {1}_{A_8} = \sum _{k=1}^{8} \; \mathbb {1}_{A_{k}}= \sum _{k=1}^{8} \bigg[\; \mathbb {1}_{\left\{ \omega _{k} = 1, \; \omega _{k+1} = 0\right\} } + \; \mathbb {1}_{\left\{ \omega _{k} = 0, \; \omega _{k+1} = 1\right\} }\bigg] \end{align} \]

where \(A_i = \left\{ \omega_i \neq \omega_{i+1}\right\}\) is the event corresponding to a turn at step \(i\), and \(\; \mathbb {1}_{A_i} = \; \mathbb {1}_{A_i}(\omega )\) is the indicator of this event.

Note that for an arbitrary event \(A\) the indicator has a Bernoulli distribution: \(\; \mathbb {1}_{A} \sim \operatorname {Ber}(\mathbb {P}\left(A\right))\), hence

\[ \mathbb {E}\left[\; \mathbb {1}_{A}\right] = \mathbb {P}\left(A\right), \quad \operatorname {Var}\left[\; \mathbb {1}_{A}\right] = \mathbb {P}\left(A\right) \cdot (1 - \mathbb {P}\left(A\right)) \]

Enum-item1.

The expectation of a random variable equal to the sum of indicators of some events can be computed as the sum of the probabilities of these events. Note that this formula works regardless of whether the events are dependent (as is the case here) or independent.

\[ \begin{align} \mathbb {E}\left[X\right] = \mathbb {E}\left[\sum _{i=1}^{8} \; \mathbb {1}_{A_{i}}\right] = \sum _{i=1}^{8} \mathbb {P}\left(A_{i}\right) \end{align} \]

Let us compute the probability of an individual event:

\[ \mathbb {P}\left(A_i\right) = \mathbb {P}\left(\left\{ \omega \; \; : \; \; \omega _i = 0, \; \omega _{i+1} = 1\right\} \right) + \mathbb {P}\left(\left\{ \omega \; \; : \; \; \omega _{i} = 1, \; \omega _{i+1} = 0\right\} \right) = 2 \cdot \frac{C_{7}^4}{C_{9}^5} = \frac{5}{9} \]

Note that the probability does not depend on \(i\).

Altogether, \(\mathbb {E}\left[X\right] = 8 \cdot \frac{5}{9} = \frac{40}{9}\).

Enum-item2.

The variance is trickier, since computing it requires accounting for the dependencies between the events inside the indicators. We have

\[ \begin{align} \operatorname {Var}\left[X\right] = \operatorname {Cov}\left[ X, X \right] & = \sum _{i,j=1}^{8} \operatorname {Cov}\left[ \; \mathbb {1}_{A_{i}}, \; \mathbb {1}_{A_{j}} \right] = \sum _{i=1}^{8}\operatorname {Var}\left[\; \mathbb {1}_{A_{i}}\right] + \sum _{\substack {i,j=1 \\ i \neq j}}^{8} \operatorname {Cov}\left[ \; \mathbb {1}_{A_{i}}, \; \mathbb {1}_{A_{j}} \right] = \\ & = \sum _{i=1}^{8}\operatorname {Var}\left[\; \mathbb {1}_{A_{i}}\right] + 2\sum _{\substack {i,j=1 \\ i < j}}^{8} \operatorname {Cov}\left[ \; \mathbb {1}_{A_{i}}, \; \mathbb {1}_{A_{j}} \right] \end{align} \]

Note that \(\operatorname {Cov}\left[ \; \mathbb {1}_{A_{i}}, \; \mathbb {1}_{A_{j}} \right]\) depends only on \(\left|i-j\right|\): if \(\left|i-j\right| = 1\), i.e., these are adjacent turns, then they affect one another. If \(\left|i-j\right| \geq 2\), the turns do not affect one another. Hence,

\[ \begin{align} \operatorname {Var}\left[X\right] & = \sum _{i=1}^{8}\operatorname {Var}\left[\; \mathbb {1}_{A_{i}}\right] + 2\sum _{i=1}^{7} \operatorname {Cov}\left[ \; \mathbb {1}_{A_{i}}, \; \mathbb {1}_{A_{i+1}} \right] + 2\sum _{\substack {i,j=1 \\ i + 1 < j}}^{8} \operatorname {Cov}\left[ \; \mathbb {1}_{A_{i}}, \; \mathbb {1}_{A_{j}} \right] = \\ & = 8 \cdot \operatorname {Var}\left[\; \mathbb {1}_{A_{1}}\right] + 2 \cdot 7 \cdot \operatorname {Cov}\left[ \; \mathbb {1}_{A_1}, \; \mathbb {1}_{A_2} \right] + \left(64 - 14 - 8\right) \cdot \operatorname {Cov}\left[ \; \mathbb {1}_{A_{1}}, \; \mathbb {1}_{A_{3}} \right] \end{align} \]

Let us compute each term separately.

• \(\operatorname {Var}\left[\; \mathbb {1}_{A_{1}}\right] = \mathbb {P}\left(A_1\right) \cdot (1 - \mathbb {P}\left(A_1\right)) = \frac{5}{9} \cdot \frac{4}{9} = \frac{20}{81}\)

• \(\operatorname {Cov}\left[ \; \mathbb {1}_{A_{1}}, \; \mathbb {1}_{A_{2}} \right] = \mathbb {E}\left[\; \mathbb {1}_{A_{1}, \; A_{2}}\right] -\mathbb {E}\left[\; \mathbb {1}_{A_{1}}\right]\mathbb {E}\left[\; \mathbb {1}_{A_2}\right] = \mathbb {E}\left[\; \mathbb {1}_{A_{1}, \; A_{2}}\right] - \left(\frac{5}{9}\right)^2\). We have

  \[ \begin{align} \mathbb {E}\left[\; \mathbb {1}_{A_{1}, \; A_{2}}\right] & = \mathbb {P}\left(\left\{ \omega \; : \; \omega _1 = \omega _3 = 1, \; \omega _2 = 0\right\} \right) + \mathbb {P}\left(\left\{ \omega \; : \; \omega _1 = \omega _3 = 0, \; \omega _2 = 1\right\} \right) = \\ & = \frac{1}{C_9^5} \left(C_6^4 + C_{6}^3\right) = \cdots = \frac{5}{18} \end{align} \]

  Altogether, \(\operatorname {Cov}\left[ \; \mathbb {1}_{A_{1}}, \; \mathbb {1}_{A_{2}} \right] = \frac{5}{18} - \frac{25}{81} = \frac{45 - 50}{162} = -\frac{5}{162}\).

• \(\operatorname {Cov}\left[ \; \mathbb {1}_{A_{1}}, \; \mathbb {1}_{A_{3}} \right] = \mathbb {E}\left[\; \mathbb {1}_{A_{1}, \; A_{3}}\right] -\mathbb {E}\left[\; \mathbb {1}_{A_{1}}\right]\mathbb {E}\left[\; \mathbb {1}_{A_3}\right] = \mathbb {E}\left[\; \mathbb {1}_{A_{1}, \; A_{3}}\right] - \left(\frac{5}{9}\right)^2\). We have

  \[ \begin{align} \mathbb {E}\left[\; \mathbb {1}_{A_{1}, \; A_{3}}\right] & = 4\mathbb {P}\left(\left\{ \omega \; : \; \omega _1 = 1, \; \omega _2 = 0, \; \omega _3 = 1, \; \omega _4 = 0\right\} \right) = 4\frac{C_5^3}{C_9^5} = \cdots = \frac{20}{63} \end{align} \]

  Altogether, \(\operatorname {Cov}\left[ \; \mathbb {1}_{A_{1}}, \; \mathbb {1}_{A_{3}} \right] = \frac{20}{63} - \frac{25}{81} = \frac{180 - 175}{7 \cdot 9^2} = \frac{5}{567}\).

Altogether,

\[ \begin{align} \operatorname {Var}\left[X\right] = 8 \cdot \frac{20}{81} + 2 \cdot 7 \cdot \left(-\frac{5}{162}\right) + 2 \cdot 21 \cdot \frac{5}{567}= \frac{160}{81} - \frac{35}{81} + \frac{30}{81} = \frac{155}{81} \approx 1.91 \end{align} \]

Standard deviation: \(\operatorname {SD}(X) = \sqrt{\operatorname {Var}\left[X\right]} = \frac{\sqrt{155}}{9} \approx 1.38\).

(The answer can be checked by direct enumeration: there are \(C_9^4 = 126\) paths in total, and summing honestly over all of them gives exactly \(\mathbb {E}\left[X\right] = \frac{40}{9}\) and \(\operatorname {Var}\left[X\right] = \frac{155}{81}\).)

AnswerAnswer

Enum-item1.

\(\mathbb {E}\left[X\right] = \frac{40}{9} \approx 4.44\)

Enum-item2.

\(\operatorname {Var}\left[X\right] = \frac{155}{81} \approx 1.91\), \(\operatorname {SD}(X) \approx 1.38\).

ProblemProblem 1

\(N\) guests, each wearing a hat, come to visit. On leaving, in the dark hallway, each of them grabs some hat at random. Find

1. the expectation,

2. the variance and the standard deviation of the number of hats that end up with their rightful owners.

HintHint

Use the indicator method.

3 Convergence of random variables

The limit theorems that motivate this chapter (the LLN, the CLT, the law of rare events — see the next section) involve two types of convergence for sequences of random variables: convergence in probability and convergence in distribution. Let us define them using only the tools already available to us: probabilities of events and distribution functions.

3.1 Convergence in probability

Definition 2 Let \(\xi , \xi_1, \xi_2, \ldots\) be random variables defined on the same probability space. The sequence \(\xi_1, \xi_2, \ldots\) is said to converge in probability to \(\xi\) if for every \(\varepsilon > 0\) \[ \mathbb {P}\left(\left|\xi _n - \xi \right| \geq \varepsilon \right) \xrightarrow [n \to \infty ]{} 0 \] Notation: \[ \xi _n \xrightarrow [n \to \infty ]{\mathbb {P}} \xi \]

Intuition: as \(n\) grows, the random variable \(\xi_n\) deviates from \(\xi\) by more than any fixed error \(\varepsilon\) less and less often. This is exactly the convergence that appears in the LLN: the sample mean \(\frac{S_n}{n}\) converges in probability to the expectation.

Note: for the expression \(\left|\xi_n - \xi \right|\) to make sense, the random variables \(\xi_n\) and \(\xi\) must be defined on the same \(\Omega\).

ProblemProblem 2

Is it true that convergence in probability implies convergence of expectations?

ProblemProblem 3

Let \(\left(\xi_{n}-\xi \right)^{2} \xrightarrow {\mathbb {P}} 0\). Show that \(\xi_{n}^{2} \xrightarrow {\mathbb {P}} \xi^{2}\).

3.2 Convergence in distribution

The second type of convergence answers a different question: not “are the values of \(\xi_n\) and \(\xi\) close as functions on \(\Omega\)”, but “does the distribution of \(\xi_n\) resemble the distribution of \(\xi\)”. Thus the CLT asserts that the distribution of a normalized sum approaches the normal distribution; the random variables themselves do not “approach” any particular random variable — it is their distributions that converge.

A distribution on \(\mathbb {R}\) is completely described by its distribution function (see the chapter on random variables and distribution functions), so it is natural to define convergence of distributions via convergence of distribution functions. The only subtlety is at which points to require convergence. Consider an example: let \(\xi_n \equiv \frac{1}{n}\) be constant random variables. It is reasonable to expect that \(\xi_n\) converges (in any sensible sense) to \(\xi \equiv 0\). Let us look at the distribution functions:

\[ F_{\xi _n}(x) = \; \mathbb {1}_{x \geq \tfrac {1}{n}} \xrightarrow [n \to \infty ]{} \begin{cases} 1, & x > 0 \\ 0, & x \leq 0\end{cases}, \qquad \text{while} \qquad F_{\xi }(x) = \; \mathbb {1}_{x \geq 0} \]

The limits agree everywhere except at the single point \(x = 0\): \(F_{\xi_n}(0) = 0 \not\to 1 = F_{\xi }(0)\). Note that \(x=0\) is precisely the discontinuity (jump) point of the limiting distribution function. To prevent such natural examples from breaking the definition, convergence is not required at discontinuity points of the limiting \(F\).

Definition 3 A sequence of random variables \(\xi_1, \xi_2, \ldots\) is said to converge in distribution to a random variable \(\xi\) if \[ F_{\xi _n}(x) \xrightarrow [n \to \infty ]{} F_{\xi }(x) \qquad \text{for all } x \in \mathbb {R} \text{ at which } F_{\xi } \text{ is continuous} \] Notation: \[ \xi _{n} \xrightarrow [n \to \infty ]{d} \xi , \] from the English distribution.

Since only distribution functions appear in the definition, the random variables \(\xi_1, \xi_2, \ldots\) and \(\xi\) may be defined on entirely different probability spaces — unlike convergence in probability. For the same reason, instead of naming a limiting random variable one may specify the limiting distribution directly and write, for example, \(\xi_n \xrightarrow [n \to \infty ]{d} \mathscr {N}\left(0, 1\right)\) (which is exactly what we will do in the CLT).

ProblemProblem 4

Is it true that convergence in distribution implies convergence of expectations? That is, \[ \xi _n \xrightarrow [n \to \infty ]{d} \xi \quad \stackrel{?}{\; \Rightarrow \; } \quad \mathbb {E}\left[\xi _n\right] \xrightarrow [n \to \infty ]{} \mathbb {E}\left[\xi \right] \] Prove it if it is true. If it is false, give a counterexample.

HintHint

Take \(\xi\) to be the constant zero: \(\xi \equiv 0\). Check whether convergence \(\mathbb {E}\left[\xi_n\right] \to 0\) is guaranteed in this case.

ProblemProblem 5

Let \(\xi_n\) be uniformly distributed on \(\{ 1,2,\dots ,n\}\): \(\xi_n \sim \operatorname {Unif}\left\{ 1,\ldots ,n\right\}\). Let \(\eta_n = \frac{\xi_n}{n}\). Does the sequence \(\eta_1, \eta_2, \ldots\) converge in distribution?

3.3 The relationship between the two convergences

Lemma 1 Let \(\xi , \xi_1, \xi_2, \ldots\) be random variables on the same probability space. Then \[ \xi _n \xrightarrow [n \to \infty ]{\mathbb {P}} \xi \quad \; \Rightarrow \; \quad \xi _n \xrightarrow [n \to \infty ]{d} \xi \] The converse is false in general (see the problems below). However, if the limit is a constant \(c \in \mathbb {R}\) (more precisely, a random variable identically equal to \(c\)), then the two convergences are equivalent: \[ \xi _n \xrightarrow [n \to \infty ]{\mathbb {P}} c \quad \iff \quad \xi _n \xrightarrow [n \to \infty ]{d} c \]

ExampleExample 3

Prove the \(\Leftarrow\) direction of the second part of the lemma: if \(\xi_n \xrightarrow [n \to \infty ]{d} c\), then \(\xi_n \xrightarrow [n \to \infty ]{\mathbb {P}} c\).

SolutionSolution

The distribution function of the constant: \(F_c(x) = \; \mathbb {1}_{x \geq c}\). It is continuous at every point except \(x = c\). Let \(\varepsilon > 0\) be arbitrary. The points \(c - \varepsilon\) and \(c + \frac{\varepsilon }{2}\) are different from \(c\), i.e., they are points of continuity of \(F_c\), so convergence of distribution functions holds at them. We have \[ \begin{align} \mathbb {P}\left(\left|\xi _n - c\right| \geq \varepsilon \right) & = \mathbb {P}\left(\xi _n \leq c - \varepsilon \right) + \mathbb {P}\left(\xi _n \geq c + \varepsilon \right) \leq F_{\xi _n}(c-\varepsilon ) + 1 - F_{\xi _n}\left(c + \tfrac {\varepsilon }{2}\right) \xrightarrow [n \to \infty ]{} \\ & \xrightarrow [n \to \infty ]{} F_c(c - \varepsilon ) + 1 - F_c\left(c + \tfrac {\varepsilon }{2}\right) = 0 + 1 - 1 = 0 \end{align} \] Explanation of the inequality: \(\mathbb {P}\left(\xi_n \geq c + \varepsilon \right) \leq \mathbb {P}\left(\xi_n > c + \frac{\varepsilon }{2}\right) = 1 - F_{\xi_n}\left(c + \frac{\varepsilon }{2}\right)\). This completes the proof.

ProblemProblem 6

Let \(\xi_n \sim \mathrm{Ber}\! \left(\tfrac {1}{n}\right)\). Does the sequence \(\xi_1, \xi_2, \ldots\) converge in distribution (to some random variable)? What about in probability?

ProblemProblem 7

Let \(\Omega = \left\{ \omega_1, \omega_2, \omega_3\right\}\) with the classical (uniform) probability (\(\mathbb {P}\left(\omega_i\right) = \frac{1}{3}\)). Define random variables \(X\), \(Y\):

	\(\omega _1\)	\(\omega _2\)	\(\omega _3\)
\(X\)	\(1\)	\(0\)	\(0\)
\(Y\)	\(0\)	\(1\)	\(0\)

Let \(\xi_{2n-1} = X\), \(\xi_{2n} = Y\) for \(n \in \mathbb {N}\). Does the sequence \(\xi_1, \xi_2, \ldots\) converge in distribution (to some random variable)? What about in probability?

3.4 A look ahead: convergence in the language of measures (optional)

Convergence of distributions as measures, weak convergence. The definition of convergence in distribution via distribution functions is workable, but appears tied to the real line \(\mathbb {R}\): in \(\mathbb {R}^{n}\), and even more so in infinite-dimensional spaces, there is no distribution function in the familiar sense, yet convergence of distributions still needs to be defined. The “correct” definition is formulated in the language of the distributions themselves, i.e., of probability measures, and relies on concepts that we will introduce rigorously only in the chapters on systems of sets and the Borel sigma-algebra–on Lebesgue measure (Borel sets, measure on a sigma-algebra). This subsection is an optional preview: on a first reading it can be skipped and revisited after the chapters on measure theory.

Suppose we have a sequence of distributions (probability measures) \(\mathbf{P}_1, \mathbf{P}_2, \ldots\) on \((\mathbb {R}, \mathscr {B}\left(\mathbb {R}\right))\). This sequence is said to converge strongly (or converge setwise, i.e., converge on every set) to a distribution \(\mathbf{P}\) if

\[ \mathbf{P}_{n}\left(B\right) \xrightarrow [n \to \infty ]{} \mathbf{P}\left(B\right), \quad \forall B \in \mathscr {B}\left(\mathbb {R}\right) \]

Notation:

\[ \mathbf{P}_n \xrightarrow [n \to \infty ]{s} \mathbf{P}, \]

from the English strong.

Strong convergence is not very convenient. For example, if \(\mathbf{P}_n = \delta_{1/n}\), i.e., unit point masses at \(\frac{1}{n}\), then this sequence does not converge strongly to anything, and in particular it does not converge to \(\delta_0\). Indeed, taking \(B = \left\{ 0\right\}\) gives

\[ \delta _{1/n}(\left\{ 0\right\} ) = 0 \not\to 1 = \delta _{0}(\left\{ 0\right\} ) \]

as \(n \to \infty\). (Compare with the example \(\xi_n \equiv \frac{1}{n}\) above: these are the very same distributions!) For this reason one introduces weak convergence. The sequence \(\mathbf{P}_1, \mathbf{P}_2, \ldots\) is said to converge weakly to \(\mathbf{P}\) if

\[ \mathbf{P}_{n}\left(B\right) \xrightarrow [n \to \infty ]{} \mathbf{P}\left(B\right), \quad \forall B \in \mathscr {B}\left(\mathbb {R}\right), \; \mathbf{P}\left(\partial B\right) = 0 \]

The difference from strong convergence is that now we only need to check convergence not on all Borel sets, but on the so-called continuity sets for \(\mathbf{P}\), i.e., sets whose boundary has limiting measure \(0\). Notation:

\[ \mathbf{P}_n \xrightarrow [n \to \infty ]{w} \mathbf{P}, \]

from the English weak.

ProblemProblem 8

Prove that \[ \delta _{1/n} \xrightarrow [n \to \infty ]{w} \delta _0 \]

Theorem 1 (Equivalent formulations of weak convergence, without proof) The following conditions are equivalent:

• \(\mathbf{P}_{n} \xrightarrow [n \to \infty ]{w} \mathbf{P}\);

• \(\int f \; \mathrm{d}\mathbf{P}_n \to \int f \; \mathrm{d} \mathbf{P}\) for every continuous, bounded function \(f: \mathbb {R} \to \mathbb {R}\);

• \(F_{\mathbf{P}_n}(x) \to F_{\mathbf{P}}(x)\) for every point \(x \in \mathbb {R}\) at which \(F_{\mathbf{P}}\) is continuous.

The integrals in the second item are Lebesgue integrals with respect to the measures \(\mathbf{P}_n\), \(\mathbf{P}\); we will construct these in the chapter on the construction of the Lebesgue integral. Note the third item: it is exactly this condition that we adopted above as the definition of convergence in distribution. That is, our “elementary” convergence via distribution functions is precisely weak convergence of distributions:

\[ \xi _{n} \xrightarrow [n \to \infty ]{d} \xi \quad \iff \quad \mathbf{P}_{\xi _n} \xrightarrow [n \to \infty ]{w} \mathbf{P}_{\xi } \]

In terms of random variables, the theorem above can be rewritten as follows.

Theorem 2 (Equivalent formulations of convergence in distribution, without proof) The following conditions are equivalent:

• \(\xi_{n} \xrightarrow [n \to \infty ]{d} \xi\);

• \(\mathbb {E}\left[f(\xi_n)\right] \to \mathbb {E}\left[f(\xi )\right]\) for every continuous, bounded function \(f: \mathbb {R} \to \mathbb {R}\);

• \(F_{\xi_n}(x) \to F_{\xi }(x)\) for every point \(x \in \mathbb {R}\) at which \(F_{\xi }\) is continuous.

4 Limit theorems

4.1 The Law of Large Numbers

Let \(\xi_1, \xi_2, \ldots\) be independent and identically distributed random variables (i.i.d. for short) with expectation \(\mu := \mathbb {E}\left[\xi_1\right]\). The Law of Large Numbers (LLN) governs the convergence of their sample mean \(\frac{S_n}{n}\) to \(\mu\), where \(S_n = \xi_1 + \ldots + \xi_n\).

There are many different versions of the LLN. We will state the LLN in its simplest form.

Theorem 3 (LLN) Let \(X_1, X_2, \ldots\) be i.i.d. with finite second moment (i.e., the variance \(\operatorname {Var}\left[X_1\right] = \sigma^2 < \infty\) exists), and let \(\mu := \mathbb {E}\left[X_1\right]\). Then \[ \frac{1}{n}S_n \xrightarrow [n \to \infty ]{d, \mathbb {P}} \mu . \]

Honesty status: we will now prove the LLN fully rigorously — with the caveat that the properties of expectation and variance used in the proof (linearity, variance of a sum of independent variables) have so far been justified only for discrete distributions (see debt @debt:expectation). After the chapter on properties of the Lebesgue integral, the proof will become honest in full generality — without a single line of it changing.

For the proof we will need the following well-known bounds.

Theorem 4 (Markov’s inequality) Let \(Y \geq 0\) and \(\mathbb {E}\left[Y\right] < \infty\). Then for every \(a > 0\) \[ \mathbb {P}(Y \geq a) \leq \frac{\mathbb {E}\left[Y\right]}{a}. \]

Theorem 5 (Chebyshev’s inequality) Let \(Y\) have finite expectation \(\mu\) and variance \(\sigma^2\). Then for every \(\varepsilon > 0\) \[ \mathbb {P}\big(|Y - \mu | \geq \varepsilon \big) \leq \frac{\sigma ^2}{\varepsilon ^2}. \]

Both inequalities will be proved in full generality in the chapter on properties of the Lebesgue integral, once expectation becomes a Lebesgue integral. For discrete random variables, however, everything can already be proved now.

ProblemProblem 9

Prove Markov’s inequality for a discrete random variable \(Y \geq 0\). Then derive Chebyshev’s inequality from it by applying Markov’s inequality to the random variable \((Y - \mu )^2\).

Mn-proofProof

4.2 Proof of the LLN

Consider \(\frac{1}{n}S_n = \frac{1}{n}\sum_{k=1}^n X_k\). By linearity of expectation, \[ \mathbb {E}\left[\frac{1}{n}S_n\right] = \mu . \] Let us find the variance: \[ \operatorname {Var}\left[\frac{1}{n}S_n\right] = \frac{1}{n^2}\operatorname {Var}\left[\sum _{k=1}^n X_k\right] \] Since the \(X_k\) are independent and identically distributed, \[ \operatorname {Var}\left[\sum _{k=1}^n X_k\right] = n \cdot \operatorname {Var}\left[X_1\right] = n\sigma ^2. \] Hence, \[ \operatorname {Var}\left[\frac{1}{n}S_n\right] = \frac{\sigma ^2}{n}. \] By Chebyshev’s inequality, for every \(\varepsilon > 0\): \[ \mathbb {P}\! \left(\left|\frac{1}{n}S_n - \mu \right| \geq \varepsilon \right) \leq \frac{\operatorname {Var}\left[\frac{1}{n}S_n\right]}{\varepsilon ^2} = \frac{1}{n^2} \cdot \frac{\operatorname {Var}\left[S_n\right]}{\varepsilon ^2} = \frac{1}{n^2} \cdot \frac{n \sigma ^2}{\varepsilon ^2} = \frac{\sigma ^2}{n\varepsilon ^2}. \] The right-hand side tends to \(0\) as \(n \to \infty\), whence \[ \frac{1}{n}S_n \xrightarrow {\mathbb {P}} \mu . \] Since the limit is a constant, we also have convergence in distribution. This proves the theorem.

Note that some of the conditions in the LLN can be relaxed.

• Independence can be replaced by uncorrelatedness. Indeed, independence was needed only to write the variance of the sum as the sum of the variances. For this, pairwise uncorrelatedness suffices.

• Instead of identical distribution, it suffices to require that

  • the expectations converge to some constant \(\mu\): \(\mathbb {E}\left[X_n\right] \to \mu\) as \(n \to \infty\)

  • the variances are uniformly bounded: there exists \(M > 0\) such that \(\operatorname {Var}\left[X_n\right] \leq M\) for all \(n \in \mathbb {N}\)

  (check for yourself that this is indeed sufficient)

• If the LLN is stated as

  \[ \frac{1}{n} \left(S_n - \mathbb {E}\left[S_n\right]\right) \xrightarrow [n \to \infty ]{d,\mathbb {P}} 0 \]

  then \(\frac{1}{n}\) can be replaced by \(\frac{1}{n^{\alpha }}\) for any \(\alpha > 0.5\).

Theorem 6 (LLN, a more general formulation) Let \(X_1, X_2, \ldots\) be uncorrelated random variables with finite second moment. Suppose the variances are uniformly bounded: there exists \(M > 0\) such that \(\operatorname {Var}\left[X_i\right] \leq M\) for all \(i\). Then \[ \frac{1}{n^\alpha }\left(S_n - \mathbb {E}\left[S_n\right]\right) \xrightarrow [n \to \infty ]{d, \mathbb {P}} 0 \] for an arbitrary \(\alpha > 0.5\).

Mn-proofProof

Let \(Y_i = X_i - \mathbb {E}\left[X_i\right]\). Then \(\mathbb {E}\left[Y_i\right] = 0\), \(\operatorname {Var}\left[Y_i\right] = \operatorname {Var}\left[X_i\right]\), \[ S_n - \mathbb {E}\left[S_n\right] = \sum _{i=1}^n X_i - \mathbb {E}\left[\sum _{i=1}^n X_i \right] = \sum _{i=1}^n Y_i \] Next, by Chebyshev’s inequality, \[ \begin{align} \mathbb {P}\left(\left|\frac{1}{n^{\alpha }}\left(S_n - \mathbb {E}\left[S_n\right]\right) \right| > \varepsilon \right) & = \mathbb {P}\left(\left|\frac{1}{n^{\alpha }}\sum _{i=1}^n Y_i\right| > \varepsilon \right) \leq \frac{1}{n^{2\alpha }} \cdot \frac{\operatorname {Var}\left[\sum _{1}^n Y_i\right]}{\varepsilon ^2} = \frac{1}{n^{2\alpha }} \cdot \frac{\sum _{1}^n\operatorname {Var}\left[ Y_i\right]}{\varepsilon ^2} \leq \\ & \leq \frac{M}{n^{2\alpha - 1} \varepsilon ^2} \to 0 \end{align} \] The variance of the sum decomposed into the sum of the variances thanks to uncorrelatedness.

ProblemProblem 10

Let the random variable \(\eta_{n}\) be the sum of the points rolled in \(n\) throws of a fair die. Find the limit in probability of \(\frac{\eta_{n}}{n}\).

ProblemProblem 11

For independent random variables \(\xi_{1}, \xi_{2}, \ldots \sim \operatorname {Bern}(p)\), let \(\eta_{n}\) denote the number of indices \(i\) from 1 to \(n\) such that \(\xi_{i} = \xi_{i+1} = 1\). Find the limit in probability of \(\frac{\eta_{n}}{n}\).

ProblemProblem 12

The random variables \(\xi_{1}, \xi_{2}, \ldots\) are independent, \(\mathbb {E}\left[\xi_{k}\right] = a, \operatorname {Var}\left[\xi_{k}\right] = \sigma^{2} < \infty , k \in \mathbb {N}\). Let \[ \zeta _{n} = \sum _{1 \leqslant i < j \leqslant n} \xi _{i} \xi _{j} . \] Find the limit in probability of \(\frac{\zeta_{n}}{n^{2}}\).

ProblemProblem 13

The sequence \(\xi_{1}, \xi_{2}, \ldots\) consists of independent and identically distributed random variables, \(\mathbb {E}\left[\xi_{n}\right] = 0, \operatorname {Var}\left[\xi_{n}\right] = \sigma^{2} < \infty , n \in \mathbb {N}\). Do the following sequences of random variables satisfy the LLN?

1. \(\zeta_{n} = \xi_{n}+\xi_{n+1}\)?

2. \(\eta_{n} = \sum_{k = 0}^{\left[n^{\frac{1}{3}}\right]} \xi_{n+k}\)?

ProblemProblem 14

The sequence \(\xi_{1}, \xi_{2}, \ldots\) is formed by independent random variables with \[ \mathbb {E}\left[\xi _{n}\right] = 0, \quad \operatorname {Var}\left[\xi _{n}\right] = C \cdot n^{\alpha }, \quad C > 0, \quad \alpha \geqslant 0, \quad n \in \mathbb {N} . \] For which values of \(\alpha\) does the sequence \(\xi_{1}, \xi_{2}, \ldots\) satisfy the LLN, and for which values of \(\alpha\) might it fail to?

4.3 The Central Limit Theorem

Theorem 7 Let \(X_1, X_2, \ldots\) be square-integrable i.i.d. random variables. Let \(\mu = \mathbb {E}\left[X_1\right]\), \(\sigma^2 = \operatorname {Var}\left[X_1\right]\). Then \[ \frac{S_n - n\mu }{\sqrt{n}\sigma } \xrightarrow [n \to \infty ]{d} \mathscr {N}\left(0, 1\right) \]

Let us center and normalize \(X_i\): \(Y_i := \frac{X_i - \mu }{\sigma }\) (so that \(\mathbb {E}\left[Y_i\right] = 0\), \(\operatorname {Var}\left[Y_i\right] = 1\)). Then for \(\tilde{S}_n = Y_1 + \ldots + Y_n\) the CLT takes the form:

\[ \frac{\tilde{S}_n}{\sqrt{n}} \xrightarrow [n \to \infty ]{d} \mathscr {N}\left(0, 1\right) \]

The difference between the CLT and the LLN is that in the LLN the sum \(S_n\) is scaled by \(n\), whereas in the CLT it is scaled by \(\sqrt{n}\).

Honesty status: we accept the CLT without proof, and this debt will be repaid not in our course, but in the next one — the probability theory course. The standard proof uses the machinery of characteristic functions, which is itself built on the Lebesgue integral (chapter on the construction of the Lebesgue integral) of complex-valued functions. Here the CLT serves as a showcase for us: it demonstrates the results for whose sake the entire machinery of the second part of the course is being built. Note also that the limiting object — the normal distribution \(\mathscr {N}\left(0, 1\right)\) — is a distribution with a density, so we will only be able to define it rigorously after constructing the integral (see debt @debt:densities); for now we understand \(\Phi (x)\) as “the area under the Gaussian bell curve from \(-\infty\) to \(x\)” in the sense of the Riemann integral.

Informally: if we are given a sequence of i.i.d. random variables \(X_1,X_2, \ldots\) with expectation \(\mu\) and variance \(\sigma^2\), then

\[ \operatorname {Law}(S_n) = \mathbf{P}_{S_n} \approx \mathscr {N}\left(n\mu , n\sigma ^2\right) \]

where \(\operatorname {Law}(S_n)\), \(\mathbf{P}_{S_n}\) are different notations for the distribution of \(S_n = X_1 + X_2 + \ldots + X_n\).

ExampleExample 4

Using sampling with replacement, \(10000\) random digits are drawn. Find the approximate probability that the number of nines drawn is between \(940\) and \(1060\).

SolutionSolution

Consider \(n=10000\) independent random variables \(\xi_{1}, \ldots , \xi_{n}\), Bernoulli-distributed with parameter \(0.1\). We have \(\mathbb {E}\left[\xi_1\right] = \mu = \frac{1}{10}\), \(\operatorname {Var}\left[\xi_1\right]= \sigma^2 = \frac{9}{100}\). By the CLT:

\[ \frac{S_n - n\mu }{\sqrt{n}\sigma } = \frac{S_{10000} - 1000}{30} \stackrel{d}{\approx } \mathscr {N}\left(0, 1\right) \]

Hence,

\[ \begin{align} \mathbb {P}\left(940 \leq S_{10000} \leq 1060\right) = \mathbb {P}\left(-2 \leq \frac{S_{10000} - 1000}{30} \leq 2\right) \approx \mathbb {P}\left(-2 \leq \eta \leq 2\right) = \Phi (2) - \Phi (-2) , \end{align} \]

where \(\eta \sim \mathscr {N}\left(0, 1\right)\), and \(\Phi\) is the distribution function of the standard normal distribution.

Note that since the distribution \(\mathscr {N}\left(0, 1\right)\) is symmetric about zero, \(\Phi (x) + \Phi (-x) = 1\), i.e.,

\[ \Phi (2) - \Phi (-2) =2\Phi (2) - 1. \]

The value of \(\Phi (2)\) can be found, for instance, here. We have \(\Phi (2) \approx 0.97725\), hence \(2\Phi (2) - 1\approx 0.9545 = 95.45\%\).

AnswerAnswer

\(0.9545\).

ProblemProblem 15

You have invited 64 guests to a party. You need to prepare sandwiches. You believe that a guest may need 0, 1, or 2 sandwiches with probabilities \(1/4\), \(1/2\), and \(1/4\) respectively. You assume that the number of sandwiches a guest needs is independent of the appetite of the other guests. How many sandwiches should you prepare to be 95 percent confident that there will be enough for everyone?

ProblemProblem 16

Show that if the independence condition is violated, the CLT may fail to hold.

4.4 The law of rare events

Theorem 8 (The Poisson limit theorem, the law of rare events) Let \(X_1, X_2, \ldots , X_n, \ldots\) be random variables having distribution \(\operatorname {Bin}(n, p_n)\), where as \(n\) grows the success probability decreases at rate \(\frac{1}{n}\): there exists \(\lambda > 0\) such that \(p_n \sim \frac{\lambda }{n}\) as \(n \to \infty\). Equivalently: \(np_n \xrightarrow [n \to \infty ]{} \lambda\). Equivalently: \(\mathbb {E}\left[X_n\right] \xrightarrow [n \to \infty ]{} \lambda\). Then \[ X_n \xrightarrow [n \to \infty ]{d}\operatorname {Pois}(\lambda ) \]

The Poisson theorem in short:

\[ \operatorname {Bin}(n,p_n) \xrightarrow [n \to \infty ]{w} \operatorname {Pois}(\lambda ) \quad \text{ if } \lambda := \lim _{n \to \infty }np_n > 0 \]

Honesty status: unlike the CLT, the law of rare events is fully provable already now, by elementary means — it is the only limit theorem in this chapter with no debts at all.

ProblemProblem 17

Prove the Poisson limit theorem.

HintHint

First prove pointwise convergence of the mass functions: \(\mathbb {P}\left(X_n = k\right) \to \frac{\lambda^k}{k!}e^{-\lambda }\) for each fixed \(k \in \mathbb {Z}_+\). Then explain why, for integer-valued random variables, this implies convergence of the distribution functions at every point.

4.5 CLT vs. LRE

Consider the distribution \(\operatorname {Bin}(n,p)\). In which cases should one use the approximation from the CLT, and in which cases the one from the LRE (law of rare events)? For relatively large \(\lambda := np\) (typically \(\lambda > 9\)), the normal distribution is used to approximate \(\operatorname {Bin}(n,p)\):

\[ \operatorname {Bin}(n,p) \approx \mathscr {N}\left(np, np(1-p)\right) \]

For small \(\lambda = np\) (\(\lambda < 9\)), the Poisson distribution can be used for the approximation:

\[ \operatorname {Bin}(n,p) \approx \operatorname {Pois}(\lambda ) \]

ExampleExample 5

It is known that left-handed people make up on average \(1 \%\) of the population. Estimate the probability that at least four left-handed people are found among

1. \(200\) people;

2. \(10000\) people;

HintHint

Use the CLT or the law of rare events

SolutionSolution

Enum-item1.

\(n = 200\), \(p = 0.01\), \(\lambda = np = 2\). Since \(\lambda\) is small, we use the Poisson approximation:

\[ \mathbf{P}\left\{ S_{200} \geq 4\right\} = 1 - \mathbf{P}\left\{ S_{200} \leq 3\right\} \approx 1 - e^{-2}\left(1 + 2 + \frac{2^2}{2!} + \frac{2^3}{3!}\right) = 1 - e^{-2}(1 + 2 + 2 + 1.\overline{3}) \approx 1 - 0.857 \approx 0.143. \]

Enum-item2.

\(n = 10000\), \(p = 0.01\), \(\lambda = np = 100\). We use the normal approximation:

\[ \mathbf{P}\left\{ S_{10000} \geq 4\right\} \approx 1 - \Phi \left(\frac{4 - 100}{\sqrt{100 \cdot 0.99}}\right) \approx 1 - \Phi (-9.6) \approx 1. \]

ProblemProblem 18

The probability of hitting a target on a single shot is 0.001. At least two hits are needed to destroy the target. 5000 shots are fired. Find the probability that the target is destroyed.

ProblemProblem 19

It is known that the probability of a boy being born is approximately 0.515. What is the probability that among 10 thousand newborns the number of boys is no greater than the number of girls?

5 Summary of three weeks: an inventory of debts

The first three chapters rest on an honest foundation only in part. Wherever the sample space is at most countable, our definitions and proofs are complete. But in the general case we have accumulated debts — and the entire second part of the course will be their systematic repayment:

Debt~ \(\ref{debt:borel-lebesgue}\): what are Borel sets and Lebesgue measure (length, area)? Why can’t sets be measured?	The chapters~ –: systems of sets, measure, Carathéodory’s theorem, Lebesgue measure
Debt~ \(\ref{debt:measurability}\): what is measurability of a random variable?	The chapter~ : measurable functions
Debt~ \(\ref{debt:cdf-defines-distrib}\): why does a distribution function uniquely determine a distribution?	The chapters~ –: Carathéodory’s theorem, Lebesgue–Stieltjes measure
Debt~ \(\ref{debt:densities}\): what are densities and continuous distributions?	The chapters~ – (the Lebesgue integral) and the chapter~ (the Radon–Nikodym theorem)
Debt~ \(\ref{debt:expectation}\): what is \(\mathbb {E}\left[\xi \right]\) for an arbitrary random variable? Why is expectation linear?	The chapters~ –: the Lebesgue integral and its properties (including Markov’s inequality in general form)
Debt~ \(\ref{debt:weak-convergence}\): what is convergence of distributions “for real”, in the language of measures?	The chapters~ – provide the language of measures; convergence of measurable functions is covered in the chapter~
The CLT is accepted without proof	The next course (probability theory): characteristic functions

Starting from the next chapter, we will set probability aside for a while and turn to the foundations: sets that can be measured, and measures on them.