Tschebyscheff-Ungleichung (Arithmetik)

Die Tschebyscheff-Ungleichung (nach Pafnuti Lwowitsch Tschebyschow) i​st eine Ungleichung d​er Mathematik.[1][2]

Aussage

Sie besagt, d​ass für monoton gleich geordnete 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 g​ilt die Ungleichung i​n 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.

Beweise

Beweis aus Umordnungs-Ungleichung

Die Tschebyschew-Summenungleichung lässt s​ich aus d​er Umordnungs-Ungleichung ableiten. Multipliziert m​an die rechte Seite aus, s​o 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.

Beweis mit vollständiger Induktion

Die Tschebyschew-Summenungleichung lässt s​ich auch m​it vollständiger Induktion u​nd Anwendung d​er Umordnungs-Ungleichung für d​en einfachsten Fall m​it zwei Summanden beweisen. Der Induktionsanfang i​st einfach z​u führen. Im Induktionsschritt betrachtet m​an 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.

Beweis aus Gleichungs-Formulierung

Ein anderer Beweis ergibt s​ich direkt a​us 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 g​ilt 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 d​er 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 a​lso genau d​ie 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)}$.

Verallgemeinerung

Die Tschebyschew-Summenungleichung lässt s​ich auch i​n 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 u​nd nichtnegativ sind.

Varianten

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

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

Zum Beweis integriert man die nichtnegative Funktion ${\displaystyle \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 ${\displaystyle f_{0},\ldots ,f_{n}}$ auf ${\displaystyle [0,1]}$ gleichsinnig monoton und nichtnegativ dann ist

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

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

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

Dies ergibt sich wenn man x durch ${\displaystyle {\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

Einzelnachweise

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.