Dieser Blogpost besteht aus Material eines Seminarvortrags, den ich im Sommeresemester 2020 im Seminar Wahrscheinlichkeitstheorie am Hasso-Plattner-Institut bei Timo Kötzing und Matrin Schirneck gehalten habe.

Intuition

Ihr kennt sicher aus der Schule Aufgaben wie diese:

Beispiel 1: Die Bauarbeiter heben $1m^3$ Boden pro Stunde aus. Wie lange brauchen sie um ein Loch der Größe $10m \times 1m \times 1m$ zu buddeln?

Beispiel 2: Ein Mensch wird mit 1 Millionen Viren infiziert. Er ist geheilt, wenn er weniger als 1'000 Viren im Körper hat; dann erledigt das Immunsystem den Rest. Ein Medikament stoppt die Fortpflanzung des Virus und tötet pro Stunde die Hälfte der verbleibenden Viren. Wie lange dauert es, bis der Patient geheilt ist?

Drift-Theorie ist die Antwort auf die Frage: Was ist, wenn wir jetzt noch Wahrscheinlichkeit ins Spiel bringen?

Was ist nun, wenn wir folgende Frage stellen?

Beispiel 3: Die Bauarbeiter werfen nun jede Stunde eine Münze: Wenn sie Kopf zeigt, dann machen sie gar nichts. Wenn Sie Zahl zeigt, dann legen sie richtig los und heben sogar $2m^3$ aus. Wie lange brauchen sie so für die $10m \times 1m \times 1m$?

Unsere Intuition würde sagen, dass sie genau so lange brauchen. Wir erwarten, dass sie nur jede zweite Stunde arbeiten, aber dafür gleich doppelt so viel. Unsere Intuition ist aber in der Wahrscheinlichkeitstheorie ein schlechtes Werkzeug. Ändert sich eure Meinung, wenn ihr folgendes Argument hört: Die Bauarbeiter können nun bestenfalls halb so lange brauche, aber auch beliebig lange brauchen. Was denkst Du nun über den Erwartungswert?

Was machen wir, wenn wir uns nicht sicher sind, was die Antwort ist? Wir rechnen einfach mal nach! Dazu formalisieren wir zunächst unseren Prozess. Sei $X_t$ die Zufallsvariable, die angibt, wie viel Loch nach $t$ Stunden noch gebuddelt werden muss. Dann gilt $X_0 = 10m \cdot 1m \cdot 1m = 10m^3$, da am Anfang das Loch natürlich noch komplett unausgehoben ist. Für alle $t$ mit $X_t \ne 0$ gilt dann

\[ P[X_{t+1} = X_t - 2] = \frac{1}{2} \quad \text{ und} \\ P[X_{t+1} = X_t] = \frac{1}{2}. \]

Die erste Gleichung beschreibt den Fall, dass die Bauarbeiter arbeiten und die zweite, dass sie eine Pause machen.

Wir fragen uns nun, wann das Loch fertig ist, also was das kleinste $t$ ist, sodass $X_t=0$. Dieses $t$ nennen wir die First hitting time (fn::Es ist der Zeitpunkt, wo wir erstmalig das Ziel erreichen. Daher der Name.) und bezeichnen es mit $T$.

Werfen die Bauarbeiter jedes mal Zahl, so arbeiten sie voll durch und brauchen nur 5 Stunden. Die Wahrscheinlichkeit dafür können wir leicht ausrechnen:

\[ P[T = 5] = \bigg(\frac{1}{2}\bigg)^{5}. \]

Für alle anderen Werte können wir auch unser Vorwissen nutzen. Die Bauarbeiter brauchen immer genau 5 Stunden Arbeitszeit. Brauchen sie länger, so wird diese Zeit für Pausen benutzt. Dabei spielt es keine Rolle, in welcher Reihenfolge Arbeit und Pause stehen, solange die letzte Stunde gearbeitet wird. Dass heißt die vier anderen Arbeitszeiten können frei über die restliche Zeit verteilt werden. Es ergibt sich für alle $n \ge 5$ die Formel

