Musterwettlauf mit einer verzerrten Münze

• Teil 1: P(HTH erscheint vor HHT) = q/(1 + q) = (1 − p)/(2 − p).

  • Richten Sie eine Markov-Kette auf den „nützlichen Suffix“-Zuständen ein: S (kein Fortschritt), H, HH, HT. Wichtige strukturelle Tatsache: Aus dem Zustand HH gewinnt das Muster HHT mit Sicherheit, da Köpfe uns in HH halten und die erste Zahl HHT sofort vervollständigt, bevor HTH jemals gebildet werden kann; also P(HTH zuerst | HH) = 0.
  • Sei a, b, c die Wahrscheinlichkeit, dass HTH von S, H, HT aus gewinnt. Dann ist a = p·b + q·a (also a = b), b = p·0 + q·c und c = p·1 + q·a. Lösen: a = q(p + qa), also a(1 − q²) = pq, was a = pq/(p(1+q)) = q/(1+q) ergibt.
  • Plausibilitätsprüfung: Für eine faire Münze (p = 1/2) ergibt sich 1/3, was dem bekannten Ergebnis entspricht, dass HHT HTH mit einer Wahrscheinlichkeit von 2/3 schlägt.

• Teil 2: E[Anzahl der Würfe bis zum ersten von HTH oder HHT] = (1 + p q²)/(p² q (1 + q)), mit q = 1 − p.

  • Unter Verwendung derselben Zustände seien E_S, E_H, E_HH, E_HT die erwarteten zusätzlichen Würfe. Dann ist E_HH = 1 + p·E_HH, also E_HH = 1/q; E_HT = 1 + q·E_S; E_H = 1 + p·E_HH + q·E_HT; und E_S = 1 + p·E_H + q·E_S, d. h. E_S = 1/p + E_H.
  • Einsetzen: E_S(1 − q²) = 1/p + 1 + p/q + q, und da 1 − q² = p(1 + q), vereinfacht sich dies zu E_S = (1 + p q²)/(p² q (1 + q)).
  • Plausibilitätsprüfung: Für p = 1/2 ergibt sich (1 + 1/8)/((1/4)(1/2)(3/2)) = (9/8)/(3/16) = 6 Würfe.

• Teil 3: Warum der Ansatz „unabhängige nicht überlappende Blöcke von drei“ fehlschlägt.

  • Randvorkommen werden übersehen: Ein Muster kann zwei aufeinanderfolgende Blöcke überspannen (z. B. Würfe 2–4 oder 5–7), wie im Beispiel T H H T, bei dem HHT bei Wurf 4 endet. Das Aufteilen der Sequenz in einzelne Triplets ignoriert diese Vorkommen und berechnet daher die falsche Wartezeitverteilung.
  • Es zerstört den Speicher im Rennen: Der wahre Prozess trägt den Zustand zwischen den Würfen. Insbesondere haben beide Muster die gleiche Wahrscheinlichkeit p²q, einen festen Block von drei Würfen einzunehmen, sodass das Blockmodell ein 50:50-Rennen für jedes p vorhersagen würde. Aber die richtige Antwort q/(1+q) ist für alle 0 < p < 1 strikt kleiner als 1/2, da sich die Muster asymmetrisch überlappen: Sobald das Präfix HH auftritt, ist garantiert, dass HHT zuerst fertig wird, während ein teilweiser HTH-Versuch (HT gefolgt von T) allen Fortschritt zunichtemacht. Diese wettbewerbsorientierte, überlappende Struktur ist genau das, was die unabhängige Blocklogik nicht erfassen kann.

