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