Tschebyscheff-Ungleichung (Arithmetik)

Die Tschebyscheff-Ungleichung (nach Pafnuti Lwowitsch Tschebyschow) ist eine Ungleichung der Mathematik.^[1][2]

Sie besagt, dass für monoton gleich geordnete ${\displaystyle n}$-Tupel reeller Zahlen

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

und

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

die Beziehung

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

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

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

und

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

so gilt die Ungleichung in umgekehrte Richtung:

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

Man beachte, dass im Gegensatz zu vielen anderen Ungleichungen keine Voraussetzungen für die Vorzeichen von ${\displaystyle a_{i}}$ und ${\displaystyle b_{i}}$ notwendig sind.

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

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

Wegen der Umordnungs-Ungleichung ist nun jede dieser ${\displaystyle n}$ Summen (im Fall gleich geordneter Zahlen ${\displaystyle a_{i}}$ und ${\displaystyle b_{i}}$) kleiner oder gleich ${\displaystyle \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

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

Im Fall entgegengesetzt geordneter Zahlen ${\displaystyle a_{i}}$ und ${\displaystyle b_{i}}$ braucht die Umordnungs-Ungleichung nur in die umgekehrte Richtung angewendet werden.

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

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

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 ${\displaystyle a_{i}}$ und ${\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}.}$

Im Fall entgegengesetzt geordneter Zahlen ${\displaystyle a_{i}}$ und ${\displaystyle b_{i}}$ ist der Beweis analog.

Ein anderer Beweis ergibt sich direkt aus der Gleichung

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

bzw. allgemeiner mit Gewichten ${\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})}$.

Es gilt nämlich

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

Mit Umbenennung der Indizes ergibt sich

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

insgesamt also genau die Behauptung:

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

Die Tschebyschew-Summenungleichung lässt sich auch in der 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).}$

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

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

mit

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

gilt

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

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

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

fallend geordnet und nichtnegativ sind.

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

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

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

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

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

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

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

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

1. ↑ Harro Heuser: Lehrbuch der Analysis Teil 1. Wiesbaden, Vieweg+Teubner, Verlag 2003, ISBN 3-322-96828-6, S. 99.
2. ↑ Martin Aigner: Diskrete Mathematik, 6., korrigierte Auflage, Vieweg, Wiesbaden 2006, ISBN 978-3-8348-0084-8, S. 54.