Einleitung: Warum kristallisieren sich winzige Anfangszufälle zu unumkehrbaren Asymmetrien?
Zwei Videos oder Standards gleicher Qualität starten gleichzeitig: Durch einen winzigen Zufallsvorsprung gewinnt eines durch positives Feedback die Marktdominanz (Matthäus-Effekt), während das andere verschwindet. Das starke Gesetz der großen Zahlen (SLLN) lehrt für unabhängige (i.i.d.) Münzwürfe das Gegenteil: Anfangsschwankungen waschen sich für $n \to \infty$ aus und der Anteil konvergiert fast sicher gegen die Konstante $p$.
Reale Prozesse sind oft verstärkte stochastische Prozesse, bei denen das Eintreten eines Ereignisses die Wahrscheinlichkeit seiner Wiederholung erhöht. 1923 führten George Pólya und Florian Eggenberger das Pólya-Urnenmodell ein, das zwei Paradoxa zeigt:
- Erstes Paradoxon (Austauschbarkeit): Obwohl sich der Urneninhalt nach jedem Zug ändert, bleibt $\mathbb{P}(I_n = 1) = \frac{r}{r+b}$ für alle $n$ konstant, und die Wahrscheinlichkeit einer Folge hängt nur von der Anzahl roter und blauer Kugeln ab, nicht von ihrer Reihenfolge (Exchangeability).
- Zweites Paradoxon (Zufälliger Grenzwert): Für $n \to \infty$ konvergiert der rote Anteil $X_n$ fast sicher gegen eine Zufallsvariable $X_\infty \sim \mathrm{Beta}(r, b)$. Für $r=1, b=1$ ist $X_\infty \sim \mathrm{Uniform}(0, 1)$ gleichverteilt auf $[0, 1]$!
Kapitel 1: Drei Urnen-Universen — Erschöpfung, Gedächtnislosigkeit und Pólya-Verstärkung
Bei $n = 0$ enthalte eine Urne $R_0 = r$ rote und $B_0 = b$ blaue Kugeln ($N_0 = r + b$). In jedem Schritt wird eine Kugel gezogen und mit $c$ Kugeln derselben Farbe zurückgelegt: 1. Ohne Zurücklegen ($c = -1$) (negatives Feedback, hypergeometrisch), 2. Mit Zurücklegen ($c = 0$) (i.i.d. $\mathrm{Binomial}(n, \frac{r}{r+b})$), 3. Pólya-Urne ($c = +1$) (positives Feedback: gezogene Kugel plus $1$ Kugel gleicher Farbe).
flowchart TD
Start["Start (n = 0): Rot r, Blau b, X₀ = r/(r+b)"]
Draw["Schritt n+1: 1 Kugel ziehen, P(Iₙ₊₁ = 1 | Fₙ) = Xₙ"]
BranchW["1. Ohne Zurücklegen (c = -1)"]
BranchB["2. Mit Zurücklegen (c = 0)"]
BranchP["3. Polya-Urne (c = +1)"]
LimW["Endet bei n = r+b mit r/(r+b)"]
LimB["SLLN: Xₙ → r/(r+b) f.s."]
LimP["Doob: Xₙ → X_∞ ~ Beta(r, b) f.s."]
Start --> Draw
Draw --> BranchW --> LimW
Draw --> BranchB --> LimB
Draw --> BranchP --> LimP
Mit $I_n \in \{0, 1\}$ und $S_n = \sum_{k=1}^n I_k$ gilt $R_n = r + S_n$ und $N_n = r + b + n$:
$$X_n := \frac{R_n}{N_n} = \frac{r + S_n}{r + b + n}, \qquad \mathbb{P}(I_{n+1} = 1 \mid \mathcal{F}_n) = X_n, \qquad |X_{n+1} - X_n| \le \frac{1}{r + b + n + 1}$$| Eigenschaft | 1. Ohne Zurücklegen ($c = -1$) | 2. Mit Zurücklegen ($c = 0$) | 3. Pólya-Urne ($c = +1$) |
|---|---|---|---|
| Rückkopplung | Negativ (Erschöpfung) | Keine (gedächtnislos) | Positiv (Selbstverstärkung) |
| Abhängigkeit | Negativ korreliert | Unabhängig (i.i.d.) | Unendlich austauschbar |
| Verteilung $S_n$ | $\mathrm{Hypergeom}(N_0, r, n)$ | $\mathrm{Binomial}(n, \frac{r}{r+b})$ | $\mathrm{BetaBinom}(n, r, b)$ |
| Grenzwert $X_\infty$ | Konstante $\frac{r}{r+b}$ | Konstante $\frac{r}{r+b}$ f.s. | Zufallsvariable $\mathrm{Beta}(r, b)$ f.s. |
Kapitel 2: Austauschbarkeit und Beta-Binomialverteilung
Für jede Folge $(i_1, \dots, i_n) \in \{0, 1\}^n$ mit $k = \sum_{j=1}^n i_j$ roten Zügen ist das Nennerprodukt stets $(r+b)^{(n)}$ und das Zählerprodukt kommutativ stets $r^{(k)} b^{(n-k)}$:
$$\mathbb{P}(I_1 = i_1, \dots, I_n = i_n) = \frac{r^{(k)} \, b^{(n-k)}}{(r+b)^{(n)}}, \qquad \mathbb{P}(S_n = k) = \binom{n}{k} \frac{\mathrm{B}(r+k, \, b+n-k)}{\mathrm{B}(r, \, b)}$$Für $r = 1, b = 1$ kürzen sich alle Fakultäten zur diskreten Gleichverteilung $\mathbb{P}(S_n = k) = \frac{1}{n + 1}$ ($k = 0, 1, \dots, n$).
Kapitel 3: Doobscher Martingalkonvergenzsatz und $\mathrm{Beta}(r,b)$-Grenzwert
Wegen $\mathbb{E}[R_{n+1} \mid \mathcal{F}_n] = R_n + X_n = (N_n + 1)X_n$ ist $X_n$ ein beschränktes Martingal auf $[0, 1]$:
$$\mathbb{E}[X_{n+1} \mid \mathcal{F}_n] = \frac{R_n + \mathbb{E}[I_{n+1} \mid \mathcal{F}_n]}{N_n + 1} = \frac{(N_n + 1) X_n}{N_n + 1} = X_n$$Nach dem Doobschen Martingalkonvergenzsatz gilt $X_n \xrightarrow{\text{f.s.}} X_\infty$. Mit $\frac{\Gamma(z+\alpha)}{\Gamma(z+\beta)} \sim z^{\alpha-\beta}$ für $k = \lfloor np \rfloor$ folgt die Dichte der Betaverteilung $\mathrm{Beta}(r, b)$:
$$\boxed{f_{X_\infty}(p) = \frac{\Gamma(r+b)}{\Gamma(r)\Gamma(b)} \, p^{r-1} (1-p)^{b-1} \quad (0 < p < 1), \qquad \mathbb{E}[X_\infty] = \frac{r}{r+b}, \qquad \mathrm{Var}(X_\infty) = \frac{rb}{(r+b)^2(r+b+1)} > 0}$$Kapitel 4: Satz von de Finetti, Phasenübergänge und Anwendungen
- Darstellungssatz von de Finetti (1931): Jede unendlich austauschbare Folge ist eine Mischung von i.i.d. Bernoulli-Versuchen bezüglich des Prior-Maßes $\mathrm{Beta}(r,b)$: $$\mathbb{P}(I_1 = i_1, \dots, I_n = i_n) = \int_0^1 p^k (1-p)^{n-k} \, \frac{\Gamma(r+b)}{\Gamma(r)\Gamma(b)} p^{r-1}(1-p)^{b-1} \, dp$$
- Nichtlineare Urnen ($f(x) = \frac{x^\gamma}{x^\gamma + (1-x)^\gamma}$): $X_{n+1} - X_n = \frac{1}{N_n+1}[(f(X_n)-X_n) + \xi_{n+1}]$ liefert drei Phasen:
flowchart TD
Root["Nichtlineare Urne: f(x) = x^γ / (x^γ + (1-x)^γ)"]
Sub["1. Sublinear (0 < γ < 1)"]
Lin["2. Linear (γ = 1): g(x) ≡ 0"]
Sup["3. Superlinear (γ > 1)"]
ResSub["Koexistenz: Xₙ → 1/2 f.s."]
ResLin["Pfadabhängig: Xₙ → Beta(r, b) f.s."]
ResSup["Winner-Take-All: P(X_∞ ∈ {0, 1}) = 1"]
Root --> Sub --> ResSub
Root --> Lin --> ResLin
Root --> Sup --> ResSup
- Anwendungen & Grenzen: W. Brian Arthurs Lock-In (1989) erklärt Monopole bei $\gamma > 1$ (QWERTY, VHS); Preferential Attachment (Yule–Simon / Barabási–Albert) erzeugt $P(k) \sim k^{-(2 + \frac{1}{1-\alpha})}$; neue Farben mit Gewicht $\theta > 0$ aus $H_0$ führen zum Dirichlet-Prozess $\mathrm{DP}(\theta, H_0)$ (CRP); MusicLab (Salganik et al. 2006) zeigt vier Grenzen: Fitness $\eta_i$, Sättigung, Gedächtnis und Netzwerk.