ParAlg, Kapitel 7.1

7.1 Verschiedene Elemente in einem Datenstrom zählen

Formale Problembeschreibung

Die Eingabe ist ein Datenstrom $x_{1} x_{2} x_{3} \dots x_{m}$ aus Elementen aus einem Universum $U = {1, \dots, n}$ . Im obigen Beispiel war $U$ die Menge aller theoretisch möglichen IP-Adressen, also $n = 2^{32}$ . Falls es sich um IPv6-Adressen handelt, wäre $n = 2^{128}$ . Im Datenstrom kann ein Element $x \in U$ mehrfach auftreten, und unser Ziel ist es, die Anzahl verschiedener Items zu zählen. Etwas formular:

\begin{aligned} S & := {x_{1}, \dots, x_{m}} \\ k & := | S | . \end{aligned}

Falls Elemente mehrfach im Datenstrom vorkommen, gilt $| S | < m$ . Unsere Maschine liest die Eingabedaten nacheinander in zeitlicher Reihenfolge, kann also im Gegensatz zu einer Turing-Maschine nicht zurückspulen oder alte Items noch einmal betrachten. Sie hat einen internen Speicher, der typischerweise extrem klein im Vergleich zu $m$ und $n$ ist. Ziel ist es, nach Ende des Datenstroms einen Schätzwert $\hat{k}$ auszugeben, der nicht allzuweit entfernt von $k$ ist. Wir interessieren uns in diesem Zusammenhang ausschließlich für den Speicherplatz, den die Maschine benötigt, nicht für die Laufzeit ihrer Berechnungen. Sie ist also im Prinzip computationally unbounded. Um es noch formaler zu machen: die Maschine ist, ähnlich einem endlichen Automaten, definiert durch eine Funktion $δ : U \times Q \to Q$ ; die Interpretation ist, dass $x \in U$ das nächste Eingabe-Item ist und $q \in Q$ der derzeitige Speicherinhalt der Maschine; der Wert $δ (x, q) \in Q$ ist dann der Speicherinhalt im nächsten Schritt. Der benötigte Speicherplatz in Bits ist somit $⌈ \log | Q | ⌉$ . Ein Unterschied zu endlichen Automaten ist, dass $Q$ und auch $δ$ von $n$ und $m$ abhängen dürfen (wir gehen davon aus, dass die Maschine zumindest eine obere Schranke der Datenstromlänge $m$ kennt). Wir interessieren uns also primär für den Speicherplatz $\log | Q |$ und nicht dafür, wie komplex die Berechnung von $δ$ ist. In der Praxis ist aber $δ$ meist eine recht einfache Funktion, so dass diese Freiheit keine bösen Konsequenzen hat.

Exakte aber ineffiziente Algorithmen

Unsere Maschine kann natürlich einfach zu jedem Zeitpunkt $t$ die Menge $S_{t} := {x_{1}, \dots, x_{t}}$ speichern und Duplikate entfernen. Dafür braucht sie $min (m, n) \log n$ Bits: $min (m, n)$ ist eine obere Schranke für die Größe von $S_{t}$ und $\log n$ ist die Anzahl der Bits, die wir brauchen um ein Item $x_{i}$ aus dem Universum zu speichern.

Alternativ können wir uns eine boolesche Tabelle der Größe $n$ anlegen, alles mit False initialisieren und dann bei Input-Item $x_{t}$ die entsprechende Zelle auf True setzen. Dafür benötigen wir $n$ Bits.

Beobachtung 7.1.1 Wir können mit $min (n, m \log n)$ Bits Speicherplatz die Anzahl der verschiedenen Items exakt berechnen.

Effiziente approximative Algorithmen

Ein Speicherplatzbedarf $min (n, m \log n)$ gilt in diesem Modell als ineffizient. Unser Goldstandard ist $O (\log m + \log n)$ . Dies erlaubt uns, eine konstante Anzahl von Wörtern - $O (\log n)$ - sowie zum Beispiel einen Schrittzähler - $O (\log m)$ - zu speichern. Die Anzahl $k$ verschiedener Items können wir so nicht mehr exakt berechnen (dies ist selbst ein Theorem, dessen Beweis den Rahmen dieses Vorlesungsskripts sprengen würde; man benötigt hierfür Techniken der Kommunikationskomplexität). Wenn wir Randomisierung zulassen, können wir zumindest mit großer Zuverlässigkeit einen anständigen Schätzwert $\hat{k}$ für $k = | S |$ , also die Anzahl verschiedener Elemente im Datenstrom berechnen.

