Espera de la carga máxima con $n$ bolas en $n$ papeleras?

Question

Si lanzas $n$ bolas en $n$ papeleras uniformemente y de forma independiente al azar, vamos a $X$ el número de bolas en la bandeja con el mayor número de bolas en.

Hay un modo elemental para calcular $\mathbb{E}(X)$?

Este problema surge cuando se considera hash en ciencias de la computación, por ejemplo, o al azar de equilibrio de carga.

EDIT. Después de haber visto la actual respuesta, si hay una manera más simple de demostrar que $\mathbb{E}(X) =\Theta(\log{n}/\log{\log{n}})$, en lugar de una fórmula exacta que yo sería feliz con eso.

Answer 1

Más en general, supongamos que tenemos N bolas y M papeleras. Sección 9.4 de Una Introducción al Análisis de Algoritmos, Segunda Edición por Robert Sedgewick y Philippe Flajolet muestra que la media de ocupación máxima está dada por

$$\frac{N!}{M^N} [z^N] \sum_{k \ge 0} \left( e^{Mz} - \left( \sum_{0 \le j \le k} \frac{z^j}{j!} \right)^M \right) $$

donde $[z^N]$ denota el coeficiente de $z^N$ cuando la expresión siguiente es ampliado. El libro también cita una aproximación asintótica debido a Gonnet:

$$\sim \frac{\ln N}{\ln \ln N} \text{ as } N, M \to \infty$$ de tal manera que $N/M = \alpha$ $\alpha$ constante.

Answer 2

La discusión en la Sección 4 de "Bolas en cajas" - Un Simple y Apretado Análisis por Raab y Steger (se encuentra aquí) parece bastante simple, siempre y cuando usted se siente cómodo usando momento el método de las desigualdades para limitar las probabilidades de los eventos.

Answer 3

Te gustaría saber la ecuación(s) para la Carga Máxima dará un número de contenedores y cualquier número de pelotas? Usted está en el lugar correcto. Después de examinar los datos y trabajar desde ahí, estos resultados son bastante sencillos, excepto para los no tan obvio UAF.

Definiciones: T: tira de bolas, U: urnas o cajas, EM(T,U): se Espera que la Carga Máxima para T azar tira en U urnas

Probabilísticamente, no hay una sola exacto valor esperado de la Carga Máxima para un determinado número de lanzamientos y de las urnas. Por ejemplo, EM(200,2), se espera que la carga máxima para 200 tiros en 2 de las urnas, es 105.6348479009 (redondeado).

Un buen ecuación puede ser visto por la espera de la carga máxima cuando U=2 y T es suficientemente grande:

EM(T,2)= T/2 + sqrt( T / (2*pi) ) como T → ∞

Lo que si hay son 3 las urnas?

Debido a que el máximo de la urna número puede ser tan alta como T, pero el mínimo urna sólo puede ser tan bajo como cero, hay un unscalable factor de ajuste (UAF) de (0.0918881...) / 2 para U=3.

EM(T,3)= T/3 + (3/2) * sqrt( T / (3*pi) ) + 0.04594407 como T → ∞

EM(1800,3) = 620.7748847701196 que se compara favorablemente con el de la ecuación de salida de 620.77559304. (La carga adicional es 99.996% de la ecuación del límite superior en el T/U=600.)

Para determinar EM(T,U), no son definitivos aumento constante de los multiplicadores para cada U. Maravilloso. Desde EM(T,U) se encuentra en el percentil 50, mi conjetura es que no puede ser exacta multiplicadores para cada uno de los otros valores de p, también.

Las estimaciones se han determinado para un par de estas constantes a través de la simulación, donde U > 3 uso de un estelar PRNG. Aviso que EM(T,U) es escalable por la raíz cuadrada de la espera urna contar, T/U.

Para 4 urnas, donde T/U es suficientemente grande, la ecuación es de aproximadamente EM(T,4)= T/4 + 1.029 * sqrt( T/4 ) + 0.09

Para el 13 de urnas, donde T/U es suficientemente grande, la ecuación es de aproximadamente EM(T,13)= T/13 + 1.667 * sqrt( T/13 ) + 0.35

Por 100 de las urnas, donde T/U es suficientemente grande, la ecuación es de aproximadamente EM(T,100)= T/100 + 2.51 * sqrt( T/100 ) + 0.9

Para 1000 urnas, donde T/U es suficientemente grande, la ecuación es de aproximadamente EM(T,1000)= T/1000 + 3.24 * sqrt( T/1000 ) + 1.6

Cuántas urnas / contenedores estás trabajando?