Парадокс дней рождения для трёх человек

Многим известен парадокс дней рождения: в группе из 23-х случайно отобранных людей вероятность того, что хотя бы двое из них имеют совпадающий день рождения, превышает 1/2.

Проблема, которую я буду рассматривать, сформулирована в виде упражнения в книге Алгоритмы: построение и анализ:

«Сколько нужно взять человек, чтобы с той же вероятностью 1/2 встретить хотя бы трёх с совпадающим днём рождения.»

Сразу отметим, что дни рождения участников опыта, как события, считаются совместно независимыми и равновероятными.

Введём некоторые обозначения:

n = 365 (високосный год тоже опускаем).
k — количество участников. Считаем k <= 2n, иначе тройное совпадение случится с вероятностью 1.

А — событие, состоящее в том, что в группе имеются три или более человека с одним и тем же днём рождения.
B = (not А) — событие, состоящее в том, что никакие три участника не имеют одинаковый день рождения.

Событие B будет выполнено тогда и только тогда, когда на некоторое количество m различных дней в году будет приходиться ровно по два участника, а на другие (k — 2m) дней будет приходиться ровно по одному человеку:

Понятно, что m может изменяться в зависимости от конкретной группы людей от 0 до [k / 2].
Обозначим B_m — событие, состоящее в том, что на m различных дней в году приходится ровно по два участника, а на другие (k — 2m) дней — по одному.
Особенность совокупности событий {B_m, m=0, …, [k/2]} в том, что они несовместны и

B = B₀ ∪ B₁ ∪ … ∪ B_[k/2].

Поэтому вероятность события B равна:

P(B) = P(B₀) + P(B₁) + … + P(B_[k/2]).

Поэтому мы будем искать вероятность событий B_m.

Таблица, представленная выше, описывает один из элементарных исходов (событий), когда выполнено событие B_m. Количество всех исходов, когда выполнено событие B_m, можно посчитать используя основные правила комбинаторики:

N_Bm = C_n^m C_n—m^k-2m.

Здесь мы сначала определяем количество способов, которыми могут быть выбраны m дней для двойных совпадений. Затем из оставшихся дней выбираем k — 2m, на которые приходится по одному человеку.

Количество всех элементарных исходов определяется как количество сочетаний с повторениями:

N = C_n+k-1^k.

Поэтому

P(B_m) = N_Bm / N = C_n^m C_n-m^k-2m / C_n+k-1^k.
P(B) = (C_n⁰ C_n^k + C_n¹ C_n-1^k-2 + … + C_n^m C_n—m^k-2m + … + C_n^[k/2] C_n-[k/2]^k-2[k/2]) / C_n+k-1^k .

Искомая вероятность будет равна:

P(A) = 1 — P(B) = 1 — (C_n⁰ C_n^k + C_n¹ C_n-1^k-2 + … + C_n^m C_n—m^k-2m + … + C_n^[k/2] C_n-[k/2]^k-2[k/2]) / C_n+k-1^k .

Моя программа на Java выдала следующие значения этой вероятности в зависимости от k:

Итак, достаточно 52 человека, чтобы гарантировать тройное совпадение с вероятностью 1/2.

ссылка на оригинал статьи http://habrahabr.ru/post/256301/