Pull to refresh

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

Reading time 2 min
Views 39K
Многим известен парадокс дней рождения: в группе из 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 через вероятности событий Bm:

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

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

Равновероятными элементарными исходами (событиями) будут являться наборы пар: {(i, di); i=1, ..., k}, каждая из которых означает, что человек номер i имеет в качестве дня рождения di.
Количество всех элементарных исходов определяется, исходя из того, что у каждого участника есть n вариантов дня рождения:
NBm = nk.

Количество элементарных исходов, когда выполнено событие Bm считается несколько сложнее:

Bm = Cnm Cn-mk-2m k! / 2m.

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

Поэтому

P(Bm) = NBm / N = Cnm Cn-mk-2m k! / (2m nk).
P(B) = k! (Cn0 Cn-0k-0 / 20 + Cn1 Cn-1k-2 / 21 + … + Cnm Cn-mk-2m / 2m + … + Cn[k/2] Cn-[k/2]k-2[k/2] / 2[k/2]) / nk .

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

P(A) = 1 — P(B) = 1 — k! (Cn0 Cn-0k-0 / 20 + Cn1 Cn-1k-2 / 21 + … + Cnm Cn-mk-2m / 2m + … + Cn[k/2] Cn-[k/2]k-2[k/2] / 2[k/2]) / nk .

Моя программа на Java выдала следующие значения этой вероятности в зависимости от k:
k P(A)
2 0
3 7.506E-6
5 7.475E-5
10 8.877E-4
20 0.00824
40 0.0669
60 0.207
70 0.306
80 0.418
87 0.499
88 0.511
100 0.646
110 0.746
120 0.828
150 0.965
200 0.999512
250 0.999999460
Итак, нужно как минимум 88 человек, чтобы вероятность тройного совпадения превышала 1/2.
Tags:
Hubs:
+6
Comments 19
Comments Comments 19

Articles