Tschebyscheff-Ungleichung (Arithmetik)

Die Tschebyscheff-Ungleichung (nach Pafnuti Lwowitsch Tschebyschow) ist eine Ungleichung der Mathematik.<ref>Harro Heuser: Lehrbuch der Analysis Teil 1. Wiesbaden, Vieweg+Teubner, Verlag 2003, ISBN 3-322-96828-6, S. 99.</ref><ref>Martin Aigner: Diskrete Mathematik, 6., korrigierte Auflage, Vieweg, Wiesbaden 2006, ISBN 978-3-8348-0084-8, S. 54.</ref>

Aussage

Sie besagt, dass für monoton gleich geordnete <math>n</math>-Tupel reeller Zahlen

<math>a_1 \geq a_2 \geq \cdots \geq a_n</math>

und

<math>b_1 \geq b_2 \geq \cdots \geq b_n</math>,

die Beziehung

<math>n \sum_{i=1}^n a_ib_i \geq \left(\sum_{i=1}^n a_i\right)\left(\sum_{i=1}^n b_i\right)</math>.

gilt. Sind <math>a_i</math> und <math>b_i</math> hingegen entgegengesetzt geordnet, also beispielsweise

<math>a_1 \geq a_2 \geq \cdots \geq a_n</math>

und

<math>b_1 \leq b_2 \leq \cdots \leq b_n</math>,

so gilt die Ungleichung in umgekehrte Richtung:

<math>n \sum_{i=1}^n a_ib_i \leq \left(\sum_{i=1}^n a_i\right)\left(\sum_{i=1}^n b_i\right)</math>.

Man beachte, dass im Gegensatz zu vielen anderen Ungleichungen keine Voraussetzungen für die Vorzeichen von <math>a_i</math> und <math>b_i</math> 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

<math>\left(\sum_{i=1}^n a_i\right)\left(\sum_{i=1}^n b_i\right)=\left(a_1b_1 + a_2 b_2 + \dots +a_{n-1}b_{n-1}+a_nb_n\right)</math>

<math>+\left(a_1b_2 + a_2 b_3 + \dots +a_{n-1}b_{n}+a_nb_1\right)</math>

<math>+\left(a_1b_3 + a_2 b_4 + \dots +a_{n-1}b_{1}+a_nb_2\right)</math>

<math>+\left(a_1b_n + a_2 b_1 + \dots +a_{n-1}b_{n-2}+a_nb_{n-1}\right)</math>

Wegen der Umordnungs-Ungleichung ist nun jede dieser <math>n</math> Summen (im Fall gleich geordneter Zahlen <math>a_i</math> und <math>b_i</math>) kleiner oder gleich <math>\left(a_1b_1 + a_2 b_2 + \dots +a_{n-1}b_{n-1}+a_nb_n\right)</math>, insgesamt erhält man also genau die gewünschte Beziehung

<math>\left(\sum_{i=1}^n a_i\right)\left(\sum_{i=1}^n b_i\right)\leq n\left(a_1b_1 + a_2 b_2 + \dots +a_{n-1}b_{n-1}+a_nb_n\right) </math>.

Im Fall entgegengesetzt geordneter Zahlen <math>a_i</math> und <math>b_i</math> 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

<math>\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_ib_{n+1}\right)+\left(\sum_{i=1}^{n} a_i\right)\left(\sum_{i=1}^{n} b_i\right)</math>.

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 <math>a_i</math> und <math>b_i</math>)

<math>\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_ib_i</math>

Im Fall entgegengesetzt geordneter Zahlen <math>a_i</math> und <math>b_i</math> ist der Beweis analog.

Beweis aus Gleichungs-Formulierung

Ein anderer Beweis ergibt sich direkt aus der Gleichung

<math> 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)</math>

bzw. allgemeiner mit Gewichten <math>w_i</math>

<math> \sum_{i=1}^n w_i\sum_{i=1}^n w_ia_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)</math>.

Es gilt nämlich

<math> \sum_{i=1}^n w_i\sum_{k=1}^n w_ka_k b_k - \left(\sum_{i=1}^n w_i a_i\right)\left(\sum_{k=1}^n w_kb_k\right) = \sum_{i=1}^n\sum_{k=1}^n \left(w_iw_ka_kb_k-w_iw_ka_ib_k\right)</math>.

Mit Umbenennung der Indizes ergibt sich

<math>\sum_{i=1}^n\sum_{k=1}^n \left(w_iw_ka_kb_k-w_iw_ka_ib_k\right)=\sum_{k=1}^n\sum_{i=1}^n \left(w_iw_ka_ib_i-w_iw_ka_kb_i\right)</math>,

insgesamt also genau die Behauptung:

<math> \sum_{i=1}^n w_i\sum_{k=1}^n w_ka_k b_k - \left(\sum_{i=1}^n w_i a_i\right)\left(\sum_{k=1}^n w_kb_k\right) = \frac{1}{2}\sum_{i=1}^n\sum_{k=1}^n w_iw_k\left(a_kb_k-a_ib_k+a_ib_i-a_kb_i\right)=\frac{1}{2}\sum_{i=1}^n\sum_{k=1}^n w_iw_k\left(a_i-a_k\right)\left(b_i-b_k\right)</math>.

Verallgemeinerung

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

<math>\frac{1}{n} \sum_{i=1}^n a_ib_i \geq \left(\frac{1}{n}\sum_{i=1}^n a_i\right)\left(\frac{1}{n}\sum_{i=1}^n b_i\right).</math>

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

<math>a_j=\left(a_{j,1},\dots,a_{j,n}\right); j=1,\dots,m</math>

mit

gilt

<math>\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).</math>

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

fallend geordnet und nichtnegativ sind.

Varianten

Sind <math>f</math>, <math>g</math> auf <math>[0,1]</math> gleichsinnig monoton und ist <math>w \colon [0,1]\to\R_{\ge 0}</math> eine Gewichtsfunktion, d. h. <math>\int_0^1 w(x) dx=1</math>, dann ist

<math>\int_0^1 w(x) f(x) g(x) dx \ge \int_0^1 w(x) f(x) dx\; \int_0^1 w(x) g(x) dx</math>.

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

Sind <math>f_0, \ldots ,f_n</math> auf <math>[0,1]</math> gleichsinnig monoton und nichtnegativ, dann ist

<math>\int_0^1 w(x) \prod_{k=0}^n f_k \, dx \ge \prod_{k=0}^n \int_0^1 w(x) f_k \, dx</math>.

Und sind <math>f_0,\ldots,f_n</math> auf <math>[a,b]</math> gleichsinnig monoton und nichtnegativ und ist <math>w \colon [a,b]\to\R_{\ge 0}</math> eine Gewichtsfunktion, dann ist

<math>\int_a^b w(x) \prod_{k=0}^n f_k \, dx

\ge \frac{1}{(b-a)^{n-1}}\prod_{k=0}^n \int_a^b w(x) f_k \, dx</math>.

Dies ergibt sich, wenn man <math>x</math> durch <math>\frac{x-a}{b-a}</math> substituiert.

Einzelnachweise