Probabilité de gagner un jeu à tour de tour avec un élément aléatoire

Question

Je suis préparé pour un examen de programmation sur la théorie des probabilités et je suis tombé sur une question que je ne peux pas résoudre.

Compte tenu d'un sac, qui contient une quantité donnée de pierres blanches $ w $ et une quantité donnée de pierres noires $ B $ , deux joueurs apportent des virages à tour de rôle uniformément au hasard du sac. Après que chaque joueur tourne une pierre, choisis uniformément au hasard, disparaissent, et seulement l'autre joueur prend son tour. Si une pierre blanche est dessinée, le joueur, qui l'a dessinée, perd instantanément et Le jeu se termine. Si le sac devient vide, le joueur, qui a joué deuxième, gagne.

Quelle est la probabilité globale que le joueur, qui a joué deuxième, gagne?

Je suppose que c'est une question de programmation dynamique, même si je ne pouvais pas comprendre la formule de récursivité. Toute aide serait grandement appréciée. :)

Exemple d'entrée : $ w $ = 3, $ B $ Je crois que 0,4, que je suis arrivé après avoir calculé à la main toutes les manières possibles pour que le jeu soit possible, donc pas très efficace.

Answer 1

indique par $ \ pr (w, b) $ La probabilité de gagnant P2 étant donné son tour et il y a $ w $ w $ pierres blanches et $ b $ pierres noires restantes et similaires, nous écrivons $ \ Overline \ PR (W, B) $ Pour la probabilité de gagnant P2, étant donné que le tour de P1 est le tour de P1.

Dans les règles du jeu, nous obtenons que l'un des cas suivants peut se produire dans le tour de P2 (en supposant que suffisamment de pierres sont laissées):

1. blanc est dessiné et P2 perd. Cela arrive avec une probabilité $ w / (w + b) $ .
2. Noir est dessiné et une pierre blanche disparaît. La probabilité pour cela est $ B / (W + B) \ CDOT W / (W + B - 1) $ .
3. Noir est dessiné et une pierre noire disparaît. Nous trouvons la probabilité que cela soit $ B / (W + B) \ CDOT (B - 1) / (W + B - 1) $ .

   Si c'est le tour de P1 de jouer, nous trouvons des cas similaires:

   1. blanc est dessiné et P2 gagne. Cela arrive avec une probabilité $ w / (w + b) $ .
   2. Noir est dessiné et une pierre blanche disparaît. La probabilité pour cela est $ B / (W + B) \ CDOT W / (W + B - 1) $ .
   3. Noir est dessiné et une pierre noire disparaît. Nous trouvons la probabilité que cela soit $ B / (W + B) \ CDOT (B - 1) / (W + B - 1) $ .

      Nous pouvons maintenant factoriser $ \ PR $ et $ \ Overline \ PR $ Utilisation de nos distinctions de cas et une théorie de la probabilité simple: $$ \ commencer {align *} \ PR (W, B) &=PR (\ Text {Case 1.2}) \ CDOT \ Overline \ PR (W-1, B - 1) + \ PR (\ Text {Case 1.3}) \ CDOT \ Overline \ Pr (w, b - 2), \\ \ Overline \ PR (W, B) &=PR (\ Text {Case 2.1}) + \ PR (\ Text {Cas 2.2}) \ CDOT \ PR (W-1, B - 1) + \ PR (\ Texte {cas 2.3}) \ CDOT \ PR (W, B - 2) \ fin {align *} $$ Notez que nous pouvons combiner ces 2 équations pour trouver une formule récursive pour $ \ PR $ (que je ne sais pas ici ici la brièveté). Couplant ceux-ci avec les valeurs initiales $ \ PR (w, b) $ où $ w + b \ leq 4 $ (qui peut être précalculé) nous donnera une manière algorithmique de trouver la probabilité souhaitée.