Probability Inequalities

Markov’s Inequality

https://en.wikipedia.org/wiki/Markov%27s_inequality

Markov’s inequality provides a bound on the probability that the realization of random variable exceeds a given threshold. It relates probabilities to expectations.

Theorem (Markov's Inequality)

Let $X$ be a non-negative random variable, and suppose that $\mathbb{E}(X)$ exists. For any $t>0$, $\mathbb{P}\left(X>t\right)\le \frac{\mathbb{E}(X)}{t}.$

Proof

Since $X>0$,

$$\begin{array}{rl}\mathbb{E}(X)& ={\int }_0^{\infty }xf(x)dx={\int }_0^{t}xf(x)dx+{\int }_t^{\infty }xf(x)dx\\ & \ge {\int }_t^{\infty }xf(x)dx\ge {\int }_t^{\infty }f(x)dx=t\mathbb{P}(X>t).\end{array}$$

Suppose $\mathbb{E}(X)=10$, and by Markov’s Inequality, $\mathbb{P}(X\ge 20)\le 0.5$. The intuition here is that you cannot have more than half of the distribution to the right of 20 to still have enough distribution left to result in an expected value of 10. The further away of a value is from the expected value, the less density can be while keeping the expected value the same. Note that this bound may not always be tight. Markov’s Inequality is also used to prove other inequalities, such as Chebyshev’s Inequality below.

Chebyshev’s Inequality

https://en.wikipedia.org/wiki/Chebyshev%27s_inequality

Theorem (Chebyshev's Inequality)

Let $\mu =\mathbb{E}(X)$ and ${\sigma }^2=\text{Var}\left(X\right)$. Then,

$$\mathbf{P}\left(\left|X-\mu \right|\ge t\right)\le \frac{{\sigma }^2}{t^2}\text{and}\mathbf{P}\left(|Z|\ge k\right)\le \frac{1}{k^2}$$

where $Z=(X-\mu )/\sigma$. In particular, $\mathbf{P}(|Z|>2)\le \frac{1}{4}$ and $\mathbf{P}(|Z|>3)\le \frac{1}{9}$.

One way to think about Chebyshev’s inequality is that the variance is a budget of squared distance from the mean, and a tail event spends that budget very quickly. On the event $\{|X-\mu |\ge t\}$, the squared deviation $(X-\mu {)}^2$ is at least $t^2$. So if that event happens with probability $p$, it contributes at least $t^{2}p$ to the average squared deviation:

$${\sigma }^2=\mathbb{E}[(X-\mu {)}^2]1_{\{|X-\mu |\ge t\}}\ge t^2\mathbb{P}(|X-\mu |\ge t).$$

Rearranging gives the result.

Example

Suppose we test a prediction method like a neural network on a set of $n$ new test cases. Let $X_i=1$ if the prediction is wrong, and $X_i=0$ if the predictor is correct. Then ${\bar{X}}_n=n^{-1}{\sum }_i{X}_i$ is the observed error rate. Each $X_i$ may be regarded as a Bernoulli with unknown mean $p$. We would like to know the true — but unknown — error rate $p$. Intuitively, we expect that ${\bar{X}}_n$ should be close to $p$. How likely is ${\bar{X}}_n$ to not be within $ϵ$ of $p$? We have $\mathbb{V}({\bar{X}}_n)=\mathbb{V}(X_1)/n=p(1-p)/n$, and

$$\mathbb{P}(|{\overline{X}}_n-p|>ϵ)\le \frac{\mathbb{V}({\overline{X}}_n)}{{ϵ}^2}=\frac{p(1-p)}{n{ϵ}^2}\le \frac{1}{4n{ϵ}^2}$$

since $p(1-p)\le \frac{1}{4}$ for all $p$. For $ϵ=0.2$ and $n=100$, the bound is 0.0625.

Hoeffding’s Lemma

https://en.wikipedia.org/wiki/Hoeffding%27s_lemma

Hoeffding's Lemma

Let $X$ be any real-values random variable such that $a\le X\le b$. Then for all $t\in \mathbb{R}$,

$$\mathbb{E}[e^{tX}]\le \exp \left(t\mathbb{E}[X]+\frac{t^2(b-a{)}^2}{8}\right),$$

or equivalently,

$$\mathbb{E}\left[e^{t(X-\mathbb{E}[X])}\right]\le \exp \left(\frac{t^2(b-a{)}^2}{8}\right).$$

If $X$ is bounded in $[a,b]$, then the centered variable $X-\mathbb{E}[X]$ has an MGF bounded like a Gaussian.

When coming up with bounds, a common trick is to use the Chernoff / exponential Markov template:

1. Pick what you want to control, usually a sum/mean: $S=\sum (X_i-\mathbb{E}[X_i])$
2. Exponentiate to make it non-negative and allows Markov to be applicable. For any $t>0$,

$$\mathbb{P}(S\ge ϵ)=\mathbb{P}(e^{tS}\ge e^{tϵ})\le \frac{\mathbb{E}[e^{tS}]}{e^{tϵ}}$$

3. Bound the moment generating function $\mathbb{E}[e^{tS}]$: If each $X_i$ are independent, then a product can be pulled out of the exponentiated sum. Then we bound each factor using something like Hoeffding’s Lemma

Hoeffding’s Inequality

https://en.wikipedia.org/wiki/Hoeffding%27s_inequality

Theorem (Hoeffding's Inequality)

Let $X_1,\dots ,X_n$ be independent observations such that $a_i\le X_i\le b_i$. Let $S_n=X_1+\cdots +X_n$. Then, for any $ϵ>0$,

$$\mathbb{P}\left(S_n-\mathbb{E}[S_n]\ge ϵ\right)\le \exp \left(-\frac{2{ϵ}^2}{{\sum }_{i=1}^n(b_i-a_i{)}^2}\right)$$ $$\mathbb{P}\left(|S_n-\mathbb{E}[S_n]|\ge ϵ\right)\le 2\exp \left(-\frac{2{ϵ}^2}{{\sum }_{i=1}^n(b_i-a_i{)}^2}\right)$$

Hoeffding’s inequality can be used when we have independence and bounded observations, and we want high-probability finite-sample bounds. If the data is unbounded or is heavy-tailed, Hoeffding’s inequality can be invalid or overly conservative.

Proof

For any $t>0$, using that $e^{t(\cdot )}$ is increasing:

$$\mathbb{P}(S_n-\mathbb{E}[S_n]\ge ϵ)=\mathbb{P}\left(e^{t(S_n-\mathbb{E}[S_n])}\ge e^{tϵ}\right).$$

Applying Markov’s Inequality to the non-negative random variable $e^{t(S_n-\mathbb{E}[S_n])}$,

$$\mathbb{P}\left(e^{t(S_n-\mathbb{E}[S_n])}\ge e^{tϵ}\right)\le \frac{\mathbb{E}[e^{t(S_n-\mathbb{E}[S_n])}]}{e^{tϵ}}=e^{-tϵ}\mathbb{E}\left[e^{t{\sum }_{i=1}^n{Y}_i}\right]$$

where $Y_i=X_i-\mathbb{E}[X_i]$, with $\mathbb{E}[Y_i]=0$ and $a_i-\mathbb{E}[X_i]\le Y_i\le b_i-\mathbb{E}[X_i]$. If the $X_i$ are independent, so are the $Y_i$, and

$$\mathbb{E}\left[e^{t{\sum }_{i=1}^n{Y}_i}\right]=\prod _{i=1}^n\mathbb{E}[e^{t{Y}_i}].$$

This gives us

$$\mathbb{P}(S_n-\mathbb{E}[S_n]\ge ϵ)\le e^{-tϵ}\prod _{i=1}^n\mathbb{E}[e^{t{Y}_i}].$$

We can then apply Hoeffdings lemma to $Y_i$. Its range is $(\beta -\alpha )=(b_i-\mathbb{E}[X_i])-(a_i-\mathbb{E}[X_i])=b_i-a_i$, so

$$\mathbb{E}[e^{t{Y}_i}]\le \exp \left(\frac{t^2(b_i-a_i{)}^2}{8}\right).$$

Plugging this back in gives

$$\mathbb{P}(S_n-\mathbb{E}[S_n]\ge ϵ)\le e^{-tϵ}\prod _{i=1}^n\exp \left(\frac{t^2(b_i-a_i{)}^2}{8}\right).$$

Combining the product into an exponential sum:

$$\mathbb{P}(S_n-\mathbb{E}[S_n]\ge ϵ)\le \exp \left(-tϵ+\frac{t^2}{8}\sum _{i=1}^n(b_i-a_i{)}^2\right).$$

We now choose $t$ to make the bound as small as possible. Let $V={\sum }_{i=1}^n(b_i-a_i{)}^2$. We want to minimize the exponent $f(t)=-tϵ+\frac{t^{2}V}{8}$. Differentiating and setting to zero: $f^{\prime }(t)=-ϵ+\frac{tV}{4}=0\Rightarrow t^{\ast }=\frac{4ϵ}{V}.$ Plugging back in,

$$f(t^{\ast })=-ϵ\frac{4ϵ}{V}+\frac{V}{8}{\left(\frac{4ϵ}{V}\right)}^2=-\frac{2{ϵ}^2}{V}.$$

Therefore,

$$\mathbb{P}(S_n-\mathbb{E}[S_n]\ge ϵ)\le \exp \left(-\frac{2{ϵ}^2}{{\sum }_{i=1}^n(b_i-a_i{)}^2}\right).$$

The two-sided Hoeffding bound can be easily recovered by applying the same inequality to $-X_i$, where $-b_i\le -X_i\le -a_i$, so we also get

$$\mathbb{P}(\mathbb{E}[S_n]-S_n\ge ϵ)=\mathbb{P}(S_n-\mathbb{E}[S_n]\le -ϵ)\le \exp \left(-\frac{2{ϵ}^2}{{\sum }_{i=1}^n(b_i-a_i{)}^2}\right).$$

and using the union bound:

$$\begin{array}{rl}\mathbb{P}(|S_n-\mathbb{E}[S_n]|\ge ϵ)& \le \mathbb{P}(S_n-\mathbb{E}[S_n]\ge ϵ)+\mathbb{P}(\mathbb{E}[S_n]-S_n\le -ϵ)\\ & \le 2\exp \left(-\frac{2{ϵ}^2}{{\sum }_{i=1}^n(b_i-a_i{)}^2}\right)\end{array}$$

Theorem

Let $X_1,\dots ,X_n\sim \text{Bernoulli}(p)$. Then for any $ϵ>0$,

$$\mathbb{P}(|{\overline{X}}_n-p|>ϵ)\le 2e^{-2n{ϵ}^2}$$

where ${\overline{X}}_n=n^{-1}{\sum }_{i=1}^n{X}_i$.

From Hoeffding to Confidence Intervals

Hoeffding’s inequality also gives a simple way of creating a confidence interval for a binomial parameter $p$. Fix $\alpha >0$ and let

$${ϵ}_n=\sqrt{\frac{1}{2n}\log \left(\frac{2}{\alpha }\right)}.$$

By Hoeffding’s inequality,

$$\mathbb{P}(|{\overline{X}}_n-p|>ϵ)\le 2e^{-2n{ϵ}^2}=\alpha .$$

Let $C=({\overline{X}}_n-{ϵ}_n,{\overline{X}}_n+{ϵ}_n)$. Then $\mathbb{P}(p\notin C)=\mathbb{P}(|{\overline{X}}_n-p|>{ϵ}_n)\le \alpha$. Hence, $\mathbb{P}(p\in C)\ge 1-\alpha$, and we call $C$ a $1-\alpha$ confidence interval.

Mill’s Inequality

The following inequality is useful for bounding probability statements about Normal random variables.

Theorem (Mill's Inequality)

Let $Z\sim \mathcal{N}(0,1)$. Then,

$$\mathbb{P}(|Z|>t)\le \sqrt{\frac{2}{\pi }}\frac{e^{-t^2/2}}{t}.$$