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:

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

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

${\displaystyle {\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í, ${\displaystyle H_{n}}$ es el ${\displaystyle n}$-ésimo número armónico. Usando la asíntota de los números armónicos, se obtiene:

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

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

${\displaystyle \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 ${\displaystyle k}$ el número de cupones ya coleccionados, entonces:

${\displaystyle {\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 ${\displaystyle k=0}$ se obtiene el resultado original.

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

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

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

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

${\displaystyle {\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 ${\displaystyle r=\beta n\log n}$, se tiene ${\displaystyle P\left[{Z}_{i}^{r}\right]\leq e^{(-\beta n\log n)/n}=n^{-\beta }}$.

${\displaystyle {\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}}}$

• Tanto Pierre-Simon Laplace, como Paul Erdős y Alfréd Rényi, probaron el teorema del límite para la distribución de ${\displaystyle T}$. Este resulrado es una extensión a las cotas anteriores.

${\displaystyle \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 ${\displaystyle m}$ copias de cada cupón. Sea ${\displaystyle T_{m}}$ la primera vez que se coleccionan ${\displaystyle m}$ copias de cada cupón. Demostraron que la expectativa en este caso satisface:

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

En este caso, ${\displaystyle m}$ es un valor fijo. Cuando ${\displaystyle 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:

${\displaystyle \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,^[1]​

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

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

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

• Estimador de Watterson
• Paradoja del cumpleaños

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