\[ P[T = n] = \binom{n-1}{4} \bigg( \frac{1}{2} \bigg)^{5} \cdot \bigg( \frac{1}{2} \bigg)^{n - 5} \\ = \binom{n-1}{4} \bigg( \frac{1}{2} \bigg)^{n}. \]

Damit erhalten wir für den Erwartungswert

\[ E[T] = \sum_{n=5}^{\infty} n \cdot P[T = n] \\ = \sum_{n=5}^{\infty} n \cdot \binom{n-1}{4} \bigg( \frac{1}{2} \bigg)^{n} \\ = 10. \]

Das ist ja genau das, was wir vermutet haben! Unsere Intuition hat uns zwar ausnahmsweise nicht getrügt, es war aber erstaunlich schwer ein formales Ergebnis zu erhalten. (Das Ausrechnen der unendlichen Summe haben wir einfach übersprungen.) Was ist also, wenn die Aufgaben schwerer werden? Als nächstes wollen wir ein mächtiges Werkzeug kennen lernen, das diese Art von Aufgaben vereinfacht.

Die grundlegenden Drift-Theoreme

Von den folgenden Sätzen gebe ich den zweiten ohne Beweis an. Dieser ist bei [KK18] und [Len19] zu finden.

Satz 1, Additives Drift-Theorem: Sei $(X_t)_{t\in \mathbb{N}}$ ein Zufallsprozess über einem endlichen Zustandsraum $S \subset \mathbb{R}^+_0$, der die $0$ enthält. Bezeichnen wir $T=\min \{t \mid X_t = 0\}$.

Gibt es eine Konbstante $\delta > 0$, sodass für alle $s \in S$ die Gleichung

\[E[X_t - X_{t+1} \mid X_t = s, t < T] \ge \delta \text{ gilt, dann gilt auch } E[T] \le \frac{E[X_0]}{\delta}. \]

Analog ergibt sich, dass wenn für alle $s \in S$ die Gleichung

\[ E[X_t - X_{t+1} \mid X_t = s, t < T] \le \delta \text{ gilt, dann gilt auch } E[T] \ge \frac{E[X_0]}{\delta}. \]

Dieser Satz erlaubt uns Fragen wie Übung 3 zu beantworten. Als nächstes lernen wir einen Satz kennen, der Antworten auf die randomisierte Varianten von Übung 2 geben kann.

Die Bauarbeiter aus Beispiel 3 brauchen im Erwartungswert 10 Stunden.

Unabhängig vom aktuellen Zustand (wie viel Loch noch zu buddeln ist) erwarten wir, dass die Bauarbeiter in der Hälfte der Fälle nichts tun und in der anderen Hälfte der Fälle $2m^3$ ausheben. Es ergibt sich für alle Zeitpunkte vor der Fertigstellung des Lochs $t < T$ der Erwartungswert

\[ E[X_t - X_{t+1}] = 2 \cdot \frac{1}{2} + 0 \cdot \frac{1}{2} = 1. \]

Nehmen wir nun $\delta = 1$ in Satz 1, so erhalten wir die Schranken

\[ E[T] \le \frac{E[X_0]}{\delta} = \frac{10}{1} = 10 \quad \text{ und}\\ E[T] \ge \frac{E[X_0]}{\delta} = \frac{10}{1} = 10. \]

Es gilt also $E[T] = 10$.

Das war doch viel einfacher als das ganze rumärgern mit unendlichen Summen! Und vor allem sind die Drift-Theoreme, die hier vorgestellt wurden, sehr intuitiv. Wir haben im Grunde genau das getan, was wir in der fünften Klassen auch schon gemacht haben: Wir haben die Arbeitsmenge durch die Arbeitsgeschwindigkeit geteilt, um die Arbeitszeit zu erhalten. Genau das erlaubt uns das additive Drift-Theorem auch dann, wenn die Arbeitsmenge oder Arbeitsgeschwindigkeit zufällig ist.

