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

В парадоксі днів народження з'ясовується, чи хтось з випадково вибраних 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}$ (в таблиці знехтувано високосні роки):

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

${\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)},\,}$

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

З наведеної раніше формули для 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).

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

У білих комірках вказана кількість осіб у групі, за якої колізія відбудеться із заданою ймовірністю (за аналогією з парадоксом кількість вихідних ланцюжків становить 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)}}.}$

• Задача про листи

• Парадокси теорії ймовірностей .
• Порівняльний огляд алгоритмів PGP. Парадокс «днів народження» і стійкість криптографії .

• John G. Kemeny, J. Laurie Snell, Gerald Thompson. Introduction to Finite Mathematics. The first edition. — 1‑е издание. — 1957. (англ.)

• Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику : [англ.]. — Издательство иностранной литературы, 1963. — 488 с. (рос.)

• Секей Г. Парадоксы в теории вероятностей и математической статистике. — РХД, 2003. — ISBN 5-93972-150-8. (рос.)

• Козлов М. В. Элементы теории вероятностей в примерах и задачах. — МГУ, 1990. — ISBN 5-211-00312-8. (рос.)

• Ширяев А. Н. Вероятность-1. — МЦНМО, 2007. — ISBN 978-5-94057-036-3.(рос.)

• Goldberg S. A Direct Attack on a Birthday Problem // Mathematical Mathematics Magazine. — травень 1976. — No. 49. — С. 130—132.(англ.)

• Mosteller F. Understanding the Birthday Problem // The Mathematics Teacher. — травень 1962. — С. 322—325.(англ.)

• Eurobirthdays 2012 года Практичний приклад(англ.)