Markov's Inequality

Expectation of a non-negative random variable $Z$ can be written (tail-sum formula) as

Since $\mathbb{P}[Z\ge x]$ is monotonically nonincreasing, we have

Rearranging this, we get Markov's inequality:

Chebyshev's Inequality

Applying Markov's inequality on the random variable $(Z-\mathbb{E}[Z]{)}^2$, we get:

This can be used to derive that given a sequence $Z_1,Z_2,\dots ,Z_m$ of i.i.d. random variables with $\mathbb{E}[Z]=\mu$ and $\text{Var}[Z]\le 1$, then for any $\delta \in (0,1)$ with probability at least $1-\delta$, we have:

(polynomial bound for the estimation error of the mean)

Chernoff's bounds

For independent Bernoulli random variables $Z_1,Z_2,\dots ,Z_m$ where $\mathrm{\forall }i,\mathbb{P}[Z_i=1]=p_i$, denoting $p=\sum _{i=1}^m{p}_i$ and $Z=\sum _{i=1}^m{Z}_i$, we can show that:

and

Hoeffding's Inequality

For a sequence of i.i.d. random variables $Z_1,Z_2,\dots ,Z_m$ with $\mathbb{E}[Z]=\mu$ and $\mathbb{P}[a\le Z\le b]=1$, we have for any $ϵ>0$,

Proof:
Let $X_i=Z_i-\mu$ and $\overline{X}=\frac{1}{m}\sum _i^m{X}_i=\overline{Z}-\mu$. Using Markov's inequality, we have that for any $\lambda >0$ and $ϵ>0$,

Hoeffding's lemma: For a random variable $X$ bounded between $a$ and $b$ with mean zero, for every $\lambda >0$, we have $\mathbb{E}[e^{\lambda X}]\le \exp \left(\frac{{\lambda }^2(b-a{)}^2}{8}\right)$.

Using independence and Hoeffding's lemma, we can obtain:

The exponent $-\lambda ϵ+{\lambda }^2(b-a{)}^2/8m$ is minimized for $\lambda =\frac{4mϵ}{(b-a{)}^2}$ yielding:

For the other side, we can apply the same argument on the variable $-\overline{X}$ to obtain:

Combining the two cases yields the desired bound.