Расширение парадокса дня рождения более чем на 2 человека

В традиционном парадоксе дня рождения вопрос заключается в том, «каковы шансы, что два или более человека в группе из $n$ человек разделяют день рождения». Я застрял на проблеме, которая является продолжением этого.

Вместо того , чтобы знать вероятность того, что два человека разделить день рождения, мне нужно расширить вопрос , чтобы знать , какова вероятность того, что $x$ или больше людей разделяют на день рождения. С $x=2$ вы можете сделать это, рассчитав вероятность того, что ни один человек не разделит день рождения, и вычтите это из $1$ , но я не думаю, что смогу расширить эту логику до большего числа $x$ .

Чтобы еще больше усложнить это, мне также нужно решение, которое будет работать для очень больших чисел для $n$ (миллионов) и $x$ (тысяч).

Это проблема подсчета: есть возможных назначений b дней рождения n людям. Из них пусть q ( k ; n , b ) будет количеством назначений, для которых ни один день рождения не является общим для более чем k человек, но по крайней мере один день рождения фактически является общим для k человек. Вероятность, которую мы ищем, может быть найдена путем суммирования q ( k ; n , b ) для соответствующих значений k и умножения результата на b - n .$b^n$$b$$n$$q(k; n, b)$$k$$k$$q(k;n,b)$$k$$b^{-n}$

Эти подсчеты можно найти точно для значений менее нескольких сотен. Тем не менее, они не будут следовать какой-либо простой формуле: мы должны рассмотреть шаблоны способов, которыми могут быть назначены дни рождения . Я проиллюстрирую это вместо общей демонстрации. Пусть n = 4 (это наименьшая интересная ситуация). Возможности:$n$$n = 4$

• У каждого человека есть уникальный день рождения; код {4}.
• Ровно два человека делят день рождения; код {2,1}.
• Два человека имеют один день рождения, а два других - другой; код {0,2}.
• Три человека делят день рождения; код {1,0,1}.
• Четыре человека делят день рождения; код {0,0,0,1}.

Как правило, код представляет собой набор подсчетов, чей k- й элемент определяет, сколько различных дат рождения совместно используются ровно k людьми. Так, в частности,$\{a[1], a[2], \ldots\}$$k^\text{th}$$k$

Обратите внимание, что даже в этом простом случае есть два способа достижения максимум двух человек на день рождения: один с кодом а другой с кодом { 2 , 1 } .$\{0,2\}$$\{2,1\}$

