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

Матеріал з Вікіпедії — вільної енциклопедії.
Перейти до: навігація, пошук

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

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

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

Розуміння проблеми[ред.ред. код]

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

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

Обчислення ймовірності[ред.ред. код]

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

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

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

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

Схожим чином, якщо людина 3 може народитися в будь-який з 363 днів року відмінних від днів народження перших двох. І ймовірність P(3) = 363/365.

Цей розбір продовжується до досягнення 23 людини, і P(23), is 343/365.

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

(1) P(A') = 365/365 × 364/365 × 363/365 × 362/365 × ... × 343/365

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

(2) P(A') = (1/365)23 × (365 × 364 × 363 × ... × 343)

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

(3) 365! = 365 × 364 × 363 × ... × 343 × 342!.

І поділимо обидві частини на 342!:

(4) 365!/342! = 365 × 364 × 363 × ... × 343

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

(5) P(A') = 365!/342! × (1/365)23

Обчислення рівняння (5) нам дає P(A') = 0.49270276

Відповідно, P(A) = 1 − 0.49270276 = 0.507297 (50.7297%)

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

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

де "!" оператор факторіала.

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

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

 p(n) = 1 - \bar p(n). \,
Приблизна ймовірність відсутності двох людей з однаковим днем народження в групі з n осіб.

Ця ймовірність перевищує 1/2 для n = 23 (зі значенням біля 50.7%). Наступна таблиця показує ймовірності для деяких інших значень 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%

Апроксимізація[ред.ред. код]

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

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

отримаємо апроксимацію першого порядку для ex:

 e^x \approx 1 + x.\

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

\bar p(n) \approx 1 \cdot e^{-1/365} \cdot e^{-2/365} \cdots e^{-(n-1)/365}
= 1 \cdot e^{-(1+2+ \cdots +(n-1))/365}
= e^{-\frac{n(n-1)}{2 \cdot 365}}

Відповідно

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

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

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) разів, що дає нам

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

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

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

Розподіл Пуассона[ред.ред. код]

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

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

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

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

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

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

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

exp \{ \frac {-n \left(n - 1\right)}{730} \} \le 1/2
exp \{ \frac {n \left(n - 1\right)}{730} \} \ge 1/2
n \left(n - 1\right) \ge 730 ln(2)

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

Примітки[ред.ред. код]

  1. Хоча це й не парадокс у сенсі отримання логічного протиріччя, але він названий так через те, що математичний розв'язок суперечить наївній інтуїції: більшість людей оцінюють шанс менше ніж в 50%.
  2. В дійсності, дні народження не рівно розподілені впродовж року; але для цієї задачи вважаємо розподіл рівномірним.