Problema do colecionador de cupons

Gráfico do número de cupons, n versus o número esperado de tentativas (ou seja, tempo) necessárias para coletar todos eles, E (T)

Na teoria das probabilidades, o problema do coletor de cupons descreve os concursos "colete todos os cupons e ganhe". Ele faz a seguinte pergunta: "Se cada caixa de uma marca de cereais contém um cupom e existem n tipos diferentes de cupons, qual é a probabilidade de que mais de t caixas precisem ser compradas para coletar todos os n cupons?" Uma declaração alternativa é: Dados os n cupons, quantos cupons você espera que precise remover com substituição antes de remover cada um dos cupons pelo menos uma vez?" A análise matemática do problema revela que o número esperado de tentativas necessárias cresce na ordem de $\mathrm{\Theta }(n\log (n))$.Predefinição:Efn Por exemplo, quando n = 50 são necessários, em média, cerca de 225 testes.Predefinição:Efn para coletar todos os 50 cupons.

Solução

Calculando o valor esperado

Seja T o tempo para recolher todos n cupons, e deixe t_i ser o tempo adicional para de recolher o i-ésimo cupom depois de i - 1 cupons terem sido coletados. Trate T e T_i como variáveis aleatórias . Observe que a probabilidade de coletar um cupom inédito é $p_i=\frac{n-i+1}{n}$ . Portanto, $t_i$ tem distribuição geométrica com valor esperado $\frac{1}{p_i}$ . Pela linearidade do valor esperado, temos:

$\begin{array}{cc}\mathrm{E}(T)& =\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}$

Aqui H_n é o n-ésimo número harmônico. Usando a assintótica dos números harmônicos, obtemos:

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

Onde $\gamma \approx 0.5772156649$ é a constante de Euler-Mascheroni .

Agora, pode-se usar a desigualdade de Markov para limitar a probabilidade desejada:

$\mathrm{P}(T\ge cn{H}_n)\le \frac{1}{c}.$

Cálculo da variância

Usando a independência das variáveis aleatórias t_i, obtemos:

$\begin{array}{cc}\mathrm{Var}(T)& =\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}$

Como $\frac{{\pi }^2}{6}=\frac{1}{1^2}+\frac{1}{2^2}+\cdots +\frac{1}{n^2}+\cdots$ (veja o problema da Basiléia).

Agora, pode-se usar a desigualdade de Chebyshev para limitar a probabilidade desejada:

$\mathrm{P}(|T-n{H}_n|\ge cn)\le \frac{{\pi }^2}{6c^2}.$

Estimativas de cauda

Um limite superior diferente pode ser derivado da seguinte observação. Seja $Z_i^r$ um evento em que o $i$-ésimo cupom não foi escolhido nos primeiros $r$ ensaios. Então:

$\begin{array}{c}P\left[Z_i^r\right]={(1-\frac{1}{n})}^r\le e^{-r/n}\end{array}$

Assim, para $r=\beta n\log n$, temos $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}$

Extensões e generalizações

• Pierre-Simon Laplace, mas também Paul Erdős e Alfréd Rényi, provaram o teorema do limite para a distribuição de T. Esse resultado é uma extensão adicional dos limites anteriores.

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

• Donald J. Newman e Lawrence Shepp fizeram uma generalização do problema do colecionador de cupons quando é necessário coletar m cópias de cada cupom. Seja T _m ser a primeira vez m cópias de cada cupom são recolhidos. Eles mostraram que o valor esperado neste caso satisfaz:

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

Aqui m é fixo. Quando m = 1, obtemos a fórmula anterior para a expectativa.

• Generalização comum, também devido a Erdős e 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 }.$

• No caso geral de uma distribuição de probabilidade não uniforme, de acordo com Philippe Flajolet,

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

Ver também

• Paradoxo do aniversário

Notas

• Predefinição:Citation.
• Predefinição:Citation.
• Predefinição:Citation.
• Predefinição:Citation.
• Predefinição:Citation
• Predefinição:Citation.
• Predefinição:Citation.
• Predefinição:Citation.

Ligações externas

• " Problem Collector Problem ", de Ed Pegg, Jr., o Wolfram Demonstrations Project . Pacote Mathematica.
• Quantos singles, duplos, triplos, etc., o colecionador de cupons deve esperar?, uma breve nota de Doron Zeilberger .