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

от автора

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

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

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


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

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

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

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

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

Дни d1 d2 dk — 2m dk — 2m+1 dk — 2m+2 dkm dkm + 1 dn
Количество человек 1 1 1 2 2 2 0 0

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

B = B0B1 ∪ … ∪ B[k/2].

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

P(B) = P(B0) + P(B1) + … + P(B[k/2]).

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

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

NBm = Cnm Cnmk-2m.

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

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

N = Cn+k-1k.

Поэтому

P(Bm) = NBm / N = Cnm Cn-mk-2m / Cn+k-1k.
P(B) = (Cn0 Cnk + Cn1 Cn-1k-2 + … + Cnm Cnmk-2m + … + Cn[k/2] Cn-[k/2]k-2[k/2]) / Cn+k-1k .

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

P(A) = 1 — P(B) = 1 — (Cn0 Cnk + Cn1 Cn-1k-2 + … + Cnm Cnmk-2m + … + Cn[k/2] Cn-[k/2]k-2[k/2]) / Cn+k-1k .

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

k P(A)
2 0
3 0.0000447
5 0.000439
10 0.00506
20 0.0438
30 0.139
40 0.290
50 0.473
51 0.492
52 0.511
60 0.654
70 0.801
80 0.901
90 0.958
100 0.985
150 0.99999268
200 0.9999999999701

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

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


Комментарии

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *