Primera vez que voy a escribir la respuesta exacta (suma incluido) y, a continuación, diversas aproximaciones.
Deje $X$ ser la variable aleatoria que indica el número de bolas después de que la segunda colisión se produce. Queremos $E[X]$. Como $X$ sólo toma entero no negativo, los valores, su expectativa es
$$E[X] = \sum_{n=1}^{\infty}\Pr(X \ge n) = \sum_{n=0}^{\infty}\Pr(X > n)$$
The probability $\Pr(X > n)$ is the probability that after $n$ balls are thrown into the $m$ bins, the number of collisions is either $0$ or $1$. The probability of $0$ collisions is, as in the classical birthday problem, $\dfrac{m(m-1)\dots(m-n+1)}{m^n}$. The probability of exactly one collision can be calculated as follows: for this to happen, some pair of balls must go to the same bin, after which the other $n-2$ balls must go to the other $m-1$ bins without collision, so the probability of this is $\displaystyle \binom{n}{2} m \frac{1}{m^2} \frac{(m-1)(m-2)\dots(m-n+2)}{m^{n-2}} = \binom{n}{2} \frac{m(m-1)(m-2)\dots(m-n+2)}{m^n}$. Note that this is precisely $\binom{n}{2} \frac{1}{m-n+1}$ times the probability of $0$ collisions.
For the classical birthday problem, the same analysis as above gave that the expected number of balls until collision (call this random variable $Y$) is
$$
\begin{align}
E[Y]
&= \sum_{n=0}^{\infty} \frac{m(m-1)\dots(m-n+1)}{m^n} \\
&= 1 + 1 + \frac{m-1}{m} + \frac{(m-1)(m-2)}{m^2} + \frac{(m-1)(m-2)}{m^3} + \dots
\end{align}$$
La asintótica de expansión de esta suma, relativa a la Ramanujan Q-función, es conocido por ser
$$\sqrt{\frac{\pi m}{2}} + \frac{2}{3} + \frac{1}{12}\sqrt{\frac{\pi}{2m}} - \frac{4}{135m} + \dots$$
En nuestro caso, se espera que el número de bolas de hasta dos colisiones es el antiguo suma, además, la suma de los términos procedentes de las probabilidades de tener exactamente una colisión: es
$$
\begin{align}
E[X] &= \sum_{n=0}^{\infty} \left( \frac{m(m-1)\dots(m-n+1)}{m^n} + \binom{n}{2} \frac{m(m-1)(m-2)\dots(m-n+2)}{m^n} \right) \\
&= 1 + 1 + \frac{m-1}{m} + \frac{(m-1)(m-2)}{m^2} + \frac{(m-1)(m-2)(m-3)}{m^3} + \dots\\
&\phantom{=1+1} + \frac{1}{m} + 3\frac{(m-1)}{m^2} + 6\frac{(m-1)(m-2)}{m^3} + \dots
\end{align}
$$
That's the exact expression; now for the approximations.
One trivial fact we can prove rigorously is that $E[Y] < E[X] < 2E[Y]$. The former inequality is from the fact that the second collision can only happen after the first one, so $X \ge$ Y. La segunda desigualdad es el hecho de que después de la primera colisión, si queremos borrar todos los recipientes y esperar a que un choque a suceder de nuevo desde cero, la segunda colisión, sólo puede tomar más tiempo que en el caso normal. Así
$$\sqrt{\frac{\pi m}{2}} < E[X] < \sqrt{2\pi m}$$
One avenue of approximation is to instead calculate the "median" $X$, as Ross Millikan's answer does: find the number of balls $n$ for which the probability of $0$ or $1$ collisions is $\frac{1}{2}$. The expected value of $X$ will be around this. (And also strictly more than half of this $n$, because we have $E[X] \ge n \Pr(X \ge n) = \frac{n}{2}$.)
His answer already gives one way, here is another. From the expression we calculated above for the probability, we want $$ n tal que
$$
\begin{align}
\frac12
&= \frac{m(m-1)\dots(m-n+1)}{m^n} + \binom{n}{2} \frac{m(m-1)(m-2)\dots(m-n+2)}{m^n} \\
&= \left(\frac{m-n+1}{m} + \binom{n}{2}\frac{1}{m} \right) \frac{m(m-1)(m-2)\dots(m-n+2)}{m^{n-1}} \\
&= \left(\frac{m-n+1}{m} + \binom{n}{2}\frac{1}{m} \right)
\left(1 - \frac1m \right) \left(1 - \frac2m \right) \cdot \dots \cdot \left(1 - \frac{n-2}m \right) \\
&\approx \left(1 + \frac{n^2}{2m} \right)
e^{-1/m} e^{-2/m} e^{-3/m} \dots e^{-(n-2)/m} \\
&\approx \left(1 + \frac{n^2}{2m} \right) e^{-n^2/2m} \\
\end{align}$$
que nos da exactamente la misma aproximación $\frac{n^2}{2m} \approx 1.678$ como en el Ross de Millikan respuesta! En concreto, se da $E[X] \approx 1.83\sqrt{m}$.
Otra aproximación es el uso de $E[X] = E[E[X|Y]]$ y asumir que $Y$ (el tiempo de la primera colisión) se concentra alrededor de su media. Después de la primera colisión ocurre (después de $Y$ bolas), hay $Y-1$ vacía las papeleras, por lo que alrededor de una fracción $\frac{Y}{m}$ de los envases son no vacío y una fracción $1 - \frac{Y}{m}$ de los contenedores están vacíos. La segunda colisión ocurre cuando una bola cae en uno de los actualmente ocupados bandejas, o una bola aterriza por segunda vez en una de las bandejas aún no ocupados. El primero es mucho más probable que ocurra primero que el segundo. El tiempo de espera que el primero toma es $\dfrac1{Y/m}$, ya que es una distribución geométrica (como lanzar una moneda que tiene probabilidad de $\frac{Y}{m}$ de las cabezas, hasta que los jefes viene). Así
$$E[X] \approx E\left[Y + \frac{m}{Y}\right] $$
que si $Y$ está fuertemente concentrada en torno a $\sqrt{\frac{\pi m}{2}}$, será
$$E[X] \approx \sqrt{\frac{\pi m}{2}} + \sqrt{\frac{2m}{\pi}} = \sqrt{m}\left( \sqrt{\frac{\pi}2} + \sqrt{\frac2\pi} \right)$$
que ($E[X] \approx 2.05\sqrt{m}$) es ligeramente mayor que la respuesta dada por la primera aproximación.
Sabemos que $E[X]$ entre $\sqrt{\frac{\pi}{2}}\sqrt{m}$$\sqrt{2\pi}\sqrt{m}$, por lo que tenemos la certeza de que asintóticamente, $E[X] \sim c\sqrt{m}$ para algunas constantes $c$. Sólo tenemos que encontrar la constante de $c$, y parece que la mejor manera es escribir un programa para ello. He aquí un programa en Python que utiliza exactamente la fórmula anterior para calcular el valor de $E[X]$ por el aumento de $m$, e imprime $\frac{E[X]}{\sqrt{m}}$:
import math
def x(m):
ans = 2
term = 1
other_term = 1.0 / m
for n in range(2, m + 2):
term *= (m - (n - 1.0)) / m
other_term *= (m - (n - 2.0)) / m
ans += term + (n * (n - 1) * other_term) / 2
return ans
m = 1
while True:
m *= 2
n = x(m)
print m, n, n / math.sqrt(m)
que se imprime (entre otras cosas):
...
16777216 7701.36209791 1.88021535594
33554432 10890.956487 1.88014384413
67108864 15401.7241385 1.88009327862
134217728 21780.9129334 1.88005752389
...
por lo $c \approx 1.88$ o $E[X] \approx 1.88\sqrt{m}$ parece ser la verdad.
Se puede decir más acerca de los cumpleaños específicamente ($m = 365$). Con un pequeño cambio en el programa anterior, para cada una de las $n$, se puede calcular exactamente la probabilidad de que $X = n$ (es decir, que tarda $n$ de personas hasta la segunda colisión ocurre). Esto resulta para dar la siguiente distribución.
n P(X > n) P(X = n)
25 0.810743 0.023477
26 0.785794 0.024950
27 0.759490 0.026304
28 0.731969 0.027521
29 0.703384 0.028585
30 0.673899 0.029485
31 0.643690 0.030209
32 0.612939 0.030752
33 0.581830 0.031109
34 0.550548 0.031281
35 0.519278 0.031270
36 0.488198 0.031081
37 0.457476 0.030721
38 0.427275 0.030202
39 0.397741 0.029533
40 0.369011 0.028730
41 0.341204 0.027807
42 0.314426 0.026779
43 0.288763 0.025662
44 0.264290 0.024473
45 0.241061 0.023229
46 0.219117 0.021944
47 0.198482 0.020635
48 0.179168 0.019315
49 0.161170 0.017997
50 0.144476 0.016695
51 0.129058 0.015418
52 0.114881 0.014177
53 0.101902 0.012979
54 0.090072 0.011830
55 0.079334 0.010738
Así que como $P(X > 43)$ es todavía muy saludable $0.288763$, no es nada de que estar muy sorprendido de que sólo hay una colisión entre los 43 presidentes de EE.UU. hasta el momento. :-)
