El problema del cobrador de cupones

Problema en la teoría de la probabilidad.

Gráfica del número de cupones, n versus el número esperado de intentos (es decir, tiempo) necesarios para recolectarlos todos, E  ( T  )

En teoría de la probabilidad , el problema del recolector de cupones se refiere al análisis matemático de los concursos de "recoge todos los cupones y gana". Plantea la siguiente pregunta: si cada caja de un producto determinado (por ejemplo, cereales para el desayuno) 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 afirmación alternativa es: dados n cupones, ¿cuántos cupones espera que necesitará retirar 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 crece a medida que . ^[a] Por ejemplo, cuando n  = 50, se necesitan alrededor de 225 ^[b] ensayos en promedio para recolectar los 50 cupones. ${\displaystyle \Theta (n\log(n))}$

Solución

A través de funciones generadoras

Por definición de los números de Stirling del segundo tipo , la probabilidad de que se necesiten exactamente T sorteos es

$${\displaystyle {\frac {S(T-1,n-1)n!}{n^{T}}}}$$

T

$${\displaystyle f_{k}(x):=\sum _{T}S(T,k)x^{T}=\prod _{r=1}^{k}{\frac {x}{1-rx}}}$$

k ${\displaystyle (n-1)!((D_{x}x)^{k}f_{n-1}(x)){\Big |}_{x=1/n}}$ ${\displaystyle D_{x}}$ ${\displaystyle d/dx}$

$${\displaystyle \sum _{T}{\frac {S(T-1,n-1)n!}{n^{T}}}=(n-1)!f_{n-1}(1/n)=(n-1)!\times \prod _{r=1}^{n-1}{\frac {1/n}{1-r/n}}=1}$$

${\displaystyle (n-1)!(D_{x}xf_{n-1}(x)){\Big |}_{x=1/n}}$ ${\displaystyle nH_{n}}$

Calculando la expectativa

Sea el tiempo T el número de sorteos necesarios para recolectar todos los n cupones, y sea t _i el tiempo para recolectar el i -ésimo cupón después de que  se hayan recolectado i − 1 cupones. Entonces . Piense en T y t _i como variables aleatorias . Observe que la probabilidad de cobrar un nuevo cupón es . Por tanto, tiene distribución geométrica con expectativa . Por la linealidad de las expectativas tenemos: ${\displaystyle T=t_{1}+\cdots +t_{n}}$ ${\displaystyle p_{i}={\frac {n-(i-1)}{n}}={\frac {n-i+1}{n}}}$ ${\displaystyle t_{i}}$ ${\displaystyle {\frac {1}{p_{i}}}={\frac {n}{n-i+1}}}$

${\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í H _n es el n -ésimo número armónico . Usando las asintóticas de los números armónicos obtenemos:

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

¿Dónde está la constante de Euler-Mascheroni ? ${\displaystyle \gamma \approx 0.5772156649}$

Usando la desigualdad de Markov para limitar la probabilidad deseada:

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

Lo anterior se puede modificar ligeramente para manejar el caso en el que ya hayamos recolectado algunos de los cupones. Sea k el número de cupones ya cobrados, 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}}}$

Y cuando obtengamos el resultado original. ${\displaystyle k=0}$

Calculando la varianza

Usando la independencia de variables aleatorias ti _, obtenemos:

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

desde (ver problema de Basilea ). ${\displaystyle {\frac {\pi ^{2}}{6}}={\frac {1}{1^{2}}}+{\frac {1}{2^{2}}}+\cdots +{\frac {1}{n^{2}}}+\cdots }$

Limite la probabilidad deseada utilizando la desigualdad de Chebyshev :

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

Estimaciones de cola

Una estimación de cola más fuerte para la cola superior se obtiene de la siguiente manera. Denotemos el evento en el que el -ésimo cupón no se eligió en las primeras pruebas. Entonces ${\displaystyle {Z}_{i}^{r}}$ ${\displaystyle i}$ ${\displaystyle r}$

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

Así, para , tenemos . A través de una unión unida sobre los cupones, obtenemos ${\displaystyle r=\beta n\log n}$ ${\displaystyle P\left[{Z}_{i}^{r}\right]\leq e^{(-\beta n\log n)/n}=n^{-\beta }}$ ${\displaystyle n}$

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

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. Se encuentra una prueba en. ^[1]

${\displaystyle \operatorname {P} (T<n\log n+cn)\to e^{-e^{-c}},{\text{ as }}n\to \infty .}$que es una distribución de Gumbel . En la siguiente sección se ofrece una prueba sencilla mediante martingalas.

• Donald J. Newman y Lawrence Shepp hicieron una generalización del problema del coleccionista de cupones cuando es necesario 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:

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

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:

