In dieser Lehreinheit werden elementare Begriffe der Wahrscheinlichkeitsrechnung benutzt. Solltest du dich damit nicht zu sicher fühlen, sieh dir bitte zunächst die entsprechende Lehreinheit dazu an.

Konzentration

Autor: Martin Krejca

Wenn wir zufällige Prozesse analysieren, ist es oftmals nicht möglich, jedem Elementarereignis eine genaue Wahrscheinlichkeit zuzuordnen. Häufig liegt das daran, dass der Wahrscheinlichkeitsraum unendlich ist. Außerdem wird er oft nicht explizit erwähnt, weil man einerseits Zufallsvariablen benutzt und weil andererseits intuitiv klar ist, worüber man spricht. In solchen Fällen gibt man sich dann oft mit weniger zufrieden.

Die Tücken des Erwartungswerts

Für gewöhnlich interessiert man sich für den Erwartungswert einer speziellen Zufallsvariable, die den Prozess modelliert, den man untersucht. Der Erwartungswert ist einerseits natürlich ein schönes Maß, da er das durchschnittliche Verhalten eines Zufallsprozesses beschreibt und somit eine kompakte Informationen über einen Wahrscheinlichkeitsraum liefert. Andererseits hilft einem der Erwartungswert jedoch nur bedingt viel, wie die folgenden beiden Beispiele verdeutlichen sollen.

• Wir betrachten einen fairen Würfelwurf (also eine gleichverteilte Zufallsvariable über \(\{1, \ldots, 6\}\)). Der Erwartungswert eines solchen Wurfs ist \(3{,}5\). Hier wird deutlich klar, wie viel Information durch den Erwartungswert verlorengeht: Der Wert selbst ist kein gültiges Ergebnis eines Wurfs und zudem sind alle Ergebnisse gleichwahrscheinlich (und nicht etwa eher bei der \(3\) oder der \(4\)).
• Jetzt betrachten wir eine Zufallsvariable \(X\) über \(\{5, 995\}\) mit \(P(X = 5) = \tfrac{1}{2}\) und \(P(X = 995) = \tfrac{1}{2}\). Hier liegt der Erwartungswert bei \(500\) und die Probleme, die sich beim Würfelwurf aufgetan haben, werden nur noch gravierender: Nun liegen die einzigen beiden Werte, die die Zufallsvariable annehmen kann, auch noch sehr weit entfernt vom Erwartungswert. Welchen Nutzen also hat er überhaupt noch?

Um sich dieser Frage anzunehmen, muss man sich erst einmal klarmachen, dass der Erwartungswert — wie wir bereits oben kurz festgestellt hatten — immer nur eine einzige Zahl ist und daher viel weniger Information repräsentieren kann als der ihm unterliegende Wahrscheinlichkeitsraum (der potentiell unendlich sein kann). Der Erwarungswert ist eben lediglich der Durchschnitt einer arbiträren Gewichtung (gemäß der entsprechenden Zufallsvariable) der Elementarwahrscheinlichkeiten. Dafür kann man sich nun interessieren oder nicht.

Wenn man nun den Erwartungswert einer Zufallsvariable kennt und ein Ergebnis beobachtet, kann man zumindest etwas Zusatzinformation erhalten: Ist der beobachtete Wert größer als der Erwartungswert, so muss es auch kleinere Werte geben (und umgekehrt). Allerdings ist unklar, ob es viele wesentlich kleinere Werte mit weniger Wahrscheinlichkeit gibt oder ob es ein paar nicht so viel kleinere Werte mit größerer Wahrscheinlichkeit gibt.

Eine wirklich hilfreiche Eigenschaft eines Erwartungswertes ist es, endlich zu sein. Dazu betrachten wir das folgende Beispiel:

• Wir werfen eine faire Münze so oft hintereinander, bis sie zum ersten Mal Kopf zeigt. Theoretisch muss nie Kopf kommen, da bei jedem erneuten Wurf wieder eine Wahrscheinlichkeit von \(\tfrac{1}{2}\) besteht, Zahl zu erhalten. Allerdings geht diese Wahrscheinlichkeit mit steigender Anzahl an Versuchen gegen \(0\). Stochastisch gesehen handelt es sich bei dem Ergebnis des Münzwurfs um eine geometrisch verteile Zufallsvariable mit Erfolgswahrscheinlichkeit \(\tfrac{1}{2}\). Der Erwartungswert ist also \(2\). Das heißt, dass man fast sicher irgendwann einmal Kopf werfen wird.

