Tschebyscheff-Ungleichung (Arithmetik)

Die Tschebyscheff-Ungleichung (nach Pafnuti Lwowitsch Tschebyschow) ist eine Ungleichung der Mathematik.

Aussage

Sie besagt, dass für monoton gleich geordnete n-Tupel reeller Zahlen

$a_1\ge a_2\ge \cdots \ge a_n$

und

$b_1\ge b_2\ge \cdots \ge b_n$,

die Beziehung

$n\sum _{i=1}^n{a}_i{b}_i\ge \left(\sum _{i=1}^n{a}_i\right)\left(\sum _{i=1}^n{b}_i\right)$.

gilt. Sind $a_i$ und $b_i$ hingegen entgegengesetzt geordnet, also beispielsweise

$a_1\ge a_2\ge \cdots \ge a_n$

und

$b_1\le b_2\le \cdots \le b_n$,

so gilt die Ungleichung in umgekehrte Richtung

$n\sum _{i=1}^n{a}_i{b}_i\le \left(\sum _{i=1}^n{a}_i\right)\left(\sum _{i=1}^n{b}_i\right)$.

Man beachte, dass im Gegensatz zu vielen anderen Ungleichungen keine Voraussetzungen für die Vorzeichen von $a_i$ und $b_i$ notwendig sind.

Beweise

Beweis aus Umordnungs-Ungleichung

Die Tschebyschew-Summenungleichung lässt sich aus der Umordnungs-Ungleichung ableiten. Multipliziert man die rechte Seite aus, so ergibt sich

$\left(\sum _{i=1}^n{a}_i\right)\left(\sum _{i=1}^n{b}_i\right)=(a_1{b}_1+a_2{b}_2+\dots +a_{n-1}{b}_{n-1}+a_n{b}_n)$

$+(a_1{b}_2+a_2{b}_3+\dots +a_{n-1}{b}_n+a_n{b}_1)$

$+(a_1{b}_3+a_2{b}_4+\dots +a_{n-1}{b}_1+a_n{b}_2)$

$+\dots$

$+(a_1{b}_n+a_2{b}_1+\dots +a_{n-1}{b}_{n-2}+a_n{b}_{n-1})$

Wegen der Umordnungs-Ungleichung ist nun jede dieser $n$ Summen (im Fall gleich geordneter Zahlen $a_i$ und $b_i$) kleiner oder gleich $(a_1{b}_1+a_2{b}_2+\dots +a_{n-1}{b}_{n-1}+a_n{b}_n)$, insgesamt erhält man also genau die gewünschte Beziehung

$\left(\sum _{i=1}^n{a}_i\right)\left(\sum _{i=1}^n{b}_i\right)\le n(a_1{b}_1+a_2{b}_2+\dots +a_{n-1}{b}_{n-1}+a_n{b}_n)$.

Im Fall entgegengesetzt geordneter Zahlen $a_i$ und $b_i$ braucht die Umordnungs-Ungleichung nur in die umgekehrte Richtung angewendet werden.

Beweis mit vollständiger Induktion

Die Tschebyschew-Summenungleichung lässt sich auch mit vollständiger Induktion und Anwendung der Umordnungs-Ungleichung für den einfachsten Fall mit zwei Summanden beweisen. Der Induktionsanfang ist einfach zu führen. Im Induktionsschritt betrachtet man nun

$(a_{n+1}+\sum _{i=1}^n{a}_i)(b_{n+1}+\sum _{i=1}^n{b}_i)=a_{n+1}{b}_{n+1}+\sum _{i=1}^n(a_{n+1}{b}_i+a_i{b}_{n+1})+\left(\sum _{i=1}^n{a}_i\right)\left(\sum _{i=1}^n{b}_i\right)$.

Wendet man nun auf den mittleren Summanden die Umordnungs-Ungleichung für zwei Summanden und auf den letzten Summanden die Induktionsvoraussetzung an, so ergibt sich (im Fall gleich geordneter Zahlen $a_i$ und $b_i$)

$(a_{n+1}+\sum _{i=1}^n{a}_i)(b_{n+1}+\sum _{i=1}^n{b}_i)\le a_{n+1}{b}_{n+1}+\sum _{i=1}^n(a_i{b}_i+a_{n+1}{b}_{n+1})+n\sum _{i=1}^n{a}_i{b}_i$

