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

Утверждение

В группе из 23 человек вероятность того, что хотя бы у двоих совпадёт день рождения, превышает 50%.

В группе из 57 человек — превышает 99%.

Первая реакция почти у всех: этого не может быть. Дней в году 365, людей 23, откуда половина?

Где ошибается интуиция

Вы считаете не то, что считает задача.

Интуиция подставляет вопрос: «какова вероятность, что чей-то день рождения совпадёт с моим».

Это другая задача. Там сравнений всего n−1 — каждый с вами, — и для превышения 50% требуется группа примерно из 253 человек.

Исходный вопрос иной: совпадение у любых двоих. Вас в нём нет вовсе.

Считаем пары

Вот вся разгадка, в одну строку.

Количество пар в группе растёт не линейно, а как n(n−1)/2.

В группе из 23 человек — 253 пары.

Двести пятьдесят три возможности совпасть. Не двадцать три.

Теперь ответ перестаёт удивлять: 253 попытки при шансе примерно 1/365 каждая дают ожидание около 0,7 совпадения. Половина — правдоподобно.

Как считается точно

Прямой подсчёт неудобен: вариантов совпадений много и они пересекаются.

Поэтому считают через противоположное событие.

Сначала вычисляется вероятность того, что все дни рождения различны, затем она вычитается из единицы.

Первый человек — любой день. Второй — должен не совпасть: 364/365. Третий — 363/365. И так далее.

Перемножаем 22 множителя, получаем примерно 0,493 — вероятность, что совпадений нет.

Значит, вероятность совпадения примерно 0,507. Чуть больше половины.

Оговорки

Их две, и обе честные.

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

Реальное распределение рождений по дням года неравномерно — есть сезонность, есть провалы на праздниках, есть влияние плановых родов. Учёт неравномерности несколько повышает вероятность совпадения.

То есть 23 — оценка сверху по числу людей: в реальности хватит того же или чуть меньшего.

Точные значения зависят от страны и периода, поэтому обычно приводят базовый расчёт.

Где это работает всерьёз

Не только в аудитории.

Родственный эффект известен в криптографии как «атака дней рождения».

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

Это соображение определяет требования к длине хеша. Задача про именинников оказалась вопросом безопасности.

Что отсюда следует для кластера

Урок, применимый ко всем совпадениям.

Считать надо возможности, а не события.

Когда кажется, что совпадение невероятно, почти всегда оказывается, что возможностей для него было гораздо больше, чем видно на первый взгляд.

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

Двадцать три человека выглядят как двадцать три шанса. На деле их двести пятьдесят три.