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

Многим известен парадокс дней рождения: в группе из 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.
Поделиться публикацией

Комментарии 19

    +6
    гарантировать… с вероятностью 1/2.

    Смысл понятен, но фраза абсурдна. «гарантировать» и «с вероятностью 1/2», на мой взгляд несовместимы. Это все равно, что гарантировать, что случайно взятый человек окажется женщиной. Там тоже 50%.
      –1
      Это все равно, что гарантировать, что случайно взятый человек окажется женщиной. Там тоже 50%.

      50% только если брать из группы с равным количеством мужчин и женщин. Если брать со всего земного шара, то более 50%, а в некоторых странах африки — меньше.
      +1
      В вашей таблице еще один интересный (на мой взгляд) случай — группа из 150 человек, в которой вероятность уже очень близка к 100%.
      Хотя на первый взгляд кажется, что там, опять же, примерно 1/2 и выйдет.
      • НЛО прилетело и опубликовало эту надпись здесь
          +1
          Давно уж. Ладно хоть не перепечатка ответа из решебника.
          –1
          image
            +4
            30 февраля? А 30 и 31 мая никто не родился?
              +1
              похоже, что таблица должна начинаться с октября
                +4
                Они просто взяли таблицу частот дней рождения и отняли 9 месяцев. Из 30 ноября получилось 30 февраля, а 30 и 31 мая не получились вообще. Ну, и провал на 4 октября: ведь в день Независимости США никто не рождается, роды стараются перенести на пораньше.
            +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.
              0
              Согласен, есть ошибка. Постараюсь с этим разобраться.
                0
                Ошибка оказалась в том, что выбранные мною элементарные события не равновероятны.
                В качестве элементарных событий я брал наборы частот длиной 365 чисел:
                (1,1,2...,0,0)
                (2,4,2,...,1,1)
                и т.д.
              0
              А зачем ТАК сложно?

              У нас есть 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 людей.
                0
                [1+(6*ln(2)*3652)1/3] = 83, думаю, большая погрешность.
                  0
                  У меня такая же формула получилась (хотя я считал как-то по-другому). И тоже 83.
                    0
                    Погрешность там должна быть порядка 1/n2, т.е. 0.02%
                    Ход рассуждений проверил — все верно.

                    А ваша программа просто рассчитывает приведенную выше длинную сумму или моделирует саму ситуацию — выбирает тройки, считает число совпадений?
                      0
                      Рассчитывает сумму, только что её исправил
                  0
                  А вероятность того, то в какой-то день число родившихся (из выборки) = 0, почему не учитывается? Или это никак не влияет на результат?
                    0
                    В некоторые m дней число родившихся — 2, в (k — 2m) дней число родившихся — 1, в остальные дни — 0. Если я правильно понял вопрос

                  Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

                  Самое читаемое