MIT 18.650 — Lectures 1–3

Random Variables and Convergence

§ Preliminaries

First, getting some jargon and preliminary facts out of the way.

When we write $A \sim B$ , we mean $A$ is a random variable distributed as some probability measure $B$ .
- So we can write $X_1, X_2, \dots, X_n \sim \mathcal{N}(0, 1)$ , but not $X \sim Y$ where $Y$ is a random variable.
- We often say samples $X_1, X_2, \dots, X_n \sim \mathbb{P}$ are independent, identically distributed, or i.i.d. for short.
- As shorthand for “ $A$ and $B$ are independent”, we may also write “ $A \perp B$ ”.
Given a random variable $X$ …
- The sample mean is $\bar{X}_n$ , whereas the true (population) mean is $\mu = \mathbb{E}[X]$ .
  - The sample mean $\bar{X}_n := \frac{1}{n}\sum_{i = 1}^n X_i$ (assuming i.i.d. $X_1, X_2, \dots, X_n \sim \mathbb{P}$ ) is itself a random variable!
- The sample variance is $s_n^2$ , whereas the true (population) variance is $\sigma^2 = \mathbb{V}[X]$ .
Some discrete distributions to know…
- $X \sim \text{Ber}(p)$ is a weighted coin flip, with $\Pr(X = 1) = p$ and $\Pr(X = 0) = 1 - p$ .
- $X \sim \text{Bin}(n, p)$ is the sum of $n$ independent trials of $\text{Ber}(p)$ .
- $X \sim \text{Pois}(\lambda)$ is given by $\Pr(X = k) = \frac{\lambda^k e^{-\lambda}}{k!}$ .
Some continuous distributions to know…
- $X \sim \mathcal{U}(a, b)$ is the uniform distribution: all values in $[a, b]$ are equally likely.
- $X \sim \text{Exp}(\lambda)$ is the exponential distribution, with PDF $f(x) = \lambda e^{- \lambda x}$ .
- $X \sim \mathcal{N}(\mu, \sigma^2)$ is the normal distribution, with PDF $f(x) = \frac{1}{\sigma \sqrt{2\pi}} \exp\left(-\frac{(x - \mu)^2}{2\sigma^2}\right)$ .

Theorem. (Linearity) For any random variables $A$ and $B$ , we have $\mathbb{E}[A + B] = \mathbb{E}[A] + \mathbb{E}[B]$ . Furthermore, if $A$ and $B$ are independent, then $\mathbb{V}[A + B] = \mathbb{V}[A] + \mathbb{V}[B]$ .

Remark. If $A$ and $B$ are not independent, a counterexample to the latter of the two statements is $A = B$ , say.

An immediate corollary of the above fact is the following.

Theorem. (Sample Mean Stats) Suppose $X_1, X_2, \dots, X_n \sim \mathbb{P}$ are sampled i.i.d., yielding a sample mean $\bar{X}_n$ . Suppose further that $\mathbb{E}[X_i] = \mu$ and $\mathbb{V}[X_i] = \sigma^2$ . Then $\mathbb{E}[\bar{X}_n] = \mu$ and $\mathbb{V}[\bar{X}_n] = \sigma^2 / n$ .

§ Convergence Definitions

Definition (Convergence in Probability). Given random variables $\{X_n\}_{n = 1}^{\infty}$ and a random variable $X$ , we say “ $X_n$ converges to $X$ in probability” (denoted $X_n \convprob X$ ) if:

For every $\epsilon > 0$ , we have $\Pr(|X_n - X| > \epsilon) \to 0$ as $n \to \infty$ .

Definition (Convergence in Distribution). Given random variables $\{X_n\}_{n = 1}^{\infty}$ and a random variable $X$ , we say “ $X_n$ converges to $X$ in distribution” (denoted $X_n \rightsquigarrow X$ ) if:

For all $x$ where $x \mapsto \Pr(X \leq x)$ is continuous, we have $\Pr(X_n \leq x) \to \Pr(X \leq x)$ as $n \to \infty$ .

