Problema de cumpleaños - número previsto de cumpleaños compartidos

Question

Dado $m$ personas y un $n$ posibles "días del año", ¿cuál es el número esperado de días que 2 o más personas comparten como cumpleaños?

Dicho de forma más precisa $B_i$ sean aleatorios uniformes independientes en $S = \{ 1, ..., n \}$ para $i = 1, ..., m$ . ¿Cuál es la cardinalidad esperada del conjunto de $d \in S$ donde existe $i,j$ no es igual a $B_i = B_j = d$ ?

Esto suena similar a problema de cumpleaños - número previsto de colisiones que pregunta por el número de colisiones, pero esa pregunta se refería al número de personas que comparten cumpleaños, no al número de días compartidos. La respuesta a esa pregunta está en el rango $[0,m]$ mientras que la respuesta a mi pregunta está en el rango $[0,n]$ .

En última instancia, se trata en realidad de una pregunta sobre colisiones de hash y colisiones de prefijos en un árbol de prefijos, pero consideré que la formulación de cumpleaños era la más familiar y la que más probabilidades tenía de ser útil para otras personas que la buscaran en el futuro.

Answer 1

Di la respuesta en un pregunta anterior sin cálculo. He aquí la justificación

• La probabilidad de que un día no haya gente es $\left(1-\frac1n\right)^m$ por lo que el número esperado de días sin gente es $n\left(1-\frac1n\right)^m$
• La probabilidad de que un día haya una persona es ${m \choose 1}\frac1n\left(1-\frac1n\right)^{m-1}$ por lo que el número esperado de días con una persona es $m\left(1-\frac1n\right)^{m-1}$
• Por tanto, el número previsto de días con dos o más personas es de $$n - n \left(1-\frac1n\right)^m - m \left(1-\frac1n\right)^{m-1}$$

Answer 2

Para cada $d\in[n]\overset{\text{Def.}}=\{1,2,\dots, n\}$ consideremos la variable aleatoria $$X_d\overset{\text{Def.}}=\lvert\{i\in[m]: B_i = n\}\rvert.$$ $X_d$ es el número de personas que cumplen años el día $d$ .

Entonces se busca el valor esperado de la variable aleatoria $$C=\lvert\{d\in[n]: X_d\ge 2\}\rvert,$$ es decir, el valor esperado del número de días en que dos o más personas cumplen años. He denominado a la variable aleatoria " $C$ " por "colisiones".

Ahora note que, usando los corchetes Iverson, $$C=\lvert\{d\in[n]: X_d\ge 2\}\rvert = [X_1\ge 2]+[X_2\ge 2]+\dots+[X_n\ge 2].$$

En particular, $$\mathsf E(C) = \mathsf E([X_1\ge 2])+\dots+\mathsf E([X_n\ge 2]),$$ que, desde el $X_d$ tienen la misma distribución, a saber $\text{Binomial}(\text{amount}=m,p=1/n)$ (ejercicio), es igual a $$n\mathsf P(X_1\ge 2) = n (1-\mathsf P(X_1=0)-\mathsf P(X_1=1))= n\left(1-(1-1/n)^m - \frac mn (1-1/n)^{m-1}\right).$$

Nota. En $X_d$ no son independientes, pero profundizar en ellas puede revelar algo sobre la distribución de $C$ .