W13 Notes

Deviations

01 Theory - Tail estimation

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 smaller:

$${\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.

Link to original

02 Illustration

Example - Markov and Chebyshev

Markov and Chebyshev

A tire shop has 500 customers per day on average.

(a) Estimate the odds that more than 700 customers arrive today.

(b) Assume the variance in daily customers is 100. Repeat (a) with this information.

Solution

Write $X$ for the number of daily customers.

(a) Using Markov’s inequality with $c=700$, we have:

$$P[X\ge 700]\le \frac{500}{700}\approx 0.71$$

(b) Using Chebyshev’s inequality with $c=200$, we have:

$$P[|X-500|\ge 200]\le \frac{100}{{200}^2}\approx 0.0025$$

The Chebyshev estimate is much smaller!

Link to original

03 Theory - Sample mean

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.

Link to original

Large Numbers

04 Theory - Law of Large Numbers

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 }_X,\mathrm{Var}[M_n(X)]=\frac{{\sigma }_X^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 }_X|\ge c]\le \frac{{\sigma }_X^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 }_X|<c]=1& \text{(infinite LLN)}\end{array}$$

Link to original

05 Illustration

Example - LLN: Average winnings

LLN: Average winnings

A roulette player bets as follows: he wins $100 with probability 0.48 and loses $100 with probability 0.52. The expected winnings after a single round is therefore $100\cdot 0.48-100\cdot 0.52$ which equals $-$$4.

By the LLN, if the player plays repeatedly for a long time, he expects to lose $4 per round on average.

The ‘expects’ in the last sentence means: the PMF of the cumulative average winnings approaches this PMF:

$$P_{M_n(X)}(k)=\{\begin{array}{cc}1& k=4\\ 0& k\ne 4\end{array}$$

This is by contrast to the ‘expects’ of expected value: the probability of achieving the expected value (or something near) may be low or zero! For example, a single round of this game cannot result in a $4 loss.

Link to original

Exercise - Enough samples

Enough samples

Suppose $X_1,X_2,\dots ,X_n$ are IID samples of $X\sim \mathrm{Ber}(0.6)$.

(a) Compute $E[X_i]$ and $\mathrm{Var}[X_i]$ and $\mathrm{Var}\left[M_{100}(X)\right]$.

(b) Use the finite LLN to find $\alpha$ such that:

$$P[|M_{100}(X)-0.6|\ge 0.05]\le \alpha$$

(c) How many samples $n$ are needed to guarantee that:

$$P[|M_n(X)-0.6|\ge 0.1]\le 0.05$$Link to original