Numero previsto di monete

Question

Alice e Bob Gioca una partita. Bob ha un ponte ben discolpare di $ m= 4999 $ carte bianche e $ n= 4999 $ verdecarte.Ogni permutazione di carte nel mazzo è ugualmente probabile.Alice ha fissato alcune regole per Bob.

.
• Ogni volta che Bob lancia una carta bianca ottiene una moneta, altrimenti perde una moneta.In qualsiasi momento (anche all'inizio), Bob è permesso smettere di giocare a giocare e mantenere il numero di monete che ha.
• Durante il gioco, il saldo delle monete che Bob ha potrebbe essere negativo.

Se Bob gioca in modo ottimale, quale sarà la quantità prevista di monete Bob avrà?

Qualsiasi corpo può darmi un'idea o un suggerimento come risolverlo.

Answer 1

Let $ W (A, B) $ Sii il profitto previsto con $ a $ carte positivee $ B $ carte negative.Quindi $ w (0,0)= 0 $ e $$ 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). $$ In effetti, se fermiamo immediatamente il gioco, il profitto è zero.Altrimenti, con probabilità $ \ tfrac {a} {a + b} $ , tiramo fuori una carta positiva e con probabilità $ \ tfrac {b} {A + B} $ , tirò fuori una carta negativa.

Utilizzando questa ricorrenza, è facile calcolare $ w (4999.4999) $ .Sul mio laptop ci sono voluti meno di un secondo.