Satz 2, Multiplikatives Drift-Theorem: Sei $(X_t)_{t\in \mathbb{N}}$ ein Zufallsprozess über einem endlichen Zustandsraum $S \subset \mathbb{R}^+_0$, der die $0$ enthält. Bezeichnen wir $T=\min \{t \mid X_t = 0\}$.

Gibt es eine Konstante $\delta > 0$, sodass für alle $s \in S$ die Gleichung

\[ E[X_t - X_{t+1} \mid X_t = s, t < T] \ge s\delta \text{ gilt, dann gilt auch } E[T] \le \frac{1 + \ln E[X_0]}{\delta}. \]

Außerdem gilt für alle $k > 0$ und $s \in S$,

\[ P\bigg[T > \frac{k + \ln s}{\delta} \biggm| X_0 = s\bigg] \le e^{-k}. \]

Ein Beweis zwischendurch

Dieser Beweis ist an [Len19, S. 7f.] angelehnt. Wer mag, findet dort auch den Beweis für die untere Schranke.

Beweis der oberen Schranke im ADT Wir nehmen ohne Beschränkung der Allgemeinheit an, dass für alle $t \ge T$ gilt, dass $X_t = 0$.

Aus der Bedingung, dass für alle $s \ne 0$ gilt, dass \(E[X_t - X_{t+1} \mid X_t = s, t < T] \ge \delta\) erhalten wir

\begin{equation} E[X_{t+1} \mid t < T] \le E[X_t \mid t < T] - \delta. \quad (1) \end{equation}

Wenden wir nun das Gesetz der totalen Wahrscheinlichkeit an, so gilt

\[ E[X_t] = P[t < T] \cdot E[X_t \mid t < T] + P[t \ge T] \cdot E[X_t \mid t \ge T]. \]

Der letzte Summand ist nach unserer Annahme am Anfang des Beweises gleich null, also gilt \(E[X_t] = P[t < T] \cdot E[X_t \mid t < T]\).

Anolog erhalten wir

\[ E[X_{t+1}] = P[t < T] \cdot E[X_{t+1} \mid t < T] \]

Wenden wir nun die Ungleichung (1) an, so gilt

\begin{equation} E[X_{t+1}] \le P[t < T] \cdot (E[X_t \mid t < T] - \delta) \nonumber \\ = E[X_t] - \delta \cdot P[t < T]. \quad (2) \end{equation}

Da $T$ eine Zufallsvariable über $\mathbb{N}$ ist, gilt \(E[T] = \sum_{t=0}^{\infty}P[T > t]\). Daraus folgt

\[ \delta E[T] \xleftarrow{\tau \to \infty} \sum_{t=0}^\tau \delta P[T > t]. \]

Aus der Ungleichung (2) erhalten wir die Teleskopsumme

\[ \le \sum_{t=0}^\tau (E[X_t] - E[X_{t+1}]) \\ = E[X_0] - E[X_{t+1}]. \]

Und da alle Elemente des Zustandsraums nicht-negativ sind, gilt \(E[X_{t+1}] \ge 0\) und damit

\[ \le E[X_0]. \]

Fassen wir diese lange Formel nun zusammen, so erhalten wir

\[ \delta E[T] \le E[X_0]. ∎ \ \]

Anwendungen

Beweise mit den Drift-Theoremen

Einfache Beweise über Algorithmen oder ähnliche Prozesse mit Drift-Theoremen folgen häufig der folgenden Struktur. Diese soll Euch bei den Übungen helfen.

  1. Formalisiere den Algorithmus als Super-Martingal. Dafür verwendet mensch häufig nicht die Zustände des Algorithmus, sondern eine Darstellung als Zahl. Wichtig ist dabei, dass der Algorithmus genau dann terminiert, wenn der Zufallsprozess den Zustand 0 erreicht.

  2. Versuche eine Schranke für den Drift pro Schritt zu finden.

  3. Benutze Drift-Theoreme, um daraus eine Laufzeitschranke zu erhalten.

