Условие

Олег и Роман играют в игру: подкидывают честную монетку до тех пор, пока не выпадет 111 или 101 (0 — орёл, 1 — решка).

В первом случае побеждает Роман, во втором — Олег. Какова вероятность победы Олега? Ответ — несократимая дробь.

Решение

Подход — состояния

Состояния по «истории последних бросков»:

S — старт (или после последнего 0).
A — последний бросок был 1 (хвост ровно одного 1).
B — последние два броска 11 (хвост 11).
C — последние два броска 10 (хвост 10).
WIN_O — Олег победил (выпало 101).
WIN_R — Роман победил (выпало 111).

Переходы (по броскам, каждый с вероятностью 1/2)

S → 0 ведёт в S (хвост 0 не помогает); 1 ведёт в A.
A (последний 1): 0 → C (хвост 10); 1 → B (хвост 11).
B (хвост 11): 0 → C (хвост 110 → последний 10); 1 → WIN_R (получили 111).
C (хвост 10): 0 → S (хвост 00 → один 0); 1 → WIN_O (получили 101).

Уравнения вероятностей победы Олега

Пусть s, a, b, c — вероятности победы Олега из соответствующих состояний.

Из S: s = 1/2 · s + 1/2 · a ⇒ s = a. Из A: a = 1/2 · c + 1/2 · b. Из B: b = 1/2 · c + 1/2 · 0 = c/2 (т.к. 1 → Роман выиграл). Из C: c = 1/2 · s + 1/2 · 1 = (s + 1)/2.

Решение системы

Подставляем b = c/2 и c = (s+1)/2 в a:

c = (s+1)/2
b = c/2 = (s+1)/4
a = 1/2 · c + 1/2 · b = (c + b) / 2 = ((s+1)/2 + (s+1)/4) / 2 = ((2(s+1) + (s+1))/4) / 2 = 3(s+1)/8

Из s = a:

s = \frac{3(s+1)}{8}

8s = 3s + 3

5s = 3

s = \frac{3}{5}

Ответ

P(Олег) = 3/5. Соответственно P(Роман) = 2/5.

Проверка симуляцией

import random
def play():
    history = []
    while True:
        history.append(random.randint(0, 1))
        h = ''.join(map(str, history[-3:]))
        if h.endswith('111'):
            return 'R'
        if h.endswith('101'):
            return 'O'
 
N = 200_000
oleg = sum(1 for _ in range(N) if play() == 'O')
print(oleg / N)  # ≈ 0.6

Подводные камни

Считать P = 1/2 (по симметрии). Триграммы не симметричны: 111 нельзя «переиспользовать» (после 111 игра кончается), а 101 пересекается с 1 хвостом — отсюда и асимметрия в пользу Олега.
Не учитывать состояние C. Если игнорировать «хвост 10», получите неверную систему. Состояния должны полностью описывать ближайшее будущее.
B → 0. Может быть соблазн думать, что 110 не «реверсуется» в полезное состояние. На самом деле хвост 0 стирает память — но мы оказываемся в C (хвост 10), поскольку перед 0 был 1. Это важно: после 110 следующий 1 даёт 101, не 111.

Эталонный ответ

3/5. Олег побеждает с вероятностью 3/5, Роман — 2/5.

Вероятность — Олег и Роман: монета 111 vs 101