Theory

Theory 1 - Sample mean

Sample mean and its variance

The sample mean of a set $X_1,X_2,\dots ,X_n$ of IID random variables is an RV giving the average value:

$$M_n(X)=\frac{1}{n}(X_1+\cdots +X_n)$$

Statistics of the sample mean:

$$E[M_n(X)]=E[X_i],\mathrm{Var}[M_n(X)]=\frac{\mathrm{Var}[X_i]}{n}(\text{for any }i)$$

The sample mean is typically applied to repeated trials of an experiment. The trials are independent, and the probability distribution of outcomes should be identical from trial to trial.

Notice that the variance of the sample mean limits to 0 as $n\to \infty$. As more trials are repeated, and the average of all results is taken, the fluctuations of this average will shrink toward zero.

As $n\to \infty$ the distribution of $M_n(X)$ will converge to a PMF with all the probability concentrated at $E[X_i]$ and none elsewhere.

Theory 2 - Tail estimation

Every distribution must trail off to zero for large enough $|X|$. The regions where $X$ trails off to zero (large magnitude of $X$) are informally called ‘tails’.

Tail probabilities

A tail probability is a probability with one of these forms, for any $c>0$:

$$P[X\ge c]P[X\le -c]P[|X-{\mu }_X|\ge c]$$

Markov’s inequality

Assume that $X\ge 0$. Take any $c>0$.

Then the Markov’s inequality states:

$$P[X\ge c]\le \frac{{\mu }_X}{c}$$

Chebyshev’s inequality

Take any $X$, and $c>0$.

Then the Chebyshev’s inequality states:

$$P[|X-{\mu }_X|\ge c]\le \frac{{\sigma }_X^2}{c^2}$$

Markov vs. Chebyshev

Chebyshev’s inequality works for any $X$, and it usually gives a better estimate than Markov’s inequality.

The main value of Markov’s inequality is that it only requires knowledge of ${\mu }_X$.

Think of Chebyshev’s inequality as a tightening of Markov’s inequality using the additional data of ${\sigma }_X$.

Derivation of Markov’s inequality - Continuous RV

Under the hypothesis that $X\ge 0$ and $c>0$, we have:

$${\mu }_X=E[x]={\int }_0^{\infty }x{f}_X(x)dx={\int }_0^{c}x{f}_X(x)dx+{\int }_c^{\infty }x{f}_X(x)dx$$

On the range $c\le x<\infty$ we may convert $x$ to $c$, making the integrand bigger:

$${\int }_c^{\infty }x{f}_X(x)dx\ge {\int }_c^{\infty }c{f}_X(x)dx$$

Simplify:

$${\int }_c^{\infty }c{f}_X(x)dx\gg \gg c{\int }_c^{\infty }{f}_X(x)dx\gg \gg cP[X\ge c]$$

Also:

$${\int }_0^{c}x{f}_X(x)dx\ge 0$$

Therefore:

$$\begin{array}{c}{\int }_0^{\infty }x{f}_X(x)dx\ge cP[X\ge c]\\ \\ \gg \gg E[x]\ge cP[X\ge c]\end{array}$$

Extra - Derivation of Chebyshev’s inequality

Notice that the variable ${(X-{\mu }_X)}^2$ is always positive. Chebyshev’s inequality is a simple application of Markov’s inequality to this variable.

Specifically, using $c^2$ as the Markov constant, Markov’s inequality yields:

$$P[(X-{\mu }_X{)}^2\ge c^2]\le \frac{E[(X-{\mu }_X{)}^2]}{c^2}$$

Then, by monotonicity of square roots:

$${(X-{\mu }_X)}^2\ge c^2⟺|X-{\mu }_X|\ge c$$

And of course $E[(X-{\mu }_X{)}^2]={\sigma }_X^2$. Chebyshev’s inequality follows.

Theory 3 - Law of Large Numbers

Let $X_1,X_2,\dots ,X_n$ be a collection of IID random variables with $\mu =E[X_i]$ for any $i$ and ${\sigma }^2=\mathrm{Var}[X_i]$ for any $i$.

Recall the sample mean:

$$\begin{array}{c}{M}_n(X)=\frac{1}{n}(X_1+\cdots +X_n),\\ \\ E[M_n(X)]=\mu ,\mathrm{Var}[M_n(X)]=\frac{{\sigma }^2}{n}\end{array}$$

Law of Large Numbers (weak form)

For any $c>0$, by Chebyshev’s inequality we have:

$$\begin{array}{ccc}& P\left[\right|M_n(X)-\mu |\ge c]\le \frac{{\sigma }^2}{n{c}^2}& \text{(finite LLN)}\end{array}$$

Therefore:

$$\begin{array}{ccc}& \underset{n\to \infty }{\lim }P\left[\right|M_n(X)-\mu |<c]=1& \text{(infinite LLN)}\end{array}$$