Remark. Think of “convergence in distribution” as saying that the CDFs of $X_n$ and $X$ get sufficiently close together.

Example. Consider independent $X_n \sim \text{Ber}(\frac{1}{2})$ and $X \sim \text{Ber}(\frac{1}{2})$ . Then $X_n \rightsquigarrow X$ is true, but $X_n \convprob X$ is not.

Expectedly, convergence in distribution is much less strict than convergence in probability. Here's a not-completely-obvious theorem.

Theorem. (Relationship Between Convergence) If $X_n \convprob X$ , then $X_n \rightsquigarrow X$ .

Remark. Convergence in probability is possible… but it's really uncommon.

Example. Consider $X_1, X_2, \dots \overset{\text{i.i.d.}}{\sim} \mathcal{U}(0, 1)$ , and define $M_n = \max(X_1, \dots, X_n)$ . Then $M_n \convprob 1$ .
Example. Consider $U \sim \mathcal{U}(0, 1)$ , and define $X_n = U + \frac{1}{n}$ . Then $X_n \convprob U$ .

These examples feel kind of hacky, though—and it turns out, they have to be!

Fact. If $X_n \perp X$ for all $n$ and $X_n \convprob X$ , then $\Pr(X = c) = 1$ for some constant $c$ .

This isn't explicitly in the 18.650 curriculum, but we'll prove it later anyway, once we learn what we need to do so.

Here's a completely-obvious theorem.

Theorem. (Convergence to Constant) We have $X_n \convprob c$ if and only if $X_n \rightsquigarrow c$ .

§ LLN and CLT

Theorem. (Weak Law of Large Numbers) Consider i.i.d. random variables $X_1, X_2, \dots$ satisfying $\mathbb{E}[X_i] = \mu$ . Then their sample mean $\bar{X}_n$ converges in probability to $\mu$ ; that is, $\bar{X}_n \convprob \mu$ .

Proof: Chebyshev's, assuming finite variance; the point is that $\mathbb{V}[\bar{X}_n] \to 0$ as $n \to \infty$ . $\blacksquare$

Remark. The “Strong Law of Large Numbers” roughly says, more strongly, that $\Pr(\lim_{n \to \infty} \bar{X}_n = \mu) = 1$ .

Theorem. (Central Limit Theorem) Given $\{X_i\}_{i = 1}^n$ i.i.d. with mean $\mu$ and variance $\sigma^2$ , we have:

\dfrac{\sqrt{n}}{\sigma}(\bar{X}_n - \mu) \rightsquigarrow \mathcal{N}(0, 1), ~ \text{ or equivalently (hand-waving), } ~ \bar{X}_n \approx \mathcal{N}\left(\mu, \dfrac{\sigma^2}{n}\right).

Remark. We use some shorthand here: $X \rightsquigarrow \mathbb{P}$ is short for $X \rightsquigarrow Y \sim \mathbb{P}$ .

You can at least sanity-check CLT; the $\mathbb{E}$ and $\mathbb{V}$ clearly match. But the proof is very nontrivial.

§ Convergence Properties

The former of these two bullets is not hard to prove; the latter is pretty hard.

Theorem. (Convergence of Sums and Products) Consider $\{X_n\}_{n = 1}^{\infty}$ , $\{Y_n\}_{n = 1}^{\infty}$ , $X$ , and $Y$ random variables.

