Theory

Theory 1

Video by 3Blue1Brown:

• Central limit theorem

IID variables

Random variables are called independent, identically distributed when they are independent and have the same distribution.

IID variables: Same distribution, different values

Independent variables cannot be correlated, so the values taken by IID variables will disagree on all (most) outcomes.

We do have:

$$\text{same distribution}⟺\text{same PMF or PDF}$$

Standardization

Suppose $X$ is any random variable.

The standardization of $X$ is:

$$Z=\frac{X-{\mu }_X}{{\sigma }_X}$$

The variable $Z$ has $E[Z]=0$ and $\mathrm{Var}[Z]=1$. We can reconstruct $X$ by:

$$X={\sigma }_{X}Z+{\mu }_X$$

---

Suppose $X_1,X_2,\dots ,X_n$ is a collection of IID random variables.

Define:

$$S_n=\sum _{i=1}^n{X}_i{Z}_n=\frac{S_n-n\mu }{\sigma \sqrt{n}}$$

where:

$$\mu =E[X_i]{\sigma }^2=\mathrm{Var}[X_i](\text{every }i)$$

So $Z_n$ is the standardization of $S_n$.

Let $Z$ be a standard normal random variable, $Z\sim 𝒩(\mathrm{0,1})$.

Central Limit Theorem

Suppose $S_n={\sum }_{i=1}^n{X}_i$ for IID variables $X_i$, and $Z_n$ are the standardizations of $S_n$.

Then for any interval $[a,b]\subset ℝ$:

$$\underset{n\to \infty }{\lim }P[a\le Z_n\le b]=\mathrm{\Phi }(b)-\mathrm{\Phi }(a)$$

We say that $Z_n$ converges in probability to the standard normal $Z$.

---

The distribution of a very large sum of IID variables is determined merely by $\mu$ and ${\sigma }^2$ from the original IID variables, while the data of higher moments fades away.

The name “normal distribution” is used because it arises from a large sum of repetitions of any other kind of distribution. It is therefore ubiquitous in applications.

Misuse of the CLT

It is important to learn when the CLT is applicable and when it is not. Many people (even professionals) apply it wrongly.

For example, sometimes one hears the claim that if enough students take an exam, the distribution of scores will be approximately normal. This is totally wrong!

Intuition for the CLT

The CLT is about the distribution of simultaneity, or (in other words) about accumulated alignment between independent variables.

With a large $n$, deviations of the total sum are predominantly created by simultaneous (correlated) deviations of a large portion of summands away from their means, rather than the contributions of individual summands deviating a large amount.

Simultaneity across a large $n$ of independent items is described by… the bell curve.

Theory 2

Extra - Moment Generating Functions

Theory 1

In order to show why the CLT is true, we introduce the technique of moment generating functions. Recall that the $n^{th}$ moment of a distribution $X$ is simply $E[X^n]$. Write ${\mu }_n$ for this value.

Recall the power series for $e^x$:

$$e^x=1+x+\frac{1}{2!}{x}^2+\frac{1}{3!}{x}^3+\dots$$

The function $f(x)=e^x$ has the property of being a bijective differentiable map from $ℝ$ to ${ℝ}^{>0}$, and it converts addition to multiplication: $e^{x+y}=e^x\cdot e^y$.

Given a random variable $X$, we can compose $X$ with $f(x)=e^x$ to obtain a new variable. Define the moment generating function of $X$ as follows:

$$M_X(t)=E[e^{tX}].$$

This is a function of $t\in ℝ$ and returns values in $ℝ$. It is called the moment generating function because it contains the data of all the higher moments ${\mu }_n$. They can be extracted by taking derivatives and evaluating at zero:

$$\begin{array}{cc}{M}_X(t)& =1+E[X]t+E[X^2]\frac{t^2}{2!}+E[X^3]\frac{t^3}{3!}+\dots \\ M_X^{(n)}(0)& =E[X^n]={\mu }_n.\end{array}$$

It is reasonable to consider $M_X(t)$ as a formal power series in the variable $t$ that has the higher moments for coefficients.

