Número esperado de moedas

Question

Alice e Bob jogam um jogo. Bob tem um baralho bem embaralhado de $ m= 4999 $ cartões brancos e $ n= 4999 $ verdecartões.Cada permutação de cartões no convés é igualmente provável.Alice definiu algumas regras para Bob.

• Toda vez que Bob vira um cartão branco, ele recebe uma moeda, caso contrário, ele perde uma moeda.A qualquer momento (mesmo no começo), Bob é permitido parar de jogar o jogo e manter o número de moedas que ele tem.
• Durante o jogo - jogue o equilíbrio de moedas que Bob pode ser negativo.

Se Bob joga otimamente, qual a quantidade esperada de moedas Bob terá?

Qualquer corpo pode me dar uma ideia ou uma dica como resolvê-la.

Answer 1

Deixe $ w (a, b) $ o lucro esperado com $ a $ cartões positivose $ b $ cartões negativos.Então $ W (0,0)= 0 $ e $$ w (a, b)=max \ bigl (0, \ tfrac {a} {a + b} (w (a-1, b) + 1) + \ tfrac {b} {a + b} (wA, B-1) - 1) \ bigr). $$ De fato, se pararmos imediatamente o jogo, o lucro é zero.Caso contrário, com probabilidade $ {A + B} $ , nós puxamos um cartão positivo e com probabilidade $ \ tfrac {b} {a + b} $ , nós puxamos um cartão negativo.

Usando esta recorrência, é fácil calcular $ W (4999.4999) $ .No meu laptop levou menos de um segundo.