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

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

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

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

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

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

Обчислення показують, що якщо збирається щонайменше 6 чоловік, то $p_n\ge \frac{1}{e}\ge 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⟶\mathrm{\infty }$, то ця ймовірність прямує до $e^{-\lambda }$. Узагальнюючи цей результат, отримаємо: ймовірність того, що конкретна людина отримає рівно $k$ подарунків, прямує до $\frac{{\lambda }^k{e}^{-1}}{k!}$ при $n⟶\mathrm{\infty }$. Ми отримали добре відомий розподіл Пуассона. Повертаючись до “парадоксу розподілу подарунків”, отримаємо, що кількість людей, яким дістануться їх власні подарунки, також описується законом Пуассона з параметром $\lambda$.

Примітки

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