Wahrscheinlichkeit, ein rundenbasiertes Spiel mit einem Zufallselement zu gewinnen

Question

Ich bereite mich auf eine Programmierprüfung zum Thema Wahrscheinlichkeitstheorie vor und bin auf eine Frage gestoßen, die ich nicht lösen kann.

Gegeben wird ein Beutel, der eine bestimmte Menge weißer Steine ​​enthält $w$ und eine bestimmte Menge schwarzer Steine $b$, ziehen zwei Spieler abwechselnd gleichmäßig und zufällig Steine ​​aus dem Beutel. Nachdem jeder Spieler an der Reihe ist, verschwindet ein zufällig ausgewählter Stein und erst dann ist der andere Spieler an der Reihe. Wird ein weißer Stein gezogen, verliert der Spieler, der ihn gezogen hat, sofort und das Spiel endet.Ist der Beutel leer, gewinnt der Spieler, der als Zweiter gespielt hat.

Wie hoch ist die Gesamtwahrscheinlichkeit, dass der Zweitspieler gewinnt?

Ich gehe davon aus, dass es sich um eine dynamische Programmierfrage handelt, obwohl ich die Rekursionsformel nicht herausfinden kann.Jede Hilfe wäre sehr dankbar.:) :)

Beispieleingabe: $w$ = 3, $b$ = 4, dann ist die Antwort, glaube ich, 0,4, zu der ich gekommen bin, nachdem ich von Hand alle möglichen Wege für das Spiel berechnet habe, also nicht sehr effizient.

Answer 1

Bezeichnen wir mit $\Pr(w, b)$ Die Wahrscheinlichkeit, dass P2 gewinnt, wenn sie an der Reihe sind, und das gibt es $w$ weiße Steine ​​und $b$ Es bleiben schwarze Steine ​​übrig und wir schreiben in ähnlicher Weise $\overline\Pr(w, b)$ für die Wahrscheinlichkeit, dass P2 gewinnt, vorausgesetzt P1 ​​ist an der Reihe.

Aus den Spielregeln geht hervor, dass im Zug von P2 jeder der folgenden Fälle auftreten kann (vorausgesetzt, dass genügend Steine ​​übrig sind):

1. Weiß erhält ein Unentschieden und P2 verliert.Dies geschieht mit Wahrscheinlichkeit $w / (w + b)$.
2. Schwarz wird gezeichnet und ein weißer Stein verschwindet.Die Wahrscheinlichkeit dafür ist $b / (w + b) \cdot w / (w + b - 1)$.
3. Schwarz wird gezeichnet und ein schwarzer Stein verschwindet.Wir finden die Wahrscheinlichkeit dafür $b / (w + b) \cdot (b - 1) / ( w + b - 1)$.

Wenn P1 an der Reihe ist, finden wir ähnliche Fälle:

1. Weiß hat ein Unentschieden und P2 gewinnt.Dies geschieht mit Wahrscheinlichkeit $w / (w + b)$.
2. Schwarz wird gezeichnet und ein weißer Stein verschwindet.Die Wahrscheinlichkeit dafür ist $b / (w + b) \cdot w / (w + b - 1)$.
3. Schwarz wird gezeichnet und ein schwarzer Stein verschwindet.Wir finden die Wahrscheinlichkeit dafür $b / (w + b) \cdot (b - 1) / ( w + b - 1)$.

Jetzt können wir faktorisieren $\Pr$ Und $\overline\Pr$ unter Verwendung unserer Fallunterscheidungen und einer einfachen Wahrscheinlichkeitstheorie:acht 1.3}) cdot overline pr (w, b - 2), overline pr (w, b) & = pr ( text {case 2.1}) + pr ( text {case 2.2} ) cdot pr (w - 1, b - 1) + pr ( text {case 2.3}) cdot pr (w, b - 2) end {align*} $$Beachten Sie, dass wir diese beiden Gleichungen kombinieren können, um eine rekursive Formel für zu finden $\Pr$ (was ich der Kürze halber hier nicht aufzählen werde).Koppeln Sie diese mit den Anfangswerten $\Pr(w, b)$ Wo $w + b \leq 4$ (die vorberechnet werden kann) gibt uns eine algorithmische Möglichkeit, die gewünschte Wahrscheinlichkeit zu finden.