Randomised Algorithms

markov inequality

chebyshev inequality

in general, given $f:\mathbb{R}\to [0,\infty )$ and increasing, then $P(X\ge a)\le P\left(f(X)\ge f(a)\right)\le \frac{E(f(X))}{f(a)}$ and similarly for decreasing with the signs reversed.

chernoff bound