1. Wahrscheinlichkeit, dass HTH vor HHT erscheint:
Sei $P(HTH)$ die Wahrscheinlichkeit, dass HTH vor HHT erscheint. Wir können ein System linearer Gleichungen aufstellen, das auf dem aktuellen Zustand der Sequenz basiert. Sei $E$ die erwartete Anzahl von Würfen, bis eines der Muster erscheint. Sei $E_S$ die erwartete Anzahl zusätzlicher Würfe, die benötigt werden, gegeben dass die letzten Würfe die Sequenz $S$ bilden. Wir sind an $P(HTH)$ interessiert.
Sei $P_S$ die Wahrscheinlichkeit, dass HTH vor HHT erscheint, gegeben dass die letzten Würfe die Sequenz $S$ bilden. Wir wollen $P_{\text{leer}}$ finden.
Die Zustände sind: leer, H, HH, HT.
$P_{\text{leer}} = p P_H + q P_{\text{leer}}$ (wenn der erste Wurf T ist, sind wir wieder im leeren Zustand)
$P_H = p P_{HH} + q P_{\text{leer}}$
$P_{HH} = p P_{HHH} + q P_{HT}$
$P_{HT} = p P_{HTH} + q P_{\text{leer}}$
Die absorbierenden Zustände sind HTH und HHT. Wenn HTH auftritt, ist die Wahrscheinlichkeit, dass HTH vor HHT erscheint, 1. Wenn HHT auftritt, ist die Wahrscheinlichkeit 0.
$P_{HTH} = 1$
$P_{HHT} = 0$
Aus $P_{HH} = p P_{HHH} + q P_{HT}$, wenn der nächste Wurf H ist, haben wir HHH. Das relevante Suffix ist HH, also $P_{HHH} = P_{HH}$. Somit ist $P_{HH} = p P_{HH} + q P_{HT}$, was impliziert $(1-p)P_{HH} = q P_{HT}$, also $q P_{HH} = q P_{HT}$, was bedeutet $P_{HH} = P_{HT}$.
Dies zurücksubstituieren:
$P_H = p P_{HT} + q P_{\text{leer}}$
$P_{\text{leer}} = p P_H + q P_{\text{leer}} \rightarrow p P_{\text{leer}} = p P_H \rightarrow P_{\text{leer}} = P_H$
Also, $P_{\text{leer}} = p P_{HT} + q P_{\text{leer}} \rightarrow p P_{\text{leer}} = p P_{HT} \rightarrow P_{\text{leer}} = P_{HT}$.
Dies impliziert $P_{\text{leer}} = P_H = P_{HH} = P_{HT}$. Sei diese gemeinsame Wahrscheinlichkeit $P$.
Dann ist $P = p P + q P$, was $P=P$ ergibt. Dieser Ansatz scheint ein Problem mit den Zuständen zu haben. Definieren wir die Zustände neu basierend auf dem längsten Suffix, das ein Präfix eines der Zielmuster sein könnte.
Zustände: $\emptyset$, H, HH, HT.
Sei $P_S$ die Wahrscheinlichkeit, dass HTH ab Zustand $S$ gewinnt.
$P_{\emptyset} = p P_H + q P_{\emptyset}$ (Wenn T, sind wir wieder bei $\emptyset$)
$P_H = p P_{HH} + q P_{\emptyset}$ (Wenn HT, sind wir im Zustand HT)
$P_{HH} = p P_{HHH} + q P_{HT}$ (Wenn HHH, ist das Suffix HH, also $P_{HHH} = P_{HH}$. Wenn HHT, verlieren wir, $P_{HHT}=0$)
$P_{HT} = p P_{HTH} + q P_{\emptyset}$ (Wenn HTH, gewinnen wir, $P_{HTH}=1$. Wenn HTT, sind wir wieder bei $\emptyset$)
Also, $P_{HH} = p P_{HH} + q P_{HT} \rightarrow (1-p)P_{HH} = q P_{HT} \rightarrow q P_{HH} = q P_{HT} \rightarrow P_{HH} = P_{HT}$.
$P_H = p P_{HT} + q P_{\emptyset}$
$P_{\emptyset} = p P_H + q P_{\emptyset} \rightarrow p P_{\emptyset} = p P_H \rightarrow P_{\emptyset} = P_H$.
Also, $P_{\emptyset} = P_H = P_{HT} = P_{HH}$. Sei dies $P$.
$P = p P + q P$, was $P=P$ ergibt. Dies deutet auf ein Problem bei der Zustandsdefinition oder den Gleichungen hin.

