Bounding Probabilities

Definition

Bounding probabilities means deriving upper bounds or lower bounds for probabilities when the full distribution is unknown, using only coarse information such as the mean or variance.

Markov inequality

Let $X\ge 0$ be a nonnegative random variable and let $t>0$. Then

$$\mathrm{Pr}[X\ge t]\le \frac{\mathbb{E}[X]}{t}.$$

This is useful when you only know the Expected value of a nonnegative random variable.

Proof

Since $X\ge t$ implies $X/t\ge 1$, we have

$$X\ge t{1}_{\{X\ge t\}}.$$

Taking expectations gives

$$\mathbb{E}[X]\ge t\mathrm{Pr}[X\ge t]⟹\mathrm{Pr}[X\ge t]\le \frac{\mathbb{E}[X]}{t}.$$

Chebyshev inequality

Let $X$ be a random variable with mean $\mu =\mathbb{E}[X]$ and finite variance $\mathrm{Var}(X)$. Then for every $t>0$,

$$\mathrm{Pr}[|X-\mu |\ge t]\le \frac{\mathrm{Var}(X)}{t^2}.$$

Proof (Derivation from Markov)

Apply Markov’s inequality to the nonnegative random variable

$$Y:=(X-\mu {)}^2.$$

Then

$$\mathrm{Pr}[|X-\mu |\ge t]=\mathrm{Pr}[(X-\mu {)}^2\ge t^2]\le \frac{\mathbb{E}[(X-\mu {)}^2]}{t^2}=\frac{\mathrm{Var}(X)}{t^2}.$$

Example

If $\mathbb{E}[X]=10$ and $\mathrm{Var}(X)=9$, then

$$\mathrm{Pr}[|X-10|\ge 6]\le \frac{9}{36}=\frac{1}{4}.$$

Chernoff bounds

Chernoff bounds are much sharper concentration bounds for sums of independent Bernoulli random variables. (see Bernoulli distribution)

Let $X=X_1+\cdots +X_n$ where the $X_i$ are independent and $X_i\in \{0,1\}$ let $\mu =\mathbb{E}[X]$

1. $\mathrm{Pr}[X\ge (1+\delta )\mu ]\le e^{-\mu {\delta }^2/3}$
2. $\mathrm{Pr}[X\le (1-\delta )\mu ]\le e^{-\mu {\delta }^2/2}$
3. $\mathrm{Pr}[X\ge t]\le 2^{-t}$ for all $t\ge 2e\mathbb{E}[X]$

Proof of 3

Apply Markov inequality to $Y:=4^X$ There is $X\ge t⟺4^X\ge 4^t$ So

$$\mathrm{Pr}[X\ge t]=\mathrm{Pr}[4^X\ge 4^t]\le \frac{\mathbb{E}[4^X]}{4^t}$$

$X_1,X_2,\dots ,X_n$ are independent $⟹4^{X_1},\dots ,4^{X_n}$ are independent

$$\mathbb{E}[4^X]=\mathbb{E}\left[4^{{\sum }_{i=1}^n{X}_i}\right]=\mathbb{E}\left[\prod _{i=1}^n{4}^{X_i}\right]=\prod _{i=1}^n\mathbb{E}[4^{X_i}]$$

$X_i\sim \text{Bernoulli}(p_i)⟹\mathbb{E}[4^{X_i}]=4^1\cdot p_i+4^0\cdot (1-p_i)=1+3p_i\le e^{3p_i}$ (using $1+x\le e^x$) $\mathbb{E}[4^X]\le {\prod }_{i=1}^n{e}^{3p_i}=e^{3{\sum }_{i=1}^n{p}_i}=e^{3\mathbb{E}[X]}\le e^{\frac{3t}{2e}}\le 2^t$ (note that $e^{\frac{3}{2e}}\le 2$) $\mathrm{Pr}[X\ge t]\le \frac{2^t}{4^t}=2^{-t}$

NOTE

To prove 1 and 2, apply Markov’s inequality to $Y:=(1+\delta {)}^X\ge 0$ and $Y:=(1-\delta {)}^X\ge 0$

Example

Let $X\sim \mathrm{Bin}(1000,1/2)$. Then $\mu =\mathbb{E}[X]=500.$ Take $\delta =0.2$. Then

$$\mathrm{Pr}[X\ge 600]=\mathrm{Pr}[X\ge (1+0.2)\mu ]\le e^{-500\cdot 0.2^2/3}=e^{-20/3}.$$

So the probability of being at least $20\%$ above the mean is already very small.