Рулетка 2

Вперше я почув цю задачу в часи, коли готувався до і проходив інтерв'ю у фінансові компанії. Сьогодні я розвину її ще далі. Пригадаємо умову:

Тож, російська рулетка. КДБіст заряджає дві кулі підряд у шестиствольний револьвер, крутить барабан, стріляє і, на превеликий жаль, лишається живим. Передає револьвер вам: чи прокрутите ви барабан перед пострілом?

У приквелі ми закінчили знаходженням ймовірності смерти за умови невідомого розміщення двох куль у барабані. Задамося іншим питанням:

Яка ймовірність вижити, якщо гра продовжуватиметься не на життя, а на смерть?

Як ми встановили у тому ж приквелі, ймовірність вмерти без прокрутки барабану рівна 25%, що очевидно менше за третину -- ймовірність вмерти з прокруткою. Тож наразі вираз для ймовірності виглядає ось так:

Вважаємо, що ви вижили і КДБіст діє оптимально. Записуючи стан барабану у форматі 100001, де стволу відповідає перша позиція, а барабан прокручується вправо (стано 000011 переходить в 100001), маємо наступні можливі варіянти:

100001, 000011, 000110.

Для зрозумілості зазначимо, що це відповідає наступним позиціям ще до пострілу КДБіста з самого початку:

000110, 001100, 011000.

Як бачимо, варіянт 110000 вбив би КДБіста з самого початку. Варіянт же 000011 вбив би нас.

Тож, незалежно від вибору КДБіста щодо прокрутки барабану перед пострілом, його ймовірність вижити рівна 2/3. Формула оновлюється:

Проте, якщо КДБіст не прокручуватиме барабан, це означатиме, що для нас є наступні два варіянти:

100001, 000011.

Тобто ймовірність смерті вже 50%, тому ми прокрутимо барабан. Якби КДБіст його прокрутив, то цим би поставив нас у вигіднішу позицію, як було на самому початку. Проте тепер гра перевернулась на його користь. Перевернемо й вираз для оптимізму:

Тобто почали з нашої ймовірності вижити на першому ході 3/4, продовжили розділенням у миттєву смерть КДБіста на другому ході (1/3) та його непрокручувальнобарабанне життя (2/3), що змушує нас барабан прокрутити і у разі виживання (наступна 2/3) перебратись на хід, де тепер ймовірність вмерти КДБісту лише 1/4. Здавалось би, коли цей жах закінчиться? Продовжимо гру, з заміненими ролями і тими ж оптимальними стратегіями:

Як бачимо, після шостого (!) ходу гра повертається у початковий стан -- коли КДБіст тільки но вистрелив у себе з прокрученого барабану. Тому очевидно, що ймовірність вижити з цього моменту точно така ж, як і на самому початку. Розкриваючи дужки і перемножуючи дроби отримуємо:

Як бачимо, не зважаючи на сприятливу ситуацію напередодні, ймовірність вийти з гри живим рівна 7/16=43.75%. Можливо якщо ми врахуємо ймовірність смерті КДБіста на нульовому ході, все стане на свої місця? Маємо:

А й справді, шанси суттєво вищі. Аби перевірити відповідь, обрахуємо відповідним чином вираз, з якого починали:

Цей рекурсивний трюк часто зустрічається у задачах, трошки креативніших за звичайні базові з курсів статистики у інституціях старої школи. Маючи його на озброєнні, задамося наступним питанням:

Яке матсподівання кількості ходів у грі?

Ось тепер стає спекотно. Нагадаємо означення матсподівання:

Вважаючи кількістю ходів номер ходу, на якому гра закінчилась, маємо:

Як просумувати такий ряд? Помітимо, що там де сімка, члени ряду просто збільшені на 6. Пояснення цьому легко віднайти як тільки приходить усвідомлення, що матсподівання кількості ходів з першого повторення рівне матсподіванні кількості ходів від початкового моменту. А отже повна кількість ходів з цього моменту рівна Е+6 -- додаючи вже зроблені ходи. Тому вираз в дужках з 1/4*7+... можна спокійно замінити на Е+6 і отримати:

Тобто в середньому гра закінчуватиметься десь на смерті КДБіста -- I can see this as an absolute win! Твердження, насправді, жахливо статистично сформульоване, але сьогодні не про це.

Альтернативна формула матсподівання наступна (з виведенням):

Підставляючи наші дані, які достатньо легко отримати, маємо:

Збігається! І обрахунок був простіший.

Висновки (що?)

Ми розв'язали задачку, яка може попастись на співбесіді у хорошу компанію (вони дозволяють використовувати ручку й папірець у таких випадках), а також вивчили і ефективніше застосували нову формулу для матсподівання, не кажучи вже про рекурсивний метод. І як завжди -- конструктивний відгук вітається!

Щира подяка @olexdav за натхнення, демонстрацію оптимальної стратегії, та відновлення інтересу до задачі.