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 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 erfolgen, da ja für bezüglich 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

Basierend auf einem Artikel in:

Wikipedia.de