Problema del coleccionista de cupones
# Problema del coleccionista de cupones

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:

   $n$
   $t$
   $n$
   $n$

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 ditribució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.
