Задачи подсчёта: парадокс дней рождения как пример

Применяем комбинаторику к живой задаче: насколько вероятно совпадение дней рождения в группе.

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

Комбинаторные формулы оживают в задачах. Возьмём вопрос, который удивляет почти всех: сколько человек должно собраться, чтобы с вероятностью больше половины у двоих совпали дни рождения? Интуиция говорит «сотни». Правильный ответ — 23. Разберём, почему, и проверим симуляцией. Эта задача — отличная иллюстрация того, как опасно доверять «здравому смыслу» в вероятности: интуиция цепляется за число 365 и подсказывает, что людей нужно сопоставимо много. Но она отвечает не на тот вопрос. Дальше мы увидим, что секрет — в подмене вопроса: мозг считает «совпадение со мной», а задача спрашивает «совпадение хоть у кого-то». Этот разрыв между интуицией и расчётом и делает парадокс знаменитым; его любят показывать на лекциях, спрашивая зал, и почти всегда в группе из тридцати студентов совпадение находится — к всеобщему удивлению.

Считаем через противоположное

Считать «хотя бы одно совпадение» напрямую тяжело: совпасть может любая пара, троек и так далее. Куда проще посчитать противоположное событие — «все дни рождения различны». Если в году 365 дней, а в группе $k$ человек, то число благоприятных «всех различных» наборов — это размещение $365\cdot 364\cdots(365-k+1)$, а всех наборов — $365^k$. Значит, вероятность отсутствия совпадений

$$P(\text{все различны})=\frac{365}{365}\cdot\frac{364}{365}\cdots\frac{365-k+1}{365}=\prod_{i=0}^{k-1}\frac{365-i}{365}.$$

А вероятность хотя бы одного совпадения — это дополнение:

$$P(\text{совпадение})=1-\prod_{i=0}^{k-1}\frac{365-i}{365}.$$

Точный расчёт

Посчитаем эту формулу для нескольких размеров группы.

def no_match_prob(k):
    p = 1.0
    for i in range(k):
        p *= (365 - i) / 365
    return p

for k in [10, 20, 23, 30, 50, 70]:
    p_match = 1 - no_match_prob(k)
    print(f"k={k:>2}: P(совпадение) = {p_match:.4f}")

Вывод:

k=10: P(совпадение) = 0.1169
k=20: P(совпадение) = 0.4114
k=23: P(совпадение) = 0.5073
k=30: P(совпадение) = 0.7063
k=50: P(совпадение) = 0.9704
k=70: P(совпадение) = 0.9992

Уже при 23 людях вероятность переваливает за $0{,}5$, а при 50 — почти неизбежна. Причина: совпадать может любая из $\binom{k}{2}$ пар, и при $k=23$ таких пар уже 253 — отсюда стремительный рост.

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

Смоделируем тысячи случайных групп по 23 человека и посчитаем долю групп с совпадением.

import random
random.seed(11)

def has_match(k):
    bdays = [random.randint(1, 365) for _ in range(k)]
    return len(set(bdays)) < k

n = 200000
matches = sum(1 for _ in range(n) if has_match(23))
print("Симуляция k=23:", round(matches / n, 4))
print("Теория:        ", 0.5073)

Вывод:

Симуляция k=23: 0.5069
Теория:         0.5073

Эксперимент подтверждает контринтуитивный результат: в школьном классе совпадение дней рождения — обычное дело.

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

В коде set(bdays) убирает повторы, и если длина множества меньше числа людей, значит, хотя бы два дня рождения совпали — это компактная проверка события. Сравнение len(set(bdays)) < k возвращает True ровно тогда, когда есть дубликат. Симуляция не использует формулу совсем: она тупо разыгрывает дни рождения и считает долю «удачных» групп. Совпадение с произведением вероятностей — независимое подтверждение того, что наш комбинаторный вывод верен.

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

Главная ловушка — считать, что нужно много людей «потому что в году 365 дней». Это смешение двух разных вопросов: «совпадение с конкретным человеком» (вот тут да, нужно ~253 человека для вероятности $0{,}5$) и «совпадение хоть у кого-то с кем-то» (всего 23). Вторая ошибка — пытаться сложить вероятности совпадений по парам: пары не являются несовместными событиями, и простое сложение завысит ответ. Через дополнение этой ловушки нет.

Итог

• Сложные события «хотя бы одно» часто проще считать через дополнение.
• Вероятность совпадения дней рождения превышает $0{,}5$ уже при 23 людях.
• Причина — квадратичный рост числа пар $\binom{k}{2}$.
• Симуляция подтверждает точную формулу, ничего о ней не зная.