Problema del coleccionista de cupones

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:

Cierta marca de cereales contiene un cupón en cada caja. Si hay $n$ distintos tipos de cupones, ¿cuál es la probabilidad de que se necesitarán más de $t$ cajas para coleccionar todos los $n$ cupones? De forma alternativa: dados $n$ 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 $\Theta (n\log(n))$.​ Por ejemplo, cuando $n=50$ la respuesta es aproximadamente 225​ pruebas en promedio para coleccionar todos los 50 cupones.

Solución

Cálculo del valor esperado

Sea el tiempo $T$ el número de pruebas necesarias para coleccionar todos los $n$ cupones, y sea $t_{i}$ el tiempo para coleccionar el $i$-ésimo cupón después de que se tienen $i-1$ cupones en la colección. Entonces $T=t_{1}+\cdots +t_{n}$. Se puede pensar en $T$ y $t_{i}$ como variables aleatorias. Se debe observar que la probabilidad de añadir un cupón nuevo es $p_{i}={\frac {n-(i-1)}{n}}={\frac {n-i+1}{n}}$. Por lo tanto, $t_{i}$ tiene una distribución geométrica con valor esperado ${\frac {1}{p_{i}}}={\frac {n}{n-i+1}}$. Por la linealidad de la esperanza se tiene:

${\begin{aligned}\operatorname {E} (T)&{}=\operatorname {E} (t_{1}+t_{2}+\cdots +t_{n})\\&{}=\operatorname {E} (t_{1})+\operatorname {E} (t_{2})+\cdots +\operatorname {E} (t_{n})\\&{}={\frac {1}{p_{1}}}+{\frac {1}{p_{2}}}+\cdots +{\frac {1}{p_{n}}}\\&{}={\frac {n}{n}}+{\frac {n}{n-1}}+\cdots +{\frac {n}{1}}\\&{}=n\cdot \left({\frac {1}{1}}+{\frac {1}{2}}+\cdots +{\frac {1}{n}}\right)\\&{}=n\cdot H_{n}.\end{aligned}}$

Aquí, $H_{n}$ es el $n$-ésimo número armónico. Usando la asíntota de los números armónicos, se obtiene:

$\operatorname {E} (T)=n\cdot H_{n}=n\log n+\gamma n+{\frac {1}{2}}+O(1/n),$

donde $\gamma \approx 0.5772156649$ es la Constante de Euler–Mascheroni.

Aquí es posible usar la desigualdad de Márkov para establecer límites a la probabilidad deseada:

$\operatorname {P} (T\geq cnH_{n})\leq {\frac {1}{c}}.$

Se puede ver que la anterior puede ser modificada levemente para el case en el que ya se tienen algunos de los cupones. sea $k$ el número de cupones ya coleccionados, entonces:

${\begin{aligned}\operatorname {E} (T_{k})&{}=\operatorname {E} (t_{k+1}+t_{k+2}+\cdots +t_{n})\\&{}=n\cdot \left({\frac {1}{1}}+{\frac {1}{2}}+\cdots +{\frac {1}{n-k}}\right)\\&{}=n\cdot H_{n-k}\end{aligned}}$

Se aprecia que cuando $k=0$ se obtiene el resultado original.

Cálculo de la varianza

Usando la independencia de las variables aleatorias $t_{i}$ se obtienen:

${\begin{aligned}\operatorname {Var} (T)&{}=\operatorname {Var} (t_{1}+\cdots +t_{n})\\&{}=\operatorname {Var} (t_{1})+\operatorname {Var} (t_{2})+\cdots +\operatorname {Var} (t_{n})\\&{}={\frac {1-p_{1}}{p_{1}^{2}}}+{\frac {1-p_{2}}{p_{2}^{2}}}+\cdots +{\frac {1-p_{n}}{p_{n}^{2}}}\\&{}<\left({\frac {n^{2}}{n^{2}}}+{\frac {n^{2}}{(n-1)^{2}}}+\cdots +{\frac {n^{2}}{1^{2}}}\right)\\&{}=n^{2}\cdot \left({\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+\cdots +{\frac {1}{n^{2}}}\right)\\&{}<{\frac {\pi ^{2}}{6}}n^{2}\end{aligned}}$

ya que ${\frac {\pi ^{2}}{6}}={\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+\cdots +{\frac {1}{n^{2}}}+\cdots$ (véase problema de Basilea).

Ahora es posible usar la desigualdad de Chebyshev para establecer la cota:

$\operatorname {P} \left(|T-nH_{n}|\geq cn\right)\leq {\frac {\pi ^{2}}{6c^{2}}}.$

Estimaciones de cola

Es posible establecer una cota superior diferente a partir de la siguiente observación. Sea${Z}_{i}^{r}$ el evento en el que el $i$-ésimo cupón no fue seleccionado en las primeras $r$ pruebas. Entonces:

${\begin{aligned}P\left[{Z}_{i}^{r}\right]\leq \left(1-{\frac {1}{n}}\right)^{r}\leq e^{-r/n}\end{aligned}}$

Por lo tanto, como $r=\beta n\log n$, se tiene $P\left[{Z}_{i}^{r}\right]\leq e^{(-\beta n\log n)/n}=n^{-\beta }$.

${\begin{aligned}P\left[T>\beta n\log n\right]=P\left[\bigcup _{i}{Z}_{i}^{\beta n\log n}\right]\leq n\cdot P[{Z}_{1}^{\beta n\log n}]\leq n^{-\beta +1}\end{aligned}}$

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 $T$. Este resulrado es una extensión a las cotas anteriores.

$\operatorname {P} (T<n\log n+cn)\to e^{-e^{-c}},{\text{ as }}n\to \infty .$

• Donald J. Newman y Lawrence Shepp mostraron una generalización del problema cuando se necesitan coleccionar $m$ copias de cada cupón. Sea $T_{m}$ la primera vez que se coleccionan $m$ copias de cada cupón. Demostraron que la expectativa en este caso satisface:

$\operatorname {E} (T_{m})=n\log n+(m-1)n\log \log n+O(n),{\text{ as }}n\to \infty .$

En este caso, $m$ es un valor fijo. Cuando $m=1$ se obtiene la fórmula anterior para el valor esperado.

• Una generalización común, también demostrada por Erdős y Rényi:

$\operatorname {P} \left(T_{m}<n\log n+(m-1)n\log \log n+cn\right)\to e^{-e^{-c}/(m-1)!},{\text{ as }}n\to \infty .$

• En el caso general de una distribución de probabilidad no uniforme, de acuerdo aPhilippe Flajolet,​

$\operatorname {E} (T_{m})=\int _{0}^{\infty }\left(1-\prod _{i=1}^{m}\left(1-e^{-p_{i}t}\right)\right)dt.$

Esto es igual a:

$\operatorname {E} (T_{m})=\sum _{q=0}^{m-1}(-1)^{m-1-q}\sum _{|J|=q}{\frac {1}{1-P_{J}}}$

donde $m$ denota el número de cupones que deben ser coleccionados, y $P_{J}$ la probabilidad de tener cualquier cupón en el conjunto $J$ de cupones.

Véase también

• Estimador de Watterson
• Paradoja del cumpleaños

Referencias

• 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).