Problema del coleccionista de cupones
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/46/Coupon_collector_problem.svg/400px-Coupon_collector_problem.svg.png)
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:
Cierta marca de cereales contiene un cupón en cada caja. Si hay distintos tipos de cupones, ¿cuál es la probabilidad de que se necesitarán más de cajas para coleccionar todos los cupones? De forma alternativa: dados cupones, ¿cuántas muestras aleatorias con reemplazo se pueden esperar para poder seleccionar cada tipo de cupón al menos una vez?
El análisis matemático del problema revela que el valor esperado de pruebas necesarias crece a razón de .[Nota 1] Por ejemplo, cuando la respuesta es aproximadamente 225[Nota 2] 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 nuevo 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,[1]
- 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
- Estimador de Watterson
- Paradoja del cumpleaños
Notas
- ↑ 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.
- ↑ El valor esperado de pruebas para coleccionar todos los 50 cupones es La aproximación para este valor esperado nos da, en este caso .
Referencias
- ↑ Flajolet, Philippe; Gardy, Danièle; Thimonier, Loÿs (1992), «Birthday paradox, coupon collectors, caching algorithms and self-organizing search», Discrete Applied Mathematics 39 (3): 207-229, doi:10.1016/0166-218x(92)90177-c Parámetro desconocido
|citeseerx=
ignorado (ayuda).
- Blom, Gunnar; Holst, Lars; Sandell, Dennis (1994), «7.5 Coupon collecting I, 7.6 Coupon collecting II, and 15.4 Coupon collecting III», Problems and Snapshots from the World of Probability, New York: Springer-Verlag, pp. 85-87, 191, ISBN 0-387-94161-4, MR 1265713 .
- Dawkins, Brian (1991), «Siobhan's problem: the coupon collector revisited», The American Statistician 45 (1): 76-82, JSTOR 2685247, doi:10.2307/2685247 .
- Erdős, Paul; Rényi, Alfréd (1961), «On a classical problem of probability theory», Magyar Tudományos Akadémia Matematikai Kutató Intézetének Közleményei 6: 215-220, MR 0150807 .
- Laplace, Pierre-Simon (1812), Théorie analytique des probabilités, pp. 194-195 .
- Newman, Donald J.; Shepp, Lawrence (1960), «The double dixie cup problem», American Mathematical Monthly 67 (1): 58-61, JSTOR 2308930, MR 0120672, doi:10.2307/2308930 .
- Flajolet, Philippe; Gardy, Danièle; Thimonier, Loÿs (1992), «Birthday paradox, coupon collectors, caching algorithms and self-organizing search», Discrete Applied Mathematics 39 (3): 207-229, MR 1189469, doi:10.1016/0166-218X(92)90177-C .
- Isaac, Richard (1995), «8.4 The coupon collector's problem solved», The Pleasures of Probability, Undergraduate Texts in Mathematics, New York: Springer-Verlag, pp. 80-82, ISBN 0-387-94415-X, MR 1329545 .
- Motwani, Rajeev; Raghavan, Prabhakar (1995), «3.6. The Coupon Collector's Problem», Randomized algorithms, Cambridge: Cambridge University Press, pp. 57-63, ISBN 9780521474658, MR 1344451 .
Enlaces externos
- Coupon Collector Problem por Ed Pegg, Jr., en el Proyecto de Demostraciones Wolfram (en inglés)
- How Many Singles, Doubles, Triples, Etc., Should The Coupon Collector Expect?, nota por Doron Zeilberger (en inglés).
- Esta obra contiene una traducción derivada de «Coupon collector's problem» de Wikipedia en inglés, concretamente de esta versión del 19 de junio de 2021, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 4.0 Internacional.