Tschebyschow-Summenungleichung

Die Tschebyschow-Summenungleichung (nach Pafnuti Lwowitsch Tschebyschow) ist eine Ungleichung der Mathematik. In älteren Transkriptionen findet sich gelegentlich noch die Schreibweise Tschebyscheff.

Definition

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_ib_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_ib_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_1b_1 + a_2 b_2 + \dots +a_{n-1}b_{n-1}+a_nb_n\right)$

$+\left(a_1b_2 + a_2 b_3 + \dots +a_{n-1}b_{n}+a_nb_1\right)$

$+\left(a_1b_3 + a_2 b_4 + \dots +a_{n-1}b_{1}+a_nb_2\right)$

$+\dots$

$+\left(a_1b_n + a_2 b_1 + \dots +a_{n-1}b_{n-2}+a_nb_{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_1b_1 + a_2 b_2 + \dots +a_{n-1}b_{n-1}+a_nb_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_1b_1 + a_2 b_2 + \dots +a_{n-1}b_{n-1}+a_nb_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_ib_{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_ib_i$

$=a_{n+1}b_{n+1}+\sum_{i=1}^{n} a_ib_i + n a_{n+1}b_{n+1}+ n\sum_{i=1}^{n} a_ib_i=(n+1)\sum_{i=1}^{n+1} a_ib_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_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)$.

Es gilt nämlich

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

Mit Umbenennung der Indizes ergibt sich

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

insgesamt also genau die Behauptung:

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

Verallgemeinerung

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

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

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:[0,1]\to\R_{\ge 0}$ eine Gewichtsfunktion, d.h. $\int_0^1 \omega(x) dx=1$ dann ist

$\int_0^1 \omega(x) f(x) g(x) dx\ge \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₀,...,f_n auf [0,1] gleichsinnig monoton und nichtnegativ dann ist

$\int_0^1 \omega(x) \prod_{k=0}^n f_k \, dx \ge \prod_{k=0}^n \int_0^1 \omega(x) f_k \, dx$.

Und sind f₀,...,f_n auf [a,b] gleichsinnig monoton und nichtnegativ und ist $\omega:[a,b]\to\R_{\ge 0}$ eine Gewichtsfunktion dann ist $\int_a^b \omega(x) \prod_{k=0}^n f_k \, dx \ge \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