У теорії ймовірностей парадокс днів народження оцінює ймовірність того, що у випадково вибраній групі людей збігатимуться дні народження в якоїсь пари. В групах кількістю не менших 23 випадково вибраних людей, ймовірність збігу днів народження в якоїсь пари становить більше 50 %. Такий результат суперечить інтуїтивній уяві більшості.
Для 57 людей, ймовірність становить більше ніж 99 %, і досягає 100 % коли, ігноруючи високосний рік, кількість людей у групі становить 366 (через принцип Діріхле). Такий розподіл ймовірностей призвів до широко відомої криптографічної атаки відомої як атака «днів народження».
У формулюванні парадоксу йдеться саме про збіг днів народження у будь-яких двох членів групи. Одна з поширених помилок полягає в тому, що цей випадок плутають з іншим випадком, на перший погляд схожим, коли з групи вибирається одна людина, й оцінюється ймовірність того, що день народження будь-яких інших членів групи збіжиться з днем народження вибраної людини. В останньому випадку ймовірність збігу значно нижча.
Розуміння проблеми
В парадоксі днів народження з'ясовується, чи хтось з випадково вибраних 23 людей буде мати день народження в один день з кимось іншим з групи.
У списку з 23 людей, при порівнянні днів народження з першою в списку людиною, існує 22 шанси на збіг, але порівняння кожного з кожним дає 253 різні шанси: в групі з 23 людей, утворюється пари. Припускаємо, що всі дні народження однаково ймовірні, ймовірність мати день народження в певний день для конкретної людини становить (нехтуємо високосний рік, 29 лютого). Поглянувши на число можливих пар, вже значно легше прийняти факт того, що ймовірність збігу днів народження становить понад 50 %, хоча й неправильно казати, що розподіл за парами групи з 23 людей еквівалентний 253 парам вибраним незалежно.
Обчислення ймовірності
Задача полягає в обчисленні приблизної ймовірності того, що в кімнаті з людьми, щонайменше двоє мають один і той самий день народження. Для спрощення не зважатимемо на нерівномірність розподілу народжуваності протягом року, і припустимо, що існує 365 днів рівних між собою. У справжньому житті розподіл днів народження неоднаковий.
Якщо ймовірність збігу щонайменше двох днів народження, тоді можливо буде легше обчислити , ймовірність того, що в групі немає двох людей з однаковим днем народження. Через те, що та — єдині дві можливі ймовірності і вони виключають одна одну, .
Коли події незалежні одна від одної, ймовірність настання їх усіх дорівнює добутку ймовірностей кожної окремої події. Через це, якщо можна описати як 23 незалежні події, тоді може бути вирахувана як .
23 людей відповідають 23 незалежним подіям, які можна розташувати за порядком. Кожна подія може бути визначена як те, що відповідна людина має різні дні народження з усіма попередньо відібраними людьми. Для події 1 попередньо відібраних людей не має. Таким чином ймовірність того, що людина 1 не має однакових днів народження з попередньо відібраними людьми становить 100 %. Враховуючи, що ми нехтуємо високосний рік, ймовірність 1 може бути записана як , з причин які стануть зрозумілими далі. Для події 2, попередньо відібрана людина тільки одна. В нашому припущенні того, що день народження може з однаковою ймовірністю статися в будь-який день року, ймовірність , що людина 2 має відмінний від людини 1 день народження, становить . Це правильно з огляду на те, що людина 2 може народитися в будь-який з 364 серед 365 днів року і при цьому мати різні дні народження з людиною 1.
Так само, людина 3 може народитися в будь-який з 363 днів року, відмінних від днів народження перших двох, і ймовірність .
Цей розбір продовжується до досягнення 23-ї людини, і .
P(A') дорівнює добутку окремих ймовірностей:
-
(
)
Рівняння (1) можна далі записати як:
-
(
)
Для подальшого спрощення рівняння (2), розпишемо факторіал 365 як:
І поділимо обидві частини на :
-
(
)
Тепер підставимо рівняння (3) в рівняння (2):
-
(
)
Обчислення рівняння (4) нам дає .
Відповідно,
Цей процес може бути узагальнений для групи з людей, де ймовірність збігу днів народження у принаймні двох людей з . Легше спочатку вирахувати ймовірність того, що всі днів народження різні. Згідно з принципом Діріхле, коли . Коли :
Рівняння відображає описаний раніше факт отримання ймовірностей .
Ймовірність того, що принаймні двоє людей з мають однаковий день народження, комплементарна до ймовірності, що всі дні народження різні. Таким чином,
Ця ймовірність перевищує для (зі значенням біля 50.7 %). Наступна таблиця показує ймовірності для деяких інших значень (в таблиці знехтувано високосні роки):
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 % |
Апроксимація
Використавши розклад експоненційної функції в ряд Тейлора
отримаємо апроксимацію першого порядку для при :
Якщо то
Перший вираз отриманий для p(n) може бути апроксимований як
Відповідно
Навіть грубіша апроксимація отримана таким чином
як показує графік, залишається досить точною.
Просте піднесення до степеня
Ймовірність того, що будь-які двоє людей мають різні дні народження становить 364/365. В кімнаті з n людьми, налічується C(n, 2)=n(n-1)/2 пар, тобто C(n, 2) подій. Ймовірність відсутності двох людей з однаковим днем народження може бути апроксимована припущенням того, що всі ці події незалежні і знайдена як простий добуток їх ймовірностей. Коротко кажучи, дріб 364/365 може бути помножений на себе C(n, 2) разів, що дає нам
Якщо це ймовірність, що ніхто не має однакових днів народження, тоді ймовірність наявності таких людей становить
Розподіл Пуассона
Якщо в кімнаті присутні людей, то маємо пар. Ми визначили успіх за наявність однієї пари з однаковим днем народження, імовірність цього . Отже
Очікувана кількість успіхів становить
Звідси, ймовірність того, що нема такої пари, є
Якщо ми бажаємо знайти кількість людей для яких імовірність менша ніж 0.5:
що дає нам , тобто якщо в кімнаті 23 людей, то ймовірність, що дні народження двох з них збігаються, дорівнює 0.5.
Розрахунок кількості осіб, за якої ймовірність становить 50 %
З наведеної раніше формули для p(n) виразимо n. Потім замість p(n) підставимо 50 % (0,5). В результаті отримаємо:
Існує ще один спосіб оцінення n за ймовірності 50 % Згідно доведеному вище:
Знайдемо найменше n, за якого
або, що те ж саме:
Скористаємося наведеною вище апроксимацією функції експоненційною функцією:
Підставивши замість у вираз , отримаємо:
Розв'язуючи відносно n, отримаємо:
Звідси знайдемо n і округлимо до цілого :
- n = 23.
Люди, що народились в один день із заданою людиною
Порівняємо ймовірність p(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 ) — ймовірність того, що збіжаться хоча б два числа із заданих.
Якщо міркувати так само, як описано вище, можна отримати загальні розв'язки:
Обернена задача:
- дана p — ймовірність того, що збігаються хоча б два випадкових числа;
- відомо, що випадкові числа розподілені рівномірно в діапазоні від 1 до d;
- знайти n(p;d) — кількість випадкових чисел.
Розв'язок:
Кілька типів людей
Вище парадокс днів народження був розглянутий для одного «типу» людей. Можна узагальнити задачу, ввівши кілька «типів», наприклад, розділивши людей на чоловіків (m) і жінок (n). Підрахуємо ймовірність того, що хоча б в однієї жінки і в одного чоловіка збігаються дні народження (збіг днів народження у двох жінок або у двох чоловіків не враховуються):
де d = 365 и S2() — числа Стірлінга другого роду. Цікаво, що немає однозначної відповіді на питання про величину 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-бітове значення, то число випадкових вхідних даних, для яких хеш-коди з великою ймовірністю дадуть колізію (тобто знайдуться рівні хеш-коди, отримані на різних вхідних даних), дорівнює не 2N, а тільки близько 2N/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» («зловити-зловити знову»). Дійсно, якщо кожну спійману рибу позначати та відпускати, то ймовірність зловити позначену рибу буде зростати нелінійно (відповідно до наведеного вище графіка) зі зростанням кількості спроб. Розмір популяції грубо може бути оцінений як квадрат числа спроб, здійснених до виловлювання першої позначеної риби.
Розв'язок задачі в загальному вигляді застосовується у багатьох розділах математики, наприклад, у недетермінованих алгоритмах факторизації. Так, одне з найпростіших пояснень ρ-методу Полларда аналогічне поясненню парадоксу днів народження: досить мати приблизно випадкових чисел від 0 до , де — прості, щоб хоча б для однієї з пар чисел з високою ймовірністю знайшовся , який і буде дільником числа n.
Обернені задачі
- Пошук найменшого числа n, за якого ймовірність p (n) більша від заданого числа p.
- Пошук найбільшого числа n, за якого ймовірність p(n) менша від заданого числа p.
Користуючись формулою, наведеною вище, отримуємо:
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
Середнє число людей
Розглянемо іншу задачу. Скільки в середньому потрібно людей для того, щоб хоча б у двох з них збіглися дні народження?
Ця проблема мала відношення до алгоритмів хешування і була досліджена Дональдом Кнутом. Виявляється, що випадкова величина, яка нас цікавить, має математичне сподівання, рівне
де
Функція
була досліджена Рамануджаном. Він же отримав для цієї функції таке асимптотичне розкладання :
При M = 365 середня кількість людей дорівнює
Це число трохи більше, ніж число людей, що забезпечують імовірність 50 %. Як не дивно, необхідне число людей дорівнює M + 1 = 366 (у 365 людей дні народження можуть розподілитися по кожному з 365 днів року без збігів), хоча в середньому потрібно лиш 25.
Примітки
- Хоча це й не парадокс у сенсі отримання логічної суперечності, але він названий так через те, що математичний розв'язок суперечить наївній інтуїції: більшість людей оцінюють шанс менше ніж у 50 %.
- Насправді, дні народження нерівномірно розподілені впродовж року; але для цієї задачі вважаємо розподіл рівномірним.
Див. також
- (Задача про листи)
Посилання
- Парадокси теорії ймовірностей.
- Порівняльний огляд алгоритмів PGP. Парадокс «днів народження» і стійкість криптографії.
Література
- John G. Kemeny, J. Laurie Snell, Gerald Thompson. Introduction to Finite Mathematics. The first edition. — 1‑е издание. — 1957. (англ.)
- Кемени Дж., Снелл Дж., Томпсон Дж. Введение в конечную математику : ( )[англ.]. — Издательство иностранной литературы, 1963. — 488 с. (рос.)
- Секей Г. Парадоксы в теории вероятностей и математической статистике. — РХД, 2003. — . (рос.)
- Козлов М. В. Элементы теории вероятностей в примерах и задачах. — МГУ, 1990. — . (рос.)
- Ширяев А. Н. Вероятность-1. — МЦНМО, 2007. — .(рос.)
- 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 года Практичний приклад(англ.)
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
U teoriyi jmovirnostej paradoks dniv narodzhennya ocinyuye jmovirnist togo sho u vipadkovo vibranij grupi lyudej zbigatimutsya dni narodzhennya v yakoyis pari V grupah kilkistyu ne menshih 23 vipadkovo vibranih lyudej jmovirnist zbigu dniv narodzhennya v yakoyis pari stanovit bilshe 50 Takij rezultat superechit intuyitivnij uyavi bilshosti Dlya 57 lyudej jmovirnist stanovit bilshe nizh 99 i dosyagaye 100 koli ignoruyuchi visokosnij rik kilkist lyudej u grupi stanovit 366 cherez princip Dirihle Takij rozpodil jmovirnostej prizviv do shiroko vidomoyi kriptografichnoyi ataki vidomoyi yak ataka dniv narodzhennya Na grafiku pokazana priblizna jmovirnist togo sho shonajmenshe dvoye lyudej budut mati den narodzhennya v odin den U formulyuvanni paradoksu jdetsya same pro zbig dniv narodzhennya u bud yakih dvoh chleniv grupi Odna z poshirenih pomilok polyagaye v tomu sho cej vipadok plutayut z inshim vipadkom na pershij poglyad shozhim koli z grupi vibirayetsya odna lyudina j ocinyuyetsya jmovirnist togo sho den narodzhennya bud yakih inshih chleniv grupi zbizhitsya z dnem narodzhennya vibranoyi lyudini V ostannomu vipadku jmovirnist zbigu znachno nizhcha Rozuminnya problemiV paradoksi dniv narodzhennya z yasovuyetsya chi htos z vipadkovo vibranih 23 lyudej bude mati den narodzhennya v odin den z kimos inshim z grupi U spisku z 23 lyudej pri porivnyanni dniv narodzhennya z pershoyu v spisku lyudinoyu isnuye 22 shansi na zbig ale porivnyannya kozhnogo z kozhnim daye 253 rizni shansi v grupi z 23 lyudej utvoryuyetsya 232 23 222 253 displaystyle 23 choose 2 frac 23 cdot 22 2 253 pari Pripuskayemo sho vsi dni narodzhennya odnakovo jmovirni jmovirnist mati den narodzhennya v pevnij den dlya konkretnoyi lyudini stanovit 1365 displaystyle frac 1 365 nehtuyemo visokosnij rik 29 lyutogo Poglyanuvshi na chislo mozhlivih par vzhe znachno legshe prijnyati fakt togo sho jmovirnist zbigu dniv narodzhennya stanovit ponad 50 hocha j nepravilno kazati sho rozpodil za parami grupi z 23 lyudej ekvivalentnij 253 param vibranim nezalezhno Obchislennya jmovirnostiZadacha polyagaye v obchislenni pribliznoyi jmovirnosti togo sho v kimnati z n displaystyle n lyudmi shonajmenshe dvoye mayut odin i toj samij den narodzhennya Dlya sproshennya ne zvazhatimemo na nerivnomirnist rozpodilu narodzhuvanosti protyagom roku i pripustimo sho isnuye 365 dniv rivnih mizh soboyu U spravzhnomu zhitti rozpodil dniv narodzhennya neodnakovij Yaksho P A displaystyle P A jmovirnist zbigu shonajmenshe dvoh dniv narodzhennya todi mozhlivo bude legshe obchisliti P A displaystyle P A jmovirnist togo sho v grupi nemaye dvoh lyudej z odnakovim dnem narodzhennya Cherez te sho P A displaystyle P A ta P A displaystyle P A yedini dvi mozhlivi jmovirnosti i voni viklyuchayut odna odnu P A 1 P A displaystyle P A 1 P A Koli podiyi nezalezhni odna vid odnoyi jmovirnist nastannya yih usih dorivnyuye dobutku jmovirnostej kozhnoyi okremoyi podiyi Cherez ce yaksho P A displaystyle P A mozhna opisati yak 23 nezalezhni podiyi todi P A displaystyle P A mozhe buti virahuvana yak P 1 P 2 P 3 P 23 displaystyle P 1 times P 2 times P 3 times cdots times P 23 23 lyudej vidpovidayut 23 nezalezhnim podiyam yaki mozhna roztashuvati za poryadkom Kozhna podiya mozhe buti viznachena yak te sho vidpovidna lyudina maye rizni dni narodzhennya z usima poperedno vidibranimi lyudmi Dlya podiyi 1 poperedno vidibranih lyudej ne maye Takim chinom jmovirnist P 1 displaystyle P 1 togo sho lyudina 1 ne maye odnakovih dniv narodzhennya z poperedno vidibranimi lyudmi stanovit 100 Vrahovuyuchi sho mi nehtuyemo visokosnij rik jmovirnist 1 mozhe buti zapisana yak 365365 displaystyle frac 365 365 z prichin yaki stanut zrozumilimi dali Dlya podiyi 2 poperedno vidibrana lyudina tilki odna V nashomu pripushenni togo sho den narodzhennya mozhe z odnakovoyu jmovirnistyu statisya v bud yakij den roku jmovirnist P 2 displaystyle P 2 sho lyudina 2 maye vidminnij vid lyudini 1 den narodzhennya stanovit 364365 displaystyle frac 364 365 Ce pravilno z oglyadu na te sho lyudina 2 mozhe naroditisya v bud yakij z 364 sered 365 dniv roku i pri comu mati rizni dni narodzhennya z lyudinoyu 1 Tak samo lyudina 3 mozhe naroditisya v bud yakij z 363 dniv roku vidminnih vid dniv narodzhennya pershih dvoh i jmovirnist P 3 363365 displaystyle P 3 frac 363 365 Cej rozbir prodovzhuyetsya do dosyagnennya 23 yi lyudini i P 23 343365 displaystyle P 23 frac 343 365 P A dorivnyuye dobutku okremih jmovirnostej P A 365365 364365 363365 362365 343365 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 Rivnyannya 1 mozhna dali zapisati yak P A 1365 23 365 364 363 343 displaystyle P A left frac 1 365 right 23 times 365 times 364 times 363 times cdots times 343 2 Dlya podalshogo sproshennya rivnyannya 2 rozpishemo faktorial 365 yak 365 365 364 363 343 342 displaystyle 365 365 times 364 times 363 times cdots times 343 times 342 I podilimo obidvi chastini na 342 displaystyle 342 365 342 365 364 363 343 displaystyle frac 365 342 365 times 364 times 363 times cdots times 343 3 Teper pidstavimo rivnyannya 3 v rivnyannya 2 P A 365 342 1365 23 displaystyle P A frac 365 342 times left frac 1 365 right 23 4 Obchislennya rivnyannya 4 nam daye P A 0 49270276 displaystyle P A 0 49270276 Vidpovidno P A 1 0 49270276 0 507297 50 7297 displaystyle P A 1 0 49270276 0 507297 50 7297 Cej proces mozhe buti uzagalnenij dlya grupi z n displaystyle n lyudej de p n displaystyle p n jmovirnist zbigu dniv narodzhennya u prinajmni dvoh lyudej z n displaystyle n Legshe spochatku virahuvati jmovirnist p n displaystyle bar p n togo sho vsi n displaystyle n dniv narodzhennya rizni Zgidno z principom Dirihle p n 0 displaystyle bar p n 0 koli n gt 365 displaystyle n gt 365 Koli n 365 displaystyle n leq 365 p n 1 1 1365 1 2365 1 n 1365 365 364 365 n 1 365n 365 365n 365 n 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 Rivnyannya vidobrazhaye opisanij ranishe fakt otrimannya jmovirnostej p i displaystyle p i Jmovirnist togo sho prinajmni dvoye lyudej z n displaystyle n mayut odnakovij den narodzhennya komplementarna do jmovirnosti sho vsi dni narodzhennya rizni Takim chinom p n 1 p n displaystyle p n 1 bar p n Priblizna jmovirnist vidsutnosti dvoh lyudej z odnakovim dnem narodzhennya v grupi z n osib Cya jmovirnist perevishuye 12 displaystyle frac 1 2 dlya n 23 displaystyle n 23 zi znachennyam bilya 50 7 Nastupna tablicya pokazuye jmovirnosti dlya deyakih inshih znachen n displaystyle n v tablici znehtuvano visokosni roki 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 AproksimaciyaVikoristavshi rozklad eksponencijnoyi funkciyi v ryad Tejlora ex 1 x x22 displaystyle e x 1 x frac x 2 2 cdots Grafik pokazuye tochnist nablizhennya 1 e n2 2 365 displaystyle 1 e n 2 2 times 365 otrimayemo aproksimaciyu pershogo poryadku dlya ex displaystyle e x pri x 1 displaystyle x ll 1 ex 1 x displaystyle e x approx 1 x Yaksho x a 365 displaystyle x a 365 to e a 365 1 a365 displaystyle e a 365 approx 1 frac a 365 Pershij viraz otrimanij dlya p n mozhe buti aproksimovanij yak p n 1 e 1 365 e 2 365 e n 1 365 displaystyle bar p n approx 1 cdot e 1 365 cdot e 2 365 cdots e n 1 365 1 e 1 2 n 1 365 displaystyle 1 cdot e 1 2 cdots n 1 365 e n n 1 2 365 displaystyle e frac n n 1 2 cdot 365 dd Vidpovidno p n 1 p n 1 e n n 1 2 365 displaystyle p n 1 bar p n approx 1 e n n 1 2 times 365 Navit grubisha aproksimaciya otrimana takim chinom p n 1 e n2 2 365 displaystyle p n approx 1 e n 2 2 times 365 yak pokazuye grafik zalishayetsya dosit tochnoyu Proste pidnesennya do stepenya Jmovirnist togo sho bud yaki dvoye lyudej mayut rizni dni narodzhennya stanovit 364 365 V kimnati z n lyudmi nalichuyetsya C n 2 n n 1 2 par tobto C n 2 podij Jmovirnist vidsutnosti dvoh lyudej z odnakovim dnem narodzhennya mozhe buti aproksimovana pripushennyam togo sho vsi ci podiyi nezalezhni i znajdena yak prostij dobutok yih jmovirnostej Korotko kazhuchi drib 364 365 mozhe buti pomnozhenij na sebe C n 2 raziv sho daye nam 364365 C n 2 displaystyle left frac 364 365 right C n 2 Yaksho ce jmovirnist sho nihto ne maye odnakovih dniv narodzhennya todi jmovirnist nayavnosti takih lyudej stanovit p n 1 364365 C n 2 displaystyle p n approx 1 left frac 364 365 right C n 2 Rozpodil Puassona Yaksho v kimnati prisutni n displaystyle n lyudej to mayemo n2 displaystyle n choose 2 par Mi viznachili uspih za nayavnist odniyeyi pari z odnakovim dnem narodzhennya imovirnist cogo 1 365 displaystyle 1 365 Otzhe n n2 p 1 365 displaystyle n n choose 2 p 1 365 Ochikuvana kilkist uspihiv stanovit m np n2 365 n n 1 730 l displaystyle mu np n choose 2 365 n left n 1 right 730 lambda Zvidsi jmovirnist togo sho nema takoyi pari ye P X 0 e m displaystyle P X 0 e mu l00 e m exp n n 1 730 displaystyle frac lambda 0 0 e mu exp frac n left n 1 right 730 Yaksho mi bazhayemo znajti kilkist lyudej dlya yakih imovirnist mensha nizh 0 5 exp n n 1 730 1 2 displaystyle exp frac n left n 1 right 730 leq 1 2 exp n n 1 730 1 2 displaystyle exp frac n left n 1 right 730 geq 1 2 n n 1 730ln 2 displaystyle n left n 1 right geq 730 ln 2 sho daye nam n 23 displaystyle n approx 23 tobto yaksho v kimnati 23 lyudej to jmovirnist sho dni narodzhennya dvoh z nih zbigayutsya dorivnyuye 0 5 Rozrahunok kilkosti osib za yakoyi jmovirnist stanovit 50 Z navedenoyi ranishe formuli dlya p n virazimo n Potim zamist p n pidstavimo 50 0 5 V rezultati otrimayemo n 12 14 2 365 ln 0 5 22 9999 displaystyle n approx frac 1 2 sqrt frac 1 4 2 cdot 365 cdot ln 0 5 22 9999 Isnuye she odin sposib ocinennya n za jmovirnosti 50 Zgidno dovedenomu vishe p n 1 p n k 1n 1 1 k365 displaystyle bar p n 1 p n prod k 1 n 1 left 1 frac k 365 right Znajdemo najmenshe n za yakogo p n gt 12 displaystyle p n gt frac 1 2 abo sho te zh same p n lt 12 displaystyle bar p n lt frac 1 2 Skoristayemosya navedenoyu vishe aproksimaciyeyu funkciyi p n displaystyle bar p n eksponencijnoyu funkciyeyu p approx n k 1n 1 e k365 e n n 1 2 365 displaystyle bar p approx n prod k 1 n 1 left e frac k 365 right e frac n n 1 2 cdot 365 Pidstavivshi p approx n displaystyle bar p approx n zamist p n displaystyle bar p n u viraz p n lt 12 displaystyle bar p n lt frac 1 2 otrimayemo e n n 1 2 365 lt 12 displaystyle e frac n n 1 2 cdot 365 lt frac 1 2 Rozv yazuyuchi vidnosno n otrimayemo n2 n gt 2 365 ln 2 displaystyle n 2 n gt 2 cdot 365 cdot ln 2 Zvidsi znajdemo n i okruglimo do cilogo n 23 Lyudi sho narodilis v odin den iz zadanoyu lyudinoyuPorivnyayemo jmovirnist p n zi jmovirnistyu togo sho v grupi z n lyudej den narodzhennya yakoyis lyudini z grupi zbizhitsya z dnem narodzhennya deyakoyi zazdalegid vibranoyi lyudini yaka ne nalezhit do grupi Cya jmovirnist dorivnyuye q n 1 365 1365 n displaystyle q n 1 left frac 365 1 365 right n Porivnyannya grafikiv funkcij p n i q n Vis abscis kilkist osib n Vis ordinat jmovirnist p n jmovirnist togo sho v grupi z n osib prinajmni u dvoh z nih dni narodzhennya zbizhatsya q n jmovirnist togo sho v grupi z n osib den narodzhennya bud yakoyi osobi z grupi zbizhitsya z dnem narodzhennya deyakoyi zazdalegid vibranoyi lyudini sho ne nalezhit grupi Pidstavlyayuchi n 23 mayemo q n 6 12 Dlya togo shob imovirnist q n perevishila 50 chislo lyudej v grupi maye buti ne menshim nizh 253 q 252 49 91 q 253 50 05 Ce chislo bilshe nizh polovina dniv u roci 365 2 182 5 tak vihodit cherez te sho v reshti chleniv grupi dni narodzhennya mozhut zbigatisya i ce zmenshuye jmovirnist q n UzagalnennyaZbig diskretnih vipadkovih velichin Opisana zadacha mozhe buti sformulovana v zagalnomu viglyadi dani vipadkovi chisla vipadkovi chisla rozpodileni rivnomirno v diapazoni vid 1 do d n kilkist vipadkovih chisel viznachiti p n d jmovirnist togo sho zbizhatsya hocha b dva chisla iz zadanih Yaksho mirkuvati tak samo yak opisano vishe mozhna otrimati zagalni rozv yazki p n d 1 k 1n 1 1 kd n d1n gt d displaystyle p n d begin cases 1 prod k 1 n 1 left 1 k over d right amp n leq d 1 amp n gt d end cases p n d 1 e n n 1 2d displaystyle p n d approx 1 e n n 1 2d q n d 1 d 1d n displaystyle q n d 1 left frac d 1 d right n Obernena zadacha dana p jmovirnist togo sho zbigayutsya hocha b dva vipadkovih chisla vidomo sho vipadkovi chisla rozpodileni rivnomirno v diapazoni vid 1 do d znajti n p d kilkist vipadkovih chisel Rozv yazok n p d 2d ln 11 p displaystyle n p d approx sqrt 2d cdot ln left 1 over 1 p right Kilka tipiv lyudej Jmovirnist zbigu dnya narodzhennya hocha b v odnogo cholovika i v odniyeyi zhinki Vishe paradoks dniv narodzhennya buv rozglyanutij dlya odnogo tipu lyudej Mozhna uzagalniti zadachu vvivshi kilka tipiv napriklad rozdilivshi lyudej na cholovikiv m i zhinok n Pidrahuyemo jmovirnist togo sho hocha b v odniyeyi zhinki i v odnogo cholovika zbigayutsya dni narodzhennya zbig dniv narodzhennya u dvoh zhinok abo u dvoh cholovikiv ne vrahovuyutsya p0 1 1dm n i 1m j 1nS2 m i S2 n j k 0i j 1 d k 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 de d 365 i S2 chisla Stirlinga drugogo rodu Cikavo sho nemaye odnoznachnoyi vidpovidi na pitannya pro velichinu n m dlya zadanoyi jmovirnosti Napriklad jmovirnist 0 5 daye yak nabir z 16 cholovikiv i 16 zhinok tak i nabir z 43 cholovikiv i 6 zhinok Blizki dni narodzhennya Inshe uzagalnennya paradoksu dniv narodzhennya polyagaye v postanovci zadachi pro te skilki potribno lyudej dlya togo shob imovirnist nayavnosti v grupi lyudej dni narodzhennya yakih vidriznyayutsya ne bilshe nizh na odin den abo na dva tri dni i tak dali perevishila 50 Pid chas rozv yazuvannya ciyeyi zadachi vikoristovuyetsya princip vklyuchen viklyuchen Rezultat znovu zh u pripushenni sho dni narodzhennya rozpodileni rivnomirno vihodit takim Maksimalna riznicya dniv narodzhennya kilkist dniv Neobhidna kilkist lyudej1 232 143 114 95 86 87 78 7 Takim chinom jmovirnist togo sho navit u grupi z 7 lyudej dni narodzhennya hocha b u dvoh z nih budut vidriznyatisya ne bilshe nizh na tizhden perevishuye 50 ZastosuvannyaParadoks dniv narodzhennya v zagalnomu viglyadi mozhna zastosuvati do hesh funkcij yaksho hesh funkciya generuye N bitove znachennya to chislo vipadkovih vhidnih danih dlya yakih hesh kodi z velikoyu jmovirnistyu dadut koliziyu tobto znajdutsya rivni hesh kodi otrimani na riznih vhidnih danih dorivnyuye ne 2N a tilki blizko 2N 2 Ce sposterezhennya vikoristovuyetsya v ataci na kriptografichni hesh funkciyi sho otrimala nazvu ataka dniv narodzhennya N Kilkist riznih vihidnih lancyuzhkiv 2N Imovirnist hocha b odniyeyi koliziyi 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 19256 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 38384 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 58512 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 U bilih komirkah vkazana kilkist osib u grupi za yakoyi koliziya vidbudetsya iz zadanoyu jmovirnistyu za analogiyeyu z paradoksom kilkist vihidnih lancyuzhkiv stanovit 365 Podibnij matematichnij aparat vikoristovuyetsya dlya ocinyuvannya rozmiru populyacij rib v ozerah Metod nazivayetsya capture recapture zloviti zloviti znovu Dijsno yaksho kozhnu spijmanu ribu poznachati ta vidpuskati to jmovirnist zloviti poznachenu ribu bude zrostati nelinijno vidpovidno do navedenogo vishe grafika zi zrostannyam kilkosti sprob Rozmir populyaciyi grubo mozhe buti ocinenij yak kvadrat chisla sprob zdijsnenih do vilovlyuvannya pershoyi poznachenoyi ribi Rozv yazok zadachi v zagalnomu viglyadi zastosovuyetsya u bagatoh rozdilah matematiki napriklad u nedeterminovanih algoritmah faktorizaciyi Tak odne z najprostishih poyasnen r metodu Pollarda analogichne poyasnennyu paradoksu dniv narodzhennya dosit mati priblizno p displaystyle sqrt p vipadkovih chisel vid 0 do n pq displaystyle n pq de p lt q displaystyle p lt q prosti shob hocha b dlya odniyeyi z par chisel z visokoyu jmovirnistyu znajshovsya gcd x y n gt 1 displaystyle gcd left x y n right gt 1 yakij i bude dilnikom chisla n Oberneni zadachiPoshuk najmenshogo chisla n za yakogo jmovirnist p n bilsha vid zadanogo chisla p Poshuk najbilshogo chisla n za yakogo jmovirnist p n mensha vid zadanogo chisla p Koristuyuchis formuloyu navedenoyu vishe otrimuyemo n p 365 2 365 ln 11 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 008200 05 0 32029 365 6 11916 6 0 04046 7 0 056240 1 0 45904 365 8 77002 8 0 07434 9 0 094620 2 0 66805 365 12 76302 12 0 16702 13 0 194410 3 0 84460 365 16 13607 16 0 28360 17 0 315010 5 1 17741 365 22 49439 22 0 47570 23 0 507300 7 1 55176 365 29 64625 29 0 68097 30 0 706320 8 1 79412 365 34 27666 34 0 79532 35 0 814380 9 2 14597 365 40 99862 40 0 89123 41 0 903150 95 2 44775 365 46 76414 46 0 94825 47 0 954770 99 3 03485 365 57 98081 57 0 99012 58 0 99166Najkrasha poziciya Nehaj u kimnati znahodyatsya n 1 osib i yihni dni narodzhennya rizni Nehaj g n jmovirnist togo sho den narodzhennya lyudini yaka zajshla zbigayetsya z dnem narodzhennya kogos iz prisutnih u kimnati Potribno znajti znachennya n za yakogo znachennya funkciyi g n maksimalne Rozv yazuvannya zvoditsya do znahodzhennya maksimalnogo znachennya virazu p n p n 1 Vikoristovuyuchi navedenu vishe formulu dlya p n otrimayemo n 20 Serednye chislo lyudej Rozglyanemo inshu zadachu Skilki v serednomu potribno lyudej dlya togo shob hocha b u dvoh z nih zbiglisya dni narodzhennya Cya problema mala vidnoshennya do algoritmiv heshuvannya i bula doslidzhena Donaldom Knutom Viyavlyayetsya sho vipadkova velichina yaka nas cikavit maye matematichne spodivannya rivne n 1 Q M displaystyle overline n 1 Q M de Q M k 1MM M k Mk displaystyle Q M sum k 1 M frac M M k M k Funkciya Q M 1 M 1M M 1 M 2 M2 M 1 M 2 1MM 1 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 bula doslidzhena Ramanudzhanom Vin zhe otrimav dlya ciyeyi funkciyi take asimptotichne rozkladannya Q M pM2 13 112p2M 4135M displaystyle Q M sim sqrt frac pi M 2 frac 1 3 frac 1 12 sqrt frac pi 2M frac 4 135M cdots Pri M 365 serednya kilkist lyudej dorivnyuye n 1 Q M 24 61658 displaystyle overline n 1 Q M approx 24 61658 Ce chislo trohi bilshe nizh chislo lyudej sho zabezpechuyut imovirnist 50 Yak ne divno neobhidne chislo lyudej dorivnyuye M 1 366 u 365 lyudej dni narodzhennya mozhut rozpodilitisya po kozhnomu z 365 dniv roku bez zbigiv hocha v serednomu potribno lish 25 PrimitkiHocha ce j ne paradoks u sensi otrimannya logichnoyi superechnosti ale vin nazvanij tak cherez te sho matematichnij rozv yazok superechit nayivnij intuyiciyi bilshist lyudej ocinyuyut shans menshe nizh u 50 Naspravdi dni narodzhennya nerivnomirno rozpodileni vprodovzh roku ale dlya ciyeyi zadachi vvazhayemo rozpodil rivnomirnim Div takozhZadacha pro listiPosilannyaParadoksi teoriyi jmovirnostej Porivnyalnij oglyad algoritmiv PGP Paradoks dniv narodzhennya i stijkist kriptografiyi LiteraturaJohn G Kemeny J Laurie Snell Gerald Thompson Introduction to Finite Mathematics The first edition 1 e izdanie 1957 angl Kemeni Dzh Snell Dzh Tompson Dzh Vvedenie v konechnuyu matematiku angl Izdatelstvo inostrannoj literatury 1963 488 s ros Sekej G Paradoksy v teorii veroyatnostej i matematicheskoj statistike RHD 2003 ISBN 5 93972 150 8 ros Kozlov M V Elementy teorii veroyatnostej v primerah i zadachah MGU 1990 ISBN 5 211 00312 8 ros Shiryaev A N Veroyatnost 1 MCNMO 2007 ISBN 978 5 94057 036 3 ros Goldberg S A Direct Attack on a Birthday Problem angl Mathematical Mathematics Magazine traven 1976 No 49 S 130 132 angl Mosteller F Understanding the Birthday Problem angl The Mathematics Teacher traven 1962 S 322 325 angl Eurobirthdays 2012 goda Praktichnij priklad angl