Dass der Erwartungswert in dem obigen Beispiel tatsächlich endlich ist, liegt daran, dass die Wahrscheinlicht, nur Zahl zu werfen, exponentiell nach unten geht und somit dem linearen Wachsen der Fehlversuche stark entgegenwirkt. Aber wie stark muss diese Gegenkraft eigentlich sein? Um das zu verstehen, schauen wir uns einfach ein paar unendliche Wahrscheinlichkeitsräume an. Endliche Wahrscheinlichkeitsräume haben immer einen endlichen Erwartungswert, da die reellen Zahlen unter Addition und Multiplikation abgeschlossen sind.

• Gegeben sei eine Zufallsvariable \(X\), die Werte in \(\mathbf{N} \smallsetminus \{0, 1\}\) annehmen kann. Weiterhin definieren wir für alle natürlichen Zahlen \(i \geq 2\), dass \(P(X = i) = \tfrac{1}{i}\) ist. Die Wahrscheinlichkeiten fallen also nur linear ab. Um überhaupt von einem Wahrscheinlichkeitsraum sprechen zu können, müssen sie sich zudem zu \(1\) aufsummieren. Allerdings entspricht diese Summe der harmonischen Reihe (bis auf das erste Glied). Sie divergiert also. Demnach kann gar kein solcher Wahrscheinlichkeitsraum existieren.
• Schauen wir uns nun wieder eine Zufallsvariable \(X\) an, die dieselben Werte wie zuvor annehmen kann. Diesmal legen wir für \(i \geq 3\) jedoch fest, dass \(P(X = i) = \tfrac{1}{i^2}\) ist. Für \(i = 2\) schummeln wir uns einfach \(P(X = 2) = 1 - \sum_{i = 3}^{\infty}\tfrac{1}{i^2}\) zurecht. Die unendliche Summe konvergiert diesmal offensichtlich. Das quadratische Abfallen hat uns also zu einem Wahrscheinlichkeitsraum verholfen. Wenn wir nun allerdings den Erwartungswert von \(X\) berechnen wollen, dann kommen wir (fast) wieder bei der Summe aus dem vorigen Beispiel an. Der Erwartungswert ist also unendlich.

Dieses Spielchen kann man jetzt ewig so weiterführen: Nehmen wir an, dass die Wahrscheinlichkeiten wie \(\tfrac{1}{i^3}\) fallen. Dann ist der Erwartungswert zwar endlich, die Varianz aber immer noch unendlich. Wahrscheinlichkeiten, die wie ein Polynom fallen, sind also nicht ganz so schön. Die geometrische Verteilung aus dem Münzwurfbeispiel hat dieses Problem nicht. Sie hat einen endlichen Erwartungswert und eine endliche Varianz.

Abweichungen vom Erwartungswert

Bis auf die letzten beiden Beispiele haben wir immer die Abweichung einer Zufallsvariable zu ihrem Erwartungswert diskutiert. Das war natürlich Absicht, denn intuitiv stellen sich viele den Erwartungswert als den repräsentativsten Wert einer Zufallsvariable vor (obwohl dieser Wert nicht einmal angenommen werden muss!). Damit geht implizit einher, dass der Erwartungswert am wahrscheinlichsten ist. Dem ist nicht so; zumindest nicht immer. Der Würfelwurf dient wieder als gutes Beispiel, denn bei ihm sind alle Ausgänge gleichwahrscheinlich.

Nun ist es jedoch auch so, dass es tatsächlich viele Prozesse gibt, die sich stark um ihren Erwartungswert konzentrieren. Das heißt, dass es relativ unwahrscheinlich ist, dass das Ergebnis eines solchen Prozesses stark vom Erwartungswert abweicht. Das ist zum Beispiel bei der geometrischen Verteilung (unserem Münzwurfbeispiel) der Fall: So wird man mit einer Wahrscheinlichkeit von \(\tfrac{3}{4}\) bereits nach maximal zwei Würfen einmal Kopf treffen.

