Chebyshev inequality (arithmetic)

This article covers the Chebyshev arithmetic inequality. For the statistical Chebyshev inequality see Chebyshev inequality .

The Chebyshev inequality (after Pafnuti Lwowitsch Chebyshev ) is an inequality of mathematics .

statement

It says that for monotonically equally ordered n- tuples of real numbers

${\displaystyle a_{1}\geq a_{2}\geq \cdots \geq a_{n}}$

and

${\displaystyle b_{1}\geq b_{2}\geq \cdots \geq b_{n}}$,

the relationship

${\displaystyle n\sum _{i=1}^{n}a_{i}b_{i}\geq \left(\sum _{i=1}^{n}a_{i}\right)\left(\sum _{i=1}^{n}b_{i}\right)}$.

applies. Are and, however, ordered in opposite directions, for example ${\displaystyle a_{i}}$ ${\displaystyle b_{i}}$

${\displaystyle a_{1}\geq a_{2}\geq \cdots \geq a_{n}}$

and

${\displaystyle b_{1}\leq b_{2}\leq \cdots \leq b_{n}}$,

so the inequality applies in the opposite direction

${\displaystyle n\sum _{i=1}^{n}a_{i}b_{i}\leq \left(\sum _{i=1}^{n}a_{i}\right)\left(\sum _{i=1}^{n}b_{i}\right)}$.

Note that, unlike many other inequalities, no preconditions for the signs of and are necessary. ${\displaystyle a_{i}}$ ${\displaystyle b_{i}}$

proofs

Proof from rearrangement inequality

The Chebyshev total inequality can be derived from the rearrangement inequality . If you multiply the right side, the result is

${\displaystyle \left(\sum _{i=1}^{n}a_{i}\right)\left(\sum _{i=1}^{n}b_{i}\right)=\left(a_{1}b_{1}+a_{2}b_{2}+\dots +a_{n-1}b_{n-1}+a_{n}b_{n}\right)}$

${\displaystyle +\left(a_{1}b_{2}+a_{2}b_{3}+\dots +a_{n-1}b_{n}+a_{n}b_{1}\right)}$

${\displaystyle +\left(a_{1}b_{3}+a_{2}b_{4}+\dots +a_{n-1}b_{1}+a_{n}b_{2}\right)}$

${\displaystyle +\dots }$

${\displaystyle +\left(a_{1}b_{n}+a_{2}b_{1}+\dots +a_{n-1}b_{n-2}+a_{n}b_{n-1}\right)}$

Because of the rearrangement inequality , each of these sums (in the case of identically ordered numbers and ) is now smaller or equal , so overall you get exactly the desired relationship ${\displaystyle n}$ ${\displaystyle a_{i}}$ ${\displaystyle b_{i}}$ ${\displaystyle \left(a_{1}b_{1}+a_{2}b_{2}+\dots +a_{n-1}b_{n-1}+a_{n}b_{n}\right)}$

${\displaystyle \left(\sum _{i=1}^{n}a_{i}\right)\left(\sum _{i=1}^{n}b_{i}\right)\leq n\left(a_{1}b_{1}+a_{2}b_{2}+\dots +a_{n-1}b_{n-1}+a_{n}b_{n}\right)}$.

In the case of oppositely ordered numbers and the rearrangement inequality only needs to be applied in the opposite direction. ${\displaystyle a_{i}}$ ${\displaystyle b_{i}}$

Proof with complete induction

The Chebyshev sum inequality can also be proven with complete induction and application of the rearrangement inequality for the simplest case with two summands. The induction start is easy to manage. Now consider in the induction step

${\displaystyle \left(a_{n+1}+\sum _{i=1}^{n}a_{i}\right)\left(b_{n+1}+\sum _{i=1}^{n}b_{i}\right)=a_{n+1}b_{n+1}+\sum _{i=1}^{n}\left(a_{n+1}b_{i}+a_{i}b_{n+1}\right)+\left(\sum _{i=1}^{n}a_{i}\right)\left(\sum _{i=1}^{n}b_{i}\right)}$.

