Парадокс Дня Народження: Чому Колізії Стаються Набагато Раніше, ніж Здається

Налаштування та чому це здається неправильним

Класична версія задачі запитує: у кімнаті з 23 випадково обраними людьми, яка ймовірність того, що принаймні двоє з них мають однаковий день народження (не враховуючи високосні роки та вважаючи всі 365 дні однаково ймовірними)? Більшість людей роблять приблизну оцінку, яка коливається між 5% і 15% — 23 з 365 здається малим. Фактична відповідь становить трохи більше 50%. З 70 людьми в кімнаті ймовірність зростає до 99,9%. Відмінність між інтуїцією та правильною відповіддю настільки велика, що це справді називається «парадоксом», хоча в цьому немає нічого логічно суперечливого — це парадокс інтуїції, а не математики.

Чому інтуїція недооцінює: це про пари, а не людей

Інстинктивна помилка полягає в тому, щоб розглядати проблему з точки зору однієї людини – "яка ймовірність того, що хтось поділяє мою дату народження" – що насправді є малою (близько 6% у групі з 23 осіб, оскільки є лише 22 інших людей, з якими можна порівняти). Але фактичне питання стосується будь-якої пари серед усієї групи, яка має однакове число днів народження, і кількість можливих пар зростає набагато швидше, ніж кількість людей. При n людях кількість унікальних пар дорівнює n(n−1)/2. Для n = 23 це 253 окремі пари, кожна з яких є незалежною можливістю випадковості. Інтуїція відстежує лінійне зростання людей; справжня відповідь залежить від квадратичного зростання пар, і ця невідповідність є джерелом усього сюрпризу.”

Фактичний розрахунок

Простіше обчислювати ймовірність того, що ніхто не розділяє день народження, та відняти це від 1, ніж намагатися врахувати всі можливі способи, якими може статися випадковість. Додавайте людей до кімнати по черзі: перша людина може мати будь-яке днем народження (ймовірність 1). Друга людина повинна уникнути дня народження першої людини: ймовірність 364/365. Третя має уникати обох попередніх днів народжень: ймовірність 363/365. Продовжуючи цей шаблон для n людей та множачи всі окремі ймовірності разом, отримуємо ймовірність того, що всі дні народження в кімнаті є різними:

P(всі різні) = (365/365) × (364/365) × (363/365) × ... × ((365−n+1)/365)

Ймовірність принаймні одного спільного дня народження тоді дорівнює 1 мінус цьому добутку. Підставляючи n = 23, отримуємо приблизно 0,493 для «всіх різних», а комплементарний — принаймні один збіг — становить близько 0,507, трохи більше половини. Функція перетинає 50% точно у 23 людини та різко зростає від неї, що пояснює, чому стрибок від «дивовижного» до «майже певного» відбувається над відносно вузьким діапазоном розмірів груп, а не повільним підйомом.

Загальний патерн: зіткнення серед значно більшої кількості 'слотів', ніж людей

Задача про день народження насправді є особливим випадком більш загального питання: якщо ви витягуєте n предметів випадковим чином (з заміною) з басейну з N можливих значень, скільки витяжок потрібно, щоб повтор став ймовірним? Для задачі про день народження N = 365. Корисне правило, отримане шляхом наближеного обчислення вищезазначеного добутку, полягає в тому, що кількість витяжок, необхідних для досягнення 50% ймовірності зіткнення, приблизно дорівнює 1.18 × √N — квадратний корінь з розміру басейну, а не його частина. Для N = 365, √365 ≈ 19,1 і 1.18 × 19,1 ≈ 22,5, що відповідає точному результату 23. Цей квадратний корінь масштабування є тим аспектом, який узагальнюється далеко за межі днів народження.

Чому це важливо для хеш-функцій

Криптографічна хеш-функція відображає вхід будь-якого розміру у вихід фіксованої довжини — скажімо, 256 біт, що дає 2²⁵⁶ можливих значень виходу. На перший погляд, можна було б припустити, що знайти два різних входи, які виробляють однаковий хеш-вивід (тобто "колізію"), потребуватиме приблизно 2²⁵⁶ спроб, оскільки це кількість можливих виходів. Ефект квадратного кореня з проблеми дня народження говорить інакше: оскільки для колізії потрібно лише, щоб два ваші спроби співпали між собою — не певної цілі — очікувана кількість спроб, необхідних для цього, наближається до квадратного кореня простору вихідних даних, приблизно 2¹²⁸ для хеш-функції з виходом довжиною 256 біт. Це називається атакою «день народження» і саме тому криптографи подвоюють довжину виходу хеш-функції відносно рівня безпеки, який вони хочуть забезпечити від колізій: хеш-функція «безпечна проти колізій на рівні 128 біт» потребує вихідної довжини 256 біт, а не 128 біт, саме через описаний вище ефект квадратного кореня.

Це також пояснює, чому при проектуванні хеш-функцій особливу увагу приділяють довжині виходу, коли важливою є стійкість до колізій (замість просто стійкості до зловмисного відтворення), наприклад, для цифрових підписів, центрів сертифікації та систем контролю версій, які покладаються на хеші для унікальної ідентифікації вмісту. Нападник, що використовує межу «день народження», потребуватиме значно менше спроб, ніж би дозволяла б вихідна довжина.

Часті запитання

Спробуйте наживо

Усе, що вище, працює прямо у вашому браузері — відкрийте the simulation і змінюйте параметри під час роботи. Нічого не встановлюється, нічого не завантажується на сервер, уся модель живе в одній вкладці.