Chebyshev's Inequality

Chebyshev's inequality is a statement about nonincreasing sequences; i.e. sequences \(a_1 \geq a_2 \geq \cdots \geq a_n\) and \(b_1 \geq b_2 \geq \cdots \geq b_n\). It can be viewed as an extension of the rearrangement inequality, making it useful for analyzing the dot product of the two sequences.

Chebyshev's inequality states that

\[\begin{eqnarray} \dfrac{a_1b_1+a_2b_2+\cdots+a_nb_n}{n} &\ge &\dfrac{a_1+a_2+\cdots+a_n}{n} \times \dfrac{b_1+b_2+\cdots+b_n}{n} \\ &\ge &\dfrac{a_1b_n+a_2b_{n-1}+\cdots+a_nb_1}{n}, \end{eqnarray}\]

or equivalently,

\[{\frac { \sum _{ i=1 }^{ n }{ { a }_{ i }{ b }_{ i } } }{ n } \ge \frac { \sum _{ i=1 }^{ n }{ { a }_{ i } } }{ n } \times \frac { \sum _{ i=1 }^{ n }{ { b }_{ i } } }{ n } \ge \frac { \sum _{ i=1 }^{ n }{ { a }_{ i }{ b }_{ n+1-i } } }{ n } }.\]

The intuition that the sum of pairwise products is maximized by a greedy algorithm is supplied by the rearrangement inequality, which assures that \(a_1b_1+a_2b_2+\cdots+a_nb_n\) is the maximum possible result of adding pairwise products. Chebyshev's inequality gives a useful lower bound on what the precise value of \(a_1b_1+\cdots+a_nb_n\) can be.

The proof of Chebyshev's inequality is very similar to the proof of the rearrangement inequality:

Since \(a_1\ge a_2\ge \cdots\ge a_n\) and \(b_1\ge b_2\ge \cdots \ge b_n,\) the following holds for any \(i\) and \(j\):

\[\left( { a }_{ i }-{ a }_{ j } \right) \left( { b }_{ i }-{ b }_{ j } \right) \ge 0 \Rightarrow { a }_{ i }{ b }_{ i }+{ a }_{ j }{ b }_{ j }\ge { a }_{ i }{ b }_{ j }+{ a }_{ j }{ b }_{ i }.\]

Adding all the \(n^2\) inequalities, we have

\[\begin{align} \sum _{ i }^{ }{ \sum _{ j }^{ }{ ({ a }_{ i }{ b }_{ i }+{ a }_{ j }{ b }_{ j }) } } &\ge \sum _{ i }^{ }{ \sum _{ j }^{ }{ { (a }_{ i }{ b }_{ j }+{ a }_{ j }{ b }_{ i }) } } \\ 2n\sum _{ i }^{ }{ { a }_{ i }{ b }_{ i } } &\ge \sum _{ i }^{ }{ { a }_{ i } } \sum _{ j }^{ }{ { b }_{ j } } +\sum _{ j }^{ }{ { a }_{ j } } \sum _{ i }^{ }{ { b }_{ i } } \\ 2n\sum _{ i }^{ }{ a_{ i }{ b }_{ i }} &\ge 2\left( \sum _{ i }^{ }{ { a }_{ i } } \right) \left( \sum _{ j }^{ }{ { b }_{ j } } \right) \\ n\sum _{ i=1 }^{ n }{ a_{ i }{ b }_{ i }} &\ge \left( \sum _{ i=1 }^{ n }{ { a }_{ i } } \right) \left( \sum _{ j=1 }^{ n }{ { b }_{ j } } \right) . \end{align}\]

This completes the proof. \(_\square\)

The rearrangement inequality can also be used to prove Chebyshev's inequality:

By rearrangement, we have

\[\begin{align} \sum_{i=1}^n a_ib_i &\geq a_1b_1+a_2b_2+\cdots+a_nb_n\\ \sum_{i=1}^n a_ib_i &\geq a_1b_2+a_2b_3+\cdots+a_nb_1\\ \sum_{i=1}^n a_ib_i &\geq a_1b_3+a_2b_4+\cdots+a_nb_2\\ &\vdots\\ \sum_{i=1}^n a_ib_i &\geq a_1b_n+a_2b_1+\cdots+a_nb_{n-1}, \end{align}\]

and adding these \(n\) inequalities gives the result. \(_\square\)

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 \(a,b,c,x,y,z\) be positive reals such that \(a+b+c=7\) and \(x+y+z=15\). What is the smallest possible value of \(ax+by+cz?\)

---

Bogus solution: By Chebyshev's inequality, we have

\[\frac{ax+by+cz}{3} \geq \frac{a+b+c}{3} \cdot \frac{x+y+z}{3} = \frac{35}{3},\]

so the minimum possible value of \(ax+by+cz\) is 35.

The above solution does not work because it implicitly assumes that \(a,b,c\) and \(x,y,z\) are similarly ordered, which is not necessarily the case. Indeed, taking \(a=4, b=2, c=1, x=4, y=5, z=6\) gives \(ax+by+cz=32\), 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. \(a \geq b \geq c),\) and examining an inequality chain this applies. Two common examples to keep in mind include the following:

• \(a \geq b \geq c \implies a+b \geq a+c \geq b+c\)
• \(a \geq b \geq c \implies \frac{1}{a} \leq \frac{1}{b} \leq \frac{1}{c}.\)

These can be combined:

Let \(a,b,c\) be positive real numbers. Show that

\[\frac{ab}{a+b}+\frac{bc}{b+c}+\frac{ca}{c+a} \leq \frac{3(ab+bc+ca)}{2(a+b+c)}.\]

---

Assume without loss of generality that \(a \geq b \geq c\). This implies that \(\frac{1}{a} \leq \frac{1}{b} \leq \frac{1}{c}\), and so \(\frac{1}{a}+\frac{1}{b} \leq \frac{1}{a}+\frac{1}{c} \leq \frac{1}{b}+\frac{1}{c}\). Taking the reciprocal again gives

\[\frac{1}{\frac{1}{a}+\frac{1}{b}} \geq \frac{1}{\frac{1}{a}+\frac{1}{c}} \geq \frac{1}{\frac{1}{b}+\frac{1}{c}} \implies \frac{ab}{a+b} \geq \frac{ac}{a+c} \geq \frac{bc}{b+c}\]

It is also true that

\[a+b \geq a+c \geq b+c.\]

Applying Chebyshev's inequality to these two sequences gives

\[(a+b)\left(\frac{ab}{a+b}\right)+(a+c)\left(\frac{ac}{a+c}\right)+(b+c)\left(\frac{bc}{b+c}\right) \geq \frac{1}{3}\big((a+b)+(b+c)+(c+a)\big)\left(\frac{ab}{a+b}+\frac{ac}{a+c}+\frac{bc}{b+c}\right),\]

which rearranges to the desired result. \(_\square\)

There is also a continuous version of Chebyshev's inequality: if \(f\) and \(g\) are both non-increasing functions or both non-decreasing functions over \([0,1]\), and both are integrable over that interval, then

\[\int_0^1 f(x)g(x)\, dx \geq \int_0^1 f(x)\, dx\int_0^1 g(x)\, dx.\]

• Rearrangement Inequality