Effiziente Algorithmen, Kapitel 1.3

1.3 Jensens Ungleichung

Jensens Ungleichung

Eine Funktion $f : R \to R$ heißt konvex, wenn für alle zwei Punkte $p, q$ auf dem Graphen von $f$ das Geradensegment $[p q]$ auf oder oberhalb des Graphen von $f$ liegt:

Was heißt das, etwas mathematischer ausgedrückt? Welche Koordinaten hat ein Punkt auf dem Geradensegment $[p q]$ ? Es gilt ja $p = (x, f (x))$ und $q = (y, f (y))$ für $x, y \in R$ . Jeder Punkt im Interval $[x, y]$ lässt sich schreiben als Konvexkombination von $x$ und $y$ :

\begin{array}{r} α x + β y \end{array}

für zwei reelle Zahlen $α, β \geq 0$ mit $α + β = 1$ . Andere Autoren schreiben hier statt $β$ gleich $1 - α$ und sparen sich den zweiten Parameter; ich finde es aber typographisch klarer, wenn wir $α$ und $β$ schreiben. Legen wir nun eine senkrechte Gerade durch $(α x + β y, 0)$ . Diese schneidet den Graphen von $f$ in Punkt

\begin{array}{r} (1) & (α x + β y, f (α x + β y)) \end{array}

und das Geradensegment $[p q]$ im Punkt

\begin{array}{r} (2) & α p + β q = (α x + β y, α f (x) + β f (y)) . \end{array}

Die Konvexität von $f$ besagt nun, dass der Punkt ( $2$ ) auf oder oberhalb des Punktes ( $1$ ) liegen muss. Darüberhinaus muss $f$ gar nicht auf ganz $R$ definiert sein. Ein Intervall reicht aus. Somit können wir nun formal definieren:

Definition 1.3.1 Sei $I \subseteq R$ ein Interval (abgeschlossen, offen oder halb-offen). Eine Funktion $f : I \to R$ heißt konvex wenn für alle $x, y \in I$ und $α, β \geq 0$ mit $α + β = 1$ gilt:

\begin{array}{r} (3) & f (α x + β y) \leq α f (x) + β f (y) . \end{array}

Beispiel. Die Funktion $f : x \mapsto x^{2}$ ist konvex.

Beweis. Seien $x, y \in R$ und $α, β \geq 0$ mit $α + β = 1$ . Wir müssen zeigen, dass

\begin{array}{r} α x^{2} + β y^{2} \geq (α x + β y)^{2} . \end{array}

Wenn wir die rechte Seite expandieren, ergibt dies

\begin{array}{r} α x^{2} + β y^{2} \geq α^{2} x^{2} + 2 α β x y + β^{2} y^{2} . \end{array}

Wir bringen alles auf die linke Seite:

\begin{array}{r} (α - α^{2}) x^{2} - 2 α β x y + (β - β^{2}) y^{2} \geq 0 . \end{array}

Nun müssen wir erkennen, dass $α - α^{2} = α (1 - α) = α β$ und analog $β - β^{2} = α β$ , und somit bleibt zu zeigen:

\begin{array}{r} α β x^{2} - 2 α β x y + α β y^{2} \geq 0 . \end{array}

Da $α, β \geq 0$ sind, gilt auch $α β \geq 0$ . Wenn $α β =$ ist, dann gilt die obige Ungleichung mit Gleichheit, da beide Seite verschwinden. Ansonsten ist $α β > 0$ , wir können durch $α β$ dividieren und erhalten

\begin{array}{r} x^{2} - 2 x y + y^{2} \geq 0 . \end{array}

Dies ist wahr, da die linke Seite gleich $(x + y)^{2}$ ist.

Oft kommt uns die Analysis zur Hilfe: wenn die Funktion $f : I \to R$ zweimal differenzierbar ist, dann ist sie konvex genau dann, wenn $f^{″} (x) > 0$ ist für alle $x \in I$ . Zum Beispiel sind $2^{x}$ und $e^{x}$ konvex.

Definition 1.3.2 Eine Funktion $f$ heißt konkav, wenn $- f$ konvex ist.

Wiederum gilt: wenn die Funktion $f$ zweimal differenzierbar ist, dann ist $f$ genau dann konkav, wenn $f^{″} (x) \leq 0$ ist. Somit ist beispielsweise $\ln (x)$ und $\log_{2} (x)$ konkav.

Werfen wir erneut einen Blick auf die zwei Zahlen $α, β \geq 0$ mit $α + β = 1$ , wie sie in der Definition von Konvexität vorkommen. Man kann $α, β$ als Wahrscheinlichkeitsverteilung $P$ über der Menge ${x, y}$ betrachten. Der Ausdruck

