Pregunta de probabilidad: cuántos ciclos antes de que se elijan todos los elementos

Question

Tengo un contenedor de 100 artículos amarillos.

Elijo 2 al azar y pinto cada una de ellas azul.

Devuelvo los artículos al contenedor.

Si repito este proceso, en promedio ¿cuántos ciclos voy a hacer antes de que se pinten los 100 elementos?

Obviamente es 50 (100/2) si no hay reemplazo. Pero en este caso, los artículos se devuelven al contenedor, por lo que el mismo artículo se puede elegir a menudo.

¿Qué pasa si elegimos 3?

Answer 1

Podría calcular la cifra exacta de la cantidad esperada mediante la recursividad y encontrar la media es de alrededor de $258.32$ con una desviación estándar de alrededor de $62.59$.

Alternativamente, si usted tuvo las bolas de una en una, este sería el Cupón Colector del Problema, con un valor esperado de $100H_{100} \approx 518.74$: entonces usted necesidad de reducir a la mitad este, como usted está tomando elementos de dos en dos, dando así acerca de $259.37$. La respuesta real difiere de este por dos razones: su par de elementos son distintos, reduciendo el número necesario, pero esto es ligeramente compensado por la posibilidad de que el primer elemento de la final de la pareja es el último que necesita ser pintado.

Answer 2

Si elige 1 artículo cada vez, entonces el tiempo esperado hasta que todos los artículos estén pintados es$n \ln(n)$; Este es el problema del recolector de cupones.

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

Si toma 2 al azar cada vez, debería tomar aproximadamente la mitad de ese tiempo, porque acelera el proceso en un factor de dos, entonces aproximadamente$\frac{n \ln(n)}{2} $.