If we now apply the rearrangement inequality for two summands to the middle term and the induction assumption to the last term, we get (in the case of identically ordered numbers and ) ${\displaystyle a_{i}}$ ${\displaystyle b_{i}}$

${\displaystyle \left(a_{n+1}+\sum _{i=1}^{n}a_{i}\right)\left(b_{n+1}+\sum _{i=1}^{n}b_{i}\right)\leq a_{n+1}b_{n+1}+\sum _{i=1}^{n}\left(a_{i}b_{i}+a_{n+1}b_{n+1}\right)+n\sum _{i=1}^{n}a_{i}b_{i}}$

${\displaystyle =a_{n+1}b_{n+1}+\sum _{i=1}^{n}a_{i}b_{i}+na_{n+1}b_{n+1}+n\sum _{i=1}^{n}a_{i}b_{i}=(n+1)\sum _{i=1}^{n+1}a_{i}b_{i}.}$

In the case of oppositely ordered numbers and the proof is analogous. ${\displaystyle a_{i}}$ ${\displaystyle b_{i}}$

Proof from equation formulation

Another proof is straight from the equation

${\displaystyle n\sum _{i=1}^{n}a_{i}b_{i}-\left(\sum _{i=1}^{n}a_{i}\right)\left(\sum _{i=1}^{n}b_{i}\right)=\sum _{i=1}^{n}\sum _{k=i+1}^{n}(a_{i}-a_{k})(b_{i}-b_{k})={\frac {1}{2}}\sum _{i=1}^{n}\sum _{k=1}^{n}(a_{i}-a_{k})(b_{i}-b_{k})}$

or more generally with weights ${\displaystyle w_{i}}$

${\displaystyle \sum _{i=1}^{n}w_{i}\sum _{i=1}^{n}w_{i}a_{i}b_{i}-\left(\sum _{i=1}^{n}w_{i}a_{i}\right)\left(\sum _{i=1}^{n}w_{i}b_{i}\right)={\frac {1}{2}}\sum _{i=1}^{n}\sum _{k=i}^{n}w_{i}w_{k}(a_{i}-a_{k})(b_{i}-b_{k})}$.

It is true

${\displaystyle \sum _{i=1}^{n}w_{i}\sum _{k=1}^{n}w_{k}a_{k}b_{k}-\left(\sum _{i=1}^{n}w_{i}a_{i}\right)\left(\sum _{k=1}^{n}w_{k}b_{k}\right)=\sum _{i=1}^{n}\sum _{k=1}^{n}\left(w_{i}w_{k}a_{k}b_{k}-w_{i}w_{k}a_{i}b_{k}\right)}$.

Renaming the indices results in

${\displaystyle \sum _{i=1}^{n}\sum _{k=1}^{n}\left(w_{i}w_{k}a_{k}b_{k}-w_{i}w_{k}a_{i}b_{k}\right)=\sum _{k=1}^{n}\sum _{i=1}^{n}\left(w_{i}w_{k}a_{i}b_{i}-w_{i}w_{k}a_{k}b_{i}\right)}$,

all in all exactly the assertion:

${\displaystyle \sum _{i=1}^{n}w_{i}\sum _{k=1}^{n}w_{k}a_{k}b_{k}-\left(\sum _{i=1}^{n}w_{i}a_{i}\right)\left(\sum _{k=1}^{n}w_{k}b_{k}\right)={\frac {1}{2}}\sum _{i=1}^{n}\sum _{k=1}^{n}w_{i}w_{k}\left(a_{k}b_{k}-a_{i}b_{k}+a_{i}b_{i}-a_{k}b_{i}\right)={\frac {1}{2}}\sum _{i=1}^{n}\sum _{k=1}^{n}w_{i}w_{k}\left(a_{i}-a_{k}\right)\left(b_{i}-b_{k}\right)}$.

