# Chebyshev's Inequality

**Chebyshev's inequality** is a statement about nonincreasing sequences; i.e. sequences \(a_1 \geq a_2 \geq \ldots \geq a_n\) and \(b_1 \geq b_2 \geq \ldots \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.

## Definition

Chebyshev's inequality states that

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

Or, equivalently,

\[\large{\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 } }. \ _\square\]

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+\ldots+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+\ldots+a_nb_n\) can be.

## Proof

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 all \(i \ne 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\choose2\) 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 \[\sum_{i=1}^n a_ib_i \geq a_1b_1+a_2b_2+\ldots+a_nb_n\] \[\sum_{i=1}^n a_ib_i \geq a_1b_2+a_2b_3+\ldots+a_nb_1\] \[\sum_{i=1}^n a_ib_i \geq a_1b_3+a_2b_4+\ldots+a_nb_2\] \[\vdots\] \[\sum_{i=1}^n a_ib_i \geq a_1b_n+a_2b_1+\ldots+a_nb_{n-1}\] and adding these \(n\) inequalities gives the result.

## Strategies and applications

Because Chebyshev's inequality requires the knowledge of how the variables are ordered, it cannot be used directly in many cases. For instance,

## 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:

- \(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)}\]

Solution: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}((a+b)+(b+c)+(c+a))\left(\frac{ab}{a+b}+\frac{ac}{a+c}+\frac{bc}{b+c}\right)\]

which rearranges to the desired result.

## Continuous version

There is also a continuous version of Chebyshev's inequality: if \(f\) and \(g\) are both non-increasing 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\]

## See Also

**Cite as:**Chebyshev's Inequality.

*Brilliant.org*. Retrieved from https://brilliant.org/wiki/chebyshev-inequality/