If $X_n \convprob X$ and $Y_n \convprob Y$ , then $X_n + Y_n \convprob X + Y$ and $X_nY_n \convprob XY$ .
(Slutsky's Theorem) If $X_n \rightsquigarrow X$ and $Y_n \convprob c$ , then $X_n + Y_n \rightsquigarrow X + c$ , and $X_n Y_n \rightsquigarrow Xc$ .

Remark. Consider the following false statement.

If $X_n \rightsquigarrow X$ and $Y_n \rightsquigarrow Y$ , then $X_n + Y_n \rightsquigarrow X + Y$ .

A counterexample is $X_n, X, Y \sim \mathcal{N}(0, 1)$ with $X \perp Y$ , and $Y_n = -X_n$ .

To prove things about convergence, it helps to know the following fact.

Theorem. (Continuous Mapping Theorem) If $X_n \convprob X$ , then $g(X_n) \convprob g(X)$ for any continuous function $g$ . Similarly, if $X_n \rightsquigarrow X$ , then $g(X_n) \rightsquigarrow g(X)$ .

§ The Delta Method

This lets us justify the so-called “Delta method”.

Theorem. (Delta Method) Consider a sequence of random variables $Y_n$ such that $\frac{\sqrt{n}}{\sigma}(Y_n - \mu) \rightsquigarrow Y \sim \mathcal{N}(0, 1)$ . Then for any differentiable $g$ such that $g'(\mu) \neq 0$ , we have:

\dfrac{\sqrt{n}}{\sigma} \left(g(Y_n) - g(\mu)\right) \rightsquigarrow \mathcal{N}(0, g'(\mu)^2).

(Naturally, you should think to use the Delta method for $Y_n = \bar{X}_n$ .)

More intuitively, the Delta method is just the CLT with a $g$ attached; when $g(x) = x$ , the Delta method is the CLT verbatim.

Proof: Just Taylor expand $g$ around $\mu$ .

\dfrac{\sqrt{n}}{\sigma} \left(g(Y_n) - g(\mu)\right) = g'(\mu)\left[\dfrac{\sqrt{n}}{\sigma}(Y_n - \mu)\right] + \dfrac{\sqrt{n}}{\sigma}R_n.

The first term, by CLT, converges ( $\rightsquigarrow$ ) to $\mathcal{N}(0, g'(\mu)^2)$ . The second term converges ( $\convprob$ ) to $0$ . $\blacksquare$

§ Applying Convergence Theorems

Here's the set-up.

Set-Up. Someone claims Harvard grads have a mean salary of below $120$ K. To test this, you collect $X_1, X_2, \dots, X_{100}$ salaries (i.i.d.) and find that $\bar{X}_n = 121$ K and $\hat{\sigma} = 0.3$ K (in thousands).

You'd like to say $\bar{X}_n \approx \mathcal{N}(120, 0.3^2/100)$ ; this would let you compute $\Pr(\bar{X}_n \geq 121)$ using the normal distribution.

But the CLT doesn't immediately apply here—the true standard deviation isn't known to be $\hat{\sigma}$ . What now?

Remark. As a reminder, the sample standard deviation $\hat{\sigma}$ is the same as $\sqrt{s_n^2}$ , where $s_n^2$ is the sample variance.

The point is that Slutsky's Theorem lets us say $\bar{X}_n \approx \mathcal{N}(120, 0.3^2/100)$ anyway, even though we don't know the exact value of $\sigma$ .

Theorem. (Sample Variance is Unbiased) We have $\mathbb{E}[s_n^2] = \sigma^2$ , where $s_n^2 := \frac{1}{n - 1} \sum_{i = 1}^n (X_i - \bar{X}_n)^2$ is the sample variance.

Proof: Just expand everything and apply linearity. The details look like this:

\begin{align*}\mathbb{E}\left[\sum_{i = 1}^n (X_i - \bar{X}_n)^2\right] & = \mathbb{E}\left[ \sum_{i = 1}^n (X_i - \mu)^2 \right] - \mathbb{E}\left[2(\bar{X}_n - \mu)\sum_{i = 1}^n (X_i - \mu) - n(\bar{X}_n - \mu)^2\right] \\ & = \underbrace{\mathbb{E}\left[ \sum_{i = 1}^n (X_i - \mu)^2 \right]}_{n \sigma^2} - \underbrace{\mathbb{E}\left[n(\bar{X}_n - \mu)^2\right]}_{n\left(\frac{\sigma^2}{n}\right)} = (n - 1)\sigma^2.\end{align*}

And that's why the sample variance has a $\frac{1}{n - 1}$ factor; if it were $\frac{1}{n}$ , it would no longer be unbiased! $\blacksquare$

Unbiasedness alone says nothing about large $n$ , so we need one more fact.

Theorem. (Sample Variance is Consistent) Assuming $\sigma^2 < \infty$ , we have $s_n^2 \convprob \sigma^2$ .

Proof: The Law of Large Numbers doesn't apply to $s_n^2$ as written, since $s_n^2$ is not the mean of i.i.d. sampled random variables. Let's rewrite $s_n^2$ to fix that.

s_n^2 = \frac{1}{n - 1} \left[ \sum_{i = 1}^n (X_i - \bar{X}_n)^2 \right] = \frac{1}{n - 1} \left[ \left(\sum_{i = 1}^n X_i^2\right) - n \cdot \bar{X}_n^2 \right] = \frac{n}{n - 1} \left[ \left(\frac{1}{n}\sum_{i = 1}^n X_i^2\right) - \bar{X}_n^2 \right].

Now the Law of Large Numbers does apply, twice:

The $X_i^2$ are i.i.d. with finite mean $\sigma^2 + \mu^2$ , so the LLN says $\frac{1}{n}\sum_{i = 1}^n X_i^2 \convprob \mathbb{E}[X_1^2]$ .
The LLN says $\bar{X}_n \convprob \mu$ . Then the Continuous Mapping Theorem (with $g(x) = x^2$ ) gives $\bar{X}_n^2 \convprob \mu^2$ .

Convergence of Sums then handles the bracketed part of $s_n^2$ .

\left(\frac{1}{n}\sum_{i = 1}^n X_i^2\right) - \bar{X}_n^2 \convprob \mathbb{E}[X_1^2] - \mu^2 = \sigma^2.

As for the leftover $\frac{n}{n - 1}$ factor, note that $\frac{n}{n - 1} \convprob 1$ , so convergence of products yields $s_n^2 \convprob 1 \cdot \sigma^2 = \sigma^2$ , as desired. $\blacksquare$

With the above, we can justify $\bar{X}_n \approx \mathcal{N}(120, 0.3^2/100)$ as follows:

By consistency of the sample variance, $s_n^2 \convprob \sigma^2$ .
Then the Continuous Mapping Theorem (with $g(x) = \sqrt{x}$ ) gives $\hat{\sigma} \convprob \sigma$ . In other words, $\frac{\sigma}{\hat{\sigma}} \convprob 1$ .
Also, the Central Limit Theorem tells us $\frac{\sqrt{n}}{\sigma} (\bar{X}_n - \mu) \rightsquigarrow \mathcal{N}(0, 1)$ .
Applying Slutsky's Theorem on points 2 and 3 yields $\frac{\sqrt{n}}{\hat{\sigma}} (\bar{X}_n - \mu) \rightsquigarrow \mathcal{N}(0, 1)$ , done!

§ Convergence in Probability is Hard

To close things off, let's prove that not-in-18.650-curriculum fact from earlier.

Theorem. (Convergence in Probability is Hard) If $X_n \perp X$ for all $n$ and $X_n \convprob X$ , then $\Pr(X = c) = 1$ for some constant $c$ .

Proof: We may assume $X_n$ and $X$ are bounded; if they're not, just replace them with $\tan^{-1}(X_n)$ and $\tan^{-1}(X)$ , legal by the Continuous Mapping Theorem. Then the independence yields:

\mathbb{E}[X^2] \leftarrow \mathbb{E}[X_n \cdot X] = \mathbb{E}[X_n] \cdot \mathbb{E}[X] \rightarrow \mathbb{E}[X]^2.

Letting $n \to \infty$ , we get $\mathbb{E}[X^2] = \mathbb{E}[X]^2$ , or $\mathbb{V}[X] = 0$ , which implies $X$ is almost surely constant. $\blacksquare$

Remark. The convergence in probability—not true in convergence in distribution—comes from the step $X_n \cdot X \convprob X^2$ .