\begin{array}{r} α f (x) + β f (y), \end{array}

also die rechte Seite von ( $3$ ), hat nun diese Interpretation: wähle einen Wert $Z \in {x, y}$ zufällig nach Wahrscheinlichkeitsverteilung $P$ . Werte dann $f$ an diesem Punkt aus; dies ergibt nun eine reelle Zufallsvariable, und ihr Erwartungswert ist genau ( $3$ ). Analog dazu hat die linke Seite von ( $3$ ) folgende Interpretation: wähle zufällig einen Wert in $Z \in {x, y}$ . Dies ist eine reelle Zufallsvariable und hat einen Erwartungswert. Werte nun $f$ an diesem Erwartungswert aus. Die Definition sagt nun grob: $f$ am Erwartungswert von $Z$ ist höchstens der Erwartungswert von $f (Z)$ . Jensens Ungleichung besagt nun, dass dies allgemein für endliche Wahrscheinlichkeitsverteilungen gilt, nicht nur für solche über zweielementigen Mengen.

Theorem 1.3.3 (Jensens Ungleichung). Sei $I$ ein Interval in $R$ und sei $X : Ω \to I$ eine Zufallsvariable mit Wertebereich $I$ , die nur endlich viele Werte annimmt. Dann gilt

\begin{array}{r} (4) & E [f (X)] \geq f (E [X]) . \end{array}

für jede konvexe Funktion $f : I \to R$ .

Beweis. Schreiben wir die etwas kurz angebundene Ungleichung ( $4$ ) um. Seien $x_{1}, \dots, x_{n} \in I$ die Werte, die $X$ annehmen kann, und $p_{1}, \dots, p_{n}$ die entsprechenden Wahrscheinlichkeiten. Wir müssen nun zeigen:

\begin{array}{r} (5) & \sum_{i = 1}^{n} p_{i} f (x_{i}) \geq f (\sum_{i = 1}^{n} p_{i} x_{i}) . \end{array}

Wenn $n = 1$ ist, dann ist $p_{1} = 1$ und beide Seiten sind gleich, nämlich einfach $f (x_{1})$ . Wenn $n = 2$ ist, dann ist ( $5$ ) genau die Definition von Konvexität, mit $x = x_{1}$ und $y = x_{2}$ und $α = p_{1}$ und $β = p_{2}$ .

Wenn nun $n \geq 3$ ist, dann verwenden wir Induktion über $n$ . Sei

\begin{aligned} q_{1} & := \frac{p_{1}}{p_{1} + p_{2}} \\ q_{2} & := \frac{p_{2}}{p_{1} + p_{2}} . \end{aligned}

Wir setzen $y := q_{1} x_{1} + q_{2} x_{2}$ . Wegen Konvexität gilt

\begin{array}{r} q_{1} f (x_{1}) + q_{2} f (x_{2}) \geq f (y) . \end{array}

Wenn wir beide Seiten mit $p_{1} + p_{2}$ multiplizieren, erhalten wir

\begin{array}{r} p_{1} f (x_{1}) + p_{2} f (x_{2}) \geq (p_{1} + p_{2}) f (y) \end{array}

und somit

\begin{array}{r} \sum_{i = 1}^{n} p_{i} f (x_{i}) \geq (p_{1} + p_{2}) f (y) + \sum_{i = 3}^{n} p_{i} f (x_{i}) . \end{array}

Die $n - 1$ Zahlen $p_{1} + p_{2}, p_{3}, p_{4}, \dots, p_{n}$ definieren eine Wahrscheinlichkeitsverteilung über den $n - 1$ Werten ${z, x_{3}, x_{4}, \dots, x_{n}}$ . Nach Induktion gilt also

\begin{array}{r} (p_{1} + p_{2}) f (y) + \sum_{i = 3}^{n} p_{i} f (x_{i}) \geq f ((p_{1} + p_{2}) z + p_{3} x_{3} + \dots + p_{n} x_{n}) . \end{array}

Weiterhin gilt nach Definition von $z$ , dass $(p_{1} + p_{2}) z = (p_{1} + p_{2}) (q_{1} x_{1} + q_{2} x_{2}) = p_{1} x_{1} + p_{2} x_{2}$ und somit ist die rechte Seite der letzten Ungleichung gleich $f (p_{1} x_{1} + p_{2} x_{2} + p_{3} x_{3} + \dots + p_{n} x_{n})$ und das Theorem ist bewiesen. $◻$