thumb|400px|Gráfica del número de cupones n contra el número esperado de pruebas (es decir, el tiempo) necesario para tener una colección completa de ellos, E (T ). En probabilidad y estadística, el problema del coleccionista de cupones describe los concursos del tipo «colecciona todos los cupones y gana». Se trata de la siguiente pregunta:
El análisis matemático del problema revela que el valor esperado de pruebas necesarias crece a razón de .Aquí y a lo largo del artículo, "log" se refiere al logaritmo natural y no logaritmo en ninguna otra base. El uso de se refiere a la Notación O grande usada para describir cotas. Por ejemplo, cuando la respuesta es aproximadamente 225El valor esperado de pruebas para coleccionar todos los 50 cupones es La aproximación para este valor esperado nos da, en este caso . pruebas en promedio para coleccionar todos los 50 cupones.
Solución
Cálculo del valor esperado Sea el tiempo el número de pruebas necesarias para coleccionar todos los cupones, y sea el tiempo para coleccionar el -ésimo cupón después de que se tienen cupones en la colección. Entonces . Se puede pensar en y como variables aleatorias. Se debe observar que la probabilidad de añadir un cupón es . Por lo tanto, tiene una distribución geométrica con valor esperado . Por la linealidad de la esperanza se tiene:
Aquí, es el -ésimo número armónico. Usando la asíntota de los números armónicos, se obtiene:
donde es la Constante de Euler–Mascheroni.
Aquí es posible usar la desigualdad de Márkov para establecer límites a la probabilidad deseada:
Se puede ver que la anterior puede ser modificada levemente para el case en el que ya se tienen algunos de los cupones. sea el número de cupones ya coleccionados, entonces:
Se aprecia que cuando se obtiene el resultado original.
Cálculo de la varianza Usando la independencia de las variables aleatorias se obtienen:
ya que (véase problema de Basilea).
Ahora es posible usar la desigualdad de Chebyshev para establecer la cota:
Estimaciones de cola Es posible establecer una cota superior diferente a partir de la siguiente observación. Sea el evento en el que el -ésimo cupón no fue seleccionado en las primeras pruebas. Entonces:
Por lo tanto, como , se tiene .
Extensiones y generalizaciones Tanto Pierre-Simon Laplace, como Paul Erdős y Alfréd Rényi, probaron el teorema del límite para la distribución de . Este resulrado es una extensión a las cotas anteriores.
Donald J. Newman y Lawrence Shepp mostraron una generalización del problema cuando se necesitan coleccionar copias de cada cupón. Sea la primera vez que se coleccionan copias de cada cupón. Demostraron que la expectativa en este caso satisface:
En este caso, es un valor fijo. Cuando se obtiene la fórmula anterior para el valor esperado.
Una generalización común, también demostrada por Erdős y Rényi:
En el caso general de una distribución de probabilidad no uniforme, de acuerdo aPhilippe Flajolet,
Esto es igual a:
donde denota el número de cupones que deben ser coleccionados, y la probabilidad de tener cualquier cupón en el conjunto de cupones.
Véase también Paradoja del cumpleaños
Notas
Referencias
Enlaces externos Coupon Collector Problem por Ed Pegg, Jr., en el Proyecto de Demostraciones Wolfram How Many Singles, Doubles, Triples, Etc., Should The Coupon Collector Expect?, nota por Doron Zeilberger .
Categoría:Teoría de probabilidades