¿Cuántas personas se espera que compartan un cumpleaños hasta 3?

Question

Le pregunté a un algo relacionado pregunta hace poco y luego se interesó por esta otra: ¿cuántas personas son necesarias, por término medio, hasta que 3 comparten un cumpleaños? En términos más generales, si tenemos $M$ cubos, ¿cuál es el número esperado de bolas que debemos lanzar antes de que algún cubo contenga exactamente 3 bolas?

Las técnicas sencillas utilizadas en la pregunta citada anteriormente parecen difíciles de aplicar aquí porque el número de formas de obtener configuraciones con 2 bolas o menos es bastante más complicado ahora.

Pregunta: ¿cuál es el número esperado de bolas necesarias para obtener un cubo con 3 bolas?

---

Para ampliar un poco el comentario "desordenado" anterior: el FEAG para el número de formas de tirar $n$ bolas en $M$ papeleras sin que ninguna contenga más de 2 bolas es $$(1+z+z^2/2)^M$$

Así, por ejemplo, si tenemos $M=3$ bins, el número de formas de $n$ bolas que hay que ordenar (sin que ninguna bandeja tenga más de 2 bolas) se encuentra tomando el $n$ -a coeficiente de $$(1+z+z^2/2)^3 = 1/0! + 3 z/1! + 9z^2/2! + 24z^3/3! + 54z^4/4! + 90z^5/5! + 90z^6/6!$$

Así que si quiero el número de palabras de 4 letras del alfabeto $\{a,b,c\}$ donde ninguna letra aparece más de dos veces, es el coeficiente de ${z^4/4!}$ o 54 según esta fórmula. Podemos comprobarlo directamente observando que hay tres palabras de 4 letras con todos los caracteres iguales (aaaa, bbbb y cccc). Para las palabras con 3 letras iguales y una diferente, hay 4 formas de elegir la posición de la letra diferente, luego 3 opciones de cuál es esa letra, y luego 2 opciones para las tres letras que coinciden. Por lo tanto, el número total de palabras de 4 letras es $3^4=81$ , por lo que tenemos $81-3-4\cdot 3\cdot 2 = 54$ . Por supuesto, esto se complica a medida que $M$ aumenta.

Cómo se pasa de este FEAG a una estimación asintótica de la expectativa es algo que no entiendo.

---

Nota: La respuesta de Byron más abajo resuelve esto. Para cualquiera que esté interesado, esto se generaliza completamente a las "colisiones k-sabias" usando

$$E(M,k) \approx \sqrt[k]{k!}\ \Gamma(1 + 1/k)\ M^{1-1/k}$$

donde el ajuste $k=3$ produce el resultado en la respuesta de Byron a continuación. Por supuesto, este es un resultado asintótico y mejora a medida que $M$ aumenta. Para $M$ =365 esta fórmula da unos 82,87, mientras que la respuesta correcta es unos 88,73891.

Answer 1

El tiempo esperado hasta la primera colisión triple es $$\mathbb{E}(T) = \int_0^\infty \left(1+{x\over M}+{x^2\over2M^2}\right)^M \,e^{-x}\,dx.\tag1$$

En mi respuesta aquí La fórmula para las colisiones dobles la obtuve, y la extensión a las colisiones triples es sencilla. a las colisiones triples es sencilla. A partir de la ecuación (1), vemos que $\mathbb{E}(T)$ crece como un múltiplo de $M^{2/3}$ .

---

Pasé la página y me di cuenta de que en la sección 15.3 de Problemas e instantáneas del mundo de la probabilidad de Blom, Holst y Sandell, los autores dan el resultado asintótico preciso $$\mathbb{E}(T)\approx 6^{1/3}\,\Gamma(4/3)\, M^{2/3}\approx 1.6226\,M^{2/3}.$$