Der Algorithmus von Flajolet und Martin

Ich beschreibe zuerst eine impraktikable aber leichter zu analysierende Version des Algorithmus. Sei $S = {s_{1}, \dots, s_{k}}$ die Menge der $k$ verschiedenen Items. Jedes $x_{i}$ in unserem Datenstrom ist also eines dieser $s_{j}$ . Wir wählen eine zufällige Funktion $π : [n] \to [n]$ und speichern diese für die Dauer des Datenstroms. Dies ist natürlich nicht praktikabel, weil wir dafür $n \log n$ Bits bräuchten (Sie können sich vorstellen, wir legen eine Tabelle $A$ der Größe $n$ an; eine Zelle $A [x]$ muss nun den Wert $π (x)$ speichern, wofür sie wiederum $\log n$ Bits braucht; etwas informationstheoretischer: es gibt $n^{n}$ Funktionen $[n] \to [n]$ und somit braucht man $\log (n^{n}) = n \log n$ Bits, um eine zu codieren).

Wir ignorieren diese Bedenken vorerst, tun so, als hätten wir $π$ gespeichert und schauen uns an, was $π$ mit dem Datenstrom macht:

Sehen wir uns das Endergebnis noch einmal an:

Links sehen Sie am Beispiel die $k$ Werte $s_{1}, \dots, s_{k}$ . Rechts die Bilder $π (s_{1}), \dots, π (s_{k})$ . Da $π$ eine zufällige Funktion ist, sind diese Werte gleichverteilt und unabhängig. Setzen wir $Y_{i} := π (s_{i})$ . Wir haben also $k$ unabhängige Zufallsvariable $Y_{1}, \dots, Y_{k}$ , von denen jede in $[n]$ gleichverteilt ist. Machen wir nun eine Bierdeckelrechnung: diese $k$ Zufallszahlen teilen $[n]$ in $k + 1$ Intervalle ein, die im Schnitt $\frac{n}{k + 1}$ Zahlen haben. Also besteht auch das linkeste Intervall ${1, 2, \dots, min (Y_{1}, \dots, Y_{k})}$ im Schnitt aus $\frac{n}{k + 1}$ Zahlen und somit ist

\begin{array}{r} E [min (Y_{1}, \dots, Y_{k})] \approx \frac{n}{k + 1} . \end{array}

Wenn wir nach $k$ auflösen, erhalten wir

\begin{array}{r} k \approx \frac{n}{E [min (Y_{1}, \dots, Y_{k})]} - 1 . \end{array}

Den Erwartungswert von $min (Y_{1}, \dots, Y_{k})$ kennen wir nicht; den Wert $min (Y_{1}, \dots, Y_{k})$ allerdings können wir einfach berechnen, indem sich unsere Maschine zu jedem Zeitpunkt das Minimum der gesehenen Elemente (bzw. deren Bilder unter $π$ ) merkt. Hier nun also unser Algorithmus:

def FlajoletMartinImpraktikabel:

Wähle $π : [n] \to [n]$ zufällig # dies ist impraktikabel, weil dies $n \log n$ Bits Speicher benötigt.
$y^{*} := \infty$
for $x$ im Datenstrom:
1. $y^{*} := min (y^{*}, π (x))$
return $\hat{k} := n / y^{*}$ .

Das folgende Theorem besagt nun, dass $\hat{k}$ mit guter Wahrscheinlichkeit weder zu klein noch zu groß ist.

Theorem 7.1.2 Für den Schätzwert $\hat{k} :=$ FlajoletMartinImpraktikabel $(\vec{x})$ gilt:

$Pr [\hat{k} > 3 k] \leq \frac{1}{3}$ .
$Pr [\hat{k} < k / 3] \leq e^{- 3}$ .

Beweis. Für Punkt 1 sehen wir, dass

