Chebyshev's inequality states that
The intuition that the sum of pairwise products is maximized by a greedy algorithm is supplied by the rearrangement inequality, which assures that is the maximum possible result of adding pairwise products. Chebyshev's inequality gives a useful lower bound on what the precise value of can be.
The proof of Chebyshev's inequality is very similar to the proof of the rearrangement inequality:
Since and the following holds for any and :
Adding all the inequalities, we have
This completes the proof.
The rearrangement inequality can also be used to prove Chebyshev's inequality:
By rearrangement, we have
and adding these inequalities gives the result.
Because Chebyshev's inequality requires the knowledge of how the variables are ordered, it cannot be used directly in many cases. For instance, take a look at the following problem:
Let be positive reals such that and . What is the smallest possible value of
Bogus solution: By Chebyshev's inequality, we have
so the minimum possible value of is 35.
The above solution does not work because it implicitly assumes that and are similarly ordered, which is not necessarily the case. Indeed, taking gives , which is significantly smaller than the supposed minimum of 35.
As a result, Chebyshev's can only be used when an ordering of variables is given or determined. This means it is often applied by assuming a particular ordering without loss of generality e.g. and examining an inequality chain this applies. Two common examples to keep in mind include the following:
These can be combined:
Let be positive real numbers. Show that
Assume without loss of generality that . This implies that , and so . Taking the reciprocal again gives
It is also true that
Applying Chebyshev's inequality to these two sequences gives
which rearranges to the desired result.
There is also a continuous version of Chebyshev's inequality: if and are both non-increasing functions or both non-decreasing functions over , and both are integrable over that interval, then