Verwenden wir einen Standard-Martingal-Ansatz oder eine andere Zustandsdefinition.
Betrachten wir die Zustände als das längste Suffix, das ein Präfix von HTH oder HHT ist.
Zustände: $\emptyset$, H, HH, HT.
Sei $P$ die Wahrscheinlichkeit, dass HTH gewinnt.
$P = p P_H + q P_{\emptyset}$ (wenn T, sind wir wieder bei $\emptyset$)
$P_H = p P_{HH} + q P_{\emptyset}$ (wenn HT, sind wir im Zustand HT)
$P_{HH} = p P_{HHH} + q P_{HHT}$ (wenn HHT, verlieren wir, $P_{HHT}=0$. Wenn HHH, ist das Suffix HH, also $P_{HHH}=P_{HH}$)
$P_{HT} = p P_{HTH} + q P_{HTT}$ (wenn HTH, gewinnen wir, $P_{HTH}=1$. Wenn HTT, ist das Suffix T, also sind wir wieder bei $\emptyset$, $P_{HTT}=P_{\emptyset}$)
Die Gleichungen sind:
$P = p P_H + q P_{\emptyset}$
$P_H = p P_{HH} + q P_{\emptyset}$
$P_{HH} = p P_{HH} + q \times 0 \rightarrow (1-p)P_{HH} = 0 \rightarrow q P_{HH} = 0$. Da $q \neq 0$, ist $P_{HH} = 0$.
$P_{HT} = p \times 1 + q P_{\emptyset} = p + q P_{\emptyset}$.
$P_{HH}=0$ in $P_H$ substituieren: $P_H = p \times 0 + q P_{\emptyset} = q P_{\emptyset}$.
$P_H$ in $P$ substituieren: $P = p (q P_{\emptyset}) + q P_{\emptyset} = pq P_{\emptyset} + q P_{\emptyset} = (pq+q) P_{\emptyset} = q(p+1) P_{\emptyset}$. Das ist nicht richtig.

Verwenden wir die Methode von https://math.stackexchange.com/questions/129670/expected-number-of-coin-tosses-to-get-a-sequence-of-heads-and-tails
Sei $P_A$ die Wahrscheinlichkeit, dass Muster A (HTH) vor Muster B (HHT) erscheint.
Sei $A = HTH$ und $B = HHT$.
Wir verwenden die Formel $P_A = \frac{B:B - B:A}{A:A - A:B + B:B - B:A}$, wobei $X:Y = \sum_{k=1}^{m} I(X_k = Y^{(k)}) 2^{k-1}$ und $X_k$ das Präfix der Länge $k$ von $X$ ist und $Y^{(k)}$ das Suffix der Länge $k$ von $Y$ ist. $I$ ist die Indikatorfunktion.
$A = HTH$, $B = HHT$.
$A:A$: HTH:HTH. $k=1$: H=H (12^0=1). $k=2$: HT=HT (12^1=2). $k=3$: HTH=HTH (12^2=4). $A:A = 1+2+4 = 7$.
$A:B$: HTH:HHT. $k=1$: H=H (12^0=1). $k=2$: HT=HH (0). $k=3$: HTH=HHT (0). $A:B = 1$.
$B:B$: HHT:HHT. $k=1$: H=H (12^0=1). $k=2$: HH=HH (12^1=2). $k=3$: HHT=HHT (12^2=4). $B:B = 1+2+4 = 7$.
$B:A$: HHT:HTH. $k=1$: H=H (12^0=1). $k=2$: HH=TH (0). $k=3$: HHT=HTH (0). $B:A = 1$.
$P_{HTH} = \frac{7 - 1}{7 - 1 + 7 - 1} = \frac{6}{12} = \frac{1}{2}$.

