Número esperado de monedas

Question

Alice y Bob juegan un juego. Bob tiene una cubierta bien bararrada de $ m= 4999 $ tarjetas blancas y $ n= 4999 $ greentarjetas.Cada permutación de tarjetas en la cubierta es igualmente probable.Alice ha establecido algunas reglas para Bob.

• Cada vez que Bob voltea una tarjeta blanca, obtiene una moneda, de lo contrario, pierde una moneda.En cualquier momento (incluso al principio), Bob se le permite dejar de jugar el juego y mantener la cantidad de monedas que tiene.
• Durante el juego, juega el saldo de las monedas que Bob puede ser negativo.

Si Bob juega de manera óptima, ¿cuál será la cantidad esperada de monedas que Tendrá BOB?

¿Puede algún cuerpo darme una idea o una pista cómo resolverla?

Answer 1

Let $ W (a, b) $ Sé el beneficio esperado con $ a $ tarjetas positivasy $ b $ tarjetas negativas.Luego $ w (0,0)= 0 $ y $$ 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). $$ De hecho, si detenmos el juego de inmediato, el beneficio es cero.De lo contrario, con probabilidad $ \ tfrac {a} {a + b} $ , sacamos una tarjeta positiva, y con probabilidad $ \ tfrac {b} {a + b} $ , sacamos una tarjeta negativa.

Usando esta recurrencia, es fácil calcular $ W (4999,4999) $ .En mi computadora portátil tomó menos de un segundo.