10. Estimates

Markov

Theorem

Let $X$ be a random variable that takes only non-negative values. Then for all $t\in \mathbb{R}$ with $t>0$,

$$\begin{array}{rl}& \mathrm{Pr}[X\ge t]\le \frac{\mathbb{E}[X]}{t}\\ ⟺& \mathrm{Pr}[X\ge t\cdot \mathbb{E}[X]]\le \frac{1}{t}.\end{array}$$

Chebyshev

Theorem

Let $X$ be a random variable and $t\in \mathbb{R}$ with $t>0$.

\begin{align} &\Pr\bigl[\,|X - \mathbb{E}[X]| \geq t\,\bigr] \leq \frac{\mathrm{Var}[X]}{t^2} \\ \iff &\Pr\bigl[\,|X - \mathbb{E}[X]| \geq t \cdot \sigma\,\bigr] \leq \frac{1}{t^2} \end{align}$$ where $\sigma := \sqrt{\mathrm{Var}[X]}$ is the standard deviation of $X$.

For binomial