Central Limit Theorem

1. Central Limit Theorem

Central Limit Theorem wants to show the limit distribution of

$$Y_n=X_1+X_2+\cdots +X_n.$$

To constrain the mean and variance as $n$ grows, we need to standardize it as

$$Y_n^{\ast }=\frac{Y_n-\mathbb{E}[Y_n]}{\sqrt{\mathrm{Var}[Y_n]}}.$$

1.1 CLT with i.i.d. Condition

Theorem (Simplified CLT). Let $X_1,X_2,\dots ,X_n$ be i.i.d. random variables with $\mathbb{E}[X_i]=0$ and $\mathrm{Var}[X_i]=1$. Then, as $n\to \infty$,

$$\frac{1}{\sqrt{n}}\sum _{i=1}^n{X}_i\stackrel{d}{\to }\mathcal{N}(0,1).$$

Theorem (General i.i.d. CLT). Let $X_1,X_2,\dots ,X_n$ be i.i.d. random variables, and suppose there exists MGF $M_X(t)$ for some neighborhood of $0$, i.e. $\exists \delta >0$ such that $\forall t\in (-\delta ,\delta )$, $M_{X_i}(t)$ exists. Furthermore, $\mathbb{E}[X_i]=\mu$, $\mathrm{Var}[X_i]={\sigma }^2<\infty$, and

$${\bar{X}}_{(n)}=\frac{1}{n}\sum _{i=1}^n{X}_i.$$

Define $G_n(x)$ as the CDF of $\sqrt{n}\frac{{\bar{X}}_{(n)}-\mu }{\sigma }$. Then, $\forall x\in \mathbb{R}$,

$$\underset{n\to \infty }{\lim }{G}_n(x)={\int }_{-\infty }^x\frac{1}{\sqrt{2\pi }}{e}^{-t^2/2}dt.$$

Theorem (Lindeberg-Levy CLT). Let $X_1,X_2,\dots ,X_n$ be i.i.d. random variables with $\mathbb{E}[X_i]=\mu$ and $\mathrm{Var}[X_i]={\sigma }^2<\infty$. Denote

$$Y_n^{\ast }=\frac{{\sum }_{i=1}^n(X_i-\mu )}{\sigma \sqrt{n}}.$$

Then, $\forall y\in \mathbb{R}$,

$$\underset{n\to \infty }{\lim }\mathbb{P}(Y_n^{\ast }\le y)=\Phi (y)={\int }_{-\infty }^y\frac{1}{\sqrt{2\pi }}{e}^{-t^2/2}dt.$$

Proof

To prove the last equation, we only need to prove that $Y_n^{\ast }\stackrel{d}{\to }\mathcal{N}(0,1)$, and it is equivalent to show ${\phi }_{Y_n^{\ast }}(t)\to e^{-t^2/2}$, which is the CF of $\mathcal{N}(0,1)$.

Denote the CF of $X_n-\mu$ as $\phi (t)$, then the CF of $Y_n^{\ast }$ is

$${\phi }_{Y_n^{\ast }}(t)=\phi {\left(\frac{t}{\sigma \sqrt{n}}\right)}^n.$$

Given that $\mathbb{E}[X_i]=\mu$ and $\mathrm{Var}[X_i]={\sigma }^2$, we can do the Taylor expansion of $\phi (t)$ as

$$\phi (t)=\phi (0)+{\phi }^{\prime }(0)t+\frac{{\phi }^{\prime \prime }(0)}{2}{t}^2+o(t^2)=1-\frac{1}{2}{\sigma }^2{t}^2+o(t^2).$$

Then,

$${\phi }_{Y_n^{\ast }}(t)={\left(1-\frac{1}{2}\frac{t^2}{n}+o\left(\frac{t^2}{n}\right)\right)}^n\to e^{-t^2/2}$$

as $n\to \infty$. $\square$

Note: Meaning of CLT

CLT shows that, regardless of the original distribution of $X_i$, as long as $n$ is sufficiently large and the i.i.d. and finite variance assumptions hold, the distribution of ${\bar{X}}_{(n)}$ or ${\sum }_{i=1}^n{X}_i$ will be approximately normal. This also indicates why measurement error is often assumed to be normally distributed, since it is the sum of many small errors.

Example (Generate $\mathcal{N}(0,1)$ from $\mathcal{U}(0,1)$ by Lindeberg-Levy CLT).

• Generate 12 i.i.d. $\mathcal{U}(0,1)$ random variables $X_1,X_2,\dots ,X_{12}$. Then, $\mathbb{E}[X_i]=\frac{1}{2}$ and $\mathrm{Var}[X_i]=\frac{1}{12}$.
• Calculate

$$y=\sum _{i=1}^{12}{X}_i-6\dot{\sim }\mathcal{N}(0,1).$$

• Transform $y$ to $z=\sigma y+\mu \dot{\sim }\mathcal{N}(\mu ,{\sigma }^2)$.
• Repeat the above steps for $n$ times, and we can get $n$ samples from $\mathcal{N}(\mu ,{\sigma }^2)$.

