Gegeben eine unparteiische Münze, kannst du die Bernoulli-Verteilung mit einer beliebigen Wahrscheinlichkeit $p$ modellieren?

Extra: Wie funktioniert der Rückweg?

Faire Münze zu beliebiger Münze

Angenommen, du hast nur Zugang zu einer unparteiischen Münze, die Kopf und Zahl jeweils mit einer Wahrscheinlichkeit von $\frac{1}{2}$ zeigt. Gegeben eine Wahrscheinlichkeit $p$ mit $0 < p < 1$. Ich zeige dir einen eleganten Trick, wie du deine Münze effizient nutzen kannst, um einen Zufallsprozess mit einer resultierenden binären Variable $Z$ zu modellieren, sodass $P(Z = 1) = p$. Natürlich wollen wir die Anzahl der Münzwürfe $T$ im Erwartungswert minimal halten.

Die Idee ist ziemlich einfach. Unter Verwendung der $2$-adischen (oder binären) Darstellung von $p$ können wir schreiben

$$ p = [0.p_1 p_2 p_3 \dots]2 = p_1/2 + p_2/4 + p_3/8 + \dots = \sum, $$ für $p_i \in {0, 1}$. Zum Beispiel würde $p = 1/3$ geschrieben als:}^\infty{\frac{p_i}{2^i}

$$ p = 1/3 = [0.01010101\dots]_2 = [0.\overline{01}]_2. $$

Dies kann mit der bekannten Formel $\sum_{k \geq 0}{q^k} = \frac{1}{1 - q}$ für $0 < q < 1$ überprüft werden: $$ [0.\overline{01}]2 = \frac{1}{4} + \frac{1}{16} + \frac{1}{64} + \frac{1}{256} + \dots = \sum - 1 = 4/3 - 1 = 1/3. $$}{\left( \frac{1}{4}\right)^k

Die Lösung ist, durch die Ziffern der $2$-adischen Darstellung nach dem Dezimalkomma zu iterieren und in jedem Schritt eine Münze zu werfen:

• Kopf: zum nächsten Ziffernplatz fortfahren.
• Zahl: den Prozess stoppen und den Wert der aktuellen Ziffer $p_i$ als Ergebnis ausgeben.

Wir bezeichnen $S$ als die Sequenz der Münzwürfe, die im Prozess stattgefunden haben. Es kann gezeigt werden, dass die $i$-te Ziffer nach dem Dezimalkomma mit einer Wahrscheinlichkeit von $1 / 2^i$ ausgewählt wird und die einzige Sequenz des Prozesses, die zu dieser Ziffer führt, ist $S = kk\dots kz = k^{i-1}z$ ($k$ steht für Kopf, $z$ für Zahl). Dies gibt uns exakt $p$ zurück:

\begin{align} P(Z = 1) &= P(S = z, p_1 = 1) + P(S = kz, p_2 = 1) + \dots \ &= P(S = z) p_1 + P(S = kz) p_2 + \dots \ &= \frac{1}{2} p_1 + \frac{1}{4} p_2 + \dots \ &= [0.p_1 p_2 p_3 \dots]_2 = p. \end{align}

Die Anzahl der Schritte $T$, die der Prozess benötigt, ist geometrisch verteilt mit $q = 1/2$, also $$ E[T] = 1/q = 2, $$ zusammenfassend erwarten wir nur zwei Münzwürfe zu benötigen, um die Bernoulli-Verteilung mit Wahrscheinlichkeit $p$ zu modellieren.

Beliebige Münze zu fairer Münze

Der umgekehrte Weg ist ebenfalls ein bekannter Trick. Gegeben eine Münze, die mit Wahrscheinlichkeit $p$ Kopf und $1-p$ Zahl zeigt ($0 < p < 1$), müssen wir einen Prozess $Z$ modellieren, der $0$ oder $1$ mit gleicher Wahrscheinlichkeit $\frac{1}{2}$ ausgibt.

Wir werfen unsere unfaire Münze zweimal und notieren die Ergebnisse $S = (S_1, S_2)$, dann gehen wir jeden Fall wie folgt durch:

• $S = (k, z) \Rightarrow$ Ausgabe $Z = 1$;
• $S = (z, k) \Rightarrow$ Ausgabe $Z = 0$;
• $S = (k, k)$ oder $S = (z, z)$ dann werfe erneut.

Wir können leicht berechnen, dass die Wahrscheinlichkeiten der ersten beiden Fälle gleich sind:

\begin{align} P(S = (k, z)) &= P(S_1 = k, S_2 = z) \ &= P(S_1 = k) P(S_2 = z) \ &= p(1-p) = (1-p)p \ &= P(S_1 = z, S_2 = k) = P(S = (z, k)). \end{align}

Durch Induktion folgt, dass für jede Länge $T$ des Prozesses die beiden Ergebnisse gleich wahrscheinlich sind, also $1/2$ betragen müssen.

Wie viele Münzwürfe brauchen wir? Für jeden Schritt müssen wir zwei Münzen werfen, also müssen wir das Doppelte der Anzahl der Schritte $T$ des Prozesses betrachten. $T$ ist geometrisch verteilt mit Erfolgswahrscheinlichkeit $2p(1-p) = 1 - (p^2 + (1-p)^2)$. Die mittlere Anzahl der Schritte beträgt somit $\frac{1}{2p(1-p)}$.

Es kann gesehen werden, dass für die meisten Konfigurationen von $p$ wir $4$ Münzwürfe benötigen (da die erwartete Anzahl der Prozessschritte/Runden $2$ beträgt). Um $p = \frac{8}{11}, \frac{3}{11}$ herum beginnen wir, durchschnittlich $5$ Würfe zu benötigen. Offensichtlich “explodiert” dies in der Nähe der Grenzen, da entweder Kopf oder Zahl immer wieder geworfen wird, was eine weitere Runde erfordert.