Случайные блуждания и ожидаемое время

Случайные блуждания и марковские цепи: считаем ожидаемое время до цели уравнениями на состояниях.

Случайное блуждание — процесс, где из текущего состояния переходят в соседние с заданными вероятностями; нас интересует ожидаемое число шагов до поглощающего состояния.

Зачем это в олимпиадах

Задачи «робот случайно ходит по числовой прямой / по графу, сколько шагов в среднем до выхода» — частые гости олимпиад и собеседований. Они объединяют всё из предыдущих уроков: вероятность перехода, матожидание, линейность, уравнения на ожидание. Главный приём — ввести неизвестные Eᵢ (ожидаемое время из состояния i) и составить систему линейных уравнений. Для простых случаев система решается руками, для сложных — линейной алгеброй. И снова Монте-Карло страхует от ошибок в выводе.

Простейшее блуждание на отрезке

Частица стоит в точке k на отрезке [0, N]. Каждый шаг она с вероятностью 1/2 идёт влево и 1/2 вправо. Дойдя до 0 или N, останавливается (это поглощающие состояния). Сколько шагов в среднем до остановки? Пусть Eᵢ — ожидаемое число шагов из точки i. Очевидно E₀ = Eₙ = 0. Для внутренних точек, сделав один шаг, попадаем в соседа: Eᵢ = 1 + (Eᵢ₋₁ + Eᵢ₊₁)/2. Это система линейных уравнений; её точное решение — Eᵢ = i·(N−i).

def expected_steps_segment(N):
    # решаем систему E_i = 1 + (E_{i-1}+E_{i+1})/2 методом простой итерации
    E = [0.0] * (N + 1)
    for _ in range(200000):
        newE = E[:]
        for i in range(1, N):
            newE[i] = 1 + (E[i - 1] + E[i + 1]) / 2
        E = newE
    return E

E = expected_steps_segment(5)
print([round(x) for x in E])
# сверим с формулой i*(N-i)
print([i * (5 - i) for i in range(6)])

Вывод:

[0, 4, 6, 6, 4, 0]
[0, 4, 6, 6, 4, 0]

Итерационное решение системы совпало с аналитической формулой Eᵢ = i·(N−i). Из центра отрезка длины 5 (точки 2 и 3) ожидается 6 шагов до края. Формула красивая: ожидаемое время максимально в середине и симметрично.

Вывод формулы «на пальцах»

Почему Eᵢ = i·(N−i)? Подставим в уравнение Eᵢ = 1 + (Eᵢ₋₁ + Eᵢ₊₁)/2. Правая часть: 1 + [(i−1)(N−i+1) + (i+1)(N−i−1)]/2. Раскрыв скобки, в числителе получаем 2·i·(N−i) − 2, делим на 2 и прибавляем 1 — выходит ровно i·(N−i). Граничные условия E₀=Eₙ=0 тоже выполнены. Значит формула — точное решение. Этот приём «угадать ответ и проверить подстановкой» часто короче, чем решать систему в лоб.

Блуждание по состояниям общего вида

Не только отрезок: состояния могут образовывать любой граф с вероятностями переходов. Общий рецепт: для каждого непоглощающего состояния s пишем Eₛ = 1 + ∑_t P(s → t)·Eₜ, для поглощающих E = 0, и решаем систему. Разберём «лестницу из 3 состояний»: из 1 идём в 2, из 2 — равновероятно в 1 или 3, состояние 3 — цель. Найдём ожидаемое число шагов из состояния 1.

from fractions import Fraction

# Состояния: 1 -> 2 (всегда); 2 -> 1 или 3 (по 1/2); 3 — цель.
# E3 = 0
# E2 = 1 + (1/2)*E1 + (1/2)*E3
# E1 = 1 + E2
# Подставляем: E2 = 1 + (1/2)(1+E2) => E2 - E2/2 = 1 + 1/2 => E2 = 3
# E1 = 1 + 3 = 4
E2 = Fraction(3)
E1 = 1 + E2
print(E1, E2)

Вывод:

4 3

Монте-Карло для проверки

Симуляция блуждания подтверждает аналитику. Прогоним много независимых блужданий из состояния 1 и усредним число шагов до цели.

import random

random.seed(7)
trials = 300000
total = 0
for _ in range(trials):
    state = 1
    steps = 0
    while state != 3:
        steps += 1
        if state == 1:
            state = 2
        else:  # state == 2
            state = 1 if random.random() < 0.5 else 3
    total += steps
print(round(total / trials, 3))   # ожидаем ~4.0

Вывод:

4.003

Симуляция дала 4.003 против точного 4 — отлично. Связка «составить уравнения на ожидание, решить, проверить Монте-Карло» — рабочая схема для всего класса задач о случайных процессах. Для больших систем уравнения решают методом Гаусса; идея остаётся той же.

Разбор задачи: ожидаемое число бросков до двух орлов подряд

Классика на цепи состояний: сколько в среднем бросков честной монеты нужно, чтобы выпало два орла подряд (HH)? Введём состояния по «прогрессу»: S₀ — ещё нет хвоста прогресса, S₁ — последний бросок орёл, HH — цель. Уравнения: из S₀ бросок даёт орла (в S₁) или решку (обратно в S₀); из S₁ орёл завершает игру, решка отбрасывает в S₀.

from fractions import Fraction
import random

# E0 = 1 + (1/2)E1 + (1/2)E0
# E1 = 1 + (1/2)*0 + (1/2)E0
# Решение системы: E0 = 6, E1 = 4
E0, E1 = Fraction(6), Fraction(4)
# проверим, что значения удовлетворяют уравнениям
print(E0 == 1 + Fraction(1, 2) * E1 + Fraction(1, 2) * E0)
print(E1 == 1 + Fraction(1, 2) * E0)
print(E0)            # ответ: 6 бросков

# Монте-Карло
random.seed(5)
trials = 200000
total = 0
for _ in range(trials):
    prev_head = False
    steps = 0
    while True:
        steps += 1
        head = random.random() < 0.5
        if head and prev_head:
            break
        prev_head = head
    total += steps
print(round(total / trials, 3))

Вывод:

True
True
6
5.994

Аналитика даёт ровно 6, симуляция — 5.994. Любопытно, что до «орла, потом решки» (HT) ожидается лишь 4 броска — асимметрия возникает потому, что неудача в HH (выпала решка после орла) отбрасывает дальше, чем неудача в HT. Этот контринтуитивный факт — повод всегда строить уравнения на состояния аккуратно, а не доверять «симметрии».

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

Поглощающие состояния — ноль. Не забудьте задать E = 0 для целевых/выходных состояний, иначе система не определена.
Существование ожидания. Если из состояния нельзя достичь поглощающего, ожидание бесконечно — система не решится.
Точность итераций. Метод простой итерации сходится, но медленно; для точных дробей решайте систему символьно или Гауссом.
Сумма вероятностей переходов = 1. Проверяйте, что из каждого состояния вероятности суммируются в единицу.

Итог

Ожидаемое время блуждания находят системой Eₛ=1+∑P(s→t)Eₜ с нулём в поглощающих.
На симметричном отрезке [0,N] ответ Eᵢ=i·(N−i).
«Угадать формулу и проверить подстановкой» нередко короче решения системы.
Монте-Карло подтверждает аналитический ответ для случайных процессов.