Unendliche Münzwurfsequenz
Zwei Spieler $A$ und $B$ werfen eine Münze. $A$ beginnt mit $6$ Punkte und $B$ hast $4$Punkte. Sie werfen eine Münze und wenn es ein Kopf ist, dann$A$ bekommt einen Punkt von $B$. Wenn es ein Schwanz ist, dann$B$ bekommt einen Punkt von $A$. Wie groß ist die Wahrscheinlichkeit dafür?$A$ ist der erste zu $10$ Punkte?
Die Antwort ist $\frac{6}{10}$, die durch numerische Simulation verifiziert werden kann. Um dieses Ergebnis mathematisch zu erhalten, ist es auch klar, dass wir die Kombinationen in einer unendlichen Folge betrachten können als:
$$ P(A_{\text{wins}}) = \sum_{i} (\frac{1}{2})^{2i + 4} \cdot {2i + 4 \choose i } $$
Die Quelle, in der ich diese Fragen gefunden habe, besagt jedoch auch, dass das Ergebnis direkt durch Symmetrieargumente erhalten werden kann - indem beobachtet wird, dass die Spieler die gleiche Gewinnwahrscheinlichkeit haben, wenn der erste Wurf ein Schwanz ist, da in diesem Fall beim zweiten Wurf jeder Spieler dies tun würde haben $5$ Punkte und gleich wahrscheinlich zu erreichen $10$ zuerst.
Obwohl ich sehen kann, dass dies wahr ist, kann ich nicht sehen, wie ich zur Wahrscheinlichkeit von komme $\frac{6}{10}$ eines $A-\text{win}$ Von diesem Ausgangspunkt aus - kann jemand sehen, was die notwendigen weiteren Argumente sind?
Antworten
Wenn Sie mit Markov-Ketten vertraut sind, müssen Sie mit einigen Konzepten vertraut gemacht werden, mit deren Hilfe wir einen Satz schreiben und ihn zur Lösung dieses Problems verwenden können. Unser Satz wird als bezeichnet$\color{green}{\mathit{first\ step\ analysis}}$.
Eine "Stoppzeit" der Markov-Kette ist eine Funktion vom "Pfadraum" zur Zeit, die uns sagt, wann die Kette gestoppt und ihre Ergebnisse beobachtet werden sollen. Sie können beispielsweise eine Markov-Kette aus Münzwürfen (Kopf und Zahl) erstellen und nach einem Stopp fragen, wenn Sie drei aufeinanderfolgende Köpfe erhalten.
Jetzt können Sie eine "Funktion des aktuellen Zustands" zu einem Stoppzeitpunkt beobachten. Wenn Sie beispielsweise aufhören möchten, können Sie prüfen, ob Sie zu einer "guten" Gruppe von Zuständen oder zu einer "schlechten" Gruppe von Zuständen gehören. Wenn Sie beispielsweise spielen und nach einiger Zeit aufhören, sind "gute" Staaten diejenigen, für die Sie Geld gewonnen haben, und schlechte, für die Sie Geld verloren haben.
Die Analyse des ersten Schritts befasst sich speziell mit der Frage: Let $f(x)$ sei der erwartete Wert einer Zustandsfunktion zu einem Stoppzeitpunkt, vorausgesetzt, ich beginne mit dem Zustand $x$. Kann ich rechnen$f(x)$? In der Tat stellt sich heraus, dass$f(x)$ kommt drauf an $f(x')$ für einige andere Staaten $x'$ : Dies führt zu einer Folge von Gleichungen, die gelöst werden können.
In unserem Fall haben wir die Markov-Kette als Menge aller Zustände des Spiels. Lassen$(a,b)$ meinen, dass $A$ hast $a$ Punkte und $B$ hast $b$Punkte. Dann seit$a+b = 10$Wir haben den Staatsraum $\{(0,10),(1,9),(2,8),...,(9,1),(10,10)\}$.
In diesem Fall definieren wir die Stoppzeit als: Stopp, wenn Sie einen der beiden Treffer erzielen $(0,10)$ oder wenn du schlägst $(10,0)$. Wir definieren auch die Funktion des Staates$f(x)$ als die Wahrscheinlichkeit, dass Sie treffen $(0,10)$ bevor du schlägst $(10,0)$.
Sie können dies auch wie folgt schreiben: wenn die Funktion $g(y)$ ist $1$ beim $(10,0)$ und $0$ an anderer Stelle dann der erwartete Wert von $g$ vorausgesetzt du fängst an bei $x$ist $f(x)$. (Finde das selbst heraus).
Nach der Analyse des ersten Schritts "treten wir vor und schauen uns an, wie wir jetzt die Stoppzeit erreichen". Nehmen wir ein einfaches Beispiel: Angenommen, ich möchte die Wahrscheinlichkeit ermitteln, aus der$(9,1)$ ich erreiche $(10,0)$ Vor $(0,10)$. Schauen Sie sich nun den nächsten Schritt an: mit Wahrscheinlichkeit$\frac 12$, Ich schlage $(10,0)$ so erreiche ich $(10,0)$, also jetzt die Wahrscheinlichkeit zu erreichen $(10,0)$ Vor $(0,10)$ ist $f((10,0)) = 1$(offensichtlich). Andererseits könnte ich schlagen$(8,2)$ mit Wahrscheinlichkeit $\frac 12$ : dann die Wahrscheinlichkeit zu erreichen $(10,0)$ Vor $(0,10)$ ist $f((8,2))$.
Mit anderen Worten : $$ f((9,1)) = \frac{f(10,0) + f(8,2)}{2} = \frac{1 + f(8,2)}{2} $$
wir können sehr ähnlich schreiben: $$ f((x,10-x)) = \frac{f((x+1,10-x-1)) + f(x-1,10-x+1)}{2} $$
zusammen mit $f(10,0) = 1$ und $f(0,10) = 0$. Zehn Gleichungen, zehn Unbekannte, aber wir kennen das Muster: Schauen Sie nach "Gambler's Ruin", um eine Verallgemeinerung dieses Phänomens zu sehen und wie Sie diese Art von Gleichung lösen können.