inequalities in fundamental statistics

Hoeffding’s Inequality

Given $n(n>0)$ i.i.d. random variables $X_1,X_2,...,X_n \overset{iid}{\sim}$ that are almost surely bounded – meaning $\mathbf{P}(X \notin [a,b])=0$:

$\mathbf{P}\left(\left| \bar{X_n} - \mathbb{E}[X]\right| \ge \epsilon\right) \le 2 \exp\left(-{2n\epsilon^2 \over (b-a)^2}\right) \qquad \text{for all }\epsilon \gt 0$

Unlike for the central limit theorem, here the sample size $n$ does not need to be large.

Markov inequality

For a random variable $X\ge 0$ with mean $\mu \gt 0$, and any number $t \gt 0$:

$\mathbf{P}(X \ge t) \le {\mu \over t}$.

Note that the Markov inequality is restricted to non-negative random variables.

Chebyshev inequality

For a random variable $X$ with (finite) mean $\mu$ and variance $\sigma^2$, and for any number $t \ge 0$,

$\mathbf{p}\left(\left| X - \mu \right| \ge t\right) \le {\sigma^2 \over t^2}$

Remark:
When Markov inequality $\left(X-\mu\right)^2$ is applied to , we obtain Chebyshev’s inequality. Markov inequality is also used in the proof of Hoeffding’s inequality.