Ein weiteres Beispiel für eine konzentrierte Verteilung ist die Binomialverteilung. Sie hat mit der geometrischen Verteilung gemein, dass sie Prozesse beschreibt, die mehrfach ausgeführt werden. Das entspricht auch eher der Intuition hinter dem Erwartungswert: Er ist nicht ein repräsentativer Wert für nur einen Versuch, sondern für viele (unabhängige) Versuche.

Wichtig ist, dass eine starke Konzentration nicht immer vorliegt, wenn mehrere Versuche hintereinander ausgeführt werden, und dass es auch Einzelversuche geben kann, die stark konzentriert sind, wie zum Beispiel die Normal- oder die Exponentialverteilung. Die für uns relevante Information ist einfach die Wahrscheinlichkeit einer für uns relevanten Abweichung. Interessanterweise ist diese Information sehr viel aussagekräfter als einfach nur der Erwartungswert. Und für gewöhnlich interessiert man sich auch nicht für mehr als das. Wenn klar ist, dass ein Prozess sehr unwahrscheinlich von einem konkreten Wert (oftmals dem Erwartungswert) abweicht, dann ist die exakte Verteilung eigentlich nicht mehr von Belang.

Die Markowungleichung

Die erste Ungleichung, die wir uns anschauen, geht zwar nur in eine Richtung, ist aber sehr allgemein. Die einzige Anforderung, die wir an die Zufallsvariable, die wir stochastisch eingrenzen wollen, stellen, ist, dass sie nicht negativ sein darf. Mehr nicht.

• Sei \(X\) eine nichtnegative Zufallsvariable und sei \(i \in \mathbf{R}^+\!\). Dann gilt \[ P(X \geq i) \leq \frac{\mathrm{E}(X)}{i}\ . \]

Der Beweis ist sehr einfach und die Aussagekraft zunächst scheinbar nicht zu groß. Erst wenn \(i \geq \mathrm{E}(X)\) gilt, kommt man zu etwas sinnvollen Aussagen. Ein Vorteil ist jedoch, dass \(i\) ein beliebiger (positiver) Wert sein kann; nicht nur der Erwartungswert! Das macht die Ungleichung sehr flexibel.

Es ist auch wichtig zu sehen, dass die Abweichung zwar nur linear fällt, aber potentiell unendlich viele Fälle abdeckt. Das steht im Unterschied zu den zwei letzten Beispielen des ersten Abschnitts. Dort haben wir \(P(X = i)\) betrachtet und nicht, wie hier, \(P(X \geq i)\).

Konzentrieren wir uns nun jedoch auf Vielfache von \(\mathrm{E}(X)\). Mithilfe der Markowungleichung sehen wir jetzt, dass eine zunehmende Abweichung vom Erwartungswert (nach oben) zunehmend unwahrscheinlicher wird. Leider erhalten wir keine Aussage über Abweichungen nach unten.¹

Im Folgenden betrachten wir Ungleichungen, die die Abweichung einer Zufallsvariable in beide Richtungen beschränken. Interessanterweise bauen sie alle auf der Markowungleichung auf.

Die Tschebyscheffungleichung

Ein sehr simpler Ansatz, um aus der Markowungleichung eine Abweichung in beide Richtungen zu beschränken, ist, die Zufallsvariable \(\big(X - \mathrm{E}(X)\big)^2\) anstelle von \(X\) zu betrachten. Der Erwartungswert der neuen Zufallsvariable ist einfach die Varianz von \(X\) und es ergibt sich die folgende Aussage:

• Sei \(X\) eine beliebige Zufallsvariable und sei \(a \in \mathbf{R}^+\!\). Dann gilt \[ P\Big(\big(X - \mathrm{E}(X)\big)^2 \geq a^2\Big) = P\Big(\big\vert X - \mathrm{E}(X)\big\vert \geq a\Big) \leq \frac{\mathrm{Var}(X)}{a^2}\ . \]

Obwohl wir im Prinzip nur die Markowungleichung benutzen, treffen wir nun eine Aussage über beliebige Zufallsvariablen. Der Trick besteht einfach darin, die Zufallsvariable geschickt zu transformieren.²

Die Einsicht, die uns die Tschebyscheffungleichung verschafft, ist zum Glück sehr intuitiv: Je größer die Abweichung einer Zufallsvariable von ihrem Erwartungswert, umso unwahrscheinlicher tritt sie ein. Aber entspricht das bereits einer Konzentration?