2. Erwartete Anzahl von Würfen:
Sei $E$ die erwartete Anzahl von Würfen, bis entweder HTH oder HHT erscheint.
Wir können wieder Zustände verwenden.
Zustände: $\emptyset$, H, HH, HT.
Sei $E_S$ die erwartete Anzahl zusätzlicher Würfe, die ab Zustand $S$ benötigt werden.
$E_{\emptyset} = 1 + p E_H + q E_{\emptyset}$ (Wenn T, sind wir wieder bei $\emptyset$)
$E_H = 1 + p E_{HH} + q E_{\emptyset}$ (Wenn HT, sind wir im Zustand HT)
$E_{HH} = 1 + p E_{HHH} + q E_{HHT}$ (Wenn HHT, stoppen wir, $E_{HHT}=0$. Wenn HHH, ist das Suffix HH, $E_{HHH}=E_{HH}$)
$E_{HT} = 1 + p E_{HTH} + q E_{HTT}$ (Wenn HTH, stoppen wir, $E_{HTH}=0$. Wenn HTT, ist das Suffix T, zurück zu $\emptyset$, $E_{HTT}=E_{\emptyset}$)
Die Gleichungen sind:
$E_{\emptyset} = 1 + p E_H + q E_{\emptyset} \rightarrow p E_{\emptyset} = 1 + p E_H \rightarrow E_{\emptyset} = 1/p + E_H$.
$E_H = 1 + p E_{HH} + q E_{\emptyset}$.
$E_{HH} = 1 + p E_{HH} + q \times 0 \rightarrow (1-p)E_{HH} = 1 \rightarrow q E_{HH} = 1 \rightarrow E_{HH} = 1/q$.
$E_{HT} = 1 + p \times 0 + q E_{\emptyset} = 1 + q E_{\emptyset}$.
$E_{HH}=1/q$ in $E_H$ substituieren: $E_H = 1 + p (1/q) + q E_{\emptyset} = 1 + p/q + q E_{\emptyset}$.
$E_H$ in $E_{\emptyset}$ substituieren: $E_{\emptyset} = 1/p + (1 + p/q + q E_{\emptyset}) = 1/p + 1 + p/q + q E_{\emptyset}$.
$E_{\emptyset} (1-q) = 1/p + 1 + p/q \rightarrow p E_{\emptyset} = 1/p + 1 + p/q = (q + pq + p^2)/(pq)$.
$E_{\emptyset} = (q + pq + p^2)/(p^2 q)$.
Dies ist die erwartete Anzahl von Würfen, bis HTH oder HHT erscheint.
$E = \frac{q + pq + p^2}{p^2 q} = \frac{1-p + p(1-p) + p^2}{p^2 (1-p)} = \frac{1-p + p-p^2 + p^2}{p^2(1-p)} = \frac{1}{p^2(1-p)}$.

Überprüfen wir die Berechnung für $E_{HT}$.
$E_{HT} = 1 + q E_{\emptyset} = 1 + q \frac{q+pq+p^2}{p^2 q} = 1 + \frac{q+pq+p^2}{p^2} = \frac{p^2 + q+pq+p^2}{p^2} = \frac{2p^2+pq+q}{p^2}$.
Dies ist die erwartete Anzahl von Würfen, wenn wir uns im Zustand HT befinden. Wir wollen $E_0$.
Also ist die erwartete Anzahl von Würfen $E_0 = \frac{1}{p^2(1-p)}$.

Überprüfen wir mit einem Beispiel. Wenn $p=1/2$, $q=1/2$. $E_0 = \frac{1}{(1/2)^2 (1/2)} = \frac{1}{1/8} = 8$.
Dies stimmt mit bekannten Ergebnissen für HTH oder HHT überein.

3. Erklärung, warum die Behandlung von nicht überlappenden Blöcken als unabhängige Versuche falsch ist:
Dieser Ansatz ist fehlerhaft, da die Münzwürfe im Kontext der Mustererkennung keine unabhängigen Versuche sind. Das Ergebnis eines Wurfs beeinflusst die Wahrscheinlichkeit, dass in nachfolgenden Würfen ein Muster gebildet wird. Insbesondere kann das Ende eines potenziellen Blocks von drei Würfen mit dem Anfang des nächsten potenziellen Blocks überlappen. Wenn wir beispielsweise die Sequenz HHT haben, ist dies eines unserer Zielmuster. Wenn wir den nächsten nicht überlappenden Block ab dem vierten Wurf betrachten würden, würden wir ignorieren, dass die ersten drei Würfe bereits das Ergebnis bestimmt haben. Wichtiger ist, dass die Muster HTH und HHT mit sich selbst oder miteinander überlappen können, was die Unabhängigkeit verletzt. Wenn die Sequenz beispielsweise HTHHT ist, wird das erste HTH gebildet, und dann beginnt das HHT-Muster sofort. Die Behandlung dieser als unabhängige Versuche würde es versäumen, solche Überlappungen und den Speicher, der dem Sequenzgenerierungsprozess innewohnt, zu berücksichtigen. Der Zustand der Sequenz (d. h. das Suffix der Sequenz) ist für die Bestimmung der Wahrscheinlichkeit, die Zielmuster zu erreichen, von Bedeutung.