Мы можем напрямую посчитать количество возможных назначений дня рождения, соответствующих любому данному коду. Это число является произведением трех терминов. Одним из них является коэффициент многочлена; он подсчитывает число способов разбиения людей в течение [ 1 ] группы 1 , [ 2 ] группы из 2 , и так далее. Поскольку последовательность групп не имеет значения, мы должны разделить этот множитель коэффициента на a [ 1 ] ! [ 2 ] ! $n$$a[1]$$1$$a[2]$$2$$a[1]!a[2]!\cdots$; его взаимностью является второй член. Наконец, выстроите группы в группы и назначьте им каждый день рождения: в первой группе есть кандидатов, во второй b - 1 , и так далее. Эти значения должны быть умножены вместе, образуя третий член. Он равен «факториальному произведению» b ( a [ 1 ] + a [ 2 ] + ⋯ ), где b ( m ) означает b ( b - 1 ) ⋯ ( b - m + $b$$b-1$$b^{(a[1]+a[2]+\cdots)}$$b^{(m)}$ .$b(b-1)\cdots(b-m+1)$

Существует очевидная и довольно простая рекурсия, связывающая счет для шаблона с счетом для шаблона { a [ 1 ] , … , a [ k - 1 ] } . Это позволяет быстро рассчитывать значения для скромных значений n . В частности, a [ k ] представляет собой [ k ] даты рождения, разделенные ровно $\{a[1], \ldots, a[k]\}$$\{a[1], \ldots, a[k-1]\}$$n$$a[k]$$a[k]$$k$люди каждый. После этого [ к ] группы K людей были взяты из русских людей, которые могут быть сделаны в х различных способах (скажем), остались подсчитать количество способов достижения шаблона { [ 1 ] , ... , a [ k - 1 ] } среди оставшихся людей. Умножение этого на х дает рекурсию.$a[k]$$k$$n$$x$$\{a[1], \ldots, a[k-1]\}$$x$

Я сомневаюсь, что существует формула замкнутой формы для , которая получается суммированием отсчетов для всех разбиений n, чей максимальный член равен k . Позвольте мне привести несколько примеров:$q(k; n, b)$$n$$k$

С (пять возможных дней рождения) и n = 4 (четыре человека), мы получаем$b=5$$n=4$

Откуда, например, вероятность того, что три или более человек из четырех имеют одинаковый «день рождения» (из возможных дат), равна ( 80 + 5 ) / 625 = 0,136 .$5$$(80 + 5)/625 = 0.136$

В качестве другого примера возьмем и n = 23 . Вот значения q ( k ; 23 , 365 ) для наименьшего k (только для шести подписей):$b = 365$$n = 23$$q( k;23,365)$$k$

Используя эту технику, мы можем легко вычислить, что есть вероятность 50% (по крайней мере) столкновения с трехсторонним днем ​​рождения среди 87 человек, 50% вероятность столкновения с четырьмя путями среди 187 и 50% вероятность пятистороннее столкновение среди 310 человек. Этот последний расчет начинает занимать несколько секунд (в любом случае в Mathematica), потому что количество рассматриваемых разделов начинает увеличиваться. Для существенно большего нам нужно приближение.$n$

Одно приближение получено с помощью распределения Пуассона с ожиданием , потому что мы можем рассматривать присвоение дня рождения как возникающее из b почти (но не совсем) независимых переменных Пуассона, каждая с ожиданием n / b : переменная для любого данного возможного дня рождения описывает, сколько из русских людей имеют этот день рождения. Таким образом, распределение максимума приблизительно равно F ( k ) b, где F - CDF Пуассона. Это не строгий аргумент, поэтому давайте проведем небольшое тестирование. Аппроксимация для n = 23 , $n/b$$b$$n/b$$n$$F(k)^b$$F$$n = 23$ дает$b = 365$

Сравнивая с предыдущим, вы можете видеть, что относительные вероятности могут быть низкими, когда они малы, но абсолютные вероятности достаточно хорошо приближены к 0,5%. Тестирование с широким диапазоном и b показывает, что аппроксимация обычно примерно такая же.$n$$b$

Для того, чтобы обернуть, давайте рассмотрим исходный вопрос: принять (число наблюдений) и б = $n = 10,000$ (количество возможных «структур», примерно). Примерное распределение для максимального количества «общих дней рождения»$b = 1\,000\,000$

(Это быстрый расчет.) Очевидно, что наблюдение одной структуры в 10 раз из 10000 было бы весьма значительным. Поскольку и b оба большие, я ожидаю, что приближение здесь будет работать достаточно хорошо.$n$$b$

Между прочим, как отметил Шейн, симуляции могут обеспечить полезные проверки. Симуляция Mathematica создается с помощью функции

simulate[n_, b_] := Max[Last[Transpose[Tally[RandomInteger[{0, b - 1}, n]]]]];

который затем повторяется и суммируется, как в этом примере, который выполняет 10000 итераций с , b = $n = 10000$ корпус:$b = 1\,000\,000$

Tally[Table[simulate[10000, 1000000], {n, 1, 10000}]] // TableForm

Его вывод

2 8503

3 1493

4 4

Эти частоты близко согласуются с теми, которые предсказаны в приближении Пуассона.

It is always possible to solve this problem with a monte-carlo solution, although that's far from the most efficient. Here's a simple example of the 2 person problem in R (from a presentation I gave last year; I used this as an example of inefficient code), which could be easily adjusted to account for more than 2:

birthday.paradox <- function(n.people, n.trials) {
    matches <- 0
    for (trial in 1:n.trials) {
        birthdays <- cbind(as.matrix(1:365), rep(0, 365))
        for (person in 1:n.people) {
            day <- sample(1:365, 1, replace = TRUE)
            if (birthdays[birthdays[, 1] == day, 2] == 1) {
                matches <- matches + 1
                break
            }
            birthdays[birthdays[, 1] == day, 2] <- 1
        }
        birthdays <- NULL
    }
    print(paste("Probability of birthday matches = ", matches/n.trials))
}

This is an attempt at a general solution. There may be some mistakes so use with caution!

First some notation:

$P(x,n)$ be the probability that $x$ or more people share a birthday among $n$ people,

$P(y|n)$ be the probability that exactly $y$ people share a birthday among $n$ people.

Notes:

1. Abuse of notation as $P(.)$ is being used in two different ways.

2. By definition $y$ cannot take the value of 1 as it does not make any sense and $y$ = 0 can be interpreted to mean that no one shares a common birthday.

Then the required probability is given by:

$P(x,n) = 1 - P(0|n) - P(2|n) - P(3|n) .... - P(x-1|n)$

Now,

$P(y|n) = {n \choose y} (\frac{365}{365})^y \ \prod_{k=1}^{k=n-y}(1 -\frac{k}{365})$

Here is the logic: You need the probability that exactly $y$ people share a birthday.

Step 1: You can pick $y$ people in ${n \choose y}$ ways.

Step 2: Since they share a birthday it can be any of the 365 days in a year. So, we basically have 365 choices which gives us $(\frac{365}{365})^y$.

Step 3: The remaining $n-y$ people should not share a birthday with the first $y$ people or with each other. This reasoning gives us $\prod_{k=1}^{k=n-y}(1 -\frac{k}{365})$.

You can check that for $x$ = 2 the above collapses to the standard birthday paradox solution.