Markov Inequality: if X is a a positive random variable with small mean, it is unlikely to be very large
Let X be a random variable such that X >= 0.
$ \textrm{Pr}(X \geq a) \leq \frac{\textrm{E}(X)}{a}. $
Proof (discrete case):
$ \textrm{Pr}(X \geq a) = {\sum_{x \geq a} P_x(x)} $
$ {\sum_{x \geq a} P_x(x)} \leq {\sum_{x \geq a} P_x(x) \cdot \frac{x}{a}} $
$ {\sum_{x \geq a} P_x(x) \cdot \frac{x}{a}} = \frac{1}{a} {\sum_{x \geq a} x\cdot P_x(x)} $
$ \frac{1}{a} {\sum_{x \geq a} x\cdot P_x(x)} \leq \frac{1}{a} {\sum_{x} x\cdot P_x(x)} $
$ \frac{1}{a} {\sum_{x} x\cdot P_x(x)} = \frac{\textrm{E}(X)}{a} $
Chebyshev inequality:
Any RV is likely to be close to its mean
for any c >0, any x:
$ \textrm{Pr}(|x - \textrm{E}(X)| \geq c) \leq \frac{\operatorname{Var}(X)}{c^2}. $
This can be proved by letting $ Y = (x - \textrm{E}(X))^2 $ and using the markov inequality.
