Парадокс Дня Народження

Це питання про пари, а не про вас

Найчастіша пастка – уявляти запитання як "Яка ймовірність того, що хтось поділяє зі мною день народження?" - це невелика ймовірність, приблизно 1 до 365 для кожної іншої людини. Але парадокс днів народжень ставить зовсім інше питання: яка ймовірність того, що будь-які дві з n людей мають однаковий день народження? Кількість різних пар у групі з n зростає як n(n-1)/2, тобто квадратично, а не лінійно – при 23 людях вже є 253 окремі випадковості, і одна з них обов’язково трапиться"

number of pairs:  C(n,2) = n(n-1)/2
n = 23  ->  23*22/2 = 253 distinct pairs to check for a match

жива демонстрація · пов'язана симуляція● LIVE

Точна формула

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

P(no match) = (365/365) * (364/365) * (363/365) * ... * ((365-n+1)/365)
P(match)    = 1 - P(no match)

n = 23  ->  P(match) ~ 50.7%
n = 30  ->  P(match) ~ 70.6%
n = 57  ->  P(match) ~ 99.0%

Чому це росте так швидко: експоненційне наближення

Використовуючи наближення 1 - x ≈ e⁻ˣ для кожного малого множника, ми перетворюємо добуток у суму в степені, що дає чистий закритий вираз, а показник степеня залежить від n² — що саме пояснює, чому ймовірність зростає значно швидше, ніж інтуїтивно очікується. Встановлюючи це наближення рівним 0,5 і розв’язуючи рівняння відносно n, отримуємо n ≈ √(2 * 365 * ln 2) ≈ 22,99, що майже точно збігається з фактичним порогом у 23.

P(match) ~ 1 - exp( -n(n-1) / (2*365) )
n for 50% chance ~ sqrt(2 * 365 * ln 2) ~ 22.99

За межами дат народження: зіткнення хешів

Однакові комбінаторні принципи керують атаками на хеш-функції, подібними до атак на дні народження. Хеш з b бітами вихідних даних має 2^b можливих значень, і, таким чином, очікується, що два випадкових вхідних дані зіткнуться після генерації порядку квадратному кореню з 2^b зразків – не 2^b. Це саме тому криптографічні хеш-функції потребують приблизно подвоєної довжини виходу для протидії атакам на зіткнення порівняно з тим, що було б потрібно для протидії грубим пошукам preimage, і чому хеші з 128 бітами, такі як MD5, вважалися зламаними щодо стійкості до зіткнень задовго до того, як хтось міг реально шукати майже в повній площині 2^128.

Frequently asked questions

Чому 23 людини здаються замало для 50% ймовірності?

Люди інстинктивно думають про ймовірність того, що хтось поділяє їхній день народження, яка невелика (приблизно 1 з 365 у порівнянні). Справжнє питання полягає в тому, чи має хоча б двоє з 23 людей спільне день народження, а з 23 людьми існує 253 різних пар, кожна з яких має невелику ймовірність випадковості. Це кількість пар, яка зростає приблизно квадратично зі збільшенням розміру групи, що робить ймовірність швидким зростанням.

Скільки людей потрібно для 99% шансу на спільне день народження?

57 осіб. Ймовірність принаймні одного спільного дня народження швидко зростає: приблизно 50,7% у 23 осіб, приблизно 70% у 30 осіб і приблизно 99,9% у 70 осіб, ще до того, як група наблизиться до 366 людей, що гарантовано призведе до відповідності за принципом голуба та скрипки.

Що це має спільного з криптографічними хеш-функціями?

Ті самі комбінаторні міркування застосовуються до виходів хеш-функцій: якщо хеш має b біт і, отже, 2^b можливих значень, то очікується, що дві випадкові вхідні дані згенерують однаковий вихід лише після приблизно квадратного кореня від 2^b спроб, а не 2^b. Ця 'атака на день народження' пояснює, чому хеш-функції стійкі до зіткнень потребують приблизно подвоєної довжини бітів порівняно з тим, що потрібно для стійкості до грубої обробки preimage.

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

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

▶ Відкрити симуляцію Birthday Paradox

Парадокс Дня Народження: Чому 23 Люди Достатньо для Випадкового Збігу