Probabilità di vincere un gioco a turni con un elemento casuale

Question

Sto preparando per un esame di programmazione sulla teoria della probabilità e sono inciampato su una domanda che non posso risolvere.

Dato una borsa, che contiene una data quantità di pietre bianche $ W $ e qualche sommata quantità di pietre nere $ B $ , due giocatori prendono a turno che disegnano pietre uniformemente a caso dalla borsa. Dopo che il turno di ogni giocatore una pietra, scelto uniformemente a caso, svanisce, e solo allora l'altro giocatore prende il suo turno. Se viene disegnata una pietra bianca, il giocatore, che lo ha disegnato, perde istantaneamente e il gioco finisce. Se la borsa si vuole vuota, il giocatore, che ha giocato secondo, vince.

Qual è la probabilità complessiva che il giocatore, che ha giocato secondo, vince?

Presumo che sia una domanda di programmazione dinamica, anche se non riesco a capire la formula di ricorsione. Qualsiasi aiuto sarebbe molto apprezzato. :)

Esempio di ingresso : $ w $ = 3, $ B $ = 4, quindi la risposta è, credo, 0.4, che sono arrivato a dopo aver comprato a mano tutti i modi possibili per il gioco di andare, quindi non molto efficiente.

Answer 1

Denteriamo con $ \ PR (w, b) $ La probabilità di vincere P2 dato il suo turno e ci sono $ W $ pietre bianche e $ B $ Pietre nere rimanenti e allo stesso modo scriviamo $ \ overline \ PR (W, B) $ Per la probabilità di vincere P2, dato che è il turno di P1.

Dalle regole del gioco otteniamo che uno dei seguenti casi può verificarsi nella svolta di P2 (supponendo che siano rimaste pietre sufficienti):

.
1. Bianco è disegnato e P2 perde. Questo succede con probabilità $ w / (w + b) $ .
2. Il nero è disegnato e una pietra bianca svanisce. La probabilità di questa è $ B / (w + b) \ cdot w / (w + b - 1) $ .
3. Il nero è disegnato e una pietra nera svanisce. Troviamo la probabilità che questo sia $ B / (w + b) \ cdot (B - 1) / (w + b - 1) $ .

   Se è il turno di P1 per giocare, troviamo casi simili:

   .
   1. Bianco è disegnato e P2 vince. Questo succede con probabilità $ w / (w + b) $ .
   2. Il nero è disegnato e una pietra bianca svanisce. La probabilità di questa è $ B / (w + b) \ cdot w / (w + b - 1) $ .
   3. Il nero è disegnato e una pietra nera svanisce. Troviamo la probabilità che questo sia $ B / (w + b) \ cdot (B - 1) / (w + b - 1) $ .

      Possiamo ora fare il fattore $ \ PR $ e $ \ overline \ PR $ usando la nostra distinzione del caso e qualche semplice teoria della probabilità: $$ \ Begin {allinea *} \ PR (W, B) &=PR (\ TEXT {CASE 1.2}) \ CDOT \ Overline \ PR (W - 1, B - 1) + \ PR (\ Text {custodia 1.3}) \ cdot \ overline \ PR (W, B - 2), \\ \ Overline \ PR (W, B) &=PR (\ TEXT {CASE 2.1}) + \ PR (\ TEXT {CASE 2.2}) \ CDOT \ PR (W - 1, B - 1) + \ PR (\ Testo {Caso 2.3}) \ cdot \ PR (W, B - 2) \ end {allinea *} $$ Si noti che possiamo combinare queste 2 equazioni per trovare una formula ricorsiva per $ \ PR $ (che non scriverò qui per Brevity). Accoppiamento con i valori iniziali $ \ PR (w, b) $ dove $ w + b \ leq 4 $ (che può essere precomsuta) ci darà un modo algoritmico per trovare la probabilità desiderata.