Probabilidad de ganar un juego basado en turnos con un elemento aleatorio

Question

Me estoy preparando para un examen de programación en la teoría de la probabilidad y yo tropezamos con una pregunta que no puedo resolver.

Dada una bolsa, que contiene una cantidad dada de piedras blancas $ w $ y una cantidad dada de piedras negras $ B $ , dos jugadores se turnan para atraer piedras de dibujo uniformemente al azar de la bolsa. Después de que cada jugador gire una piedra, elegida de manera uniforme al azar, desaparece, y solo entonces el otro jugador toma su turno. Si se dibuja una piedra blanca, el jugador, que lo ha dibujado, instantáneamente pierde y El juego termina. Si la bolsa se vuelve vacía, el jugador, que jugó segundo, gana.

¿Cuál es la probabilidad general de que el jugador, que jugó segundo, gana?

Supongo que es una pregunta de programación dinámica, aunque no puedo entender la fórmula de recursión. Cualquier ayuda sería muy apreciada. :)

Entrada : $ w $ = 3, $ b $ = 4, entonces la respuesta es, creo, 0.4, que llegué después de la computación a mano, todas las formas posibles para que el juego fuera, así que no es muy eficiente.

Answer 1

Denotárnoslo por $ \ pr (w, b) $ la probabilidad de ganar p2 dado su turno y hay $ W $ piedras blancas y $ b $ Piedras negras restantes y similares escribimos $ \ overline \ PR (W, B) $ para la probabilidad de ganar P2 que se le da es el turno de P1.

De las reglas del juego Obtenemos que cualquiera de los siguientes casos puede ocurrir en el turno de P2 (asumiendo que se queden suficientes piedras):

1. el blanco se dibuja y p2 pierde. Esto sucede con la probabilidad $ w / (w + b) $ .
2. se dibuja negro y se desvanece una piedra blanca. La probabilidad de esto es $ b / (w + b) \ cdot w / (w + b - 1) $ .
3. se dibuja negro y se desvanece una piedra negra. Encontramos la probabilidad de que esto sea $ b / (w + b) \ CDOT (B - 1) / (W + B - 1) $ .

   Si es el turno de P1 para jugar, encontramos casos similares:

   1. el blanco se dibuja y p2 gana. Esto sucede con la probabilidad $ w / (w + b) $ .
   2. se dibuja negro y se desvanece una piedra blanca. La probabilidad de esto es $ b / (w + b) \ cdot w / (w + b - 1) $ .
   3. se dibuja negro y se desvanece una piedra negra. Encontramos la probabilidad de que esto sea $ b / (w + b) \ CDOT (B - 1) / (W + B - 1) $ .

      Ahora podemos factorizar $ \ pr $ y $ \ overline \ pr $ usando nuestras distinciones de caso y alguna teoría de probabilidad simple: $$ \ comienzan {align *} \ Pr (w, b) &=pr (\ texto {carcasa 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 (\ texto {caja 2.2}) \ CDOT \ PR (W - 1, B - 1) + \ PR (\ Texto {CASE 2.3}) \ CDOT \ PR (W, B - 2) \ End {align *} $$ Tenga en cuenta que podemos combinar estas 2 ecuaciones para encontrar una fórmula recursiva para $ \ pr $ (que no escribiré aquí para la brevedad). Acoplando estos con los valores iniciales $ \ pr (w, b) $ donde $ w + b \ leq 4 $ (que puede ser precomputado) nos dará una forma algorítmica de encontrar la probabilidad deseada.