Extendiendo la paradoja del cumpleaños a mas de 2 personas

Question

En el tradicional paradoja de cumpleaños la pregunta es "¿cuáles son las probabilidades de que dos o más personas en un grupo de n personas comparten un cumpleaños". Estoy atascado en un problema que es una extensión de este.

En lugar de conocer la probabilidad de que dos personas comparten un cumpleaños necesito para ampliar la cuestión de saber cuál es la probabilidad de que x o más personas comparten un cumpleaños. Con x=2 usted puede hacer esto mediante el cálculo de la probabilidad de que no hay dos personas que comparten un cumpleaños y restar que desde el 1, pero creo que no se puede extender esta lógica a un mayor número de x.

Para complicar aún más este también necesito una solución que funciona para números muy grandes de n (millones) y x (en miles).

Answer 1

Este es un recuento de problema: no se b^n posible cumpleaños asignaciones para n personas. De esos, vamos q(k; n, b) el número de tareas para las que no cumpleaños es compartida por más de k la gente, pero al menos uno de los cumpleaños, en realidad es compartida por k la gente. La probabilidad que buscamos puede ser encontrada por la suma de las p(k;n,b) para los valores de k y multiplicando el resultado por b^(-n).

Estos recuentos se pueden encontrar exactamente para valores de n menos de varios cientos. Sin embargo, no se sigue ningún sencilla fórmula: debemos tener en cuenta que los patrones de las formas en que los cumpleaños pueden ser asignados. Voy a ilustrar esto, en lugar de proporcionar una demostración general. Deje que n = 4 (este es el más pequeño situación interesante). Las posibilidades son:

• Cada persona tiene un único cumpleaños; el código es {4}.
• Exactamente dos personas comparten un cumpleaños; el código es {2,1}.
• Dos personas tienen un cumpleaños y los otros dos tienen otro; el código es {0,2}.
• Tres personas comparten un cumpleaños; el código es {1,0,1}.
• Cuatro personas comparten un cumpleaños; el código es {0,0,0,1}.

En general, el código {un[1], un[2], ...} es una tupla de cuenta cuyo k ésimo elemento estipula cómo muchos distintas fechas de nacimiento son compartidos por exactamente k la gente. Así, en particular,

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

Tenga en cuenta, incluso en este caso simple, que hay dos maneras en que el máximo de dos personas por cumpleaños es alcanzado: uno con el código {0,2} y otro con el código {2,1}.

Podemos contar el número de posibles cumpleaños de los trabajos correspondientes a un determinado código. Este número es el producto de tres términos. Uno es un coeficiente multinomial; cuenta el número de maneras de particiones de n personas en una[1] los grupos de 1, [2] los grupos de 2, y así sucesivamente. Debido a que la secuencia de los grupos no importa, tenemos que dividir este coeficiente multinomial por un[1]!un[2]!... ; su recíproco es el segundo término. Por último, la línea de los grupos y asignar a cada uno de ellos un cumpleaños: hay b candidatos para el primer grupo, b-1 para el segundo, y así sucesivamente. Estos valores tienen que ser multiplicados juntos, formando el tercer término. Es igual a la "factorial de producto" b^((a[1]+[2]+...)) donde b^((m)) significa que b(b-1)...(b-m+1).

Hay una evidente y bastante simple de recursividad relacionados con la cuenta de un patrón {a[1], ..., a[k]} para el recuento para el patrón {a[1], ..., a[k-1]}. Esto permite el cálculo rápido de la cuenta de modestos valores de n.

Dudo que haya una forma cerrada fórmula para p(k; n, b), que se obtiene sumando a la cuenta de todas las particiones de n , cuyo plazo máximo es igual a k. Permítanme ofrecer algunos ejemplos:

Con b = 5 (cinco posibles cumpleaños) y n = 4 (cuatro personas), obtenemos

p(1) = q(1;4,5) = 120

q(2) = 360 + 60 = 420

p(3) = 80

p(4) = 5.

De ahí que, por ejemplo, la probabilidad de que tres o más personas, de las cuatro que comparten el mismo "cumpleaños" (fuera de 5 fechas posibles) es igual a (80 + 5)/625 = 0.136.

Como otro ejemplo, tomar b = 365 y n = 23. Aquí están los valores de q( k;23,365) para los más pequeños de k (seis sig higos):

k=1: 0.49270

k=2: 0.494592

k=3: 0.0125308

k=4: 0.000172844

k=5: 1.80449 E-6

k=6: 1.48722 E-8

k=7: 9.92255 E-11

k=8: 5.45195 E-13

Usando esta técnica, se puede fácilmente calcular que hay un 50% de probabilidad de (al menos) tres cumpleaños colisión entre 87 personas, un 50% de posibilidades de forma de cuatro colisión entre 187, y un 50% de probabilidades de cinco colisión entre 310 personas. Que el último cálculo comienza a tomar un par de segundos (en Mathematica, de todos modos) debido a que el número de particiones que se van a considerar empieza a ser grande. Sustancialmente mayor n necesitamos una aproximación.

Una aproximación se obtiene por medio de la distribución de Poisson, con expectativa, n/b, porque podemos ver un cumpleaños de asignación como el resultado de b casi (pero no del todo) independiente de Poisson de las variables de cada uno con la expectativa n/b: la variable para cualquier posible cumpleaños describe cómo muchas de las n personas que han cumpleaños. La distribución de la máxima es, por tanto, aproximadamente F(k)^b donde F es la distribución de Poisson CDF. Este no es un argumento riguroso, así que vamos a hacer un poco de prueba. La aproximación para n = 23, b = 365 da

k=1: 0.498783

k=2: 0.496803

k=3: 0.014187

k=4: 0.000225115

Comparando con la anterior se puede ver que la relación de las probabilidades pueden ser buenos cuando son pequeños, pero en términos absolutos las probabilidades están razonablemente bien aproximada a alrededor de 0.5%. Prueba con una amplia gama de n y b sugiere que la aproximación es por lo general alrededor de esta buena.

Para terminar, vamos a considerar la pregunta original: tomar n = 10,000 (el número de observaciones) y b = 1,000,000 (el número de posibles "estructuras", aproximadamente). La distribución aproximada por el número máximo de "compartida de cumpleaños"

k=1: 0

k=2: 0.8475+

k=3: 0.1520+

k=4: .0004+

k>4: < 1E-6

(Este es un cálculo rápido.) Claramente, la observación de una estructura de 10 veces fuera de 10,000 sería muy significativo. Porque n y b son grandes, espero que la aproximación que funciona bastante bien aquí.

Por cierto, como Shane dio a entender, las simulaciones pueden servir de cheques. Un Mathematica simulación es creado con una función como

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

que luego se reiteró y se resume, como en este ejemplo que se ejecuta 10.000 iteraciones de la n = 10,000, b = 1,000,000 caso:

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

Su salida es

2 8503

3 1493

4 4

Estas frecuencias cerca de acuerdo con los predichos por la aproximación de Poisson.

Answer 2

Siempre es posible resolver este problema con una solución de monte carlo, aunque es lejos el más eficiente. Aquí está un ejemplo simple del problema en R 2 personas (de una presentación que dio el año pasado; Yo utiliza esto como un ejemplo de código ineficiente), que puede ajustarse fácilmente para tener en cuenta más de 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))
}