Парадокс днів народження
10/23/2011 | stryjko_bojko
У теорії ймовірностей парадокс днів народження оцінює ймовірність того, що в випадково обраній групі збіжаться дні народження якоїсь пари. В групах кількістю не менших 23 випадково вибраних людей, ймовірність збігу днів народження в якоїсь пари складає більше 50%. Такий результат суперечить інтуїтивній уяві більшості.
Для 57 людей, ймовірність складає більше ніж 99%, і досягає 100% коли, ігноруючи високосний рік, кількість людей в групі становить 366 (через принцип Діріхле). Такий розподіл ймовірностей призвів до широко-відомої криптографічної атаки відомої як атака «днів народження».
На графіку показана приблизна ймовірність того, що щонайменше двоє людей будуть мати день народження в один день.
Розуміння проблеми
Парадокс днів народження запитує, коли хтось з випадково вибраних 23 людей буде мати день народження в один день з кимось іншим з групи.
У списку з 23 людей, при порівнянні днів народження з першою в списку людиною існує 22 шанси на збіг, але порівняння кожного з кожним дає 253 різні шанси: в групі з 23 людей, утворюється {23 \choose 2} = \frac{23 \cdot 22}{2} = 253 пари. Припускаємо, що всі дні народження однаково ймовірні, ймовірність мати день народження в певний день для конкретної людини становить 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:
де "!" оператор факторіала.
Рівняння відображає описаний раніше факт утворення ймовірностей 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%
wikipedia
Для 57 людей, ймовірність складає більше ніж 99%, і досягає 100% коли, ігноруючи високосний рік, кількість людей в групі становить 366 (через принцип Діріхле). Такий розподіл ймовірностей призвів до широко-відомої криптографічної атаки відомої як атака «днів народження».
На графіку показана приблизна ймовірність того, що щонайменше двоє людей будуть мати день народження в один день.
Розуміння проблеми
Парадокс днів народження запитує, коли хтось з випадково вибраних 23 людей буде мати день народження в один день з кимось іншим з групи.
У списку з 23 людей, при порівнянні днів народження з першою в списку людиною існує 22 шанси на збіг, але порівняння кожного з кожним дає 253 різні шанси: в групі з 23 людей, утворюється {23 \choose 2} = \frac{23 \cdot 22}{2} = 253 пари. Припускаємо, що всі дні народження однаково ймовірні, ймовірність мати день народження в певний день для конкретної людини становить 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:
де "!" оператор факторіала.
Рівняння відображає описаний раніше факт утворення ймовірностей 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%
wikipedia