¿Cuántos cubos hacen al azar números de relleno?

Question

Es una secuencia $\langle a_1,a_2,\ldots,a_n\rangle$ sobre el alfabeto $\{1,2,\ldots,m\}$ elegido uniformemente al azar entre las posibilidades de $m^n$. ¿Cuál es el tamaño esperado del conjunto $\{a_1,a_2,\ldots,a_n\}$?

Si $m=n$ se parece la respuesta tiende a $(1-1/e)n$ $n\to\infty$, pero no sé por qué.

Golpea en esto mientras benchmarking algún código para tablas hash, por lo que no me sorprendería si se trata de un resultado estándar en el mundo de hash.

Answer 1

Definir el indicador variable aleatoria$I_i$ para$1 \leq i \leq m$ como$1$ si alfabeto$i$ está presente en el conjunto${a_1,\dots,a_n}$. A continuación, el tamaño del conjunto es simplemente$\sum_{i=1}^m I_i$. La expectativa de que esto puede ser fácilmente calculada por la linealidad de la expectativa. La probabilidad de que$I_i$ es igual al$1$ está dada por$1-\left( \frac{m-1}{m} \right)^n$ y, por lo tanto el tamaño esperado del conjunto es$m \left[ 1- \left( 1 - \frac{1}{m} \right)^n \right]$. Para$m=n$, el valor límite es de hecho como usted ha mencionado en la pregunta.

Answer 2

Esto es tratado en profundidad en http://www.math.uah.edu/stat/urn/Birthday.html.