Парадокс Ймовірності

Ця задача стосується повторних підкидань чесної монети. Кожен результат, H або T, має ймовірність $1/2$. Будь-яка конкретна послідовність підкидань тієї ж довжини, як HHH або THH, має однакову ймовірність (наприклад, $1/8$ для послідовності довжини $3$).

Тепер розглянемо таку гру для двох гравців. Кожен гравець обирає унікальний шаблон можливих підкидань монети з фіксованою довжиною. Наприклад, перший гравець може передбачити HHH, тоді як другий передбачає THH. Гра починається з того, що обидва гравці спостерігають за тією ж монетою, яка підкидається повторно, поки один з них не побачить свій шаблон. Наприклад, якщо послідовність спостережуваних підкидань починається з HHTHTTHH... другий гравець у нашому прикладі виграє гру, побачивши шаблон THH.

Питання, яке нас цікавить, полягає в тому, наскільки ймовірно, що перший гравець виграє гру, враховуючи шаблони обох гравців. Оскільки ми підкидаємо чесну монету, багато хто припустив би, що шаблони не мають значення і що кожен гравець має ймовірність $1/2$ виграти гру. Однак це не так, що призводить до того, що відомо як Парадокс Ймовірності.

Для деяких шаблонів буде так, що перший гравець виграє з ймовірністю точно $1/2$. Наприклад, за симетрією, шаблони TT і HH мають рівні шанси з'явитися першими.

Однак, розглянемо знову наш початковий приклад, у якому перший гравець обирає HHH, а другий гравець обирає THH. Для цього конкретного поєдинку єдиний спосіб, яким перший гравець може виграти, це якщо кожне з перших трьох підкидань є H. Адже якщо перше HHH з'явиться десь, крім початку гри, шаблон може бути представлений як

...?HHH

де "..." означає можливо порожню початкову частину послідовності, а "?" відноситься до підкидання безпосередньо перед HHH. "?" не може відноситися до H, як у

...HHHH

тому що тоді було б раніше HHH, яке закінчило б гру, підкреслена частина ...HHHH. Але якщо попереднє підкидання було T, як у

...THHH.

тоді другий гравець вже виграв би, побачивши шаблон THH на підкресленому ...THHH. Отже, коли розглядаємо шаблон HHH проти THH, перший гравець виграє, якщо і тільки якщо перші три підкидання є H, подія, яка відбувається з ймовірністю $1/8$.

Ще один приклад, якщо перший гравець обирає TTH, а другий обирає THH, перший гравець виграє з ймовірністю $2/3$. Ваше завдання - написати програму, яка обчислює таку ймовірність.