Парадокс днів народження

У теорії ймовірностей парадокс днів народження^[1] оцінює ймовірність того, що у випадково вибраній групі людей збігатимуться дні народження в якоїсь пари. В групах кількістю не менших 23 випадково вибраних людей, ймовірність збігу днів народження в якоїсь пари становить більше 50 %. Такий результат суперечить інтуїтивній уяві більшості.

Для 57 людей, ймовірність становить більше ніж 99 %, і досягає 100 % коли, ігноруючи високосний рік, кількість людей у групі становить 366 (через принцип Діріхле). Такий розподіл ймовірностей призвів до широко відомої криптографічної атаки відомої як атака «днів народження».

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

У формулюванні парадоксу йдеться саме про збіг днів народження у будь-яких двох членів групи. Одна з поширених помилок полягає в тому, що цей випадок плутають з іншим випадком, на перший погляд схожим, коли з групи вибирається одна людина, й оцінюється ймовірність того, що день народження будь-яких інших членів групи збіжиться з днем народження вибраної людини. В останньому випадку ймовірність збігу значно нижча.

Розуміння проблеми

В парадоксі днів народження з'ясовується, чи хтось з випадково вибраних 23 людей буде мати день народження в один день з кимось іншим з групи.

У списку з 23 людей, при порівнянні днів народження з першою в списку людиною, існує 22 шанси на збіг, але порівняння кожного з кожним дає 253 різні шанси: в групі з 23 людей, утворюється ${\displaystyle {23 \choose 2}={\frac {23\cdot 22}{2}}=253}$ пари. Припускаємо, що всі дні народження однаково ймовірні^[2], ймовірність мати день народження в певний день для конкретної людини становить ${\displaystyle {\frac {1}{365}}}$ (нехтуємо високосний рік, 29 лютого). Поглянувши на число можливих пар, вже значно легше прийняти факт того, що ймовірність збігу днів народження становить понад 50 %, хоча й неправильно казати, що розподіл за парами групи з 23 людей еквівалентний 253 парам вибраним незалежно.

Обчислення ймовірності

Задача полягає в обчисленні приблизної ймовірності того, що в кімнаті з ${\displaystyle n}$ людьми, щонайменше двоє мають один і той самий день народження. Для спрощення не зважатимемо на нерівномірність розподілу народжуваності протягом року, і припустимо, що існує 365 днів рівних між собою. У справжньому житті розподіл днів народження неоднаковий.

