Supongamos que lanzar bolas una por una en $b$ baldes, uniformemente al azar. ¿A qué hora se hace el tamaño de algunos (cualquier) balde exceder el tamaño de la $s$?
Es decir, considerar el siguiente proceso aleatorio. En cada uno de los tiempos de $t=1, 2, 3, \dots$,
- Recoger una bola (a partir de una fuente infinita de bolas que tiene).
- Asignar a uno de $b$ baldes, uniformemente al azar, e independiente de las opciones anteriores bolas.
Para este proceso aleatorio, vamos a $T = T(s,b)$ ser el momento en que
- En el momento $T-1$ (después de la $T-1$th pelota fue asignada), para cada uno de ellos, el número de bolas asignado a se $\le s$.
- En el momento $T$ (después de la $T$th pelota fue asignada), hay algunos cubo para que el número de bolas asignado a es $s + 1$.
¿Qué podemos decir acerca de $T$? Si podemos obtener la distribución de los $T(s,b)$ eso sería genial, más aún sabiendo que su valor esperado y la varianza, o incluso sólo el valor esperado, sería bueno.
Más allá del hecho obvio de que $T \le bs+1$ (y, por tanto, $E[T]$ existe), no veo nada muy útil. La motivación viene de la vida real-equipo de hashing (los números de interés son algo como $b = 10000$$s = 64$).
