En la teoría de la probabilidad , el problema del recolector de cupones describe los concursos de "recolectar todos los cupones y ganar". Hace la siguiente pregunta: Si cada caja de una marca de cereales contiene un cupón y hay n tipos diferentes de cupones, ¿cuál es la probabilidad de que sea necesario comprar más de t cajas para recolectar los n cupones? Una declaración alternativa es: Dados n cupones, ¿cuántos cupones espera que necesite sacar con reemplazo antes de haber extraído cada cupón al menos una vez? El análisis matemático del problema revela que el número esperado de ensayos necesarios aumenta a medida que. [a] Por ejemplo, cuando n = 50, se necesitan aproximadamente 225 [b] pruebas en promedio para recolectar los 50 cupones.
Solución
Calculando la expectativa
Deje que el tiempo T es el número de sorteos necesario para recoger todos los n cupones, y dejar que t i ser el momento de recoger el i cupón -ésimo después de i - 1 cupones han sido recogidos. Luego. Piense en T y t i como variables aleatorias . Observe que la probabilidad de obtener un nuevo cupón es. Por lo tanto,tiene distribución geométrica con expectativa. Por la linealidad de las expectativas tenemos:
Aquí H n es el n -ésimo número armónico . Usando las asintóticas de los números armónicos, obtenemos:
dónde es la constante de Euler-Mascheroni .
Ahora se puede usar la desigualdad de Markov para acotar la probabilidad deseada:
Calculando la varianza
Usando la independencia de las variables aleatorias t i , obtenemos:
desde (ver problema de Basilea ).
Ahora se puede usar la desigualdad de Chebyshev para acotar la probabilidad deseada:
Estimaciones de cola
Se puede derivar un límite superior diferente de la siguiente observación. Dejar denotar el evento que el -th cupón no fue recogido en el primero Ensayos. Luego:
Por lo tanto, para , tenemos .
Extensiones y generalizaciones
- Pierre-Simon Laplace , pero también Paul Erdős y Alfréd Rényi , demostraron el teorema del límite para la distribución de T . Este resultado es una extensión adicional de los límites anteriores.
- Donald J. Newman y Lawrence Shepp dieron una generalización del problema del recolector de cupones cuando se deben recolectar m copias de cada cupón. Sea T m la primera vez que se recolectan m copias de cada cupón. Demostraron que la expectativa en este caso satisface:
- Aquí m está fijo. Cuando m = 1 obtenemos la fórmula anterior para la expectativa.
- Generalización común, también debida a Erdős y Rényi:
- En el caso general de una distribución de probabilidad no uniforme, según Philippe Flajolet , [1]
- Esto es igual a
- donde m denota el número de cupones para ser recogida, y P J denota la probabilidad de obtener cualquier cupón en el conjunto de cupones J .
Ver también
Notas
- ^ Aquí ya lo largo de este artículo, "log" se refiere al logaritmo natural en lugar de un logaritmo a alguna otra base. El uso de Θ aquí invoca la notación O grande .
- ^ E (50) = 50 (1 + 1/2 + 1/3 + ... + 1/50) = 224.9603, el número esperado de pruebas para recolectar los 50 cupones. La aproximación para este número esperado da en este caso .
Referencias
- ^ Flajolet, Philippe; Gardy, Danièle; Thimonier, Loÿs (1992), "Paradoja del cumpleaños, recolectores de cupones, algoritmos de almacenamiento en caché y búsqueda autoorganizada", Matemáticas aplicadas discretas , 39 (3): 207–229, CiteSeerX 10.1.1.217.5965 , doi : 10.1016 / 0166-218x (92) 90177-c
- Blom, Gunnar; Holst, Lars; Sandell, Dennis (1994), "7.5 Recolección de cupones I, 7.6 Recolección de cupones II y 15.4 Recolección de cupones III", Problemas e instantáneas del mundo de la probabilidad , Nueva York: Springer-Verlag, págs. 85–87, 191, ISBN 0-387-94161-4, MR 1265713.
- Dawkins, Brian (1991), "Siobhan's problem: the cupon collector revisited", The American Statistician , 45 (1): 76–82, doi : 10.2307 / 2685247 , JSTOR 2685247.
- Erdős, Paul ; Rényi, Alfréd (1961), "Sobre un problema clásico de la teoría de la probabilidad" (PDF) , 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 , págs. 194-195.
- Newman, Donald J .; Shepp, Lawrence (1960), "The double dixie cup problem", American Mathematical Monthly , 67 (1): 58–61, doi : 10.2307 / 2308930 , JSTOR 2308930 , MR 0120672
- Flajolet, Philippe ; Gardy, Danièle; Thimonier, Loÿs (1992), "Paradoja del cumpleaños, recolectores de cupones, algoritmos de almacenamiento en caché y búsqueda autoorganizada" , Matemáticas aplicadas discretas , 39 (3): 207–229, doi : 10.1016 / 0166-218X (92) 90177-C , Señor 1189469.
- Isaac, Richard (1995), "8.4 El problema del coleccionista de cupones resuelto", The Pleasures of Probability , Undergraduate Texts in Mathematics , Nueva York: Springer-Verlag, pp. 80-82, ISBN 0-387-94415-X, MR 1329545.
- Motwani, Rajeev ; Raghavan, Prabhakar (1995), "3.6. El problema del coleccionista de cupones", algoritmos aleatorios , Cambridge: Cambridge University Press, págs. 57–63, ISBN 9780521474658, MR 1344451.
enlaces externos
- " Problema del colector de cupones " por Ed Pegg, Jr. , el Proyecto de demostraciones de Wolfram . Paquete de Mathematica.
- ¿Cuántos individuales, dobles, triples, etc. debe esperar el coleccionista de cupones? , una breve nota de Doron Zeilberger .