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

Парадокс

Спросите людей, сколько гостей должно прийти на вечеринку, чтобы у двоих из них, скорее всего, совпали дни рождения, и большинство ответит: около 180, половина от 365. Правильный ответ — 23: тогда вероятность равна 50,7 %. При 57 гостях она составляет 99 %. Это называют парадоксом не потому, что здесь есть противоречие, а потому, что ответ так сильно расходится с интуицией.

Почему подводит интуиция

В комнате мы бессознательно рассуждаем от себя: какова вероятность, что кто-то родился в один день со мной? При 365 днях в году эта вероятность мала. Но парадокс касается всех возможных пар в комнате, а не совпадения с одним конкретным человеком: A и B, B и C, A и C и так далее. Из 23 человек можно составить 253 разные пары, и у каждой из них дни рождения могут совпасть.

Число пар растёт как квадрат

n человек образуют n × (n − 1) / 2 пар: 10 человек — 45 пар, 23 — 253, 57 — 1596, а 100 — 4950. В каждой паре дни рождения совпадают с вероятностью 1/365, поэтому 253 пары дают в среднем 253/365 ≈ 0,69 пары с общим днём рождения. Если удвоить группу, пар станет примерно вчетверо больше, и именно поэтому вероятность общего дня рождения так резко взлетает.

Вычисление шаг за шагом

Проще всего найти вероятность того, что ни у кого дни рождения не совпадают, и вычесть её из 100 %. Первый человек занимает любой день. Второй с вероятностью 364/365 родился не в тот же день. Третий с вероятностью 363/365 отличается от первых двух, и так далее. Для 23 человек:

365/365 × 364/365 × 363/365 × … × 343/365 ≈ 49,3 %

Раз вероятность того, что у всех дни рождения разные, равна 49,3 %, то противоположное событие — хотя бы один общий день рождения — имеет вероятность 100 % − 49,3 % = 50,7 %.

Кто-то с вашим днём рождения

Вероятность того, что кто-то родился в один день именно с вами, — это другой вопрос. Каждый из остальных n − 1 человек не попадает на ваш день рождения с вероятностью 364/365, поэтому вероятность, что хоть кто-то родился в ваш день, равна 1 − (364/365)ⁿ⁻¹. При 23 людях это всего 5,9 %, и нужно 253 других человека, чтобы она превысила 50 %. Из 253 пар в группе из 23 человек вас включают только 22.

Правило квадратного корня и атака «дней рождения»

Если есть N равновероятных значений, повтор становится вероятным примерно после 1,2 × √N случайных выборов: √365 ≈ 19, а 1,2 × 19 ≈ 23. Это очень важно для компьютерной безопасности. Злоумышленники используют атаку «дней рождения», чтобы найти два разных входных значения с одинаковым криптографическим хешем, то есть коллизию, например чтобы подделать цифровую подпись. Благодаря парадоксу дней рождения им нужно гораздо меньше попыток, чем подсказывает интуиция: около 2⁶⁴ для 128-битного хеша вместо 2¹²⁸. Поэтому у современных хеш-функций, таких как SHA-256, длинные значения.

Исследуйте в PictorX

Откройте парадокс дней рождения, и на круге по одному соберётся группа из 23 человек. Каждый новичок проводит линию к каждому, кто уже есть, а подпись считает пары. Их дни рождения падают на календарь, и день, на который приходятся два дня рождения или больше, подсвечивается. Ниже вычисление для этого размера группы стоит рядом с долей проверенных групп, в которых нашёлся общий день рождения, а график показывает вероятность для каждого размера группы — для любых двух людей и для кого-то с вашим днём рождения. Добавляйте людей по одному, выбирайте от 2 до 366 человек, проверяйте до 100 000 групп со скоростью до 10 000 в секунду или проверьте все размеры групп и смотрите, как точки вычерчивают кривую.