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 ${\displaystyle \Theta (n\log(n))}$.^[a] Por exemplo, quando n = 50 são necessários, em média, cerca de 225 testes.^[b] 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 é ${\displaystyle p_{i}={\frac {n-i+1}{n}}}$ . Portanto, ${\displaystyle t_{i}}$ tem distribuição geométrica com valor esperado ${\displaystyle {\frac {1}{p_{i}}}}$ . Pela linearidade do valor esperado, temos:

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

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

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

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

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

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

${\displaystyle \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 ${\displaystyle {Z}_{i}^{r}}$ um evento em que o ${\displaystyle i}$-ésimo cupom não foi escolhido nos primeiros ${\displaystyle r}$ ensaios. Então:

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

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

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.

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

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

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

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

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

Notas

Referências

 

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 .