Example - Moment generating function of a standard normal

We compute $M_Z(t)$ where $Z\sim 𝒩(\mathrm{0,1})$. From the formula for expected value of a function of a random variable, we have:

$$E[e^{tZ}]=\frac{1}{\sqrt{2\pi }}{\int }_{-\infty }^{+\infty }{e}^{tx-x^2/2}dx.$$

Complete the square in the exponent: $tx-x^2/2=-\frac{1}{2}{(x-t)}^2+\frac{1}{2}{t}^2$. Thus:

$$e^{tx-x^2/2}=e^{-\frac{1}{2}{(x-t)}^2}{e}^{\frac{1}{2}{t}^2}.$$

The last factor can be taken outside the integral:

$$E[e^{tZ}]=e^{t^2/2}\frac{1}{\sqrt{2\pi }}{\int }_{-\infty }^{+\infty }{e}^{-\frac{1}{2}{(x-t)}^2}dx=e^{t^2/2}=M_Z(t).$$

Exercise - Moment generating function of an exponential variable

Compute $M_X(t)$ for $X\sim \mathrm{Exp}(\lambda )$.

Moment generating functions have the remarkable property of encoding the distribution itself:

Distributions determined by MGFs

Assume $M_X(t)$ and $M_Y(t)$ both converge. If $M_X(t)=M_Y(t)$, then $X\sim Y$.

Moreover, if $M_X(t)=M_Y(t)$ for any interval of values $t\in (-\epsilon ,\epsilon )$, then $M_X(t)=M_Y(t)$ for all $t$ and $X\sim Y$.

Be careful about moments vs. generating functions!

Sometimes the moments all exist, but they grow so fast that the moment generating function does not converge. For example, the log-normal distribution $e^Z$ for $Z\sim 𝒩(\mathrm{0,1})$ has this property.

The fact above does not apply when this happens.

When moment generating functions approximate each other, their corresponding distributions also approximate each other:

Distributions converge when MGFs converge

Suppose that $M_{X_n}(t)\to M_X(t)$ for all $t$ on some interval $t\in (-\epsilon ,+\epsilon )$. (In particular, assume that $M_X(t)$ converges on some such interval.) Then for any $[a,b]$, we have:

$$\underset{n\to \infty }{\lim }P(X_n\in [a,b])=P(X\in [a,b]).$$

Exercise Using an MGF

Suppose $X$ is nonnegative and $M_X(t)={(1-2t)}^{-3/2}$ when $t<1/2$ and $M_X(t)=\infty$ when $t\ge 1/2$. Find a bound on $P(X>8)$ using (a) Markov’s Inequality, and (b) Chebyshev’s Inequality.

Link to original

Extra - Derivation of CLT

Theory 2

The main role of moment generating functions in the proof of the CLT is to convert the sum $X_1+\cdots +X_n$ into a product $e^{X_1}\cdots e^{X_n}$ by putting the sum into an exponent.

We have $S_n=X_1+\cdots +X_n$, and recall $Z_n=\frac{S_n-n\mu }{\sigma \sqrt{n}}$, so $E[Z_n]=0$ and $\mathrm{Var}(Z_n)=1$. First, compute the MGF of $Z_n$. We have:

$$M_{Z_n}(t)=E[e^{t{Z}_n}]=E\left[e^{t\frac{S_n-n\mu }{\sigma \sqrt{n}}}\right]$$

Exchange the sum in the exponent for a product of exponentials:

$$\begin{array}{cc}\exp \left(t\frac{S_n-n\mu }{\sigma \sqrt{n}}\right)& =\exp \left(\frac{t}{\sigma \sqrt{n}}\sum _{i=1}^n(X_i-\mu )\right)\\ & =\prod _{i=1}^n\exp \left(\frac{t}{\sigma \sqrt{n}}(X_i-\mu )\right)\end{array}$$

