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:

El análisis matemático del problema revela que el valor esperado de pruebas necesarias crece a razón de $\mathrm{\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 Plantilla:Enf 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{array}{cc}\mathrm{E}(T)& =\mathrm{E}(t_1+t_2+\cdots +t_n)\\ & =\mathrm{E}(t_1)+\mathrm{E}(t_2)+\cdots +\mathrm{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 (\frac{1}{1}+\frac{1}{2}+\cdots +\frac{1}{n})\\ & =n\cdot H_n.\end{array}$

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

$\mathrm{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:

$\mathrm{P}(T\ge cn{H}_n)\le \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{array}{cc}\mathrm{E}(T_k)& =\mathrm{E}(t_{k+1}+t_{k+2}+\cdots +t_n)\\ & =n\cdot (\frac{1}{1}+\frac{1}{2}+\cdots +\frac{1}{n-k})\\ & =n\cdot H_{n-k}\end{array}$

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{array}{cc}\mathrm{Var}(T)& =\mathrm{Var}(t_1+\cdots +t_n)\\ & =\mathrm{Var}(t_1)+\mathrm{Var}(t_2)+\cdots +\mathrm{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}\\ & <(\frac{n^2}{n^2}+\frac{n^2}{(n-1{)}^2}+\cdots +\frac{n^2}{1^2})\\ & =n^2\cdot (\frac{1}{1^2}+\frac{1}{2^2}+\cdots +\frac{1}{n^2})\\ & <\frac{{\pi }^2}{6}{n}^2\end{array}$

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:

$\mathrm{P}(|T-n{H}_n|\ge cn)\le \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{array}{c}P\left[Z_i^r\right]\le {(1-\frac{1}{n})}^r\le e^{-r/n}\end{array}$

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

$\begin{array}{c}P[T>\beta n\log n]=P\left[\bigcup _i{Z}_i^{\beta n\log n}\right]\le n\cdot P[Z_1^{\beta n\log n}]\le n^{-\beta +1}\end{array}$

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.

$\mathrm{P}(T<n\log n+cn)\to e^{-e^{-c}},\text{ as }n\to \mathrm{\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:

$\mathrm{E}(T_m)=n\log n+(m-1)n\log \log n+O(n),\text{ as }n\to \mathrm{\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:

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

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

$\mathrm{E}(T_m)=\underset{0}{\overset{\mathrm{\infty }}{\int }}(1-\prod _{i=1}^m(1-e^{-p_{i}t}))dt.$

Esto es igual a:

$\mathrm{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

• Plantilla:Citation
• Plantilla:Citation
• Plantilla:Citation
• Plantilla:Citation
• Plantilla:Citation
• Plantilla:Citation
• Plantilla:Citation
• Plantilla:Citation

Enlaces externos

• Coupon Collector Problem por Ed Pegg, Jr., en el Proyecto de Demostraciones Wolfram Plantilla:En
• How Many Singles, Doubles, Triples, Etc., Should The Coupon Collector Expect?, nota por Doron Zeilberger Plantilla:En.