Coupon-Collector

Wir haben $n$ verschiedene Sammelkarten, die jeweils gleichverteilt mit der Wahrscheinlichkeit \(1/n\) auftreten. Die Frage lautet nun: Wie viele Karten muss ich im Erwartungswert kaufen, um alle Sammelbilder zu haben?

Satz 3: Beim Coupon-Collector-Prozess mit \(n\) Sammelbildern müssen im Erwartungswert maximal \(n (1+\ln n)\) Karten gekauft werden.

Beweis Sei \(X_t\) der Zufallsprozess, der die Anzahl der fehlenden Karten nach \(t\) Käufen angibt. Die Wahrscheinlichkeit im Zustand \(X_t\) eine neue Karte zu erhalten (also einen Fortschritt von 1 zu machen), ist \(\frac{X_t}{n}\). Also können wir über den Drift sagen, dass

\[ E[X_t - X_{t+1} \mid X_t = s] = \frac{s}{n}. \]

Nehmen wir nun im multiplikativen Drift-Theorem (Satz 2) \(delta = \frac{1}{n}\), so erhalten wir eine Schranke für den erwarteten Zeitpunkt \(T\) zu dem wir alle Karten besitzen:

\[ E[T] \le \frac{1+\ln E[X_0]}{\frac{1}{n}} = n (1+\ln E[X_0]). \] Da uns zu Beginn noch alle \(n\) Karten fehlen, gilt \(E[X_0] = n\) und damit erhalten wir die gesuchte Schranke. ∎

Randomisierte Algorithmen

Sortieren in \(\mathcal{O}(n^2 \log n)\)

Zugegeben, das klingt jetzt erstmal nicht so toll, illustriert aber gut, wie man Drift-Theoreme auf randomisierte Algorithmen anwenden kann.

Definition 4 Ein Fehlstand in einem Array \(A\) ist ein Paar von Indizes \(i < j\), sodass \(A[i] > A[j]\).

Die Anzahl der Fehlstände eines Array gibt uns also ein Maß dafür, wie unsortiert der Array ist. Genau das nutzen wir in der Analyse des folgenden Algorithmus.

Satz 5: Unser Algorithmus erhält einen Array der Länge \(n\). In jedem Schritt wählt er gleichverteilt zufällig zwei Positionen aus und überprüft, ob die entsprechenden Elemente in der falschen Reihenfolge sind. Dann tauscht er sie aus.

Der Array ist im Erwartungswert nach \(\mathcal{O}(n^2 \log n)\) Schritten sortiert.

Um die Anwendung der Drift-Theorie im Beweis des Satzes klarer zu sehen, werden wir voher ein paar Details als Lemma beweisen.

Lemma 6: Sei \(A\) ein Array der Länge \(n\) und sei \(i<j\) ein Fehlstand in \(A\). Vertauschen wir die Elemente an den Positionen \(i,j\) in \(A\), so reduziert sich die Anzahl der Fehlstände um mindestens 1.

Beweis Offensichtlich sind nur die Elemente an Positionen \(i < k < j\) für uns interessant.\footnote{Für alle anderen ändert sich die Beziehung zu \(A[i]\) und \(A[j]\) nicht.}

Betrachten wir nun drei Fälle.

Fall I: \(A[k] < A[j] (< A[i])\). Dann ist \((k,j)\) ein Fehlstand vor der Vertauschung und danach. Außerdem ist \((i,k)\) weder vor der Vertauschung noch danach ein Fehlstand. Damit bleibt die Anzahl der Fehlstände konstant.

Fall II: \(A[k] > A[i] (> A[j])\). Dieser Fall verläuft analog zu Fall I und die Anzahl der Fehlstände bleibt konstant.

Fall III: \(A[j] < A[k] < A[i]\). Dann sind \((i,k)\) und \((k,j)\) Fehlstände vor der Vertauschung, nicht aber danach. Die Anzahl der Fehlstände reduziert sich also.

