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

Парадокс дней рождения — это вероятностное явление, заключающееся в том, что в группе, состоящей из 23 или более человек, вероятность того, что хотя бы у двух из них совпадут дни рождения (число и месяц), превышает 50 %. При увеличении размера группы до 75 человек эта вероятность достигает 99,9 %. Парадокс противоречит интуитивным ожиданиям большинства людей, которые обычно считают, что для такого совпадения требуется гораздо большее количество людей (например, 183 человека — половина от 366 возможных дат, включая 29 февраля). Название «парадокс» отражает не логическое противоречие, а неожиданность результата с точки зрения здравого смысла.

Математическая формулировка

Парадокс дней рождения является классической задачей теории вероятностей. Он рассматривает вероятность того, что в случайно выбранной группе из \( n \) человек все дни рождения различны. При стандартных допущениях (год не високосный, 365 дней, дни рождения распределены равномерно и независимо) вероятность отсутствия совпадений вычисляется как произведение убывающих множителей:

\[ P(\text{нет совпадений}) = \frac{365}{365} \cdot \frac{364}{365} \cdot \frac{363}{365} \cdots \frac{365 - n + 1}{365} \]

Вероятность хотя бы одного совпадения \( P(\text{совпадение}) = 1 - P(\text{нет совпадений}) \). Для \( n = 23 \) это значение составляет примерно 0,507, то есть чуть больше половины. Для \( n = 22 \) — около 0,476, для \( n = 30 \) — около 0,706, для \( n = 50 \) — около 0,970, а для \( n = 70 \) — около 0,999.

Приближённая оценка

Для упрощения расчётов часто используют приближение, основанное на экспоненциальной функции. При малых \( n \) относительно 365 вероятность совпадения приближённо равна:

\[ P(\text{совпадение}) \approx 1 - e^{-\frac{n(n-1)}{2 \cdot 365}} \]

Это приближение даёт хорошую точность для \( n \), не превышающих 100. Например, для \( n = 23 \) оно даёт значение около 0,500.

Интуитивное объяснение

Основная причина, по которой результат кажется парадоксальным, — путаница между двумя разными вопросами:

1. Какова вероятность, что у конкретного человека (например, вас) день рождения совпадёт с днём рождения другого конкретного человека? Она равна \( \frac{1}{365} \approx 0,27\% \).
2. Какова вероятность, что в группе из \( n \) человек найдётся хотя бы одна пара с совпадающими днями рождения?

Второй вопрос рассматривает не одну пару, а все возможные пары в группе. Количество пар в группе из \( n \) человек равно \( \frac{n(n-1)}{2} \). Для \( n = 23 \) это \( \frac{23 \cdot 22}{2} = 253 \) пары. Хотя вероятность совпадения для каждой отдельной пары мала, большое количество пар делает появление хотя бы одного совпадения весьма вероятным. Человеческая интуиция обычно оценивает вероятность, исходя из первой модели (один конкретный человек), а не из второй (все возможные пары).

История и происхождение

Парадокс дней рождения впервые был описан в 1939 году американским математиком и статистиком Ричардом фон Мизесом. Он предложил задачу как иллюстрацию неочевидных свойств вероятности. Позднее, в 1950-х годах, задача получила широкую известность благодаря работам по теории вероятностей и комбинаторике. В 1970-х годах парадокс стал популярен в учебной литературе и массовой культуре, часто приводится как пример когнитивного искажения — склонности людей недооценивать вероятность редких событий при большом числе попыток.

Обобщения и вариации

Различное количество дней в году

Если рассматривать високосный год (366 дней), то пороговое значение \( n \) для вероятности 50 % увеличивается незначительно — до 23,1 (округляется до 24). Для года с 365 днями и учётом 29 февраля вероятность рассчитывается с неравномерным распределением, но практическое влияние на порог минимально.

Неравномерное распределение дней рождения

В реальности дни рождения распределены не равномерно: в некоторых месяцах (например, в сентябре) рождается больше детей, чем в других. Это может незначительно увеличить вероятность совпадений для заданного \( n \). Однако для практических целей (например, в криптографии) равномерное распределение является стандартным допущением.

Парадокс дней рождения в криптографии

В криптографии парадокс дней рождения используется для оценки стойкости хеш-функций. Атака «дней рождения» (birthday attack) — это метод, основанный на том, что вероятность коллизии (совпадения хеш-значений для двух разных сообщений) возрастает гораздо быстрее, чем можно было бы ожидать. Для хеш-функции с \( N \) возможными значениями ожидаемое число попыток для нахождения коллизии составляет примерно \( \sqrt{N} \), а не \( N \), как при поиске заданного значения. Например, для хеш-функции с 128-битным выходом (2^128 вариантов) атака дней рождения требует около \( 2^{64} \) попыток, что значительно меньше, чем \( 2^{128} \). Это делает атаку практичной для многих криптографических систем, если не используются достаточно длинные хеши.

Обобщение на произвольное число совпадений

Задача может быть обобщена на поиск не одного, а нескольких совпадений. Например, какова вероятность, что в группе из \( n \) человек найдутся трое с одинаковым днём рождения? Для этого требуется большее \( n \): для вероятности 50 % — около 88 человек, для 99,9 % — около 200 человек.

Применение в реальной жизни

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

• Статистика и социология: для оценки вероятности совпадений в выборках, например, при анализе данных о днях рождения в группах людей (классы, рабочие коллективы, спортивные команды).
• Криптография: как основа для атак на хеш-функции и цифровые подписи.
• Информатика: в алгоритмах хеширования, для оценки вероятности коллизий в базах данных и системах хранения.
• Теория игр и принятие решений: как пример когнитивного искажения, который может влиять на оценку рисков.

Критика и ограничения

Парадокс дней рождения часто воспринимается как «парадокс» лишь из-за неверной интерпретации условия. Критики отмечают, что в реальных условиях (неравномерное распределение дней рождения, возможные високосные годы, неслучайный состав групп) точные значения могут отличаться от теоретических. Однако для большинства практических задач эти отклонения незначительны. Кроме того, парадокс не является парадоксом в строгом логическом смысле — он не приводит к противоречию, а лишь демонстрирует разрыв между интуицией и математическим расчётом.

Источники

• Фон Мизес Р. «Вероятность, статистика и истина» (1939).
• Феллер В. «Введение в теорию вероятностей и её приложения» (1968).
• Менезес А., ван Ооршот П., Ванстон С. «Справочник по прикладной криптографии» (1996).
• Кнут Д. «Искусство программирования», том 3 (1998).