ParAlg, Kapitel 2.7

2.7 Probabilistisches Zwischenspiel: Chernoff Bounds

Seien $X_{1}, \dots, X_{n}$ unabhängige Zufallsvariable, die jeweils die Werte $0$ und $1$ annehmen, und sei $Pr [X_{i} = 1] = p$ für jedes $i$ . Für $X := X_{1} + \dots + X_{n}$ gilt $E [X] = p n$ . Wir interessieren uns für die Wahrscheinlichkeit, dass $X$ deutlich kleiner (oder deutlich größer) als sein Erwartungswert ist, und wollen zeigen, dass diese Wahrscheinlichkeit klein ist. Sei nun also $q < p$ . Wir wollen zeigen, dass

\begin{array}{r} (1) & Pr [X \leq q n] \end{array}

sehr klein ist. Aus Gründen der Lesbarkeit gehen wir davon aus, dass $q n$ eine ganze Zahl ist, weil wir nicht immer $⌊ q n ⌋$ schreiben wollen. Rechnen wir:

\begin{aligned} Pr [X \leq q n] & = \sum_{i = 0}^{q n} Pr [X = i] \\ (2) & = \sum_{i = 0}^{q n} p^{i} (1 - p)^{n - i} (\binom{n}{i}) \end{aligned}

Führen wir nun, rein aus Gründen der Analyse, Zufallsvariable $Y_{1}, \dots, Y_{n}$ ein mit $Pr [Y_{i} = 1] = q$ und $Pr [Y_{i} = 0] = 1 - q$ . Für $Y := Y_{1} + \dots + Y_{n}$ gilt $E [Y] = q n$ und somit wird $Pr [Y \leq q n]$ wohl nicht besonders klein sein. Auf jeden Fall gilt aber

\begin{array}{r} (3) & 1 \geq Pr [Y \leq q n] = \sum_{i = 0}^{q n} q^{i} (1 - q)^{n - i} (\binom{n}{i}) \end{array}

Die Ausdrücke ( $2$ ), für den wir eine obere Schranke suchen, und ( $3$ ), für den wir mit $1$ bereits eine nicht ganz schlechte obere Schranke gefunden haben, sehen rein formal sehr ähnlich aus. Versuchen wir nun, ersteren aus letzterem "herauszuquetschen":

\begin{aligned} 1 & \geq \sum_{i = 0}^{q n} q^{i} (1 - q)^{n - i} (\binom{n}{i}) \\ = \sum_{i = 0}^{q n} {(\frac{q}{p})}^{i} {(\frac{1 - q}{1 - p})}^{n - i} p^{i} (1 - p)^{n - i} (\binom{n}{i}) \end{aligned}

Jetzt müssen wir scharf hinschauen: da $q < p$ gilt, ist $\frac{q}{p} < 1$ und ist ${(\frac{q}{p})}^{i}$ abnehmend in $i$ ; ebenso ist $\frac{1 - q}{1 - p} > 1$ und somit ist ${(\frac{1 - q}{1 - p})}^{n - i}$ auch abnehmend in $i$ . Es gilt also: der Ausdruck ${(\frac{q}{p})}^{i} {(\frac{1 - q}{1 - p})}^{n - i}$ in der obigen Summe nimmt für $i = q n$ sein Minimum an, und somit gilt auch

\begin{aligned} 1 & \geq \sum_{i = 0}^{q n} {(\frac{q}{p})}^{i} {(\frac{1 - q}{1 - p})}^{n - i} p^{i} (1 - p)^{n - i} (\binom{n}{i}) \\ \geq \sum_{i = 0}^{q n} {(\frac{q}{p})}^{q n} {(\frac{1 - q}{1 - p})}^{n - q n} p^{i} (1 - p)^{n - i} (\binom{n}{i}) \\ = {(\frac{q}{p})}^{q n} {(\frac{1 - q}{1 - p})}^{n - q n} \cdot \sum_{i = 0}^{n} p^{i} (1 - p)^{n - i} (\binom{n}{i}) \\ = {(\frac{q}{p})}^{q n} {(\frac{1 - q}{1 - p})}^{n - q n} \cdot Pr [X \leq q n] . \end{aligned}

Wir lösen nach $Pr [X \leq n]$ auf und erhalten

\begin{array}{r} (4) & Pr [X \leq q n] \leq {({(\frac{q}{p})}^{q} {(\frac{1 - q}{1 - p})}^{1 - q})}^{- n} . \end{array}

Der Ausdruck $({(\frac{q}{p})}^{q} {(\frac{1 - q}{1 - p})}^{1 - q})$ ist immer mindestens $1$ und ist genau $1$ nur dann, wenn $p = q$ ist. Der Logarithmus dieses Ausdrucks, nämlich

\begin{array}{r} q \log (\frac{q}{p}) + (1 - q) \log (\frac{1 - q}{1 - p}) \end{array}

ist in der Literatur als Kullback-Leibler-Divergenz bekannt und wird manchmal mit $D (q | | p)$ abgekürzt.

Übungsaufgabe 2.7.1 Sei $q > p$ . Zeigen Sie, dass auch $Pr [X \geq q n]$ durch den Ausdruck in ( $4$ ) beschränkt ist.

Zusammenfassend erhalten wir:

Theorem 2.7.1 (Chernoff Bound). Seien $X_{1}, \dots, X_{n}$ Zufallsvariable mit Wertebereich ${0, 1}$ und $Pr [X_{i}] = p$ für jedes $i$ . Sei $X := X_{1} + \dots + X_{n}$ und $q \in [0, 1]$ . Dann gilt

\begin{array}{r} (falls q \leq p) & Pr [X \leq q n] \leq {({(\frac{q}{p})}^{q} {(\frac{1 - q}{1 - p})}^{1 - q})}^{- n} \\ (falls q \geq p) & Pr [X \geq q n] \leq {({(\frac{q}{p})}^{q} {(\frac{1 - q}{1 - p})}^{1 - q})}^{- n} \end{array}

Anwendung auf den Anderson-Miller-Algorithmus für List Ranking

Sei $T = 16 \log n$ . In Kapitel 2.6 haben wir gezeigt:

\begin{aligned} Pr [Nach T Schritten sind nicht alle Prozessoren fertig] & \leq \sum_{i = 1}^{p} Pr [\sum_{t = 1}^{T} Y_{t} < \log n] \\ = n \cdot Pr [\sum_{t = 1}^{T} Y_{t} < \log n] . \end{aligned}

Sei $Y = Y_{1} + \dots + Y_{T}$ . Es gilt $Pr [Y_{t}] = \frac{1}{4} =: p$ und $\log n = \frac{1}{16} \cdot T$ . Für $q := \frac{1}{16}$ haben wir nun also

\begin{aligned} Pr [Y < \log n] & = Pr [Y < q T] \\ \leq {({(\frac{q}{p})}^{q} {(\frac{1 - q}{1 - p})}^{1 - q})}^{- T} \\ = {({(\frac{1 / 16}{1 / 4})}^{1 / 16} {(\frac{15 / 16}{3 / 4})}^{15 / 16})}^{- 16 \log n} \\ = {(\frac{5^{15}}{4^{16}})}^{- \log n} \\ \leq 7^{- \log n} = n^{- 7} . \end{aligned}

und somit

\begin{aligned} Pr [Nach 16 \log n Schritten sind nicht alle Prozessoren fertig] & \leq n^{- 6} . \end{aligned}