Парадокс дней рождения: почему совпадение вероятно уже среди 23 человек
В группе из 23 человек вероятность совпадения хотя бы двух дней рождения равна 50,73%. Причина в том, что участники образуют 253 пары.
Дальше вы поймёте, чем совпадение с вашим днём рождения отличается от совпадения внутри всей группы, выведете точную вероятность через противоположное событие и сможете провести собственный случайный эксперимент.
В статье вы узнаете:
Интуиция сравнивает вас со всеми, а задача всех со всеми
Когда человек слышит про группу из 23 участников, он часто выбирает себя и мысленно проверяет ещё 22 дня рождения. Вероятность найти среди них совпадение со своей датой составляет всего 5,86%. До половины здесь далеко, поэтому ответ 50,73% кажется фокусом.
Но парадокс задаёт другой вопрос: совпадут ли дни рождения хотя бы у какой-нибудь пары. Ваш день может ни с кем не совпасть, зато два других человека окажутся рождены 14 марта. Для успеха подходит любая общая дата у любых двух участников.
Разница похожа на поиск одинаковых ключей. Найти ключ, совпадающий с одним заранее выбранным, трудно. Найти любую одинаковую пару в коробке проще, потому что каждый новый ключ сравнивается со всеми предыдущими.
Парадокс находится в формулировке, а не в календаре. Условия не противоречат теории вероятностей. Неожиданным оказывается только количество сравнений, которое человек по привычке недооценивает.
У 23 человек есть 253 разные пары
Первый участник образует пару с 22 остальными. Второй уже сравнивался с первым, поэтому добавляет 21 новую пару. Затем появляются ещё 20, 19 и так далее до последней пары. Сумма 22 + 21 + ... + 1 равна 253.
То же число даёт сочетание из 23 элементов по два:
C(23, 2) = 23 × 22 / 2 = 253
Порядок внутри пары не важен: Анна с Борисом и Борис с Анной являются одной парой. Эту механику можно проверить в калькуляторе числа сочетаний, задав n = 23 и k = 2.
Число пар растёт быстрее самой группы. У 10 человек их 45, у 23 уже 253, у 50 получается 1 225. Каждый новый участник добавляет не одно сравнение, а столько сравнений, сколько людей уже находилось в комнате.
Однако делить 253 на 365 и объявлять вероятность равной 69,3% нельзя. События для разных пар связаны между собой: если у трёх людей одна дата, совпадают сразу три пары. Чтобы не считать такие пересечения несколько раз, удобнее зайти с противоположной стороны.
Проще сначала посчитать группу без совпадений
Первый человек может родиться в любой день, поэтому он ничего не ограничивает. Чтобы второй не совпал с первым, ему подходят 364 дня из 365. Третьему нужно избежать уже двух занятых дат, поэтому остаются 363 дня. Для четвёртого остаются 362, и так далее.
Вероятность того, что все n дней рождения различаются, равна произведению этих долей:
P0 обозначает вероятность нуля совпадений. Множители зависят от уже занятых дат: после каждого нового уникального дня свободных вариантов становится на один меньше.
Теперь противоположное событие. Если из единицы вычесть вероятность полностью разных дат, останется вероятность хотя бы одного совпадения:
Для 23 человек произведение даёт примерно 0,4927028. Значит, вероятность обойтись без совпадений равна 49,2703%, а вероятность найти хотя бы одну общую дату равна 50,7297%.
Умножение здесь имеет смысл последовательного фильтра. Сначала подходят любые группы. Затем остаются только те, где второй человек не совпал с первым. Следующий множитель оставляет среди них группы с новой датой третьего участника. После 23 шагов остаются только группы без повторов.
При 366 участниках в модели с 365 днями произведение неизбежно становится нулём: свободной даты для последнего человека уже нет. Совпадение гарантирует принцип Дирихле, известный также как принцип ящиков. Если объектов больше, чем ящиков, хотя бы в одном ящике окажутся два объекта.
После порога в 23 человека вероятность растёт быстро
Число 23 является первым целым размером группы, при котором вероятность превышает 50%. Оно не является особой константой календаря. Если изменить число возможных дат, порог тоже сдвинется.
| Людей | Пар | Вероятность |
|---|---|---|
| 2 | 1 | 0,27% |
| 5 | 10 | 2,71% |
| 10 | 45 | 11,69% |
| 20 | 190 | 41,14% |
| 23 | 253 | 50,73% |
| 30 | 435 | 70,63% |
| 41 | 820 | 90,32% |
| 50 | 1 225 | 97,04% |
| 57 | 1 596 | 99,01% |
| 70 | 2 415 | 99,92% |
После 23 человек шанс не останавливается около половины. В группе из 41 человека он превышает 90%, из 57 человек 99%, из 70 человек 99,9%. При этом занята лишь небольшая часть из 365 возможных дат. Важна не доля занятых дней, а количество пар, которые могут совпасть.
Для быстрой оценки используют приближение:
При n = 23 показатель степени содержит 253/365, или примерно 0,69315. Это почти в точности ln 2. Поэтому приближение даёт 1 − e−ln 2 = 1/2. Точная формула учитывает последовательное уменьшение свободных дат и поднимает результат до 50,73%.
Из приближения видно общее правило: половинный порог растёт примерно как квадратный корень из числа возможных значений. Поэтому тот же эффект появляется не только у дат, но и у коротких кодов, случайных идентификаторов и хешей.
Эксперименту обязательно нужны повторы
Парадокс можно проверить без списка настоящих дней рождения. Пронумеруйте дни года от 1 до 365 и случайно выберите 23 числа с возможностью повторения. Если одно число появилось дважды, в условной группе нашлась общая дата.
Для такого опыта подойдёт случайный выбор из списка. Добавьте числа от 1 до 365 по одному в строке, включите режим «Разрешить повторы» и запросите 23 результата. Один запуск изображает одну группу людей.
Режим повторов является частью модели. Если запретить одинаковые результаты, инструмент заранее удалит все совпадения. Эксперимент будет каждый раз выдавать разные даты и уверенно доказывать правило, которое сам же тайком встроил в условия.
Один запуск ничего не обязан подтвердить. Примерно 49 групп из 100 не содержат общей даты, поэтому серия без совпадения является нормальной. Повторите опыт много раз и разделите количество групп с дублями на общее количество групп. При росте числа опытов доля будет собираться около 50,73%.
Симуляция помогает увидеть разброс и проверить алгоритм, но точное значение даёт формула. Десять опытов могут закончиться счётом 3:7 или 8:2, и теория от этого не ломается. Небольшая случайная выборка вообще любит выглядеть так, будто у неё появился характер.
Реальные дни рождения немного сложнее учебной модели
Классический расчёт сравнивает только день и месяц. Год рождения не учитывается: люди, родившиеся 5 мая 1998 и 5 мая 2007 года, считаются совпавшей парой.
Модель предполагает 365 равновероятных дат, независимые рождения и отсутствие 29 февраля. В жизни количество рождений меняется по сезонам и дням недели, близнецы рождаются в один день, а состав конкретной группы может зависеть от возраста и места. Поэтому для реального класса, компании или семьи точная вероятность немного отличается.
Неравномерность сама по себе обычно увеличивает вероятность совпадения. Если часть дат встречается чаще, люди сильнее собираются в этих точках календаря. Равномерное распределение растягивает рождения по доступным дням наиболее аккуратно и тем самым служит удобной нижней моделью для независимых выборов.
Главная логика сохраняется и за пределами календаря. Хеш является коротким цифровым отпечатком данных, а коллизией называют одинаковый хеш у двух разных входов. Если система выдаёт M одинаково вероятных значений, вероятность найти хотя бы одну коллизию достигает 50% уже примерно после 1,177√M результатов. Для 32-битного хеша существует около 4,29 миллиарда вариантов, но первая случайная коллизия становится вероятной уже около 77 тысяч хешей.
Это не означает, что конкретный заранее выбранный хеш угадывается за 77 тысяч попыток. Снова меняется вопрос. Найти совпадение с одной целью трудно, а найти любую одинаковую пару среди собственных результатов намного проще. В криптографии такую разницу используют атаки, основанные на парадоксе дней рождения.
Число 23 перестаёт выглядеть магическим, если считать правильные объекты. У группы есть 253 пары, вероятность удобнее находить через отсутствие совпадений, а каждый следующий человек добавляет всё больше новых сравнений. Календарь здесь только декорация. Интуицию обгоняет квадратный рост числа пар.
Есть что добавить?
Напишите своё мнение, комментарий или предложение.