Bolas al azar al Azar en Cubos: ¿cuáles son las características de la distribución?

Question

Tengo N cubos, numerados del 1 al N.

Puedo dibujar k enteros aleatorios uniformemente distribuidos en el intervalo de 1 a N, con reemplazo, y para cada entero de que me caiga un balón en el correspondiente depósito. k puede ser de cualquier tamaño; en concreto puede ser cualquier valor entre 2 y N, o mayor que N.

• ¿Cuáles son las características estadísticas (distribución de probabilidad, etc) de los números de las bolas en cada uno de ellos al final?
• ¿Cuáles son los las características estadísticas de los números de cubos con 0,1,...k las pelotas?

Esta pregunta surge de una necesidad de medir la 'bondad' (en cierto sentido) de un algoritmo de hash. Dada una muestra de la distribución de las llaves entre los cubos, necesito una medida de donde se encuentra en una escala de "Muy buena" a "Muy mala", y para ser capaz de trabajar en cosas como '¿cuáles son las posibilidades de que más de x pelotas en un cubo dado k y N?'

Obviamente, de la manera que yo he escrito esto, y a partir de los nombres al azar he asignado a mi las variables, no tengo absolutamente ninguna estadística sofisticación. Por favor, ser amable; quiero aprender. Por favor, siéntase libre de, por ejemplo, para cambiar los nombres de las variables a algo más convencional, o cualquier otra cosa.

Answer 1

Suponiendo que cada cubo es elegido con igual probabilidad, y las bolas son lanzadas de forma independiente, entonces el número de bolas en cada cubo se siga una distribución multinomial con $k$ ensayos y $p_1 = p_2 = \cdots = p_N = 1/N$. La probabilidad de que un particular cubeta que contiene $x$ bolas vendría dado por la probabilidad binomial, que en este caso es $\Pr(X=x) = \frac{k!}{x!(k-x)!} \frac{(N-1)^{k-x}}{N^k}$. Usted puede usar esto para obtener el $\Pr(X \geq x)$. Si $k$ es grande y $k/N$ es razonable magnitud, entonces podemos usar una aproximación de la distribución de Poisson (o una aproximación normal).

El número esperado de cubos que contienen exactamente $x$ bolas acaba de ser $N\Pr(X=x)$. Por supuesto, los totales en los cubos no son independientes, pero los totales de un par de (decir $M$) baldes será de aproximadamente independiente de si $k$ es grande en comparación a $M$. Así podríamos aproximar la varianza del número de baldes conteniendo $x$ bolas por $N\Pr(X=x) (1 - \Pr(X=x))$.

Por ejemplo, si tenemos 1000 bolas y 100 cubos, esperamos 9.5 baldes que contienen exactamente 12 bolas, pero la desviación estándar de este número es de 2.9, por lo que hay aproximadamente una probabilidad del 95% que se encuentran entre los 4 y los 15 años. (Ver código R).

> p = dbinom(12, size=1000, prob=1/100)
> 100*p
[1] 9.516152
> sqrt(100*p*(1-p))
[1] 2.934379
> 100*p + c(-1, 1)*1.96*sqrt(100*p*(1-p))
[1]  3.764769 15.267534