Якщо ${\displaystyle P(A)}$ ймовірність збігу щонайменше двох днів народження, тоді можливо буде легше обчислити ${\displaystyle P(A')}$, ймовірність того, що в групі немає двох людей з однаковим днем народження. Через те, що ${\displaystyle P(A)}$ та ${\displaystyle P(A')}$ — єдині дві можливі ймовірності і вони виключають одна одну, ${\displaystyle P(A')=1-P(A)}$.

Коли події незалежні одна від одної, ймовірність настання їх усіх дорівнює добутку ймовірностей кожної окремої події. Через це, якщо ${\displaystyle P(A')}$ можна описати як 23 незалежні події, тоді ${\displaystyle P(A')}$ може бути вирахувана як ${\displaystyle P(1)\times P(2)\times P(3)\times \cdots \times P(23)}$.

23 людей відповідають 23 незалежним подіям, які можна розташувати за порядком. Кожна подія може бути визначена як те, що відповідна людина має різні дні народження з усіма попередньо відібраними людьми. Для події 1 попередньо відібраних людей не має. Таким чином ймовірність ${\displaystyle P(1)}$ того, що людина 1 не має однакових днів народження з попередньо відібраними людьми становить 100 %. Враховуючи, що ми нехтуємо високосний рік, ймовірність 1 може бути записана як ${\displaystyle {\frac {365}{365}}}$, з причин які стануть зрозумілими далі. Для події 2, попередньо відібрана людина тільки одна. В нашому припущенні того, що день народження може з однаковою ймовірністю статися в будь-який день року, ймовірність ${\displaystyle P(2)}$, що людина 2 має відмінний від людини 1 день народження, становить ${\displaystyle {\frac {364}{365}}}$. Це правильно з огляду на те, що людина 2 може народитися в будь-який з 364 серед 365 днів року і при цьому мати різні дні народження з людиною 1.

Так само, людина 3 може народитися в будь-який з 363 днів року, відмінних від днів народження перших двох, і ймовірність ${\displaystyle P(3)={\frac {363}{365}}}$.

Цей розбір продовжується до досягнення 23-ї людини, і ${\displaystyle P(23)={\frac {343}{365}}}$.

P(A') дорівнює добутку окремих ймовірностей:

${\displaystyle P(A')={\frac {365}{365}}\times {\frac {364}{365}}\times {\frac {363}{365}}\times {\frac {362}{365}}\times \cdots \times {\frac {343}{365}}}$

(1)

Рівняння (1) можна далі записати як:

${\displaystyle P(A')=\left({\frac {1}{365}}\right)^{23}\times (365\times 364\times 363\times \cdots \times 343)}$

(2)

Для подальшого спрощення рівняння (2), розпишемо факторіал 365 як:

${\displaystyle 365!=365\times 364\times 363\times \cdots \times 343\times 342!}$

І поділимо обидві частини на ${\displaystyle 342!}$:

${\displaystyle {\frac {365!}{342!}}=365\times 364\times 363\times \cdots \times 343}$

(3)

Тепер підставимо рівняння (3) в рівняння (2):

${\displaystyle P(A')={\frac {365!}{342!}}\times \left({\frac {1}{365}}\right)^{23}}$

(4)

Обчислення рівняння (4) нам дає ${\displaystyle P(A')=0.49270276}$.

Відповідно, ${\displaystyle P(A)=1-0.49270276=0.507297(50.7297\%)}$

Цей процес може бути узагальнений для групи з ${\displaystyle n}$ людей, де ${\displaystyle p(n)}$ ймовірність збігу днів народження у принаймні двох людей з ${\displaystyle n}$. Легше спочатку вирахувати ймовірність ${\displaystyle {\bar {p}}(n)}$ того, що всі ${\displaystyle n}$ днів народження різні. Згідно з принципом Діріхле, ${\displaystyle {\bar {p}}(n)=0}$ коли ${\displaystyle n>365}$. Коли ${\displaystyle n\leq 365}$:

${\displaystyle {\bar {p}}(n)=1\cdot \left(1-{\frac {1}{365}}\right)\cdot \left(1-{\frac {2}{365}}\right)\cdot \ldots \cdot \left(1-{\frac {n-1}{365}}\right)={365\cdot 364\cdot \ldots \cdot (365-n+1) \over 365^{n}}={365! \over 365^{n}(365-n)!}.}$

Рівняння відображає описаний раніше факт отримання ймовірностей ${\displaystyle p(i)}$.

Ймовірність того, що принаймні двоє людей з ${\displaystyle n}$ мають однаковий день народження, комплементарна до ймовірності, що всі дні народження різні. Таким чином,

${\displaystyle p(n)=1-{\bar {p}}(n).\,}$

Приблизна ймовірність відсутності двох людей з однаковим днем народження в групі з n осіб.

Ця ймовірність перевищує ${\displaystyle {\frac {1}{2}}}$ для ${\displaystyle n=23}$ (зі значенням біля 50.7 %). Наступна таблиця показує ймовірності для деяких інших значень ${\displaystyle n}$ (в таблиці знехтувано високосні роки):

n	p(n)
10	11.7 %
20	41.1 %
23	50.7 %
30	70.6 %
50	97.0 %
57	99.0 %
100	99.99997 %
200	99.9999999999999999999999999998 %
300	(100 − (6×10−80))%
350	(100 − (3×10−129))%
366	100 %

Апроксимація

Використавши розклад експоненційної функції в ряд Тейлора

${\displaystyle e^{x}=1+x+{\frac {x^{2}}{2!}}+\cdots }$

Графік показує точність наближення ${\displaystyle 1-e^{-n^{2}/(2\times 365)}}$

отримаємо апроксимацію першого порядку для ${\displaystyle e^{x}}$ при ${\displaystyle x\ll 1}$:

${\displaystyle e^{x}\approx 1+x.\ }$

Якщо ${\displaystyle x=-a/365,}$ то

${\displaystyle e^{-a/365}\approx 1-{\frac {a}{365}}.}$

Перший вираз отриманий для p(n) може бути апроксимований як

${\displaystyle {\bar {p}}(n)\approx 1\cdot e^{-1/365}\cdot e^{-2/365}\cdots e^{-(n-1)/365}}$

${\displaystyle =1\cdot e^{-(1+2+\cdots +(n-1))/365}}$

${\displaystyle =e^{-{\frac {n(n-1)}{2\cdot 365}}}}$

Відповідно

${\displaystyle p(n)=1-{\bar {p}}(n)\approx 1-e^{-n(n-1)/(2\times 365)}.}$

Навіть грубіша апроксимація отримана таким чином

${\displaystyle p(n)\approx 1-e^{-n^{2}/(2\times 365)},\,}$

як показує графік, залишається досить точною.

Просте піднесення до степеня

Ймовірність того, що будь-які двоє людей мають різні дні народження становить 364/365. В кімнаті з n людьми, налічується C(n, 2)=n(n-1)/2 пар, тобто C(n, 2) подій. Ймовірність відсутності двох людей з однаковим днем народження може бути апроксимована припущенням того, що всі ці події незалежні і знайдена як простий добуток їх ймовірностей. Коротко кажучи, дріб 364/365 може бути помножений на себе C(n, 2) разів, що дає нам

${\displaystyle \left({\frac {364}{365}}\right)^{C(n,2)}.}$

Якщо це ймовірність, що ніхто не має однакових днів народження, тоді ймовірність наявності таких людей становить

${\displaystyle p(n)\approx 1-\left({\frac {364}{365}}\right)^{C(n,2)}.}$

Розподіл Пуассона

Якщо в кімнаті присутні ${\displaystyle n}$ людей, то маємо ${\displaystyle {n \choose 2}}$ пар. Ми визначили успіх за наявність однієї пари з однаковим днем народження, імовірність цього ${\displaystyle 1/365}$. Отже

${\displaystyle n={n \choose 2},\ p=1/365}$

Очікувана кількість успіхів становить

${\displaystyle \mu \ =np={n \choose 2}/365=n\left(n-1\right)/730=\lambda }$

Звідси, ймовірність того, що нема такої пари, є

${\displaystyle P(X=0)=e^{-\mu }}$${\displaystyle {\frac {\lambda ^{0}}{0!}}=e^{-\mu }=\exp\{{\frac {-n\left(n-1\right)}{730}}\}}$

Якщо ми бажаємо знайти кількість людей для яких імовірність менша ніж 0.5:

${\displaystyle \exp\{{\frac {-n\left(n-1\right)}{730}}\}\leq 1/2}$

${\displaystyle \exp\{{\frac {n\left(n-1\right)}{730}}\}\geq 1/2}$

${\displaystyle n\left(n-1\right)\geq 730\ln(2)}$

що дає нам ${\displaystyle n\approx 23}$, тобто якщо в кімнаті 23 людей, то ймовірність, що дні народження двох з них збігаються, дорівнює 0.5.

Розрахунок кількості осіб, за якої ймовірність становить 50 %

З наведеної раніше формули для p(n) виразимо n. Потім замість p(n) підставимо 50 % (0,5). В результаті отримаємо:

${\displaystyle n\approx {\frac {1}{2}}+{\sqrt {{\frac {1}{4}}-2\cdot 365\cdot \ln(0,5)}}=22,9999.}$

Існує ще один спосіб оцінення n за ймовірності 50 % Згідно доведеному вище:

${\displaystyle {\bar {p}}(n)=1-p(n)=\prod _{k=1}^{n-1}\left(1-{\frac {k}{365}}\right).}$

Знайдемо найменше n, за якого

${\displaystyle p(n)>{\frac {1}{2}}}$

або, що те ж саме:

${\displaystyle {\bar {p}}(n)<{\frac {1}{2}}.}$

Скористаємося наведеною вище апроксимацією функції ${\displaystyle {\bar {p}}(n)}$ експоненційною функцією:

${\displaystyle {\bar {p}}_{approx}(n)=\prod _{k=1}^{n-1}\left(e^{\frac {-k}{365}}\right)=e^{\frac {-n(n-1)}{2\cdot 365}}.}$

Підставивши ${\displaystyle {\bar {p}}_{approx}(n)}$ замість ${\displaystyle {\bar {p}}(n)}$ у вираз ${\displaystyle {\bar {p}}(n)<{\frac {1}{2}}}$, отримаємо:

${\displaystyle e^{\frac {-n(n-1)}{2\cdot 365}}<{\frac {1}{2}}.}$

Розв'язуючи відносно n, отримаємо:

${\displaystyle n^{2}-n>2\cdot 365\cdot \ln 2\,\!.}$

Звідси знайдемо n і округлимо до цілого :

n = 23.

Люди, що народились в один день із заданою людиною

Порівняємо ймовірність p(n) зі ймовірністю того, що в групі з n людей день народження якоїсь людини з групи збіжиться з днем народження деякої заздалегідь вибраної людини, яка не належить до групи. Ця ймовірність дорівнює

${\displaystyle q(n)=1-\left({\frac {365-1}{365}}\right)^{n}.}$

Порівняння графіків функцій p(n) і q(n) * Вісь абсцис: кількість осіб n. * Вісь ординат: ймовірність. * p(n) — ймовірність того, що в групі з n осіб принаймні у двох з них дні народження збіжаться. * q(n) — ймовірність того, що в групі з n осіб день народження будь-якої особи з групи збіжиться з днем народження деякої заздалегідь вибраної людини, що не належить групі.

Підставляючи n = 23, маємо q(n) ≈ 6,12 %. Для того, щоб імовірність q(n) перевищила 50 %, число людей в групі має бути не меншим, ніж 253 (q(252) ≈ 49,91 %; q(253) ≈ 50,05 %). Це число більше, ніж половина днів у році (365/2 = 182,5); так виходить через те, що в решти членів групи дні народження можуть збігатися, і це зменшує ймовірність q(n).

Узагальнення

Збіг дискретних випадкових величин

Описана задача може бути сформульована в загальному вигляді:

• дані випадкові числа;
• випадкові числа розподілені рівномірно в діапазоні від 1 до d;
• n — кількість випадкових чисел;
• визначити p( n ; d ) — ймовірність того, що збіжаться хоча б два числа із заданих.

Якщо міркувати так само, як описано вище, можна отримати загальні розв'язки:

${\displaystyle p(n;d)={\begin{cases}1-\prod _{k=1}^{n-1}\left(1-{k \over d}\right)&n\leq d\\1&n>d\end{cases}};}$

${\displaystyle p(n;d)\approx 1-e^{-(n(n-1))/2d};}$

${\displaystyle q(n;d)=1-\left({\frac {d-1}{d}}\right)^{n}.}$

Обернена задача:

• дана p — ймовірність того, що збігаються хоча б два випадкових числа;
• відомо, що випадкові числа розподілені рівномірно в діапазоні від 1 до d;
• знайти n(p;d) — кількість випадкових чисел.

Розв'язок:

${\displaystyle n(p;d)\approx {\sqrt {2d\cdot \ln \left({1 \over 1-p}\right)}}.}$

Кілька типів людей

Ймовірність збігу дня народження хоча б в одного чоловіка і в однієї жінки

Вище парадокс днів народження був розглянутий для одного «типу» людей. Можна узагальнити задачу, ввівши кілька «типів», наприклад, розділивши людей на чоловіків (m) і жінок (n). Підрахуємо ймовірність того, що хоча б в однієї жінки і в одного чоловіка збігаються дні народження (збіг днів народження у двох жінок або у двох чоловіків не враховуються):

${\displaystyle p_{0}=1-{\frac {1}{d^{m+n}}}\sum _{i=1}^{m}\sum _{j=1}^{n}S_{2}(m,i)S_{2}(n,j)\prod _{k=0}^{i+j-1}(d-k),}$

де d = 365 и S₂() — числа Стірлінга другого роду. Цікаво, що немає однозначної відповіді на питання про величину n+m для заданої ймовірності. Наприклад, ймовірність 0,5 дає як набір з 16 чоловіків і 16 жінок, так і набір з 43 чоловіків і 6 жінок.

Близькі дні народження

Інше узагальнення парадоксу днів народження полягає в постановці задачі про те, скільки потрібно людей для того, щоб імовірність наявності в групі людей, дні народження яких відрізняються не більше ніж на один день (або на два, три дні і так далі), перевищила 50 %. Під час розв'язування цієї задачі використовується принцип включень-виключень. Результат (знову ж у припущенні, що дні народження розподілені рівномірно) виходить таким:

Максимальна різниця днів народження, кількість днів	Необхідна кількість людей
1	23
2	14
3	11
4	9
5	8
6	8
7	7
8	7

Таким чином, ймовірність того, що навіть у групі з 7 людей дні народження хоча б у двох з них будуть відрізнятися не більше ніж на тиждень, перевищує 50 %.

Застосування

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

N	Кількість різних вихідних ланцюжків (2N)	Імовірність хоча б однієї колізії (p)
		10 −18	10 −15	10 −12	10 −9	10 −6	0,1 %	1 %	25 %	50 %	75 %
32	4,3 × 10 9	2	2	2	2.9	93	2.9 × 10³	9.3 × 10³	5.0 × 10⁴	7.7 × 10⁴	1.1 × 10⁵
64	1,8 × 10 19	6.1	1.9 × 10²	6.1 × 10³	1.9 × 10⁵	6.1 × 10⁶	1.9 × 10⁸	6.1 × 10⁸	3.3 × 10⁹	5.1 × 10⁹	7.2 × 10⁹
128	3,4 × 10 38	2.6 × 10 10	8.2 × 10 11	2.6 × 10 13	8.2 × 10 14	2.6 × 10 16	8.3 × 10 17	2.6 × 10 18	1.4 × 10 19	2.2 × 10 19	3.1 × 10 19
256	1,2 × 10 77	4.8 × 10 29	1.5 × 10 31	4.8 × 10 32	1.5 × 10 34	4.8 × 10 35	1.5 × 10 37	4.8 × 10 37	2.6 × 10 38	4.0 × 10 38	5.7 × 10 38
384	3,9 × 10 115	8.9 × 10 48	2.8 × 10 50	8.9 × 10 51	2.8 × 10 53	8.9 × 10 54	2.8 × 10 56	8.9 × 10 56	4.8 × 10 57	7.4 × 10 57	1.0 × 10 58
512	1,3 × 10 154	1.6 × 10 68	5.2 × 10 69	1.6 × 10 71	5.2 × 10 72	1.6 × 10 74	5.2 × 10 75	1.6 × 10 76	8.8 × 10 76	1.4 × 10 77	1.9 × 10 77

У білих комірках вказана кількість осіб у групі, за якої колізія відбудеться із заданою ймовірністю (за аналогією з парадоксом кількість вихідних ланцюжків становить 365).

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

Розв'язок задачі в загальному вигляді застосовується у багатьох розділах математики, наприклад, у недетермінованих алгоритмах факторизації. Так, одне з найпростіших пояснень ρ-методу Полларда аналогічне поясненню парадоксу днів народження: досить мати приблизно ${\displaystyle {\sqrt {p}}}$ випадкових чисел від 0 до ${\displaystyle n=pq}$, де ${\displaystyle p<q}$ — прості, щоб хоча б для однієї з пар чисел з високою ймовірністю знайшовся ${\displaystyle \gcd \left(|x-y|,n\right)>1}$, який і буде дільником числа n.

Обернені задачі

1. Пошук найменшого числа n, за якого ймовірність p (n) більша від заданого числа p.

1. Пошук найбільшого числа n, за якого ймовірність p(n) менша від заданого числа p.

Користуючись формулою, наведеною вище, отримуємо:

${\displaystyle n(p;365)\approx {\sqrt {2\cdot 365\cdot \ln \left({1 \over 1-p}\right)}}.}$

p	n	n ↓	p (n ↓)	n ↑	p (n ↑)
0.01	0.14178√365 = 2.70864	2	0.00274	3	0.00820
0.05	0.32029√365 = 6.11916	6	0.04046	7	0.05624
0.1	0.45904√365 = 8.77002	8	0.07434	9	0.09462
0.2	0.66805√365 = 12.76302	12	0.16702	13	0.19441
0.3	0.84460√365 = 16.13607	16	0.28360	17	0.31501
0.5	1.17741√365 = 22.49439	22	0.47570	23	0.50730
0.7	1.55176√365 = 29.64625	29	0.68097	30	0.70632
0.8	1.79412√365 = 34.27666	34	0.79532	35	0.81438
0.9	2.14597√365 = 40.99862	40	0.89123	41	0.90315
0.95	2.44775√365 = 46.76414	46	0.94825	47	0.95477
0.99	3.03485√365 = 57.98081	57	0.99012	58	0.99166

Найкраща позиція

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

Розв'язування зводиться до знаходження максимального значення виразу

p(n) - p(n-1).

Використовуючи наведену вище формулу для p(n) отримаємо n = 20

Середнє число людей

Розглянемо іншу задачу. Скільки в середньому потрібно людей для того, щоб хоча б у двох з них збіглися дні народження?

Ця проблема мала відношення до алгоритмів хешування і була досліджена Дональдом Кнутом. Виявляється, що випадкова величина, яка нас цікавить, має математичне сподівання, рівне

${\displaystyle {\overline {n}}\,=\,1+Q(M),}$

де

${\displaystyle Q(M)=\sum _{k=1}^{M}{\frac {M!}{(M-k)!M^{k}}}.}$

Функція

${\displaystyle Q(M)\,=\,1+{\frac {M-1}{M}}+{\frac {(M-1)(M-2)}{M^{2}}}+\cdots +{\frac {(M-1)(M-2)\cdots 1}{M^{M-1}}}}$

була досліджена Рамануджаном. Він же отримав для цієї функції таке асимптотичне розкладання :

${\displaystyle Q(M)\sim {\sqrt {\frac {\pi M}{2}}}-{\frac {1}{3}}+{\frac {1}{12}}{\sqrt {\frac {\pi }{2M}}}-{\frac {4}{135M}}+\cdots .}$

При M = 365 середня кількість людей дорівнює

${\displaystyle {\overline {n}}\,=\,1+Q(M)\approx 24.61658.}$

Це число трохи більше, ніж число людей, що забезпечують імовірність 50 %. Як не дивно, необхідне число людей дорівнює M + 1 = 366 (у 365 людей дні народження можуть розподілитися по кожному з 365 днів року без збігів), хоча в середньому потрібно лиш 25.