Парадокс роздачі подарунків

Парадокс роздачі подарунків — один з найвідоміших парадоксів в теорії ймовірності. Вперше був розглянутий в книзі Ремона де Монмора, опублікованій в Парижі в 1708 р.

Формулювання парадоксу

Декілька чоловік вирішили зробити один одному подарунки таким чином: кожен з них приносить подарунок, подарунки складаються разом, змішуються і випадково розподіляються серед учасників. Парадоксально, але ймовірність того, що ніхто не отримає свій власний подарунок, менша ${\frac {1}{2}}$ (крім випадку, коли учасників двоє, і ця ймовірність дорівнює ${\frac {1}{2}}$).

Пояснення парадоксу

Розглянемо компанію з $n$ чоловік, тоді кількість подарунків теж рівна n. Подарунки можуть бути розподіленні n! різними способами (це спільне число випадків). Число випадків, при яких ніхто не отримає свій подарунок дорівнює ${\binom {n}{0}}n!-{\binom {n}{1}}(n-1)!+{\binom {n}{2}}(n-2)!-{\binom {n}{3}}(n-3)!+\ldots (-1)^{n}0!$ тоді, відношення числа позитивних випадків до загального числа випадків обчислюється за формулою $p_{n}=1/2!-1/3!+\ldots +(-1)^{n}/n!$. Тоді $p_{n}$ справді менше ${\frac {1}{2}}$ при $n>2$.

Обчислення показують, що якщо збирається щонайменше 6 чоловік, то $p_{n}\geq {\frac {1}{e}}\geq 0.3679$ з точністю до чотирьох знаків після крапки. Ймовірність конкретного співпадання дорівнює ${\frac {1}{n}}$ і прямує до $0$ при збільшенні $n$.

Зауваження

Розглянемо дещо іншу проблему. Нехай подарунки розподіляються так, що кожен чоловік може отримати будь-який подарунок з однаковою ймовірністю незалежно від розподілу інших подарунків. Нехай подія $A$ полягає в тому, що конкретний чоловік не отримає подарунку. Тоді ймовірність $A$ дорівнює $p_{n}={\frac {(n-1)^{n}}{n^{n}}}=(1-{\frac {1}{n}})^{n}$ і прямує так само до $e^{-1}$. Розглянемо тепер випадок, коли кількість людей $n$ не обов'язково збігається з кількістю подарунків $m$. В цьому випадку шукана ймовірність дорівнює $p_{n}={\frac {(n-1)^{m}}{n^{m}}}=(1-{\frac {1}{n}})^{m}$.

Якщо ${\frac {m}{n}}$ прямує до $\lambda$, при $n\longrightarrow \infty$, то ця ймовірність прямує до $e^{-\lambda }$. Узагальнюючи цей результат, отримаємо: ймовірність того, що конкретна людина отримає рівно $k$ подарунків, прямує до ${\frac {\lambda ^{k}e^{-1}}{k!}}$ при $n\longrightarrow \infty$. Ми отримали добре відомий розподіл Пуассона. Повертаючись до “парадоксу розподілу подарунків”, отримаємо, що кількість людей, яким дістануться їх власні подарунки, також описується законом Пуассона з параметром $\lambda$.

Примітки

1. Секей Г. Парадоксы теории вероятностей и математической статистики / Г. Секей. — М.: Наука, 1989. — 240с.[1]
2. www.unicyb.kiev.ua/Library/OKZ/Spetskurs.doc