Probabilidade de ganhar um jogo baseado em turnos com um elemento aleatório

Question

Estou me preparando para um exame de programação sobre a teoria da probabilidade e eu tropeço em uma pergunta que não consigo resolver.

Dado uma bolsa, que contém alguma quantidade de pedras brancas $ W $ e alguma vez dada quantidade de pedras negras $ B $ , dois jogadores se revezam desenhando pedras uniformemente aleatoriamente a partir do saco. Após a volta de cada jogador, escolhido uniformemente aleatoriamente, desaparece, e só então o outro jogador leva a sua vez. Se uma pedra branca é desenhada, o jogador, que desenhou, instantaneamente perde e O jogo termina. Se a bolsa ficar vazia, o jogador, que jogou segundo, vence.

Qual é a probabilidade geral de que o jogador, que jogou segundo, ganha?

Eu suponho que é uma questão de programação dinâmica, embora eu não consiga descobrir a fórmula de recursão. Qualquer ajuda seria muito apreciada. :)

Entrada de exemplo : $ W $ = 3, $ B $ = 4, então a resposta é, eu acredito, 0,4, que cheguei depois de computação à mão todas as formas possíveis para o jogo ir, portanto, não muito eficiente.

Answer 1

Deixe-nos denotar por $ \ PR (W, b) $ A probabilidade de ganhar p2 dado a sua vez e há uma recipiente de matemática $ W $ Pedras brancas e $ B $ Pedras negras restantes e similarmente escrevemos $ \ Overline \ PR (W, b) $ Para a probabilidade de ganhar P2 dado é a vez de P1.

Das regras do jogo, recebemos que qualquer um dos seguintes casos pode ocorrer na curva do P2 (assumindo que pedras suficientes são deixadas):

.
1. branco é desenhado e P2 perde. Isso acontece com probabilidade $ w / (w + b) $ .
2. Black é desenhado e uma pedra branca desaparece. A probabilidade para isso é $ b / (W + B) \ CDOT W / (W + B - 1) $ .
3. preto é desenhado e uma pedra preta desaparece. Encontramos a probabilidade de que isso seja $ b / (w + b) \ Cdot (B - 1) / (W + B - 1) $ .

   Se é a vez de P1 para jogar, encontramos casos semelhantes:

   .
   1. branco é desenhado e p vitórias p2. Isso acontece com probabilidade $ w / (w + b) $ .
   2. Black é desenhado e uma pedra branca desaparece. A probabilidade para isso é $ b / (W + B) \ CDOT W / (W + B - 1) $ .
   3. preto é desenhado e uma pedra preta desaparece. Encontramos a probabilidade de que isso seja $ b / (w + b) \ Cdot (B - 1) / (W + B - 1) $ .

      Podemos agora flexionar $ \ PR $ e $ \ overline \ PR $ Usando nossas distinções de caso E alguma teoria de probabilidade simples: $$ \ começo {alinhar *} \ 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 (\ Texto {Case 2.1}) + \ PR (\ Text {Case 2.2}) \ Cdot \ PR (W - 1, B - 1) + \ PR (\ Texto {Case 2.3}) \ Cdot \ PR (W, B - 2) \ final {alinhar *} $$ Observe que podemos combinar essas duas equações para encontrar uma fórmula recursiva para $ \ PR $ (que eu não dirigirei aqui para brevidade). Acoplando estes com os valores iniciais $ \ PR (w, b) $ onde $ W + B \ LEQ 4 $ (que pode ser pré-computado) nos dará uma maneira algorítmica de encontrar a probabilidade desejada.