1.2 CLT with Independent but Not Identical Condition

In practice, the i.i.d. condition is often too strict. In many cases, the random variables are independent but not identical. Here, we still want to show that, even if the random variables $X_i$ are not identically distributed, given some conditions, the sum $Y_n={\sum }_{i=1}^n{X}_i$ will be approximately normal.

1.2.1 Lindeberg-Feller CLT

In Lindeberg-Feller CLT, the key is to make each term $X_i$ “uniformly small” compared to the sum of all terms.

Definition (Lindeberg-Feller condition). Let $X_1,X_2,\dots ,X_n$ be independent random variables with finite mean and variance: $\mathbb{E}[X_i]={\mu }_i$ and $\mathrm{Var}[X_i]={\sigma }_i^2$. Denote $Y_n={\sum }_{i=1}^n{X}_i$. Then

$$\mathbb{E}[Y_n]=\sum _{i=1}^n{\mu }_i,$$

and

$$\sigma (Y_n)=\sqrt{\mathrm{Var}[Y_n]}=\sqrt{\sum _{i=1}^n{\sigma }_i^2}:=B_n.$$

Then $Y_n$ can be standardized as

$$Y_n^{\ast }=\frac{Y_n-\mathbb{E}[Y_n]}{\sigma (Y_n)}=\frac{Y_n-{\sum }_{i=1}^n{\mu }_i}{\sqrt{{\sum }_{i=1}^n{\sigma }_i^2}}=\sum _{i=1}^n\frac{X_i-{\mu }_i}{B_n}.$$

To make each term of $Y_n^{\ast }$ “uniformly small”, we can constrain the probability of event $\{\frac{X_i-{\mu }_i}{B_n}\ge \gamma ,\forall \gamma >0\}$ to converge to $0$:

$$\underset{n\to \infty }{\lim }\underset{(:=†)}{\underbrace{\mathbb{P}\left(\underset{1\le i\le n}{\max }|X_i-{\mu }_i|>\gamma B_n\right)}}=0,\forall \gamma >0.$$

By probability theory, we can further derive:

$$(†)=\mathbb{P}\left(\bigcup _{i=1}^n\{|X_i-{\mu }_i|>\gamma B_n\}\right)\le \sum _{i=1}^n\mathbb{P}(|X_i-{\mu }_i|>\gamma B_n).$$

And the last term can be further derived as:

$$\begin{array}{rl}RHS& =\sum _{i=1}^n{\int }_{|x-{\mu }_i|>\gamma B_n}{f}_{X_i}(x)dx\\ & \le \frac{1}{{\gamma }^2{B}_n^2}\sum _{i=1}^n{\int }_{|x-{\mu }_i|>\gamma B_n}(x-{\mu }_i{)}^2{f}_{X_i}(x)dx.\end{array}$$

Then, we can derive the Lindeberg-Feller condition as, for any $\gamma >0$:

$$\underset{n\to \infty }{\lim }\frac{1}{{\gamma }^2{B}_n^2}\sum _{i=1}^n{\int }_{|x-{\mu }_i|>\gamma B_n}(x-{\mu }_i{)}^2{f}_{X_i}(x)dx=0.(\star )$$

Here, $(\star )$ is the Lindeberg-Feller condition.

Theorem (Lindeberg-Feller CLT). For random variables $X_1,X_2,\dots ,X_n$ satisfying the Lindeberg-Feller condition, for any $x\in \mathbb{R}$,

$$\underset{n\to \infty }{\lim }\mathbb{P}\left(\frac{1}{B_n}\sum _{i=1}^n(X_i-{\mu }_i)\le x\right)=\Phi (x).$$

It can be further proved that, if $\{X_i\}$ are i.i.d. with finite variance, then the Lindeberg-Feller condition is satisfied.

1.2.2 Lyapunov CLT

Theorem (Lyapunov CLT). Let $\{X_n\}$ be a sequence of independent random variables. If there exists a $\delta >0$ such that $\forall x$:

$$\underset{n\to \infty }{\lim }\frac{1}{B_n^{2+\delta }}\sum _{i=1}^n\mathbb{E}[|X_i-{\mu }_i{|}^{2+\delta }]=0,$$

then

$$\underset{n\to \infty }{\lim }\mathbb{P}\left(\frac{1}{B_n}\sum _{i=1}^n(X_i-{\mu }_i)\le x\right)=\Phi (x).$$

2. Applications Using CLT

2.1 Error Analysis

