Оценка вероятностей сложных событий

Если вероятность события трудно посчитать на бумаге — заставьте компьютер пережить это событие тысячи раз и просто посчитайте, как часто оно случилось.

Оценка вероятности симуляцией — приём метода Монте-Карло, при котором интересующее событие многократно разыгрывается в коде, а его вероятность оценивается как доля испытаний, в которых событие произошло.

Теория вероятностей умеет красиво считать простые случаи: вероятность выпадения шестёрки, двух орлов подряд, вытащить туза. Но стоит условиям чуть усложниться — появляются комбинаторные дебри, формулы включения-исключения, условные вероятности — и аккуратный вывод превращается в источник ошибок. Метод Монте-Карло предлагает не выводить вероятность, а измерить её экспериментом. И часто это и быстрее, и надёжнее ручных выкладок.

Симуляция вместо формулы

Логика предельно прозрачна. Чтобы оценить вероятность события, нужно уметь сделать всего две вещи: разыграть один случайный исход и проверить, произошло ли в нём интересующее нас событие. Дальше — рутина: повторяем розыгрыш N раз, считаем, сколько раз событие случилось, и делим на N. Полученная доля и есть оценка вероятности.

Прелесть в том, что нам совершенно не нужно понимать устройство вероятности — достаточно честно воспроизвести правила. Компьютеру всё равно, считаем мы вероятность выигрыша в карты, поломки сложной системы или редкого совпадения. Везде один шаблон: симулируй много раз, считай долю.

Парадокс дней рождения

Возьмём задачу, на которой интуиция почти всегда ошибается. Вопрос: сколько человек должно собраться в комнате, чтобы вероятность того, что у двоих совпадут дни рождения, превысила 50%? Большинство называет числа вроде 100, 180, «половину от 365». Правильный ответ поражает: достаточно всего 23 человек.

Выводить это аналитически можно, но возни много: проще посчитать вероятность отсутствия совпадений и вычесть из единицы. А вот симуляцией задача решается в лоб — буквально «собираем комнату людей и смотрим, есть ли совпадение».

import random
random.seed(20)

def has_collision(k):
    days = set()
    for _ in range(k):
        b = random.randint(1, 365)
        if b in days:
            return True
        days.add(b)
    return False

N = 20000
for k in (23, 30, 50):
    hits = sum(has_collision(k) for _ in range(N))
    print(f"Группа {k}: P(совпадение) ~ {hits/N:.3f}")

Вывод:

Группа 23: P(совпадение) ~ 0.508
Группа 30: P(совпадение) ~ 0.711
Группа 50: P(совпадение) ~ 0.972

Симуляция подтверждает контринтуитивный факт: уже в группе из 23 человек совпадение случается чаще, чем нет (50.8%). А в группе из 50 человек совпадение почти неизбежно — 97 случаев из 100. Функция has_collision(k) собирает «комнату» из k человек: каждому выдаёт случайный день рождения random.randint(1, 365) и проверяет, не встречался ли такой день раньше. Множество days хранит уже занятые дни; как только новый день в нём уже есть — фиксируем совпадение и сразу возвращаем True.

Почему уже 23 человека? Интуиция против комбинаторики

Откуда такой парадокс? Главная ловушка интуиции в том, что мы невольно представляем вопрос как «сколько людей нужно, чтобы кто-то совпал со мной». Вот для этого действительно понадобилась бы большая группа. Но в задаче спрашивается про совпадение любой пары — а пар в группе гораздо больше, чем людей.

В группе из 23 человек число различных пар равно 23 × 22 / 2 = 253. Двести пятьдесят три возможности для совпадения! Каждая отдельная пара совпадает с маленькой вероятностью 1/365, но пар так много, что суммарный шанс «где-то да совпадёт» переваливает за половину. Чем больше людей — тем быстрее (квадратично!) растёт число пар, поэтому вероятность взлетает стремительно: 23 человека дают 50%, а 50 человек — уже 97%.

людей:  23      30        50
пар:    253     435       1225
P:      0.508   0.711     0.972

Как работает под капотом

Каждый вызов has_collision(k) — это одно полное испытание Бернулли: исход либо «совпадение есть» (True), либо «совпадений нет» (False). Выражение sum(has_collision(k) for _ in range(N)) опирается на то, что в Python True при суммировании ведёт себя как 1, а False как 0. Поэтому сумма по N испытаниям — это просто число удач, а hits/N — доля удач, то есть оценка вероятности.

Внутри одного испытания мы используем множество days как быстрый способ узнать, встречался ли уже такой день. Проверка b in days для множества работает практически мгновенно, не перебирая все элементы. Как только находим повтор — выходим из функции досрочно через return True, не тратя время на оставшихся людей: совпадение ведь уже есть, дальше проверять незачем.

Частые ошибки

Путать «совпадение с конкретным человеком» и «совпадение любой пары». Это разные задачи с очень разными ответами — именно подмена и порождает парадокс.
Брать слишком мало испытаний N. На паре сотен прогонов оценка вероятности гуляет в пределах нескольких процентов, и тонкое «чуть больше 50%» можно не разглядеть.
Использовать randint(1, 364) или randint(0, 365) вместо randint(1, 365). В Python random.randint включает оба конца, поэтому правильный диапазон для 365 дней — именно от 1 до 365.
Забывать про досрочный выход. Без return True при первом же совпадении логика усложняется, а смысл «есть ли хоть одно совпадение» теряется.
Ожидать, что симуляция выдаст ровно теоретические 0.507 — у Монте-Карло всегда есть случайный разброс в последних знаках.

Итоги

Вероятность сложного события можно не выводить формулой, а оценить: симулировать событие много раз и взять долю удачных исходов.
Шаблон один на все задачи: разыграть исход → проверить событие → повторить N раз → поделить число удач на N.
Парадокс дней рождения: уже в группе из 23 человек вероятность совпадения дней рождения превышает 50%.
Причина контринтуитивности — мы считаем совпадения любой пары, а число пар растёт квадратично (в группе 23 человек их 253).
В Python True/False при суммировании работают как 1/0, что делает подсчёт доли удач компактным.