Про парадокс дня народження
Парадокс дня народження — це контрінтуїтивний імовірнісний результат: у групі лише з 23 осіб імовірність того, що принаймні двоє мають однаковий день народження, перевищує 50%; а у групі з 70 осіб вона досягає 99,9%. Точна формула: P(збіг) = 1 − (365/365) × (364/365) × (363/365) × … × ((365−n+1)/365). Комбінаторний підхід з урахуванням усіх пар: при n людях є n(n−1)/2 пар, і збіг хоча б в одній з них настає набагато швидше, ніж здається. При n = 23 таких пар уже 253.
У симуляторі натисніть «Додати людей», щоб заповнити арену випадковими особами з випадковими днями народження, або вкажіть потрібну кількість вручну й натисніть «Запустити». Червоні лінії з'єднують пари з однаковими датами. Графік праворуч показує теоретичну криву ймовірності разом із накопиченою емпіричною частотою підтверджень. Спостерігайте, як вже при 23 особах теорія і експеримент перетинають позначку 50%.
Часті запитання
Чому 23 людини — це 50%, а не потрібно 183 (половина від 365)?
Інтуїція підказує порівнювати одну людину з певною датою — і тоді дійсно потрібно ~183 особи. Але парадокс виникає тому, що збіг може статися між будь-якою парою з усіх n людей. При n = 23 є 253 пари, і кожна пара має шанс 1/365 на збіг. Сума ймовірностей за парами вже більша за 0,5, ще й незначна від'ємна корекція на взаємозалежність — звідси 50,7%.
Чи враховує симулятор лише дату чи також рік народження?
Класичний парадокс дня народження враховує лише дату (1 з 365), ігноруючи рік і високосні роки. Симулятор дотримується цього припущення, рівномірно розподіляючи дні народження по 365 позиціях. Реальні дні народження нерівномірні (більше пологів у серпні–вересні в більшості країн), тому справжній поріг 50% для реальних даних ледь інший — але різниця мала, кілька осіб.
Яке практичне застосування парадоксу дня народження у криптографії?
«Атака дня народження» — клас атак на хеш-функції. Щоб знайти колізію в хеш-просторі розміром 2^N, досить перебрати ~2^(N/2) повідомлень замість очікуваних 2^N, адже логіка та сама: шукаємо збіг між будь-якою парою. Саме тому криптографічні стандарти вимагають хешів принаймні 256 біт: 2^128 перебірок для колізії все ще недосяжні для будь-якого комп'ютера.
Як розрахувати точну ймовірність для довільної групи?
P(хоча б один збіг | n осіб) = 1 − P(жодного збігу) = 1 − 365!/( (365−n)! × 365ⁿ ). Зручніший рекурентний розрахунок: P(збіг після k-ї особи) = 1 − (1 − P(no match, k−1)) × (365−k+1)/365. Починаючи з P = 0 при k = 1, додайте щоразу наступний множник — і ви отримаєте ту саму криву, що будує симулятор.
Що відбувається, якщо діаметр простору подій не 365, а більший?
При розмірі простору d (наприклад, для секунди в році d ≈ 31,5 млн) поріг 50% зсувається до ~√(d × ln 2) ≈ 0,83√d. Для 365 це дає ≈15,9 — збіг з формульним розрахунком. Застосування: кількість MAC-адрес у мережі, UUID-колізії (d = 2^122) — тут поріг 50% потребує ~2^61 генерованих значень, тому UUID4 на практиці безпечний.
Чому результат здається таким неочікуваним психологічно?
Люди автоматично порівнюють нову людину зі своїм власним днем народження, а не враховують всі можливі пари всередині групи. Це когнітивне упередження зветься «зациклення на егоцентричній перспективі». Схожа помилка трапляється в задачі «Монті Холл»: ми не коригуємо інтуїцію під кількість альтернативних подій, що зростає квадратично.
Як змінюється результат для трьох людей з однаковою датою?
Якщо шукати не пару, а трійцю з однаковим днем народження, поріг 50% зростає до n ≈ 88 осіб. Задача «k людей зі збігом» — це узагальнений парадокс дня народження, де кількість потрібних людей масштабується як d^((k−1)/k), де d = 365. Кожен наступний рівень збігу вимагає значно більшої групи.
Чи можна «відчути» парадокс на реальних людях?
Так! Виберіть будь-яку аудиторію з 30–35 студентів і попросіть назвати дні народження по черзі — збіг майже гарантований (~70%). Протягом десятиліть це стає стандартним демо на уроках статистики. Інший приклад: у будь-якому чемпіонаті Прем'єр-ліги (20 команд, 25 гравців кожна) збіг днів народження в одній команді трапляється майже щосезону.
Що таке «узагальнений парадокс дня народження» у теорії хешів?
У криптографії нас цікавить не лише перша колізія, а і розподіл кількості колізій у великому наборі. Якщо n >> √d, то очікувана кількість колізій ≈ n²/(2d). Для хеш-таблиць це означає: при заповненні до 70% ємності колізії неминучі й частіші. Алгоритми відкритої адресації і ланцюжків — прямий наслідок парадоксу дня народження у структурах даних.