\begin{array}{r} \hat{k} > 3 k ⟺ \frac{n}{y^{*}} > 3 k ⟺ y^{*} < \frac{n}{3 k} ⟺ min (Y_{1}, \dots, Y_{k}) < \frac{n}{3 k} ⟺ Y_{1} < \frac{n}{3 k} \lor Y_{2} < \frac{n}{3 k} \lor \dots \lor Y_{k} < \frac{n}{3 k} . \end{array}

In Worten: das Minimum von $k$ Zahlen ist kleiner als eine Schranke genau dann, wenn mindestens eine der Zahlen kleiner als diese Schranke ist. Wir rechnen nun weiter:

\begin{aligned} Pr [\hat{k} > 3 k] & = Pr [Y_{1} < \frac{n}{3 k} \lor Y_{2} < \frac{n}{3 k} \lor \dots \lor Y_{k} < \frac{n}{3 k}] \\ (Union Bound) & \leq \sum_{i = 1}^{k} Pr [Y_{i} \leq \frac{n}{3 k}] \end{aligned}

Zur Erinnerung: der Union Bound besagt, dass für zwei Ereigbnisse $A$ und $B$ $Pr [A \cup B] \leq Pr [A] + Pr [B]$ gilt. Dies lässt sich unmittelbar von zwei auf $k$ Ereignisse verallgemeinern. Für ein festes $i$ können wir $Pr [Y_{i} < n / 3 k]$ wie folgt bestimmen: der Wert $Y_{i}$ ist ja $π (s_{i})$ und ist somit ein zufälliger Wert in ${1, \dots, n}$ . Die Wahrscheinlichkeit, dass er kleiner als $n / 3 k$ ist, ist

\begin{aligned} Pr [Y_{i} < \frac{n}{3 k}] & \leq Pr [Y_{i} \leq \frac{n}{3 k}] = \frac{⌊ \frac{n}{3 k} ⌋}{n} \leq \frac{\frac{n}{3 k}}{n} = \frac{1}{3 k} . \end{aligned}

Wir setzen das in den obigen Union Bound ein und erhalten

\begin{aligned} Pr [\hat{k} > 3 k] & \leq \sum_{i = 1}^{k} Pr [Y_{i} \leq \frac{n}{3 k}] \\ \leq \sum_{i = 1}^{k} \frac{1}{3 k} = \frac{1}{3}, \end{aligned}

wie behauptet. Somit ist Punkt 1 gezeigt. Für Punkt 2 gehen wir anfangs ähnlich vor:

\begin{array}{r} \hat{k} < \frac{k}{3} ⟺ \frac{n}{y^{*}} < \frac{k}{3} ⟺ y^{*} > \frac{3 n}{k} ⟺ min (Y_{1}, \dots, Y_{k}) > \frac{3 n}{k} ⟺ Y_{1} > \frac{3 n}{k} \land Y_{2} > \frac{3 n}{k} \land \dots \land Y_{k} > \frac{3 n}{k} . \end{array}

In Worten: das Minimum von $k$ Zahlen ist größer als eine Schranke, wenn jede diese Zahlen größer als die Schranke ist. Somit gilt

\begin{aligned} Pr [\hat{k} < \frac{k}{3}] & = Pr [Y_{1} > \frac{3 n}{k} \land Y_{2} > \frac{3 n}{k} \land \dots \land Y_{k} > \frac{3 n}{k}] \\ (Unabhängigkeit) & = \prod_{i = 1}^{k} Pr [Y_{i} > \frac{3 n}{k}] \end{aligned}

Für festes $i$ schätzen wir $Pr [Y_{i} > 3 n / k]$ wie folgt ab:

\begin{aligned} Pr [Y_{i} > \frac{3 n}{k}] & = 1 - Pr [Y_{i} \leq \frac{3 n}{k}] \\ = 1 - \frac{\frac{3 n}{k}}{n} = 1 - \frac{3}{k}, \end{aligned}

und somit

\begin{aligned} Pr [\hat{k} < \frac{k}{3}] & = \prod_{i = 1}^{k} Pr [Y_{i} > \frac{3 n}{k}] \\ = {(1 - \frac{3}{k})}^{k} \leq e^{- 3}, \end{aligned}

wobei wir in der letzten Ungleichung die Tatsache $1 + x \leq e^{x}$ verwendet haben. $◻$

Den Algorithmus praktikabel machen: paarweise unabhängige Zufallsvariable