Was heißt eigentlich konzentriert?

Zuvor haben wir gesehen, wie man die Wahrscheinlichkeit, dass eine Zufallsvariable von ihrem Erwartungswert abweicht, abschätzen kann. Normalerweise spricht man dann jedoch nicht auch gleich von Konzentration. Wann man etwas konzentriert nennt, bleibt eigentlich jedem selbst überlassen; in der Analyse randomisierter Algorithmen gibt es allerdings für gewöhnlich einen Konsens.

Eine sehr wichtige Größe eines randomisierten Algorithmus ist seine Laufzeit. Vor allem interessiert man sich für die erwartete Laufzeit.³ Nun möchte man natürlich am liebsten effiziente Algorithmen haben, also welche, deren (erwartete) Laufzeit polynomiell ist. Hat man einen solchen effizienten Algorithmus, wird er in seiner Lebensspanne mehrfach ausgeführt. Eine polynomielle Anzahl von Versuchen ist dabei realistisch. Es wäre also wünschenswert, wenn er während dieser Zeit fast nie stark von seiner erwarteten Laufzeit abweichen würde.

Ein Ereignis, das eine superpolynomiell geringe Wahrscheinlichkeit ⁴ besitzt, tritt in polynomiell vielen Versuchen fast sicher nicht auf. Das folgt ganz einfach aus einer Union-Bound. Aus diesem Grund sagt man oft, dass eine Zufallsvariable um einen Wert konzentriert ist, wenn die Wahrscheinlichkeit, davon abzuweichen, höchstens superpolynomiell gering ist. Im Folgenden sprechen wir von Konzentration jedoch einfach dann, wenn wir eine Abweichung in beide Richtungen beschränken können.

Die Chernoffschranken

In diesem Abschnitt werden wir etwas konkreter. Das heißt, dass wir die Zufallsvariablen, die wir betrachten, stärker als zuvor einschränken. Dafür erhalten wir aber auch wesentlich stärkere Resultate.

Im Gegensatz zu den beiden vorherigen Ungleichungen betrachten wir hier zwei Ungleichungen und nicht nur eine. Zudem kann man in vielen Fällen mithilfe dieser beiden Ungleichungen tatsächlich Konzentration um den Erwartungswert zeigen. Werfen wir also mal einen Blick auf die eigentlichen Aussagen.

• Seien \(X_1, \ldots, X_n\) i. i. d. bernoulliverteile Zufallsvariablen mit Erfolgswahrscheinlichkeit \(p\). Dann gilt
  • einerseits für jedes \(\delta \in \mathbf{R}^+\) \[ P\bigg(\sum_{i = 1}^n X_i \geq (1 + \delta)np\bigg) \leq \mathrm{e}^{-\frac{\min\{\delta, \delta^2\}}{3}pn} \]
  • und andererseits für jedes \(\delta \in (0, 1)\) \[ P\bigg(\sum_{i = 1}^n X_i \leq (1 - \delta)np\bigg) \leq \mathrm{e}^{-\frac{\delta^2}{2}pn}\ . \]

Das beschreibt die Intuition, dass mehrfaches Hintereinanderausführen eine starke Konzentration hervorruft, ganz wie es eingangs bereits einmal erwähnt wurde. Die Summe der \(X_i\) ist dabei eine binomialverteile Zufallsvariable und \(np\) ihr Erwartungswert. Im Prinzip decken die Chernoffschranken damit nur eine Verteilung ab. Die tritt dafür aber ziemlich häufig auf.

Ein anderer wichtiger Punkt ist, dass die hier aufgeführten Ungleichungen nur eine relative Abweichung vom Erwartungswert beschränken. Es gibt auch Chernoffschranken für absolute Abweichungen. Die sehen dann aber nicht mehr so schön aus.

Die Hoeffdingungleichung

Wir betrachten jetzt die letzte Ungleichung in dieser Unit, werden wieder etwas allgemeiner, schauen uns aber weiterhin \(n\) unabhängige Zufallsprozesse an.

Im Abschnitt zuvor haben wir gesehen, dass die Chernoffschranken gute Konzentrationen liefern. Leider müssen die Zufallsvariablen dafür bernoulliverteilt sein; sie dürfen also nur zwei Werte annehmen.⁵ Außerdem müssen die Zufallsvariablen alle identisch verteilt sein. Diese beiden Bedingungen werden bei der Hoeffdingungleichung über Bord geworfen. Zudem wird wieder die absolute Abweichung beschränkt.

