Nombre attendu de pièces

Question

Alice et Bob jouent à une partie. Bob a une terrasse bien mélangée de $ m= 4999 $ cartes blanches et $ n= 4999 $ vertcartes.Chaque permutation de cartes dans le pont est également probable.Alice a défini certaines règles pour Bob.

• Chaque fois que Bob bat une carte blanche, il reçoit une pièce de monnaie, sinon il perd une pièce de monnaie.À tout moment (même au début), Bob est autorisé à arrêter de jouer au jeu et à conserver le nombre de pièces de monnaie qu'il a.
• Pendant le jeu, jouez la balance des pièces de monnaie que Bob a peut-être négativement.

Si Bob joue de manière optimale, quelle est la quantité attendue de pièces de monnaie Bob aura?

Un corps peut-il me donner une idée ou un indice comment le résoudre.

Answer 1

let $ w (a, b) $ soit le bénéfice attendu avec $ A $ A $ cartes positiveset $ B $ cartes négatives.Alors $ w (0,0)= 0 $ et $$ w (a, b)=max \ bigl (0, \ tffrac {A} {A + B} (w (A-1, B) + 1) + \ tfrac {b} {A + B} (w (A, B-1) - 1) \ BIGR). $$ En effet, si nous arrêtons le jeu immédiatement, le profit est nul.Sinon, avec probabilité $ \ tfrac {A} {A + B} $ , nous tirons une carte positive et avec une probabilité $ \ tffrac {b} {A + B} $ , nous tirons une carte négative.

Utilisation de cette récurrence, il est facile de calculer $ w (4999.4999) $ .Sur mon ordinateur portable, il a fallu moins d'une seconde.