Now since the $X_i$ are independent, the factors $\exp \left(\frac{t}{\sigma \sqrt{n}}(X_i-\mu )\right)$ are also independent of each other. Use the product rule $E[XY]=E[X]E[Y]$ when $X,Y$ are independent to obtain:

$$M_{Z_n}(t)=\prod _{i=1}^{n}E\left[\exp \left(\frac{t}{\sigma \sqrt{n}}(X_i-\mu )\right)\right]$$

Now expand the exponential in its Taylor series and use linearity of expectation:

$$\begin{array}{cc}{M}_{Z_n}(t)& =\prod _{i=1}^{n}E[1+\frac{t}{\sigma \sqrt{n}}(X_i-\mu )+\frac{1}{2!}{\left(\frac{t}{\sigma \sqrt{n}}\right)}^2{(X_i-\mu )}^2+\dots ]\\ & =\prod _{i=1}^n(1+\frac{t}{\sigma \sqrt{n}}E[X_i-\mu ]+\frac{1}{2!}{\left(\frac{t}{\sigma \sqrt{n}}\right)}^{2}E[{(X_i-\mu )}^2]+\dots )\\ & =\prod _{i=1}^n(1+0+\frac{t^2}{2!n}+\dots )\\ & \approx \prod _{i=1}^n(1+\frac{t^2}{2n}).\end{array}$$

We don’t give a complete argument for the final approximation, but a few remarks are worthwhile. For fixed $n,\sigma ,\mu$, and assuming the moments $E[{(X_i-\mu )}^k]$ have adequately bounded growth in $k$, the series in each factor converges for all $t$. Using Taylor’s theorem we could write an error term as a shrinking function of $n$. The real trick of analysis is to show that in the product of $n$ factors, these error terms shrink fast enough that the limit value is not affected.

In any case, the factors of the last line are independent of $n$, so we have:

$$M_{Z_n}(t)\approx {(1+\frac{t^2}{2n})}^n\underset{n\to \infty }{⟶}\exp \left(\frac{t^2}{2}\right)$$

But $e^{\frac{t^2}{2}}$ is the MGF of $Z\sim 𝒩(\mathrm{0,1})$. Therefore $M_{Z_n}(t)\to M_Z(t)$, so $F_{Z_n}(x)\to F_Z(x)$.

Link to original

Theory 3

Normal approximations rely on the limit stated in the CLT to approximate probabilities for large sums of variables.

Normal approximation

Let $S_n=X_1+\cdots +X_n$ for IID variables $X_i$ with $\mu =E[X_i]$ and ${\sigma }^2=\mathrm{Var}[X_i]$.

The normal approximation of $S_n$ is:

$$F_{S_n}(s)\approx \mathrm{\Phi }\left(\frac{s-n\mu }{\sigma \sqrt{n}}\right)$$

For example, suppose $X_i\sim \mathrm{Ber}(p)$, so $S_n\sim \mathrm{Bin}(n,p)$. We know $\mu =p$ and $\sigma =pq$. Therefore:

$$F_{S_n}(s)\approx \mathrm{\Phi }\left(\frac{s-np}{\sqrt{npq}}\right)$$

A rule of thumb is that the normal approximation to the binomial is effective when $npq>10$.

Efficient computation

This CDF is far easier to compute for large $n$ than the CDF of $S_n$ itself. The factorials in $\left(\genfrac{}{}{0px}{}{n}{k}\right)$ are hard (even for a computer) when $n$ is large, and the summation adds another $n$ factor to the scaling cost.

Theory 4

De Moivre-Laplace Continuity Correction Formula

The normal approximation to a discrete distribution, for integers $a$ and $b$ close together, should be improved by adding 0.5 to the range on either side:

$$\begin{array}{cc}P[a\le S_n\le b]& \approx P[a-0.5\le \sigma \sqrt{n}Z+n\mu \le b+0.5]\\ & \\ & \approx \mathrm{\Phi }\left(\frac{b+0.5-n\mu }{\sigma \sqrt{n}}\right)-\mathrm{\Phi }\left(\frac{a-0.5-n\mu }{\sigma \sqrt{n}}\right)\end{array}$$