• In numerical analysis, there is a kind of error called round-off error, which is caused by the finite precision of computer arithmetic. For example, when we calculate $\pi$, we can only use a finite number of digits to represent it like ${\pi }^{\prime }\dot{=}3.14159$.
• More generally, if we calculate summation of such $n$ numbers $S_n={\sum }_{i=1}^n{X}_i$, approximating it as $S_n^{\prime }={\sum }_{i=1}^n{X}_i^{\prime }$, and denote the error as ${\epsilon }_n=X_n-X_n^{\prime }$, then the overall error is $S_n-S_n^{\prime }={\sum }_{i=1}^n{\epsilon }_i$.
• By the property of rounding, if the approximated value $X_i^{\prime }=\overline{x_0.x_1{x}_2\cdots x_k}$, then the real value should be in the interval $[x_0.x_1{x}_2\cdots (x_k-1)5,x_0.x_1{x}_2\cdots x_{k}4]$. Thus the error of a $k$-digit approximation can be regarded as a uniform distribution in $[-0.5\times 10^{-k},0.5\times 10^{-k}]$.
• Now use CLT to analyze the error of $S_n-S_n^{\prime }$. Since the error of each term ${\epsilon }_i$ is uniformly distributed in $[-0.5\times 10^{-k},0.5\times 10^{-k}]$, then $\mathbb{E}[{\epsilon }_i]=0$ and $\mathrm{Var}[{\epsilon }_i]=\frac{1}{12}\times 10^{-2k}$. By CLT:

$$\sum _{i=1}^n{\epsilon }_i\stackrel{d}{\to }\mathcal{N}\left(0,\frac{n}{12}\times 10^{-2k}\right).$$

2.2 Normal Approximation

2.2.1 Normal Approximation with Unknown ${\sigma }^2$

From CLT above,

$$\sqrt{n}({\bar{X}}_{(n)}-\mu )\stackrel{d}{\to }\mathcal{N}(0,{\sigma }^2).$$

However, in practice, we often do not know the value of ${\sigma }^2$. In this case, we can use the sample variance

$$S_n^2=\frac{1}{n-1}\sum _{i=1}^n(X_i-{\bar{X}}_{(n)}{)}^2$$

to estimate ${\sigma }^2$. Then, Slutsky’s theorem can guarantee that:

$$\frac{\sqrt{n}({\bar{X}}_{(n)}-\mu )}{S_n}\stackrel{d}{\to }\mathcal{N}(0,1).$$

2.2.2 Normal Approximation of Negative-Binomial Distribution

Assume $X_1,X_2,\dots ,X_n$ are i.i.d. $\mathrm{NegBin}(r,p)$. Then $\mathbb{E}[X_i]=\frac{r(1-p)}{p}$ and $\mathrm{Var}[X_i]=\frac{r(1-p)}{p^2}$. By CLT:

$$\frac{{\sum }_{i=1}^n{X}_i-n\frac{r(1-p)}{p}}{\sqrt{n\frac{r(1-p)}{p^2}}}=\frac{\sqrt{n}({\bar{X}}_n-\frac{r(1-p)}{p})}{\sqrt{\frac{r(1-p)}{p^2}}}\stackrel{d}{\to }\mathcal{N}(0,1).$$

2.2.3 Normal Approximation of Bernoulli Distribution

Note: De Moivre-Laplace CLT

De Moivre-Laplace CLT is a special case of CLT, and actually the first one to be proved. It shows that the binomial distribution can be approximated by normal distribution when $n$ is large.

Assume in $n$ Bernoulli trials $\mathbb{P}(A)=p$, and denote $S_n$ as the number of times $A$ happened. Then $\mathbb{E}[S_n]=np$ and $\mathrm{Var}[S_n]=np(1-p)$. By CLT:

$$\frac{S_n-np}{\sqrt{np(1-p)}}\stackrel{d}{\to }\mathcal{N}(0,1).$$

Note: Normal approximation details

• Normal approximation vs. Poisson approximation. Empirically, when $np>5$ and $n(1-p)>5$, the normal approximation is better than Poisson approximation. Else if $p$ is small, Poisson approximation is better.
• Laplace’s correction. In De Moivre-Laplace CLT, we use a continuous distribution to approximate a discrete distribution. If $S_n\sim \mathrm{Bin}(n,p)$ and $Y\sim \mathcal{N}(np,np(1-p))$, then:

$$\mathbb{P}(S_n\le x)=\mathbb{P}(Y\le x+0.5)$$ $$\mathbb{P}(S_n\ge x)=\mathbb{P}(Y\ge x-0.5)$$ $$\mathbb{P}(k_1\le S_n\le k_2)=\mathbb{P}(k_1-0.5\le Y\le k_2+0.5)$$

especially when $k_1,k_2$ are integers.

Using CLT, we can approximate:

$$\mathbb{P}\left(Y_n^{\ast }=\frac{S_n-np}{\sqrt{npq}}\le y\right)\approx \mathbb{P}(Z\le y)=\Phi (y),$$

where $Z\sim \mathcal{N}(0,1)$, $\Phi (y)$ is the CDF of $\mathcal{N}(0,1)$, and $S_n\sim \mathrm{Bin}(n,p)$.

Related Notes

• Convergence of Random Variables
• Chebyshev Inequality
• Generating Binomial Random Variables from Uniforms