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

29

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

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

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

Саймон Эндрюс
источник
1
Я предполагаю, что это проблема биоинформатики
csgillespie
3
На самом деле это проблема биоинформатики, но поскольку она сводится к той же концепции, что и парадокс дня рождения, я подумал, что спасу не относящиеся к делу детали!
Саймон Эндрюс
4
Обычно я бы с вами согласился, но в этом случае конкретика может иметь значение, так как уже может быть пакет биокондуктора, который делает то, что вы просите.
csgillespie
Если вы действительно хотите знать, это проблема поиска шаблонов, в которой я пытаюсь точно оценить вероятность заданного уровня обогащения подпоследовательности в наборе более крупных последовательностей. Поэтому у меня есть набор подпоследовательностей с соответствующими счетчиками, и я знаю, сколько подпоследовательностей я наблюдал и сколько теоретически наблюдаемых последовательностей доступно. Если я видел конкретную последовательность в 10 раз из 10000 наблюдений, мне нужно знать, насколько вероятно, что это произошло случайно.
Саймон Эндрюс
Почти восемь лет спустя я опубликовал ответ на эту проблему по адресу stats.stackexchange.com/questions/333471 . Код там не работает при большом хотя, потому что это занимает квадратичное время в п . n,n
whuber

Ответы:

17

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

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

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

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

1a[1]+2a[2]+...+ka[k]+=n.

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

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

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

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

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

q(1)=q(1;4,5)=120q(2)=360+60=420q(3)=80q(4)=5.

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

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

k=1:0.49270k=2:0.494592k=3:0.0125308k=4:0.000172844k=5:1.80449E6k=6:1.48722E8k=7:9.92255E11k=8:5.45195E13.

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

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

k=1:0.498783k=2:0.496803k=3:0.014187k=4:0.000225115.

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

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

k=1:0k=2:0.8475+k=3:0.1520+k=4:0.0004+k>4:<1E6.

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

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

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

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

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

Его вывод

2 8503

3 1493

4 4

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

whuber
источник
What a fantastic answer, thank you very much @whuber.
JKnight
"There is an obvious and fairly simple recursion" — Namely?
Kodiologist
1
@Kodiologist I inserted a brief description of the idea.
whuber
+1 but where in the original question did you see that n=10000 and b=1mln? The OP looks like it is asking about n=1mln and k=10000, with b unspecified (presumably b=365). Not that it matters at this point :)
amoeba says Reinstate Monica
1
@amoeba After all this time (six years, 1600 answers, and closely reading tens of thousands of posts) I cannot recall, but most likely I misinterpreted the last line. In my defense, note that if we read it literally the answer is immediate (upon applying a version of the Pigeonhole Principle): it is certain that among n=millions of people there will be at least one birthday that is shared among at least x=thousands of them!
whuber
2

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))
}
Shane
источник
I am not sure if the multiple types solution will work here.
I think that generalisation still only works for 2 or more people sharing a birthday - just that you can have different sub-classes of people.
Simon Andrews
1

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)=1P(0|n)P(2|n)P(3|n)....P(x1|n)

Now,

P(y|n)=(ny)(365365)y k=1k=ny(1k365)

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

Step 1: You can pick y people in (ny) 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 (365365)y.

Step 3: The remaining ny people should not share a birthday with the first y people or with each other. This reasoning gives us k=1k=ny(1k365).

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


источник
Will this solution suffer from the curse of dimensionality? If instead of n=365, n=10^6 is this solution still feasible?
csgillespie
Some approximations may have to be used to deal with high dimensions. Perhaps, use Stirling's approximation for factorials in the binomial coefficient. To deal with the product terms you could take logs and compute the sums instead of the products and then take the anti-log of the sum.
There are also several other forms of approximations possible using for example the Taylor series expansion for the exponential function. See the wiki page for these approximations: en.wikipedia.org/wiki/Birthday_problem#Approximations
Suppose y=2, n=4, and there are just two birthdays. Your formula, adapted by replacing 365 by 2, seems to say the probability that exactly 2 people share a birthday is Comb(4,2)*(2/2)^2*(1-1/2)*(1-2/2) = 0. (In fact, it's easy to see--by brute force enumeration if you like--that the probabilities that 2, 3, or 4 people share a "birthday" are 6/16, 8/16, and 2/16, respectively.) Indeed, whenever n-y >= 365, your formula yields 0, whereas as n gets large and y is fixed the probability should increase to a non-zero maximum before n reaches 365*y and then decrease, but never down to 0.
whuber
Why you are replacing 365 by n? The probability that 2 people share a birthday is computed as: 1 - Prob(they have unique birthday). Prob(that they have unique birthday) = (364/365). The logic is as follows: Pick a person. This person can have any day of the 365 days as a birthday. The second person can then only have a birthday on one of the remaining 364 days. Thus, the prob that they have a unique birthday is 364/365. I am not sure how you are calculating 6/16.