العدد المتوقع من العملات المعدنية

Question

أليس وبوب تلعب لعبة. يحتوي Bob على سطح صفوف جيدا من $ m= 4999 $ البطاقات البيضاء و $ n= 4999 $ greenبطاقات.كل التقليب من البطاقات في السطح أمر من المحتمل بنفس القدر.أليس قد وضعت بعض القواعد لبوب.

• في كل مرة يقلب بها بوب بطاقة بيضاء يحصل على عملة واحدة، وإلا فإنه يفقد عملة واحدة.في أي لحظة (حتى في البداية)، يسمح ب بوب بالتوقف عن تشغيل اللعبة والحفاظ على عدد العملات المعدنية التي لديه.
• خلال اللعبة - تشغيل رصيد العملات المعدنية قد يكون بوب سلبي.

إذا كان بوب يلعب على النحو الأمثل، فما هي المبلغ المتوقع من العملات المعدنية بوب؟

هل يمكن لأي شخص أن يعطيني فكرة أو تلميحا في كيفية حلها.

Answer 1

دع $ w (a، b) $ يكون الربح المتوقع مع $ $ بطاقات إيجابية $و $ B $ البطاقات السلبية.ثم $ W (0،0)= 0 $ و $$ W (a، b)=max \ bigl (0، \ tfrac {a + b} {a + b} (w (a-1، b) + 1) + \ tfrac {b} {a + b} (w (A، B-1) - 1) \ Bigr). $ في الواقع، إذا أوقفنا اللعبة على الفور، فإن الربح صفر.خلاف ذلك، مع احتمال $ \ tfrac {a + b} {a + b} $ ، نحن نسحب بطاقة إيجابية، ومع الاحتمالات $ \ Tfrac {b} {a + b} $ ، نحن نسحب بطاقة سالبة.

باستخدام هذا التكرار، من السهل حساب $ W (4999،4999) $ .على الكمبيوتر المحمول استغرق الأمر أقل من ثانية.