[Из песочницы] Парадокс дней рождения для трёх человек
Многим известен парадокс дней рождения: в группе из 23-х случайно отобранных людей вероятность того, что хотя бы двое из них имеют совпадающий день рождения, превышает ½.Проблема, которую я буду рассматривать, сформулирована в виде упражнения в книге Алгоритмы: построение и анализ:
«Сколько нужно взять человек, чтобы с той же вероятностью ½ встретить хотя бы трёх с совпадающим днём рождения.»
Сразу отметим, что дни рождения участников опыта, как события, считаются совместно независимыми и равновероятными.Введём некоторые обозначения:
n = 365 (високосный год тоже опускаем).k — количество участников. Считаем k <= 2n, иначе тройное совпадение случится с вероятностью 1.
А — событие, состоящее в том, что в группе имеются три или более человека с одним и тем же днём рождения.B = (not А) — событие, состоящее в том, что никакие три участника не имеют одинаковый день рождения.
Событие B будет выполнено тогда и только тогда, когда на некоторое количество m различных дней в году будет приходиться ровно по два участника, а на другие (k — 2m) дней будет приходиться ровно по одному человеку:
Дни d1 d2 … dk — 2m dk — 2m+1 dk — 2m+2 … dk — m dk — m + 1 … dn Количество человек 1 1 … 1 2 2 … 2 0 … 0 Понятно, что m может изменяться в зависимости от конкретной группы людей от 0 до [k / 2].Обозначим Bm — событие, состоящее в том, что на m различных дней в году приходится ровно по два участника, а на другие (k — 2m) дней — по одному.Особенность совокупности событий {Bm, m=0, …, [k/2]} в том, что они несовместны иB = B0 ∪ B1 ∪… ∪ B[k/2].
Поэтому вероятность события B равна:
P (B) = P (B0) + P (B1) + … + P (B[k/2]).
Поэтому мы будем искать вероятность событий Bm.
Таблица, представленная выше, описывает один из элементарных исходов (событий), когда выполнено событие Bm. Количество всех исходов, когда выполнено событие Bm, можно посчитать используя основные правила комбинаторики:
NBm = Cnm Cn-mk-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 Cn-mk-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 Cn-mk-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 человека, чтобы гарантировать тройное совпадение с вероятностью ½.
