Laws of Large Numbers

Central Limit Theorem

Markov’s inequality: If $X$ is a random variable that takes only nonnegative values, then for any value $a>0$, $P\{X\ge a\}\le \frac{E[X]}{a}$.

This is simple to prove. Let $I$ indicate $X\ge a$. We see $I\le \frac{X}{a}$. Therefore, $E[I]=P\{X\ge a\}\le \frac{E[X]}{a}$.

As a corollary,
Chebyshev’s inequality: If $X$ is a random variable with finite mean $\mu$ and variance ${\sigma }^2$, then for any $k>0$, $P\{|X-\mu |\ge k\}\le \frac{{\sigma }^2}{k^2}$

To get this, we apply Markov’s inequality on $(X-\mu {)}^2$ with $a=k^2$, obtaining $P\{(X-\mu {)}^2\ge k^2\}\le \frac{E[(X-\mu {)}^2]}{k^2}$. This is directly equivalent to Chebyshev’s.

These bounds are important when we know little about a distribution besides mean (and variance).

Central Limit Theorem: Let $X_1,X_2\dots$ be a sequence of independent and identically distributed random variables, with mean $\mu$ and variance ${\sigma }^2$. The distribution of $\frac{X_1+\cdots +X_n-n\mu }{\sigma \sqrt{n}}$ tends towards the standard normal as $n\to \infty$.

That is, for $-\infty <a<\infty$, $P\left\{\frac{X_1+\cdots +X_n-n\mu }{\sigma \sqrt{n}}\le a\right\}\to \frac{1}{\sqrt{2\pi }}{\int }_{-\infty }^a{e}^{-x^2/2}dx$ as $n\to \infty$

The proof leverages the following,
Lemma: Let $Z_1,Z_2,\dots$ be a sequence of random variables with distribution functions $F_{Z_n}$ and moment generating functions $M_{Z_n},n\ge 1$, and let $Z$ be a random variable having distribution function $F_Z$ and moment generating function $M_Z$. If $M_{Z_n}(t)\to M_Z(t)$ for all $t$, then $F_{Z_n}(t)\to F_Z(t)$ for all $t$ at which $F_Z(t)$ is continuous. This makes sense with our previous intuition that $M$ is fully representative of a random variable.

If we let $Z$ be a standard normal random variable, $M_Z(t)=e^{t^2/2}$. Therefore, we just need to show that our sequence of random variables will tend towards $M_Z(t)$

Assuming the generating function of $X_i$, $M(i)$ exists and is finite, the moment generating function of $X_i/\sqrt{n}$ is $E\left[\exp \left\{\frac{t{X}_i}{\sqrt{n}}\right\}\right]=M\left(\frac{t}{\sqrt{n}}\right)$

Since these are independent, we can say that the moment generating function of $\sum _{i=1}^n{X}_i/\sqrt{n}$ is ${\left[M\left(\frac{t}{\sqrt{n}}\right)\right]}^2$

Let $L(t)=\log M(t)$. Note that $L^{\prime }(0)=\frac{M^{\prime }(0)}{M(0)}=\mu =0$ and $L^{\prime \prime }(0)=\frac{M(0)M^{\prime \prime }(0)-[M^{\prime }(0){]}^2}{[M(0){]}^2}=E[X^2]-(E[X]{)}^2=1$

We must show that $[M(t/\sqrt{n}){]}^n\to e^{t^2/2}$, equivalently that $nL(t/\sqrt{n})\to t^2/2$.

Using L’Hôpital, $\underset{n\to \infty }{\lim }\frac{L(t/\sqrt{n})}{n^{-1}}=\underset{n\to \infty }{\lim }\frac{-L^{\prime }(t/\sqrt{n})n^{-3/2}t}{-2n^{-2}}=\underset{n\to \infty }{\lim }\left[\frac{L^{\prime }(t/\sqrt{n})t}{2n^{-1/2}}\right]$
$=\underset{n\to \infty }{\lim }\left[\frac{-L^{\prime \prime }(t/\sqrt{n})n^{-3/2}{t}^2}{-2n^{-3/2}}\right]=\underset{n\to \infty }{\lim }\left[L^{\prime \prime }\left(\frac{t}{\sqrt{n}}\right)t\frac{{}^2}{2}\right]=\frac{t^2}{2}$

This proves the central limit theorem on standard variables. The same result can be applied to any variable by considering its standardized version $X_i^{\ast }=(X_i-\mu )/\sigma$

This theorem states that for each individual $a$, $P\left\{\frac{X_1+...+X_n-n\mu }{\sigma \sqrt{n}}\le a\right\}\to \Phi (a)$
It can also be shown that this convergence is uniform in $a$, meaning for all $ϵ>0$, there is a point where $|f_n(a)-f(a)|<ϵ$ for all $a$

Example:
Suppose an astronomer wants to measure the distance to a star. He has a technique but he knows there’s a a variance of $4$ light-years in his observations. He wants to make $n$ observations and take the average $d$ as his estimation. How many measurements does he need to make sure $d$ is with $\pm .5$ light-years?

$\bar{X}={\sum }_{i=1}^n{X}_i$
The central limit theorem tells us $Z_n=\frac{\bar{X}-nd}{2\sqrt{n}}$ is approximately normal
$P\left\{-.5\le \frac{\bar{X}}{n}-d\le .5\right\}=P\left\{-.5\frac{\sqrt{n}}{2}\le Z_n\le .5\frac{\sqrt{n}}{2}\right\}\approx \Phi \left(\frac{\sqrt{n}}{4}\right)-\Phi \left(-\frac{\sqrt{n}}{4}\right)$
$=2\Phi \left(\frac{\sqrt{n}}{4}\right)-1$

So we need to find $2\Phi \left(\frac{\sqrt{n}}{4}\right)-1=.95$, or $\Phi \left(\frac{\sqrt{n}}{4}\right)=.975$
The inverse CDF does not have a closed-form, but a solver would tell us $\frac{\sqrt{n}}{4}=1.96$, which means $n\approx 62$ observations

Technically, we don’t know when the normal approximation will begin to be a good approximation of this distribution. If we are especially unsure, we can use Chebyshev’s inequality for a tight bound.

$P\left\{|\frac{\bar{X}}{n}-d|>.5\right\}\le \frac{4}{n(.5{)}^2}=\frac{16}{n}$, so $n=320$ observations

General Central Limit Theorem: Let $X_1,X_2,\dots$ be a sequence of independent random variables with ${\mu }_i=E[X_i],{\sigma }_i^2=\text{Var}(X_i)$. If $X_i$ are uniformly bounded and ${\sum }_{i=1}^{\infty }{\sigma }_i^2=\infty$ then $P\left\{\frac{{\sum }_{i=1}^n(X_i-{\mu }_i)}{\sqrt{{\sum }_{i=1}^n{\sigma }_i^2}}\le a\right\}\to \Phi (a)$ as $n\to \infty$

It really is a remarkable fact.

Strong Law of Large Numbers

Theorem: Let $X_1,X_2,\dots$ be a sequence of i.i.d. random variables, with $\mu =E[X_i]$. With probability $1$, $\frac{X_1+X_2+\cdots +X_n}{n}\to \mu$ as $n\to \infty$

This implies we can approximate the probability of an event by repeating many trials.

Proof:
We assume the fourth moment of $X_i$ is finite, i.e. $E[X_i^4]=K<\infty$ (however the theorem can be proven without this)

Assume $\mu =0$. Let $S_n={\sum }_{i=1}^n{X}_i$. Consider, $E[S_n^4]=E[(X_1+\cdots +X_n{)}^4]$. Expanding these terms yields results in the form $X_i^4$, $X_i^3{X}_j$, $X_i^2{X}_j^2$, $X_i^2{X}_j{X}_k$, and $X_i{X}_j{X}_k{X}_l$, where $i\ne j\ne k\ne l$. The terms with single $X_{i}s$ have mean $0$ by independence. So expanding yields,
$E[S_n^4]=nE[X_i^4]+\left(\genfrac{}{}{0ex}{}{4}{2}\right)\left(\genfrac{}{}{0ex}{}{n}{2}\right)E[X_i^2{X}_j^2]=nK+3n(n-1)E[X_i^2]E[X_j^2]$

$0\le \text{Var}(X_i^2)=E[X_i^4]-E[X_i^2{]}^2$ so $E[X_i^2{]}^2\le E[X_i^4]=K$

Therefore, $E[S_n^4]\le nK+3n(n-1)K$ which implies $E\left[\frac{S_n^4}{n^4}\right]\le \frac{K}{n^3}+\frac{3K}{n^2}$

$E\left[{\sum }_{n=1}^{\infty }{S}_n^4\right]={\sum }_{n=1}^{\infty }E\left[\frac{S_n^4}{n^4}\right]<\infty$, since the series converges. This implies that the series is finite with probability $1$ (since the expectation would otherwise be infinite). The convergence of the series implies ${\lim }_{n\to \infty }\frac{S_n^4}{n^4}=0$, which implies $\frac{S_n}{n}\to 0$

When $\mu \ne 0$, we can apply this argument to the random variables $X_i-\mu$ to obtain that $\underset{n\to \infty }{\lim }\sum _{i=1}^n\frac{X_i-\mu }{n}=0$