# Problema do colecionador de cupons

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