Zusammenfassend gilt also, dass der Fehlstand \((i,j)\) beseitigt wird und alle anderen Fehlstände entweder erhalten bleiben oder verschwinden, aber nie neue entstehen. Damit reduziert sich die Anzahl der Fehlstände mindestens um 1. ∎

Nach dem wir nun genau untersucht haben, was passiert, wenn man Fehlstände korrigiert, können wir den Algorithmus analysieren.

Beweis zu Satz 5 Sei \(X_t\) der Zufallsprozess, der angibt, wie viele Fehlstände nach \(t\) Schritten im Arary sind. Wählt der Algorithmus ein Paar aus, das kein Fehlstand ist, so pasiert nichts, wählt er einen Fehlstand aus, so verringert sich die Anzahl der Fehlstände nach Lemma 6 um mindestens eins. Damit gilt

\[ E[X_t - X_{t+1} \mid t < T] \le \frac{X_t}{\binom{n}{2}} \cdot 1. \]

Wobei der Nenner daher stammt, dass es \(\binom{n}{2}\) Möglichkeiten gibt, ein Paar von Indizes auzuwählen.

Nehmen wir nun \(\delta = 1/\binom{n}{2}\) im multiplikativen Drift-Theorem, so erhalten wir eine Schranke für die erwartete Anzahl von Schritten

\[ E[T] \le \frac{1+\ln E[X_0]}{\frac{1}{\binom{n}{2}}} = \binom{n}{2} (1+\ln E[X_0]). \]

Da maximal alle Paare von Indizes Fehlstände sein können, gilt \(E[X_0] \le \binom{n}{2}\), gilt

\[ E[T] \le \binom{n}{2} \bigg(1+\ln \binom{n}{2}\bigg). \] Aus der Kombinatorik wissen wir \(\binom{n}{2}=\frac{1}{2} n(n-1) \le n^2\). Damit gilt \(E[T] \le n^2(1 + \ln(n^2)) = n^2 + n^2 \cdot 2 \ln n \in \mathcal{O}(n^2 \log n)\). ∎

Literaturausblick

Ich folge in meiner Darstellung [GKK18]. Dort finden sich auch viele der Übungen und ähnliche einfache algorithmische Anwendungen.

Bei [KK18] finden sich viele sehr coole Beweise zu Drift-Theoremen.

Bei [DJW12] findet sich eine gute Einführung in Drift-Theorie zur Analyse von evolutionären Algorithmen.

Die mathematischen und algorithmischen Grundlagen, die man für Drift-Theorie benötigt, kann man gut bei [MR95] nachlesen.

[DJW12] Benjamin Doerr, Daniel Johannsen und Carola Winzen. „Multiplicative Drift Analysis“. In: Al gorithmica 64.4 (2012). Place: New York, NY Publisher: Springer, S. 673–697. issn: 0178-4617. doi: 10.1007/s00453-012-9622-x.

[GKK18] Andreas Göbel, Timo Kötzing und Martin S. Krejca. „Intuitive Analyses via Drift Theory“. In: (2018). _eprint: 1806.01919. url: https://arxiv.org/pdf/1806.01919.pdf.

[KK18] Timo Kötzing und Martin S. Krejca. „First-Hitting Times Under Additive Drift“. In: Lecture Notes in Computer Science (2018). ISBN: 9783319992594 Publisher: Springer International Publishing, S. 92–104. issn: 1611-3349. doi: 10.1007/978- 3- 319- 99259- 4_8. url: http://dx.doi.org/10.1007/978-3-319-99259-4_8.

[Len19] Johannes Lengler. „Drift Analysis“. In: Theory of Evolutionary Computation (Nov. 2019). ISBN: 9783030294144 Publisher: Springer International Publishing, S. 89–131. issn: 1619-7127. doi: 10.1007/978-3-030-29414-4_2. url: http://dx.doi.org/10.1007/978-3-030-29414-4_2.

[MR95] Rajeev Motwani und Prabhakar Raghavan. Randomized Algorithms. 1/e. Cambridge: Cambridge University Press, 1995.