3.3 Central Limit Theorem

Central Limit Theorem

The Central Limit Theorem states that, under certain conditions, the distribution of the standardized sum (or average) of a large number of independent and identically distributed (i.i.d.) random variables approaches a normal distribution, regardless of the shape of the original population distribution.

Formally, let $X_1,X_2,\dots ,X_n$ be i.i.d. random variables with mean $\mu$ and variance ${\sigma }^2$, and define the sum $S_n=\sum _{i=1}^n{X}_i$. Then, it follows that
${\lim }_{n\to \infty }\mathbb{P}\left(\frac{S_n-\mathbb{E}[S_n]}{\sqrt{\mathrm{Var}(S_n)}}\le x\right)={\lim }_{n\to \infty }\mathbb{P}\left(\frac{S_n-n\mu }{\sigma \sqrt{n}}\le x\right)=\Phi (x),$
where $\Phi (x)$ is the CDF of the normal distribution.

Proof

Examples

Binomial Concentration

Here, we will prove that the binomial distribution is concentrated about its mean as the number of trials tends to $\infty$. Suppose we have i.i.d. trials, each with a probability of success $1/2$. Let $S_n$ be the number of successes in the first $n$ trials.

Compute the mean and variance of $S_n$. Since $S_n\sim \text{Bin}(n,1/2)$, it follows that $\mathbb{E}(S_n)=n/2$ and $\mathrm{Var}(S_n)=n/4$.

Define $Z_n$ in terms of $S_n$ such that $Z_n$ has mean $0$ and variance $1$. To normalize the sum, let $Z_n=\frac{S_n-n\mu }{\sigma \sqrt{n}}$. Since $\mu$ and ${\sigma }^2$ should be the mean and variance of a single trial $X_i$, then in terms of $S_n$, $Z_n=\frac{S_n-\mathbb{E}(S_n)}{\sqrt{\mathrm{Var}(X)}}=\frac{S_n-n/2}{\sqrt{n}/2}.$

What is the distribution of $Z_n$ as $n\to \infty$? Per CLT, we have that $\underset{n\to \infty }{\lim }{f}_Z(z)=\frac{1}{\sqrt{2\pi }}{e}^{-z^2/2}$, and therefore $Z_n\to \mathcal{N}(0,1)$ in the discrete realm.

Use the bound $P(Z>z)\le (z\sqrt{2\pi }{)}^{-1}{e}^{-z^2/2}$ (where $Z$ is a standard normal) to approximately bound $P(S_n/n>1/2+\delta )$, where $\delta >0$. It follows that \begin{align}\mathbb{P}(S_{n} / n > 1 / 2 + \delta) &= \mathbb{P}((\sqrt{ n } / 2) Z_{n}) + n / 2 > n / 2 + \delta n) \\ &= \mathbb{P}(Z_{n} > 2\delta \sqrt{ n }) \leq \frac{1}{2\delta\sqrt{ 2\pi n }}\exp(-2\delta^2n).\end{align}

Packet Erasures & Inverse CDFs

Alice is sending $1000$ bits to Bob. The probability that a bit gets erased is $p$, and the erasure of each bit is independent of the others.

Alice is using a scheme that can tolerate up to one-fifth of the bits being erased. That is, as long as Bob receives at least 801 of the 1000 bits correctly, he can decode Alice’s message. The probability of more than $1/5$ of the bits being erased should be at most $10^{-6}$.

Use Chebyshev’s inequality to upper bound $p$ such that the probability of a communications breakdown is at most $10^{-6}$. Express the number of erased bits as $N\sim \text{Bin}(1000,p)$. Then,

P(N \ge 200) &= P(N - 1000p \ge 200-1000p) \
&\leq \frac{1000p(1-p)}{(200-1000p)^2} \
&= \frac{p(1-p)}{40(1-5p)^2} \leq 10^{-6}
\end{align}$$

which yields $p\le 3.9986\times 10^{-5}$.

Use CLT to find an approximate bound for p such that the probability of a communications breakdown is at most $10^{-6}$. Note that ${\Phi }^{-1}(1-10^{-6})\approx 4.753$. Let $N\sim \mathrm{Bin}(1000,p)$ be again the number of erasures. Then, $Z=\frac{N-1000p}{10\sqrt{p(1-p)}}$. As such, it holds that

\begin{aligned} P(N \ge 200) &= P\left( Z \ge \frac{200-1000p}{\sqrt{ 1000p(1-p) }} \right) \\ &= 1- \Phi\left( \frac{200-1000p}{\sqrt{ 1000p(1-p) }} \right) \le 10^{-6} \\ \end{aligned} \\ \\ \Big\Updownarrow \\ \\ \begin{aligned} \frac{200-1000p}{\sqrt{ 1000p(1-p) }} &\ge \Phi^{-1}(1-10^{-6}) = 4.753. \end{aligned} \end{alignat}

This yields $p\le 0.1468$.