$=a_{n+1}{b}_{n+1}+\sum _{i=1}^n{a}_i{b}_i+n{a}_{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.$

Im Fall entgegengesetzt geordneter Zahlen $a_i$ und $b_i$ ist der Beweis analog.

Beweis aus Gleichungs-Formulierung

Ein anderer Beweis ergibt sich direkt aus der Gleichung

$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)$

bzw. allgemeiner mit Gewichten $w_i$

$\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)$.

Es gilt nämlich

$\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(w_i{w}_k{a}_k{b}_k-w_i{w}_k{a}_i{b}_k)$.

Mit Umbenennung der Indizes ergibt sich

$\sum _{i=1}^n\sum _{k=1}^n(w_i{w}_k{a}_k{b}_k-w_i{w}_k{a}_i{b}_k)=\sum _{k=1}^n\sum _{i=1}^n(w_i{w}_k{a}_i{b}_i-w_i{w}_k{a}_k{b}_i)$,

insgesamt also genau die Behauptung:

$\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(a_k{b}_k-a_i{b}_k+a_i{b}_i-a_k{b}_i)=\frac{1}{2}\sum _{i=1}^n\sum _{k=1}^n{w}_i{w}_k(a_i-a_k)(b_i-b_k)$.

Verallgemeinerung

Die Tschebyschew-Summenungleichung lässt sich auch in der Form

$\frac{1}{n}\sum _{i=1}^n{a}_i{b}_i\ge \left(\frac{1}{n}\sum _{i=1}^n{a}_i\right)\left(\frac{1}{n}\sum _{i=1}^n{b}_i\right).$

schreiben. In dieser Form lässt sie sich auch auf mehr als zwei gleich geordnete n-Tupel verallgemeinern, wobei die betrachteten Zahlen allerdings größer oder gleich Null sein müssen: Für

$a_j=(a_{j,1},\dots ,a_{j,n});j=1,\dots ,m$

mit

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

gilt

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

Der Beweis kann beispielsweise mit vollständiger Induktion nach $m$ erfolgen, da ja für bezüglich $i$ fallend geordnete nichtnegative Zahlen $a_{j_i}$ auch deren Produkte

$\prod _{j=1}^m{a}_{j,1}\ge \prod _{j=1}^m{a}_{j,2}\ge \dots \ge \prod _{j=1}^m{a}_{j,n}\ge 0$

fallend geordnet und nichtnegativ sind.

Varianten

Sind $f,g$ auf $[0,1]$ gleichsinnig monoton und ist $\omega :[0,1]\to {ℝ}_{\ge 0}$ eine Gewichtsfunktion, d. h. $\underset{0}{\overset{1}{\int }}\omega (x)dx=1$ dann ist

$\underset{0}{\overset{1}{\int }}\omega (x)f(x)g(x)dx\ge \underset{0}{\overset{1}{\int }}\omega (x)f(x)dx\underset{0}{\overset{1}{\int }}\omega (x)g(x)dx$.

Zum Beweis integriert man die nichtnegative Funktion $\omega (x)\omega (y)(f(x)-f(y))(g(x)-g(y))$ ausmultipliziert nach x und y jeweils von 0 bis 1. Dies lässt sich weiter verallgemeinern:

Sind $f_0,\dots ,f_n$ auf $[0,1]$ gleichsinnig monoton und nichtnegativ dann ist

$\underset{0}{\overset{1}{\int }}\omega (x)\prod _{k=0}^n{f}_{k}dx\ge \prod _{k=0}^n\underset{0}{\overset{1}{\int }}\omega (x)f_{k}dx$.

Und sind $f_0,...,f_n$ auf $[a,b]$ gleichsinnig monoton und nichtnegativ und ist $\omega :[a,b]\to {ℝ}_{\ge 0}$ eine Gewichtsfunktion dann ist

$\underset{a}{\overset{b}{\int }}\omega (x)\prod _{k=0}^n{f}_{k}dx\ge \frac{1}{(b-a{)}^{n-1}}\prod _{k=0}^n\underset{a}{\overset{b}{\int }}\omega (x)f_{k}dx$.

Dies ergibt sich wenn man x durch $\frac{x-a}{b-a}$ substituiert.

Siehe auch

• Tschebyschow-Ungleichung – eine Ungleichung aus dem Bereich der Stochastik, die ebenfalls nach Pafnuti Lwowitsch Tschebyschow benannt wurde