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{aligned} \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{aligned}$$

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{aligned} \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{aligned}$$

This completes the proof. $_\square$

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

By rearrangement, we have

$$\begin{aligned} \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{aligned}$$

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