• Seien \(X_1, \ldots, X_n\) unabhängige Zufallsvariablen, sodass für jedes \(i \in \{1, \ldots, n\}\) immer \(a_i \leq X_i - \mathrm{E}(X_i) \leq b_i\) gilt, wobei \(a_i, b_i \in \mathbf{R}\) sind. Dann gilt für jedes \(c \in \mathbf{R}^+\) \[ P\bigg(\sum_{i = 1}^n \big(X_i - \mathrm{E}(X_i)\big) \geq c\bigg) \leq \mathrm{e}^{-\frac{2c^2}{\sum_{i = 1}^n (b_i - a_i)^2}}\ . \]

Diese eine Ungleichung beschränkt zunächst scheinbar nur eine Abweichung nach oben vom Erwartungswert. Wenn wir aber \(X'_i = - X_i\) wählen, dann sehen wir, dass dieselbe Schranke auch nach unten gilt.⁶ Wir können das \(\geq c\) also auch getrost durch ein \(\leq -c\) ersetzen. Durch eine Union-Bound über diese beiden Fälle erhalten wir damit dann auch eine gute Abschätzung, wie wahrscheinlich überhaupt vom Erwartungswert abgewichen wird.

Zuletzt sei noch eine wichtige Beobachtung aus der Hoeffdingungleichung genannt: Die Zufallsprozesse, die man betrachtet, müssen beschränkt sein. Tatsächlich muss man sogar angeben, wie stark jeder Prozess vom Erwartungswert abweichen kann. Die einzige Zusatzinformation, die man danach erhält, ist, wie wahrscheinlich eine Abweichung auftritt. So kann man die Hoeffdingungleich zum Beispiel auch nur für ein einzelnes \(X\), also \(n = 1\) betrachten. Oftmals interssiert man sich aber für das asymptotische Verhalten von \(n\). Was die Ungleichung dann aussagt, ist, dass konzentrierte unabhängige Prozesse in der Summe ebenfalls konzentriert sind beziehungsweise noch konzentrierter werden.

Was haben wir gelernt?

• Erwartungswerte sind gut, Konzentrationen sind besser
• Die Summe von unabhängigen Zufallsprozessen ist oft stark konzentriert
• Das Transformieren von Zufallsvariablen kann einem dabei helfen, an gewünschte Ergebnisse zu kommen

1Obwohl \(X\) nichtnegativ ist, wäre eine untere Schranke durchaus sinnvoll, um wirklich von einer Konzentration zu sprechen.↩

2Das ist ein sehr beliebter Trick in der Stochastik: Wenn etwas nicht passt, wird es einfach passend gemacht. Oftmals muss man seinen Prozess nur geschickt transformieren, um sich viel Rechenarbeit zu sparen.↩

3Hier ist es bereits praktisch zu wissen, dass die erwartete Laufzeit endlich ist. Denn das heißt, dass der Algorithmus immerhin fast sicher terminiert!↩

4Das sind Wahrscheinlichkeiten \(p\), für die für jedes \(c \in \mathbf{R}^+\) gilt, dass \(p \in \mathrm{o}(n^{-c})\). Eigentlich müsste man von rationalen Funktionen mit Zähler \(1\) sprechen. Das wäre aber sehr mühselig. Exponentiell geringe Wahrscheinlichkeiten fallen in diese Kategorie.↩

5Eigentlich meint man bei bernoulliverteilten Zufallsvariablen für gewöhnlich welche, die nur die beiden Werte \(0\) und \(1\) annehmen können. Sind es zwei andere Werte, kann man seine Zufallsvariable aber transformieren, sodass sie bernoulliverteilt im herkömmlichen Sinne ist. Diese Transformation kann man dann auch in die Chernoffschranken stecken.↩

6Was sich dabei dann ändert, ist lediglich, dass jeweils \(a_i\) und \(b_i\) vertauscht werden und ihre Vorzeichen ändern. Da in der Ungleichung aber nur ihre Differenz entscheidend ist und die auch noch quadriert wird, ändert sich das Endergebnis nicht.↩