Einleitung: Das kontraintuitivste Wunder der Wahrscheinlichkeitstheorie
2003 stellte der dänische Informatiker Peter Bro Miltersen das berühmte Problem der 100 Gefangenen vor:
- $100$ zum Tode verurteilte Gefangene tragen die Nummern $1$ bis $100$. In einem Raum stehen $100$ verschlossene Schubladen, in denen die Nummern $1$ bis $100$ zufällig verteilt liegen (eine Permutation $\sigma \in S_{100}$).
- Regel: Jeder Gefangene betritt einzeln den Raum und darf höchstens $50$ Schubladen öffnen, um seine eigene Nummer zu finden. Danach wird der Raum exakt in den Ausgangszustand versetzt; jede Kommunikation nach Spielbeginn ist ausgeschlossen (vorher darf eine Strategie vereinbart werden).
- Überlebensbedingung: Nur wenn alle $100$ Gefangenen ihre Nummer finden, werden alle begnadigt; scheitert auch nur ein Einziger, werden alle hingerichtet.
Öffnet jeder unabhängig $50$ zufällige Schubladen (unabhängige Strategie), hat jeder einzeln die Chance $1/2$, doch die gemeinsame Überlebenswahrscheinlichkeit beträgt:
$$\mathbb{P}(\text{alle überleben})_{\text{unabh.}} = \left(\frac{1}{2}\right)^{100} \approx 7{,}89 \times 10^{-31}$$Dennoch fand Miltersens Kollege Sven Skyum die Zyklensuchstrategie (Pointer-Following Strategy), die die Überlebenschance ohne ein einziges Bit Kommunikation auf $31{,}18\,\%$ katapultiert!
Kapitel 1: Die Zyklensuchstrategie und disjunkte Permutationszyklen
Skyums Strategie für Gefangenen Nummer $k \in \{1, \dots, 100\}$ lautet:
- Schritt 1: Öffne zuerst Schublade Nr. $k$.
- Schritt 2: Liegt darin der Zettel $x_1 = k$, bist du fertig. Falls $x_1 \neq k$, öffne als Nächstes Schublade Nr. $x_1$.
- Schritt 3: Lies die neue Nummer $x_2$ und öffne Schublade Nr. $x_2$, d. h. folge der Kette $k \mapsto \sigma(k) \mapsto \sigma^2(k) \mapsto \cdots$, bis $k$ gefunden ist oder $50$ Versuche verbraucht sind.
flowchart TD
Start["Gefangener k betritt den Raum (max. 50 Versuche)"]
Step1["Schritt 1: Öffne Schublade k, lies Zettel x = σ(k)"]
Check{"Zettel x == k ?"}
Win["Eigene Nummer k gefunden!"]
Limit{"Geöffnete Schubladen < 50 ?"}
Next["Folge dem Zeiger: Öffne Schublade x (x ← σ(x))"]
Lose["Nach 50 Schritten nicht bei k: Alle werden hingerichtet"]
Start --> Step1 --> Check
Check -- "Ja" --> Win
Check -- "Nein" --> Limit
Limit -- "Ja" --> Next --> Check
Limit -- "Nein (Zykluslänge ℓ > 50)" --> Lose
Warum funktioniert das? Die Zuordnung Schublade $\mapsto$ Zettel ist eine Bijektion $\sigma$ in der symmetrischen Gruppe $S_{2n}$ ($2n=100$). Jede endliche Permutation zerfällt eindeutig in disjunkte Zyklen:
$$\sigma = C_1 \circ C_2 \circ \cdots \circ C_m, \qquad \sum_{i=1}^m |C_i| = 2n = 100$$Da $\sigma$ bijektiv ist, hat kein Zyklus Sackgassen: Wer bei Schublade $k$ startet, durchläuft den eindeutigen Zyklus, der $k$ enthält, und endet beim Vorgänger $\sigma^{-1}(k)$ (der Schublade, die den Zettel $k$ enthält). Daher gilt:
- Gefangener $k$ hat genau dann Erfolg, wenn sein Zyklus die Länge $\ell \le 50$ hat.
- Alle $100$ Gefangenen überleben genau dann, wenn die Permutation $\sigma \in S_{100}$ keinen einzigen Zyklus der Länge $\ell > 50$ besitzt!
Kapitel 2: Abzählung langer Zyklen und harmonische Zahlen ($1 - \ln 2$)
Für $2n$ Gefangene ($n = 50$) kann eine Permutation $\sigma \in S_{2n}$ höchstens einen einzigen Zyklus der Länge $\ell > n$ enthalten, da zwei disjunkte Zyklen mindestens $(n+1)+(n+1) = 2n+2 > 2n$ Elemente bräuchten. Die Ereignisse $E_\ell := \{\sigma \text{ enthält einen Zyklus der Länge } \ell\}$ für $\ell = n+1, \dots, 2n$ sind somit paarweise disjunkt! Die Anzahl solcher Permutationen ist:
- Wähle $\ell$ Elemente für den langen Zyklus: $\binom{2n}{\ell}$ Möglichkeiten;
- Ordne diese $\ell$ Elemente zu einem gerichteten Kreis an: $(\ell - 1)!$ Möglichkeiten;
- Permutiere die übrigen $2n - \ell$ Elemente beliebig: $(2n - \ell)!$ Möglichkeiten.
Multiplikation kürzt fast alle Fakultäten weg:
$$|E_\ell| = \binom{2n}{\ell} \cdot (\ell - 1)! \cdot (2n - \ell)! = \frac{(2n)!}{\ell! \, (2n - \ell)!} \cdot (\ell - 1)! \, (2n - \ell)! = \frac{(2n)!}{\ell}$$Division durch $|S_{2n}| = (2n)!$ ergibt exakt $\mathbb{P}(E_\ell) = \frac{1}{\ell}$. Mit den harmonischen Zahlen $H_N = \sum_{k=1}^N \frac{1}{k}$ folgt die exakte Überlebenswahrscheinlichkeit:
$$\boxed{P_{\text{success}}(2n) = 1 - \sum_{\ell = n+1}^{2n} \frac{1}{\ell} = 1 - \left(H_{2n} - H_n\right) \xrightarrow{n \to \infty} 1 - \int_1^2 \frac{dx}{x} = 1 - \ln 2 \approx 30{,}685\,\%}$$Für $2n = 100$ erhält man $P_{\text{success}}(100) = 1 - (H_{100} - H_{50}) \approx \mathbf{31{,}1828\,\%}$!
Kapitel 3: Risikokopplung statt Informationsübertragung
flowchart TD
Pool["Fester Fehlerpool: Erwartete Fehlversuche E[Fehler] = 50"]
Indep["Unabhängige Strategie: Erfolge unkorreliert (Fehler über fast alle Welten verteilt)"]
Cycle["Zyklensuchstrategie: Schicksale über Zyklusstruktur von σ gekoppelt"]
ResI["In 99,99...92 % der Welten scheitert mind. 1 → Überleben ≈ 7,89×10⁻³¹"]
ResC["68,82 % der Welten (ℓ>50) bündeln alle Fehler → 31,18 % der Welten 100 % fehlerfrei!"]
Pool --> Indep --> ResI
Pool --> Cycle --> ResC
| Merkmal | 1. Unabhängige Strategie | 2. Zyklensuchstrategie |
|---|---|---|
| Einzelwahrscheinlichkeit $\mathbb{P}(A_k)$ | $50{,}00\,\%$ | $50{,}00\,\%$ (identisch) |
| Erwartete Erfolge $\mathbb{E}[X]$ | $50$ Gefangene | $50$ Gefangene (identisch) |
| Korrelation | Unabhängig | Stark positiv gekoppelt über $\sigma$ |
| Überlebenschance aller $100$ | $(1/2)^{100} \approx 7{,}89 \times 10^{-31}$ | $1 - (H_{100} - H_{50}) \approx 31{,}18\,\%$ |
| Grenzwert $n \to \infty$ | $0$ | $1 - \ln 2 \approx 30{,}685\,\%$ |
- Kopplung (Coupling): Da 1 Fehlversuch genauso tödlich ist wie 51 Fehlversuche, bündelt die Zyklensuchstrategie alle Fehlversuche in den $68{,}82\,\%$ Permutationen mit einem langen Zyklus ($\ell > 50$), sodass volle $31{,}18\,\%$ des Wahrscheinlichkeitsraums komplett fehlerfrei bleiben!
- Schutz gegen einen böswilligen Wärter: Vereinbaren die Gefangenen vorab eine geheime Zufallsbijektion $\tau \in S_{100}$, verwandelt die Konjugation $\tau \sigma \tau^{-1}$ jede manipulierte Anordnung wieder in eine gleichverteilte Zufallspermutation mit $31{,}18\,\%$ Überlebenschance.