Statt $π : [n] \to [n]$ zufällig zu wählen, wählen wir es pseudozufällig. Hierfür wählen wir eine Primzahl $p \geq n$ und betrachten die Menge $Z_{p} := {0, \dots, p - 1}$ als unser neues Universum. Wir wählen zwei zufällige Zahlen $a, b \in Z_{p}$ gleichverteil und unabhängig und setzen

\begin{aligned} π : Z_{p} & \to Z_{p} \\ x & \mapsto a x + b \mod p . \end{aligned}

Der Rest des Algorithmus ist identisch:

def FlajoletMartin:

Wähle eine Primzahl $p \in [n, 2 n]$ und setze $Z_{p} := {0, 1, \dots, p - 1}$ .
Wähle $a, b \in Z_{p}$ und definiere $π : x \mapsto a x + b \mod p$
$y^{*} := \infty$
for $x$ im Datenstrom:
1. $y^{*} := min (y^{*}, π (x))$
return $\hat{k} := n / y^{*}$ .

Zur Erinnerung: $y \mod p$ ist der Rest, der bei der Division von $y$ durch $p$ übrigbleibt. Wenn zwei Zahlen $y$ und $z$ modulo $p$ den gleichen Rest ergeben, dann schreiben wir $y \equiv_{p} z$ und lesen " $y$ ist äquivalent zu $z$ modulo $p$ ". Dies gilt genau dann, wenn $p | (y - z)$ , wenn also $p$ ein Teiler der Differenz $y - z$ ist.

Wenn wir jetzt den Beweis von Theorem 7.1.2 durchgehen, sehen wir, dass dieser spätestens bei dem Argument der Unabhängigkeit scheitern wird. Die Werte $Y_{1} := π (x_{1}), \dots, Y_{k} := π (x_{k})$ sind nicht mehr unabhängig. Ist zumindest $Y_{i}$ gleichverteilt?

Lemma 7.1.3 Sei $s \in Z_{p}$ . Dann ist der Wert $π (s)$ gleichverteilt in $Z_{p}$ .

Beweis. Um zu zeigen, dass $π (s_{i})$ gleichverteilt in $Z_{p}$ ist, müssen wir zeigen, dass für jedes feste $z \in Z_{p}$ gilt, dass $Pr [π (s) = z]$ . Es gilt

\begin{array}{r} π (s) = z \Leftrightarrow a s + b \equiv_{p} z \Leftrightarrow b \equiv_{p} z - a s . \end{array}

Wieviele Möglichkeiten $(a, b)$ gibt es, für die $b \equiv_{p} z - a s$ gilt? Für jede Wahl von $a \in Z_{p}$ gibt es genau eine Möglichkeit für $b$ , nämlich eben $z - a s$ . In anderen Worten: die Gleichung $b \equiv_{p} z - a s$ in den Unbekannten $a$ und $b$ hat $p$ Lösungen. Insgesamt gibt es für $(a, b)$ genau $p^{2}$ Möglichkeiten; $p$ viele davon erfüllen $b \equiv_{p} z - a s$ , und somit gilt

\begin{array}{r} Pr [π (s) = z] = \frac{1}{p} . \end{array}

Wir sehen:

π (s)

ist gleichverteilt in

Z_{p}

◻

Das nächste Lemma zeigt, dass die $π (s_{1}), \dots, π (s_{k})$ paarweise unabhängig sind. Hier werden wir benötigen, dass $p$ eine Primzahl ist.

Lemma 7.1.4 Seien $s_{1}, s_{2}$ zwei verschiedene Werte in $Z_{p}$ . Dann sind $π (s_{1}), π (s_{2})$ gleichverteilt in $Z_{p}$ und unabhängig.

Beweis. Wir müssen nun zeigen, dass das Paar $(π (s_{1}), π (s_{2}))$ gleichverteilt in $Z_{p} \times Z_{p}$ ist. Dass also für jedes $(z_{1}, z_{2}) \in Z_{p} \times Z_{p}$ gilt: $Pr [(π (s_{1}), π (s_{2})) = (z_{1}, z_{2})] = 1 / p^{2}$ . Wir sehen, dass $(π (s_{1}), π (s_{2})) = (z_{1}, z_{2})$ genau dann gilt, wenn

