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 $\Theta (n\log(n))$. Por exemplo, quando n = 50 são necessários, em média, cerca de 225 testes. 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{aligned}\operatorname {E} (T)&=\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}}$

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

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

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

Cálculo da variância

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

${\begin{aligned}\operatorname {Var} (T)&=\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}}$

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:

$\operatorname {P} \left(|T-nH_{n}|\geq cn\right)\leq {\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{aligned}P\left[{Z}_{i}^{r}\right]=\left(1-{\frac {1}{n}}\right)^{r}\leq e^{-r/n}\end{aligned}}$

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

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.

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

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

$\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 .$

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

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

Ver também

• Paradoxo do aniversário

 

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 .