There are several famous inequalities in the theory of probability. The simplest one is the Markov inequality:
for any random variable and real number .
If we consider the random variable , substitute into the Markov inequality, we have
By substituting where , we have the Chebyshev inequality
which it is required that and is non-zero and finite.
Two other useful but more complicated probability inequalities are about deviation from mean. The Chernoff bound says that, for i.i.d. Bernoulli random variables , each having the probability , the probability of having more than occurrences among the of them is
While these Bernoulli random variable shall produce the expectation of occurrences, the probability of deviation from is bounded by the Hoefding’s inequality, saying that for , the probability of no less than occurrences is
and the probability of no more than occurrences is
so the probability of having occurrences, which , is
Hoefding’s inequality can be generalized so that, for a.s. and are independent, we have the empirical mean and its expectation
then for we have