\begin{aligned} a s_{1} + b & \equiv_{p} z_{1} \\ a s_{2} + b & \equiv_{p} z_{2} . \end{aligned}

Dies ist ein Gleichungssystem mit zwei Gleichungen und zwei Unbekannten $a$ und $b$ .

Wir können nun das Gleichungssystem in Matrix-Vektor-Form schreiben

\begin{array}{r} [\begin{array}{c} s_{1} & 1 \\ s_{2} & 1 \end{array}] \cdot [\begin{array}{c} a \\ b \end{array}] = [\begin{array}{c} z_{1} \\ z_{2} \end{array}] \end{array}

Die Matrix hat vollen Rang und somit hat das Gleichungssytem genau eine Lösung.

◻

Um das Argument mit der Matrix und dem vollen Rang zu verstehen, müssen Sie sich (1) an Ihre lineare Algebra erinnern und wahrscheinlich auch (2) davon überzeugen, dass alles, was Sie in linearer Algebra mit reellen Zahlen gemacht haben, auch funktioniert, wenn Sie nun mit Zahlen modulo $p$ zu tun haben. Ich möchte allerdings in diesem Skript so wenig Grundlagen wie möglich voraussetzen. Daher werde ich im nächsten Teilkapitel den Beweis "zu Fuß" ablaufen. Nehmen wir nun aber für erste Lemma 7.1.4 als gegeben an.

Theorem 7.1.5 Für den Schätzwert $\hat{k} :=$ FlajoletMartin $(\vec{x})$ gilt:

$Pr [\hat{k} > 3 k] \leq \frac{1}{3}$ .
$Pr [\hat{k} < k / 3] \leq 1 / 3$ .

Beweis. Punkt 1 geht genau so wie der Beweis von Theorem 7.1.2, da wir hierfür nur benötigen, dass für jedes feste $s \in Z_{p}$ der Wert $π (s)$ gleichverteilt in $Z_{p}$ ist. Für Punkt 2 werden wir benötigen, dass die $Y_{1} := π (s_{1}), \dots, Y_{k} := π (s_{k})$ paarweise unabhängig sind. Fast genau so wie beim Beweis von Theorem 7.1.2 gilt

\begin{array}{r} \hat{k} < \frac{k}{3} ⟺ \frac{n}{y^{*}} < \frac{k}{3} ⟺ y^{*} > \frac{3 p}{k} ⟺ min (Y_{1}, \dots, Y_{k}) > \frac{3 p}{k} ⟺ Y_{1} > \frac{3 p}{k} \land Y_{2} > \frac{3 p}{k} \land \dots \land Y_{k} > \frac{3 p}{k} . \end{array}

Wir können die Wahrscheinlichkeit des Schnitts der $k$ Ereignisse $[Y_{i} > 3 p / k]$ nicht per Unabhängigkeit abschätzen und gehen daher einen alternativen Weg. Wir führen Indikatorvariable ein:

\begin{array}{r} Z_{i} := {\begin{cases} 1 & falls π (s_{i}) \leq \frac{3 p}{k}, \\ 0 & sonst. \end{cases} \end{array}

Des Weiteren setzen wir $Z := Z_{1} + \dots + Z_{k}$ . Wir sehen: $\hat{k} < \frac{k}{3}$ tritt genau dann ein, wenn kein $Y_{i}$ in den Bereich $[0, 3 p / k]$ fällt; wenn also $Z = 0$ eintritt. Als erstes berechnen wir den Erwartungswert von $Z$ :

\begin{aligned} E [Z] & = E [\sum_{i = 1}^{k} Z_{i}] = \sum_{i = 1}^{k} E [Z_{i}] \\ = \sum_{i = 1}^{k} Pr [π (s_{i}) \leq \frac{3 p}{k}] = k \cdot \frac{\frac{3 p}{k}}{p} = 3 . \end{aligned}

Hierfür reicht ein Union Bound leider nicht aus. Wir brauchen die sogenannte Tschebyschow-Ungleichung.

Markov-Ungleichung und Tschebyschow-Ungleichung

Lemma 7.1.6 Sei $X$ eine Zufallsvariable, die Werte in $R_{0}^{+}$ annimmt. Dann gilt für jedes $c \geq 0$ :

\begin{array}{r} Pr [X \geq c] \leq \frac{E [X]}{c} . \end{array}

Als Beispiel: höchstens ein drittel aller Deutschen haben ein Einkommen, dass das deutsche Durchschnittseinkommen um das Dreifache oder mehr übersteigt. Die Markow-Ungleichung ist oft eine sehr schwache Schranke. Die Durchschnittshöhe einer deutschen Frau liegt laut https://en.wikipedia.org/wiki/Average_human_height_by_country bei circa 1,66 Metern Zentimetern. Lauf Markow-Ungleichung ist höchstens jede zweite deutsche Frau größer als 3,32 Meter. Wahr, aber nicht sehr aussagekräftig.

Beweis von Reference "lemma-markov-inequality" not found. Go to put-all-in-one-page.html and read the instructions. Wir beschränken uns auf endliche Wahrscheinlichkeitsräume $Ω$ . Jedes Element $ω \in Ω$ hat eine Wahrscheinlichkeit $Pr [ω]$ . Die Zufallsvariable $X$ ist nun eine Funktion

\begin{array}{r} X : Ω \to R_{0}^{+} . \end{array}

Der Erwartungswert von $X$ ist definiert als die Summe

\begin{array}{r} (1) & E [X] = \sum_{ω \in Ω} Pr [ω] X (ω) . \end{array}

Wir teilen $Ω$ in zwei Teile auf, je nachdem, ob $X$ groß ist oder klein:

\begin{aligned} Ω_{k l e i n} & := {ω \in Ω | X (ω) < c} \\ Ω_{g r o ß} & := {ω \in Ω | X (ω) \geq c} \end{aligned}

Wir teilen nun die Summe ( $1$ ) auf:

\begin{aligned} E [X] & = \sum_{ω \in Ω} Pr [ω] X (ω) \\ = \sum_{ω \in Ω_{k l e i n}} Pr [ω] X (ω) + \sum_{ω \in Ω_{g r o ß}} Pr [ω] X (ω) \\ (weil X (ω) \geq 0) & \geq \sum_{ω \in Ω_{g r o ß}} Pr [ω] X (ω) \\ (weil X (ω) \geq c in Ω_{g r o ß}) & \geq \sum_{ω \in Ω_{g r o ß}} Pr [ω] c \\ = c \cdot \sum_{ω \in Ω_{g r o ß}} Pr [ω] = c \cdot Pr [Ω_{g r o s s}] \end{aligned}

Zusammenfassend erhalten wir $E [X] \geq c \cdot Pr [Ω_{g r o s s}]$ und somit

\begin{aligned} Pr [X \geq c] & = Pr [Ω_{g r o ß}] \leq \frac{E [X]}{c} . \end{aligned}

◻

Die Markow-Ungleichung hat den Vorteil, dass sie auf jede nicht-negative Zufallsvariable anwendbar ist. Der Nachteil ist, dass sie oft sehr schwach ist, also keine guten Schranken liefert, und nichts über Wahrscheinlichkeiten der Form $Pr [X \leq c]$ aussagt. Sie beschränkt nur Abweichungen nach oben, nicht nach unten. Um genauere Schranken zu beweisen, können wir die Varianz der Zufallsvariable betrachten.

Varianz. Sei $X$ eine Zufallsvariable, die reelle Werte (gerne auch negative) annimmt. Sei $μ := E [X]$ ihr Erwartungswert. Um zu messen, wie sehr $X$ typischerweise von $μ$ abweicht, betrachten wir den Wert $(X - μ)^{2}$ ; dieser ist immer positiv, und somit ist auch

\begin{array}{r} Var (X) := E [(X - μ)^{2}], \end{array}

die Varianz von $X$ , immer positiv. Wenn wir die Varianz einer Zufallsvariable kennen und diese klein ist, so können wir Abschätzungen angeben, die genauer sind als die Markow-Ungleichung:

Tschebyschow-Ungleichung 7.1.7 Sei $X$ eine Zufallsvariable und $μ := E [X]$ . Dann gilt

\begin{array}{r} Pr [| X - μ | \geq c] \leq \frac{Var (X)}{c^{2}} . \end{array}

Beweis. Die Ungleichung $| X - μ | \geq c$ gilt genau dann, wenn auch $(X - μ)^{2} \geq c^{2}$ gilt. Sei nun $Y := (X - μ)^{2}$ . Dies ist wiederum eine Zufallsvariable, und es gilt $E [Y] = Var (X)$ nach Definition der Varianz. Wir wenden jetzt die Markow-Ungleichung auf $Y$ an:

\begin{aligned} Pr [| X - μ | \geq c] & = Pr [(X - μ)^{2} \geq c^{2}] \\ = Pr [Y \geq c^{2}] \\ (Markow-Ungleichung) & \leq \frac{E [Y]}{c^{2}} \\ = \frac{Var (X)}{c^{2}}, \end{aligned}

wie behauptet. $◻$

Weiterhin ist die Varianz nützlich, wenn die Zufallsvariable $X$ die Summe unabhängig (oder auch paarweise unabhängiger) Zufallsvariablen ist. In diesem Falle ist die Varianz üblicherweise klein. Dies entspricht der Intuition: wenn wir unabhängige Zufallszahlen aufaddieren, sollten sich die Abweichungen in den meisten Fällen in etwa ausgleichen. Wir beginnen mit einer alternativen Formel für $Var (X)$ :

Beobachtung 7.1.8 $Var (X) = E [X^{2}] - {(E [X])}^{2}$ .

Beweis. Sei $μ := E [X]$ . Wir rechnen:

\begin{aligned} Var (X) & = E [(X - μ)^{2}] \\ = E [X^{2} - 2 X μ + μ^{2}] \\ = E [X^{2}] - 2 μ E [X] + μ^{2} \\ = E [[X^{2}] - 2 μ^{2} + μ^{2} \\ = E [[X^{2}] - μ^{2}, \end{aligned}

Wie behauptet.

◻

Lemma 7.1.9 Seien $Z_{1}, \dots, Z_{k}$ paarweise unabhängige Zufallsvariable und $Z := Z_{1} + \dots + Z_{k}$ . Dann gilt

\begin{array}{r} Var (Z) = Var (Z_{1}) + \dots + Var (Z_{k}) . \end{array}

Beweis. Sei $μ_{i} := E [Z_{i}]$ und $μ = E [Z] = μ_{1} + \dots + μ_{k}$ . Wir berechnen als erstes $E [Z^{2}]$ :

\begin{aligned} E [Z^{2}] & = E [(Z_{1} + \dots + Z_{k})^{2}] \\ = E [\sum_{i = 1}^{k} \sum_{j = 1}^{k} Z_{i} Z_{j}] \\ = \sum_{i = 1}^{k} \sum_{j = 1}^{k} E [Z_{i} Z_{j}] . \end{aligned}

Da die $Z_{i}$ paarweise unabhängig sind, gilt $E [Z_{i} Z_{j}] = E [Z_{i}] E [Z_{j}] = μ_{i} \cdot μ_{j}$ für $i \neq j$ . Für $i = j$ gilt $E [Z_{i} Z_{j}] = E [Z_{i}^{2}]$ . Somit ist

\begin{aligned} E [Z^{2}] & = \sum_{i = 1}^{k} \sum_{j = 1}^{k} [i \neq j] μ_{i} μ_{j} + \sum_{i = 1}^{k} E [Z_{i}^{2}] \\ = \sum_{i = 1}^{k} \sum_{j = 1}^{k} μ_{i} μ_{j} - \sum_{i = 1}^{k} μ_{i}^{2} + \sum_{i = 1}^{k} E [Z_{i}^{2}] \\ = (μ_{1} + \dots + μ_{k})^{2} \sum_{i = 1}^{k} (E [Z_{i}^{2}] - μ_{i}^{2}) \\ = μ^{2} + \sum_{i = 1}^{k} Var (Z_{i}) \end{aligned}

Und somit gilt $Var (Z) = E [Z^{2}] - μ^{2} = \sum_{i = 1}^{k} Var (Z_{i})$ , wie behauptet. $◻$

Wenden wir diese Maschinerie auf unsere Zufallsvariablen $Z_{i}$ an. Zur Erinnerung: diese haben wir definiert als

\begin{array}{r} Z_{i} := {\begin{cases} 1 & falls π (s_{i}) \leq \frac{3 p}{k}, \\ 0 & sonst. \end{cases} \end{array}

Es gilt $E [Z_{i}] = \frac{3}{k}$ und