${\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, según Philippe Flajolet et al. ^[2]

${\displaystyle \operatorname {E} (T)=\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)=\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 a recolectar y P _J denota la probabilidad de obtener cualquier cupón del conjunto de cupones J.

martingalas

Esta sección se basa en. ^[3]

Defina un proceso aleatorio discreto dejando ser el número de cupones que aún no se ven después de los sorteos. El proceso aleatorio es solo una secuencia generada por una cadena de Markov con estados y probabilidades de transición. ${\displaystyle N(0),N(1),\dots }$ ${\displaystyle N(t)}$ ${\displaystyle t}$ ${\displaystyle n,n-1,\dots ,1,0}$

$${\displaystyle p_{i\to i-1}=i/n,\quad p_{i\to i}=1-i/n}$$

$${\displaystyle M(t):=N(t)\left({\frac {n}{n-1}}\right)^{t}}$$

martingala

$${\displaystyle E[M(t+1)|M(t)]=(n/(n-1))^{t+1}E[N(t+1)|N(t)]=(n/(n-1))^{t+1}(N(t)-N(t)/n)=M(t)}$$

${\displaystyle E[N(t)]=n(1-1/n)^{t}}$ ${\displaystyle \lim _{n\to \infty }E[N(n\ln n+cn)]=e^{-c}}$ ${\displaystyle c>0}$ ${\displaystyle T}$

De manera más general, cada uno es un proceso de martingala, que nos permite calcular todos los momentos de . Por ejemplo, ${\displaystyle \left({\frac {n}{n-k}}\right)^{t}N(t)\cdots (N(t)-k+1)}$ ${\displaystyle N(t)}$

$${\displaystyle E[N(t)^{2}]=n(n-1)\left({\frac {n-2}{n}}\right)^{t}+n\left({\frac {n-1}{n}}\right)^{t},\quad n\geq 2}$$

${\displaystyle \lim _{n\to \infty }Var[N(n\ln n+cn)]=e^{-c}}$

$${\displaystyle \lim _{n\to \infty }E[N(n\ln n+cn)\cdots (N(n\ln n+cn)-k+1)]=e^{-kc}}$$

${\displaystyle N(n\ln n+cn)}$ ${\displaystyle 0,1,2,\dots }$

Sea la variable aleatoria con distribución límite. Tenemos ${\displaystyle N}$

$${\displaystyle {\begin{aligned}E[1]&=1\\E[N]&=e^{-c}\\E[N(N-1)]&=e^{-2c}\\E[N(N-1)(N-2)]&=e^{-3c}\\&\vdots \end{aligned}}}$$

${\displaystyle t}$

$${\displaystyle E[1+Nt/1!+N(N-1)t^{2}/2!+\cdots ]=1+e^{-c}t/1!+e^{-2c}t^{2}/2!+\cdots }$$

${\displaystyle E[(1+t)^{N}]=e^{e^{-c}t}}$

En el límite tenemos , que es precisamente lo que establece la ley del límite. ${\displaystyle t\to 0}$ ${\displaystyle Pr(N=0)=e^{-e^{-c}}}$

Al tomar la derivada varias veces, encontramos que es una distribución de Poisson . ${\displaystyle d/dt}$ ${\displaystyle Pr(N=k)={\frac {e^{-kc}}{k!}}e^{-e^{-c}}}$

Ver también

• Monopoly de McDonald's : un ejemplo del problema del coleccionista de cupones que aumenta aún más el desafío al hacer que algunos cupones del conjunto sean más raros.
• estimador de Watterson
• problema de cumpleaños

Notas

1. Aquí y a lo largo de este artículo, "log" se refiere al logaritmo natural en lugar de a un logaritmo con alguna otra base. El uso de Θ aquí invoca la notación O grande .
2. 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 . ${\displaystyle n\log n+\gamma n+1/2}$ ${\displaystyle 50\log 50+50\gamma +1/2\approx 195.6011+28.8608+0.5\approx 224.9619}$

Referencias

1. Mitzenmacher, Michael (2017). Probabilidad y computación: aleatorización y técnicas probabilísticas en algoritmos y análisis de datos . Eli Upfal (2ª ed.). Cambridge, Reino Unido. Teorema 5.13. ISBN 978-1-107-15488-9. OCLC  960841613.{{cite book}}: CS1 maint: location missing publisher (link)
2. 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 
3. Kan, Dakota del Norte (1 de mayo de 2005). "Enfoque martingala para el problema del cobro de cupones". Revista de Ciencias Matemáticas . 127 (1): 1737-1744. doi :10.1007/s10958-005-0134-y. ISSN  1573-8795.

• 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, señor  1265713.
• Dawkins, Brian (1991), "El problema de Siobhan: el cobrador de cupones revisitado", 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), "El problema de la doble taza de dixie", 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", Los placeres de la probabilidad, Textos de pregrado en matemáticas , Nueva York: Springer-Verlag, págs. 80–82, ISBN 0-387-94415-X, señor  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, SEÑOR  1344451.

enlaces externos

• "Problema del coleccionista de cupones" de Ed Pegg, Jr. , Proyecto de demostraciones de Wolfram . Paquete de matemáticas.
• ¿Cuántos sencillos, dobles, triples, etc. debe esperar el coleccionista de cupones? , una breve nota de Doron Zeilberger .