Перегляд вихідного коду сторінки Парадокс днів народження

У [[Теорія ймовірностей|теорії ймовірностей]] '''парадокс днів народження'''<ref>Хоча це й не [[парадокс]] у сенсі отримання [[Логіка|логічної]] суперечності, але він названий так через те, що математичний розв'язок суперечить наївній [[Інтуїція|інтуїції]]: більшість людей оцінюють шанс менше ніж у 50&nbsp;%.</ref> оцінює ймовірність того, що у випадково вибраній групі людей збігатимуться дні народження в якоїсь пари. В групах кількістю не менших 23 випадково вибраних людей, ймовірність збігу днів народження в якоїсь пари становить більше 50&nbsp;%. Такий результат суперечить інтуїтивній уяві більшості.

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

[[Файл:Birthday Paradox ua.svg|thumb|450px|На графіку показана приблизна ймовірність того, що щонайменше двоє людей будуть мати день народження в один день.]]

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

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

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

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

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

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

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

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

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

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

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

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

{{NumBlk|:|<math>P(A')=\frac{365}{365}\times\frac{364}{365}\times\frac{363}{365}\times\frac{362}{365}\times\cdots\times\frac{343}{365}</math>|{{EquationRef|1}}}}

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

{{NumBlk|:|<math>P(A')=\left(\frac{1}{365}\right)^{23}\times(365\times364\times363\times\cdots\times343)</math>|{{EquationRef|2}}}}

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

<math>365!=365\times364\times363\times\cdots\times343\times342 !</math>

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

{{NumBlk|:|<math>\frac{365!}{342!}=365\times364\times363\times\cdots\times343</math>|{{EquationRef|3}}}}

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

{{NumBlk|:|<math>P(A')=\frac{365!}{342!}\times\left(\frac{1}{365}\right)^{23}</math>|{{EquationRef|4}}}}

Обчислення рівняння ({{EquationNote|4}}) нам дає <math>P(A')=0.49270276</math>.

Відповідно, <math>P(A)=1-0.49270276=0.507297 (50.7297 \%)</math>

Цей процес може бути узагальнений для групи з <math>n</math> людей, де <math>p(n)</math> ймовірність збігу днів народження у принаймні двох людей з <math>n</math>. Легше спочатку вирахувати ймовірність <math>\bar p(n)</math> того, що всі <math>n</math> днів народження ''різні''. Згідно з [[Принцип Діріхле|принципом Діріхле]], <math>\bar p(n)=0</math> коли <math>n>365</math>. Коли <math>n\leq365</math>:

: <math>\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)!}.</math>

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

[[Випадкова подія|Ймовірність]] того, що принаймні двоє людей з <math>n</math> мають однаковий день народження, комплементарна до ймовірності, що всі дні народження різні. Таким чином,

: <math> p(n) = 1 - \bar p(n). \, </math>

[[Файл:Birthdaymatch ua.svg|thumb|450px|Приблизна ймовірність відсутності двох людей з однаковим днем народження в групі з n осіб.]]

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

{| class="wikitable"
!''n''!!''p''(''n'')
|-
|10 || 11.7&nbsp;%
|-
|20 || 41.1&nbsp;%
|-
|23 || 50.7&nbsp;%
|-
|30 || 70.6&nbsp;%
|-
|50 || 97.0&nbsp;%
|-
|57 || 99.0&nbsp;%
|-
|100 || 99.99997&nbsp;%
|-
|200 || 99.9999999999999999999999999998&nbsp;%
|-
|300 || (100 − (6×10<sup>−80</sup>))%
|-
|350 || (100 − (3×10<sup>−129</sup>))%
|-
|366 || 100&nbsp;%
|}

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

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

: <math> e^x = 1 + x + \frac{x^2}{2!}+\cdots </math>

[[Файл:Birthday paradox approximation.svg|thumb|right|300px|Графік показує точність [[Апроксимація|наближення]] <math>1-e^{-n^2/(2 \times 365)}</math>]]

отримаємо апроксимацію першого порядку для <math>e^x</math> при <math>x \ll 1</math>:

: <math> e^x \approx 1 + x.\ </math>

Якщо <math>x = -a/365,</math> то

: <math>e^{-a/365} \approx 1 - \frac{a}{365}.</math>

Перший вираз отриманий для ''<u style="text-decoration:overline">p</u>''(''n'') може бути апроксимований як

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

Відповідно

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

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

: <math>p(n)\approx 1-e^{- n^2/(2 \times 365)},\,</math>

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

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

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

: <math>\left(\frac{364}{365}\right)^{C(n,2)}.</math>

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

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

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

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

: <math>n = {n \choose 2} ,\  p = 1/365</math>

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

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

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

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

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

: <math>\exp \{ \frac {-n \left(n - 1\right)}{730} \} \le 1/2 </math>

: <math>\exp \{ \frac {n \left(n - 1\right)}{730} \} \ge 1/2 </math>

: <math>n \left(n - 1\right) \ge 730 \ln(2)  </math>

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

== Розрахунок кількості осіб, за якої ймовірність становить 50&nbsp;% ==
З наведеної раніше формули для {{Nobr|''p''(''n'')}} виразимо ''n''. Потім замість {{Nobr|''p''(''n'')}} підставимо {{Nobr|50 %}} (0,5). В результаті отримаємо:

: <math> n \approx \frac{1}{2} + \sqrt{ \frac{1}{4} - 2 \cdot 365 \cdot \ln(0,5) } = 22,9999. </math>

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

: <math> \bar p(n) = 1 - p(n) = \prod_{ k=1 }^{ n-1 } \left( 1 - { \frac{k}{365} } \right). </math>

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

: <math> p(n) > \frac{1}{2} </math>

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

: <math> \bar p(n) < \frac{1}{2}. </math>

Скористаємося наведеною [[Парадокс днів народження|вище]] [[Апроксимація|апроксимацією]] {{Nobr|функції <math> \bar p(n) </math>}} [[Показникова функція|експоненційною функцією]]:

: <math> \bar p_{approx}(n) = \prod_{ k=1 }^{ n-1 } \left( e^{ \frac{-k}{365} } \right) = e^{ \frac{ -n(n-1) }{ 2 \cdot 365 } }. </math>

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

: <math> e^{ \frac{ -n(n-1) }{ 2 \cdot 365 } } < \frac{1}{2}. </math>

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

: <math> n^2 - n > 2 \cdot 365 \cdot \ln 2 \,\!. </math>

Звідси знайдемо ''n'' і [[Округлення|округлимо]] до [[Цілі числа|цілого]] :

: {{Nobr|1=''n'' = 23}}.

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

: <math> q(n) = 1 - \left( \frac{ 365-1 }{365} \right)^n. </math>

[[Файл:Birthday_paradox.svg|праворуч|міні|290x290пкс| Порівняння графіків функцій {{Nobr|''p''(''n'')}} і {{Nobr|''q''(''n'')}}

* Вісь [[Абсциса|абсцис]]: кількість осіб ''n.''
* Вісь [[Ордината|ординат]]: ймовірність.
* {{Nobr|''p''(''n'')}}&nbsp;— ймовірність того, що в групі з ''n'' осіб принаймні у двох з них дні народження збіжаться.
* {{Nobr|''q''(''n'')}}&nbsp;— ймовірність того, що в групі з ''n'' осіб день народження будь-якої особи з групи збіжиться з днем народження деякої заздалегідь вибраної людини, що не належить групі.
]]
Підставляючи {{Nobr|1=''n'' = 23}}, маємо {{Nobr|''q''(''n'') ≈ 6,12 %}}. Для того, щоб імовірність {{Nobr|''q''(''n'')}} перевищила {{Nobr|50 %}}, число людей в групі має бути не меншим, ніж 253 ({{Nobr|''q''(252) ≈ 49,91 %}}; {{Nobr|''q''(253) ≈ 50,05 %}}). Це число більше, ніж половина днів у році ({{Nobr|1=365/2 = 182,5}}); так виходить через те, що в решти членів групи дні народження можуть збігатися, і це зменшує ймовірність {{Nobr|''q''(''n'')}}.

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

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

* дані випадкові числа;
* випадкові числа [[Дискретний рівномірний розподіл|розподілені рівномірно]] в діапазоні від 1 до ''d;''
* ''n''&nbsp;— кількість випадкових чисел;
* визначити {{Nobr|''p''( ''n'' ; ''d'' )}}&nbsp;— [[Імовірність|ймовірність]] того, що збіжаться хоча б два числа із заданих.

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

: <math> p(n;d) = \begin{cases} 1 - \prod_{ k=1 }^{ n-1 } \left( 1 - { k \over d } \right) & n \le d \\ 1 & n > d \end{cases} ; </math>
: <math> p(n;d) \approx 1 - e^{ -( n(n-1) )/2d } ; </math>
: <math> q(n;d) = 1 - \left( \frac{ d-1 }{d} \right)^n. </math>

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

* дана ''p''&nbsp;— ймовірність того, що збігаються хоча б два випадкових числа;
* відомо, що випадкові числа [[Дискретний рівномірний розподіл|розподілені рівномірно]] в діапазоні від 1 до ''d;''
* знайти {{Nobr|''n''(''p'';''d'')}}&nbsp;— кількість випадкових чисел.

Розв'язок:

: <math> n(p;d) \approx \sqrt{ 2d \cdot \ln \left( { 1 \over 1 - p } \right) }. </math>

=== Кілька типів людей ===
[[Файл:2d_birthday.png|міні|Ймовірність збігу дня народження хоча б в одного чоловіка і в однієї жінки]]
Вище парадокс днів народження був розглянутий для одного «типу» людей. Можна узагальнити задачу, ввівши кілька «типів», наприклад, розділивши людей на чоловіків ''(m)'' і жінок ''(n).'' Підрахуємо ймовірність того, що хоча б в однієї жінки і в одного чоловіка збігаються дні народження (збіг днів народження у двох жінок або у двох чоловіків не враховуються):

: <math> 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 ) , </math>

де {{Nobr|1=''d'' = 365}} и ''S''<sub>2</sub>()&nbsp;— [[числа Стірлінга другого роду]]. Цікаво, що немає однозначної відповіді на питання про величину {{Nobr|''n''+''m''}} для заданої ймовірності. Наприклад, ймовірність 0,5 дає як набір з 16 чоловіків і 16 жінок, так і набір з 43 чоловіків і 6 жінок.

=== Близькі дні народження ===
Інше узагальнення парадоксу днів народження полягає в постановці задачі про те, скільки потрібно людей для того, щоб імовірність наявності в групі людей, дні народження яких відрізняються не більше ніж на один день (або на два, три дні і так далі), перевищила 50&nbsp;%. Під час розв'язування цієї задачі використовується [[Формула включень-виключень|принцип включень-виключень]]. Результат (знову ж у припущенні, що дні народження [[Дискретний рівномірний розподіл|розподілені рівномірно]]) виходить таким:
{| class="wikitable"
! Максимальна різниця днів народження, кількість днів
! Необхідна кількість людей
|-
| 1
| 23
|-
| 2
| 14
|-
| 3
| 11
|-
| 4
| 9
|-
| 5
| 8
|-
| 6
| 8
|-
| 7
| 7
|-
| 8
| 7
|}
Таким чином, ймовірність того, що навіть у групі з 7 людей дні народження хоча б у двох з них будуть відрізнятися не більше ніж на тиждень, перевищує {{Nobr|50 %}}.

== Застосування ==
Парадокс днів народження в загальному вигляді можна застосувати до [[Хеш-функція|хеш-функцій]]: якщо хеш-функція генерує ''N''-бітове значення, то число випадкових вхідних даних, для яких [[Хеш-сума|хеш-коди]] з великою ймовірністю дадуть [[Колізія геш-функції|колізію]] (тобто знайдуться рівні хеш-коди, отримані на різних вхідних даних), дорівнює не 2<sup>''N,''</sup> а тільки близько 2<sup>''N''/2.</sup> Це спостереження використовується в атаці на криптографічні хеш-функції, що отримала назву «<nowiki/>[[Атака «днів народження»|атака „днів народження“]]<nowiki/>».
{| class="wikitable"
! rowspan="2" | N
! rowspan="2" | Кількість різних вихідних ланцюжків (2<sup>N</sup>)
! colspan="10" | Імовірність хоча б однієї [[Колізія геш-функції|колізії]] ''(p)''
|-
! 10 <sup>−18</sup>
! 10 <sup>−15</sup>
! 10 <sup>−12</sup>
! 10 <sup>−9</sup>
! 10 <sup>−6</sup>
! 0,1&nbsp;%
! 1&nbsp;%
! 25&nbsp;%
! 50&nbsp;%
! 75&nbsp;%
|- align="center"
| bgcolor="lightgrey" | 32
| bgcolor="lightgrey" | 4,3 × 10 <sup>9</sup>
| 2
| 2
| 2
| 2.9
| 93
| 2.9 × 10³
| 9.3 × 10³
| 5.0 × 10⁴
| 7.7 × 10⁴
| 1.1 × 10⁵
|- align="center"
| bgcolor="lightgrey" | 64
| bgcolor="lightgrey" | 1,8 × 10 <sup>19</sup>
| 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⁹
|- align="center"
| bgcolor="lightgrey" | 128
| bgcolor="lightgrey" | 3,4 × 10 <sup>38</sup>
| 2.6 × 10 <sup>10</sup>
| 8.2 × 10 <sup>11</sup>
| 2.6 × 10 <sup>13</sup>
| 8.2 × 10 <sup>14</sup>
| 2.6 × 10 <sup>16</sup>
| 8.3 × 10 <sup>17</sup>
| 2.6 × 10 <sup>18</sup>
| 1.4 × 10 <sup>19</sup>
| 2.2 × 10 <sup>19</sup>
| 3.1 × 10 <sup>19</sup>
|- align="center"
| bgcolor="lightgrey" | 256
| bgcolor="lightgrey" | 1,2 × 10 <sup>77</sup>
| 4.8 × 10 <sup>29</sup>
| 1.5 × 10 <sup>31</sup>
| 4.8 × 10 <sup>32</sup>
| 1.5 × 10 <sup>34</sup>
| 4.8 × 10 <sup>35</sup>
| 1.5 × 10 <sup>37</sup>
| 4.8 × 10 <sup>37</sup>
| 2.6 × 10 <sup>38</sup>
| 4.0 × 10 <sup>38</sup>
| 5.7 × 10 <sup>38</sup>
|- align="center"
| bgcolor="lightgrey" | 384
| bgcolor="lightgrey" | 3,9 × 10 <sup>115</sup>
| 8.9 × 10 <sup>48</sup>
| 2.8 × 10 <sup>50</sup>
| 8.9 × 10 <sup>51</sup>
| 2.8 × 10 <sup>53</sup>
| 8.9 × 10 <sup>54</sup>
| 2.8 × 10 <sup>56</sup>
| 8.9 × 10 <sup>56</sup>
| 4.8 × 10 <sup>57</sup>
| 7.4 × 10 <sup>57</sup>
| 1.0 × 10 <sup>58</sup>
|- align="center"
| bgcolor="lightgrey" | 512
| bgcolor="lightgrey" | 1,3 × 10 <sup>154</sup>
| 1.6 × 10 <sup>68</sup>
| 5.2 × 10 <sup>69</sup>
| 1.6 × 10 <sup>71</sup>
| 5.2 × 10 <sup>72</sup>
| 1.6 × 10 <sup>74</sup>
| 5.2 × 10 <sup>75</sup>
| 1.6 × 10 <sup>76</sup>
| 8.8 × 10 <sup>76</sup>
| 1.4 × 10 <sup>77</sup>
| 1.9 × 10 <sup>77</sup>
|}
У білих комірках вказана кількість осіб у групі, за якої [[Колізія геш-функції|колізія]] відбудеться із заданою [[Імовірність|ймовірністю]] (за аналогією з парадоксом кількість вихідних ланцюжків становить 365).

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

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

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

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

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

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

: <math> n(p;365) \approx \sqrt{ 2 \cdot 365 \cdot \ln \left( { 1 \over 1 - p } \right) }. </math>

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

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

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

: {{Nobr|''p''(''n'') - ''p''(''n''-1)}}.

Використовуючи наведену [[Парадокс днів народження|вище]] формулу для {{Nobr|''p''(''n'')}} отримаємо {{Nobr|1=''n'' = 20}}

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

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

: <math> \overline{n} \, = \, 1 + Q(M) , </math>

де

: <math> Q(M) = \sum_{ k=1 }^{M} \frac{ M! }{ (M-k)! M^k }. </math>

Функція

: <math> 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} }</math>

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

: <math> Q(M) \sim \sqrt{ \frac{ \pi M }{2} } - \frac{1}{3} + \frac{1}{12} \sqrt{ \frac{\pi}{2M} } - \frac{4}{ 135 M } + \cdots. </math>

При {{Nobr|1=''M'' = 365}} середня кількість людей дорівнює

: <math> \overline{n} \, = \, 1 + Q(M) \approx 24.61658. </math>

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

== Примітки ==
{{reflist}}

== Див. також ==
* [[Безлад (перестановка)#Задача про листи|Задача про листи]]

== Посилання ==
* [http://stepanov.lk.net/gardner/hex/hex05.html Парадокси теорії ймовірностей].
* [http://www.pgpru.com/%C1%E8%E1%EB%E8%EE%F2%E5%EA%E0/%D1%F2%E0%F2%FC%E8/%D1%F0%E0%E2%ED%E8%F2%E5%EB%FC%ED%FB%E9%CE%E1%E7%EE%F0%C0%EB%E3%EE%F0%E8%F2%EC%EE%E2PGP?show_comments=1 Порівняльний огляд алгоритмів PGP. Парадокс «днів народження» і стійкість криптографії].

== Література ==
* {{книга-ру
| автор = John G. Kemeny, J. Laurie Snell, Gerald Thompson
| заглавие = Introduction to Finite Mathematics. The first edition
| издание = 1‑е издание
| год = [[1957]]
}} {{ref-en}}

* {{книга-ру
| автор = Кемени Дж., Снелл Дж., Томпсон Дж.
| заглавие = Введение в [[Дискретна математика|конечную математику]]
| издательство = Издательство иностранной литературы
| год = [[1963]]
| страниц = 488
| язык = en
}} {{ref-ru|}}

* {{книга-ру
| автор = Секей Г.
| заглавие = Парадоксы в теории вероятностей и математической статистике
| издательство = РХД
| год = [[2003]]
| isbn = 5-93972-150-8
}} {{ref-ru}}

* {{книга-ру
| автор = Козлов М. В.
| заглавие = Элементы теории вероятностей в примерах и задачах
| издательство = МГУ
| год = [[1990]]
| isbn = 5-211-00312-8
}} {{ref-ru}}

* {{книга-ру
| автор = Ширяев А. Н.
| заглавие = Вероятность-1
| издательство = МЦНМО
| год = [[2007]]
| isbn = 978-5-94057-036-3
}}{{ref-ru}}

* {{статья
| автор = Goldberg S.
| заглавие = A Direct Attack on a Birthday Problem
| язык = en
| издание = Mathematical Mathematics Magazine
| год = травень [[1976]]
| выпуск = 49
| страницы = 130—132
}}{{ref-en}}

* {{статья
| автор = Mosteller F.
| заглавие = Understanding the Birthday Problem
| язык = en
| издание = The Mathematics Teacher
| год = травень [[1962]]
| страницы = 322—325
}}{{ref-en}}

* [http://www.matifutbol.com/docs/units/eurobirthdays.html Eurobirthdays 2012 года Практичний приклад]{{ref-en}}

{{Парадокс}}

[[Категорія:Ймовірнісні парадокси|День народження]]
[[Категорія:Ймовірнісні проблеми|Днів народження]]
[[Категорія:Прикладна ймовірність]]
[[Категорія:Математичні задачі]]
[[Категорія:Дні народження]]