generalization

The Chebyshev total inequality can also be expressed in the form

${\displaystyle {\frac {1}{n}}\sum _{i=1}^{n}a_{i}b_{i}\geq \left({\frac {1}{n}}\sum _{i=1}^{n}a_{i}\right)\left({\frac {1}{n}}\sum _{i=1}^{n}b_{i}\right).}$

write. In this form, it can also be generalized to more than two equally ordered n- tuples , although the numbers considered must be greater than or equal to zero: For

${\displaystyle a_{j}=\left(a_{j,1},\dots ,a_{j,n}\right);j=1,\dots ,m}$

With

${\displaystyle a_{j,1}\geq a_{j,2}\geq \dots \geq a_{j,n}\geq 0.}$

applies

${\displaystyle {\frac {1}{n}}\sum _{i=1}^{n}\prod _{j=1}^{m}a_{j,i}\geq \prod _{j=1}^{m}\left({\frac {1}{n}}\sum _{i=1}^{n}a_{j,i}\right).}$

The proof can, for example, be carried out with complete induction according to , since for non-negative numbers ordered with respect to decreasing also their products ${\displaystyle m}$ ${\displaystyle i}$ ${\displaystyle a_{j_{i}}}$

${\displaystyle \prod _{j=1}^{m}a_{j,1}\geq \prod _{j=1}^{m}a_{j,2}\geq \dots \geq \prod _{j=1}^{m}a_{j,n}\geq 0}$

are descending and are nonnegative.

variants

Are monotonous to the same direction and is a weight function, i. H. then ${\displaystyle f,\,g}$ ${\displaystyle [0,1]}$ ${\displaystyle \omega \colon [0,1]\to \mathbb {R} _{\geq 0}}$ ${\displaystyle \int _{0}^{1}\omega (x)dx=1}$

${\displaystyle \int _{0}^{1}\omega (x)f(x)g(x)dx\geq \int _{0}^{1}\omega (x)f(x)dx\;\int _{0}^{1}\omega (x)g(x)dx}$.

To prove this, one integrates the nonnegative function multiplied by x and y from 0 to 1. This can be further generalized: ${\displaystyle \omega (x)\omega (y){\Big (}f(x)-f(y){\Big )}{\Big (}g(x)-g(y){\Big )}}$

Are monotonous and nonnegative then is in the same direction ${\displaystyle f_{0},\ldots ,f_{n}}$ ${\displaystyle [0,1]}$

${\displaystyle \int _{0}^{1}\omega (x)\prod _{k=0}^{n}f_{k}\,dx\geq \prod _{k=0}^{n}\int _{0}^{1}\omega (x)f_{k}\,dx}$.

And are monotonous and nonnegative on the same direction and then is a weight function ${\displaystyle f_{0},...,f_{n}}$ ${\displaystyle [a,b]}$ ${\displaystyle \omega \colon [a,b]\to \mathbb {R} _{\geq 0}}$

${\displaystyle \int _{a}^{b}\omega (x)\prod _{k=0}^{n}f_{k}\,dx\geq {\frac {1}{(b-a)^{n-1}}}\prod _{k=0}^{n}\int _{a}^{b}\omega (x)f_{k}\,dx}$.

This is the result of substituting x with . ${\displaystyle {\frac {x-a}{b-a}}}$

See also

• Chebyshev's inequality - an inequality in the field of stochastics , which also after Pafnuty Chebyshev was named

Individual evidence

1. ↑ Harro Heuser : Textbook of Analysis Part 1. Wiesbaden, Vieweg + Teubner , Verlag 2003, ISBN 3-322-96828-6 , p. 99.
2. ↑ Martin Aigner : Diskrete Mathematik , 6th, corrected edition, Vieweg, Wiesbaden 2006, ISBN 978-3-8348-0084-8 , p. 54.