Buscando una distribución de probabilidad

Question

Hace poco comenté un experimento con un amigo. Supongamos que empezamos un experimento aleatorio. Al principio hay una matriz de tamaño $100,000$ , todo ello ajustado a $0$ . Calculamos en cada ronda un número aleatorio módulo $2$ y seleccionar una posición al azar en esa matriz. Si el número de la matriz es $1$ no se cambia nada y, en caso contrario, se establece el valor precalculado. La pregunta es: ¿cuántos valores hash distintos habremos añadido en $1$ %, $5$ %, $50$ %, $95$ %, $99$ ¿Gracias a los casos?

Ejemplo: $4$ rondas con array de tamaño $10$ :

Array                     Position   random number
[0,...,0]                    5              0
[0,...,0]                    7              1
[0,...0,1,0,0,0]             6              1
[0,..0,.1,1,0,0,0]           6              0
[0,..0,.1,1,0,0,0]           2              0

Primero consideramos que se trataba de un problema algo sencillo, pero después de pensar durante algunas horas, buscar en la web y preguntar a algunos estudiantes de matemáticas, no pudimos encontrar una solución. ¿Conoces una distribución de probabilidad para este problema?

Observación: También se publicó en Desbordamiento matemático y obtuvo su respuesta allí.

Answer 1

Según la respuesta de T. en MathOverflow.

Esto equivale a (entre otros nombres) el problema del recolector de cupones. Se pregunta por la distribución del número de cupones recogidos después de t pasos, cuando el número total de cupones posibles es n.

http://en.wikipedia.org/wiki/Coupon_collector%27s_problem

AÑADIDO: ésta y otras distribuciones relacionadas también se estudian con otros nombres como Problema de Cumpleaños, mapeos aleatorio y hashing aleatorio. Kolchin-Sevastyanov-Chistyakov Al azar Asignaciones , Knuth El arte de la programación Programación, vol. 2 y Flajolet & Sedgwick Combinatoria analítica todos los discuten estos problemas y pueden contener la asintótica precisa de la distribución que está buscando.

III.10 en Flajolet y Sedgewick da la respuesta de Poisson $1−\exp(−t/n)$ cuando la relación se mantiene constante, pero otros regímenes asintóticos son también de interés, especialmente en los problemas de problemas de hashing. El problema del cumpleaños es cuando $t=O(n^{1/2})$ y se obtienen estadísticas del número de colisiones. Para t=n^k con 1/2