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}\geq a_{2}\geq \cdots \geq a_{n}$

und

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

die Beziehung

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

gilt. Sind $a_{i}$ und $b_{i}$ hingegen entgegengesetzt geordnet, also beispielsweise

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

und

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

so gilt die Ungleichung in umgekehrte Richtung

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

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)=\left(a_{1}b_{1}+a_{2}b_{2}+\dots +a_{n-1}b_{n-1}+a_{n}b_{n}\right)$

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

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

$+\dots$

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

Wegen der Umordnungs-Ungleichung ist nun jede dieser $n$ Summen (im Fall gleich geordneter Zahlen $a_{i}$ und $b_{i}$) kleiner oder gleich $\left(a_{1}b_{1}+a_{2}b_{2}+\dots +a_{n-1}b_{n-1}+a_{n}b_{n}\right)$, 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)\leq n\left(a_{1}b_{1}+a_{2}b_{2}+\dots +a_{n-1}b_{n-1}+a_{n}b_{n}\right)$.

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

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

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

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

$=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}.$

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}\left(w_{i}w_{k}a_{k}b_{k}-w_{i}w_{k}a_{i}b_{k}\right)$.

Mit Umbenennung der Indizes ergibt sich

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

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

Verallgemeinerung

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

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

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}=\left(a_{j,1},\dots ,a_{j,n}\right);j=1,\dots ,m$

mit

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

gilt

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

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}\geq \prod _{j=1}^{m}a_{j,2}\geq \dots \geq \prod _{j=1}^{m}a_{j,n}\geq 0$

fallend geordnet und nichtnegativ sind.

Varianten

Sind $f,\,g$ auf $[0,1]$ gleichsinnig monoton und ist $\omega \colon [0,1]\to \mathbb {R} _{\geq 0}$ eine Gewichtsfunktion, d. h. $\int _{0}^{1}\omega (x)dx=1$ dann ist

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

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

Sind $f_{0},\ldots ,f_{n}$ auf $[0,1]$ gleichsinnig monoton und nichtnegativ dann ist

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

Und sind $f_{0},...,f_{n}$ auf $[a,b]$ gleichsinnig monoton und nichtnegativ und ist $\omega \colon [a,b]\to \mathbb {R} _{\geq 0}$ eine Gewichtsfunktion dann ist

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

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