Erwartete Anzahl von Münzen

Question

Alice und Bob spielen ein Spiel. Bob hat ein gut mischtes Terrasse von $ M= 4999 $ Weiße Karten und $ n= 4999 $ grünKarten.Jede Permutation von Karten im Deck ist ebenso wahrscheinlich wahrscheinlich.Alice hat einige Regeln für Bob eingestellt.

.
• Jedes Mal, wenn Bob eine weiße Karte flippt, bekommt er eine Münze, sonst verliert er eine Münze.In jedem Moment (auch am Anfang) darf Bob aufhören, das Spiel zu spielen und die Anzahl der Münzen zu halten, die er hat.
• Während des Spiels spielen Sie das Gleichgewicht der Münzen, die Bob negativ sein kann.

Wenn Bob optimal spielt, was die erwartete Menge von Münzen Bob hat?

Kann jeder Körper mir eine Idee oder einen Tipp geben, wie man es lösen kann.

Answer 1

lass $ w (a, b) $ Seien Sie der erwartete Gewinn mit $ A $ positive Kartenund $ B $ Negative Karten.Dann $ w (0,0)= 0 $ und $$ w (a, b)=max \ bigl (0, \ tfrac {a} {a + b} (w (a-1, b) + 1) + \ tfrac {b} {a + b} (w (A, B-1) - 1) \ BIGR). $$ Wenn wir das Spiel sofort aufhalten, ist der Gewinn Null.Ansonsten, mit der Wahrscheinlichkeit $ \ tfrac {a} {a + b} $ , ziehen wir eine positive Karte aus und mit Wahrscheinlichkeit $ \ tfrac {b} {a + b} $ , wir ziehen eine negative Karte heraus.

Mit diesem Wiederauftreten können Sie einfach $ W (4999.4999) $ berechnen.Auf meinem Laptop dauerte es weniger als eine Sekunde.