Проблема, которую я буду рассматривать, сформулирована в виде упражнения в книге Алгоритмы: построение и анализ:
«Сколько нужно взять человек, чтобы с той же вероятностью 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 |
Комментарии (19)
cher11
21.04.2015 21:27+1В вашей таблице еще один интересный (на мой взгляд) случай — группа из 150 человек, в которой вероятность уже очень близка к 100%.
Хотя на первый взгляд кажется, что там, опять же, примерно 1/2 и выйдет.
Imp5
21.04.2015 22:27-1
Mr_Floppy
21.04.2015 23:05+430 февраля? А 30 и 31 мая никто не родился?
Hacker13ua
21.04.2015 23:21+1похоже, что таблица должна начинаться с октября
Mrrl
21.04.2015 23:50+4Они просто взяли таблицу частот дней рождения и отняли 9 месяцев. Из 30 ноября получилось 30 февраля, а 30 и 31 мая не получились вообще. Ну, и провал на 4 октября: ведь в день Независимости США никто не рождается, роды стараются перенести на пораньше.
sielover
22.04.2015 00:36+2Не претендуя на истинность в последней инстанции
Попробовал прогнать случайным перебором.
Для 2 дней рождения вероятность 0.5 получается в районе 22-24, т.е. близко к математике, а вот для 3 дней рождения — только для 86-88.
P.S. Копнул чуть глубже. Оригинальная статья Anirban DasGupta, The matching, birthday and the strong birthday problem: a contemporary review, Journal of Statistical Planning and Inference 130 (2005), 377-389 тоже говорит 88.strikerdimabel Автор
22.04.2015 01:07Согласен, есть ошибка. Постараюсь с этим разобраться.
strikerdimabel Автор
22.04.2015 01:59Ошибка оказалась в том, что выбранные мною элементарные события не равновероятны.
В качестве элементарных событий я брал наборы частот длиной 365 чисел:
(1,1,2...,0,0)
(2,4,2,...,1,1)
и т.д.
pomme
22.04.2015 00:57А зачем ТАК сложно?
У нас есть n человек.
Тройку из них можно выбрать Cn3 = n(n-1)(n-2)/6 способами. Можно считать, (n-1)3/6, нас устроит не аналитически точное решение.
Вероятность того, что в случайно выбранной тройке все дни рождения совпадут = 1/3652 (обозначим как 1/m, где m = 3652), а что не совпадут = 1-1/m.
Если мы возьмем m троек, то вероятность несовпадения ни в одной из них = 1/e (замечательный предел: (1-1/m)m = 1/e).
Если мы возьмем m*ln(2) троек, то вероятность несовпадения ни в одной из них = (1-1/m)m*ln(2) = ((1-1/m)m)ln(2) = (1/e)ln(2) = 1/2. И вероятность совпадения хотя бы в одной тоже = 1/2.
Получается, что число троек (n-1)3/6 должно быть больше, чем m*ln(2).
Ответ: нужно 1+(6*ln(2)*3652)1/3 людей.strikerdimabel Автор
22.04.2015 01:08[1+(6*ln(2)*3652)1/3] = 83, думаю, большая погрешность.
Mrrl
22.04.2015 01:27У меня такая же формула получилась (хотя я считал как-то по-другому). И тоже 83.
pomme
22.04.2015 01:55Погрешность там должна быть порядка 1/n2, т.е. 0.02%
Ход рассуждений проверил — все верно.
А ваша программа просто рассчитывает приведенную выше длинную сумму или моделирует саму ситуацию — выбирает тройки, считает число совпадений?
allegator
22.04.2015 09:56А вероятность того, то в какой-то день число родившихся (из выборки) = 0, почему не учитывается? Или это никак не влияет на результат?
strikerdimabel Автор
22.04.2015 10:07В некоторые m дней число родившихся — 2, в (k — 2m) дней число родившихся — 1, в остальные дни — 0. Если я правильно понял вопрос
bay73
Смысл понятен, но фраза абсурдна. «гарантировать» и «с вероятностью 1/2», на мой взгляд несовместимы. Это все равно, что гарантировать, что случайно взятый человек окажется женщиной. Там тоже 50%.
ad1Dima
50% только если брать из группы с равным количеством мужчин и женщин. Если брать со всего земного шара, то более 50%, а в некоторых странах африки — меньше.