Problema do colecionador de cupons
![](http://upload.wikimedia.org/wikipedia/commons/thumb/4/46/Coupon_collector_problem.svg/400px-Coupon_collector_problem.svg.png)
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 .[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 ti ser o tempo adicional para de recolher o i-ésimo cupom depois de i - 1 cupons terem sido coletados. Trate T e Ti como variáveis aleatórias . Observe que a probabilidade de coletar um cupom inédito é . Portanto, tem distribuição geométrica com valor esperado . Pela linearidade do valor esperado, temos:
Aqui Hn é o n-ésimo número harmônico. Usando a assintótica dos números harmônicos, obtemos:
Onde é a constante de Euler-Mascheroni .
Agora, pode-se usar a desigualdade de Markov para limitar a probabilidade desejada:
Cálculo da variância
Usando a independência das variáveis aleatórias ti, obtemos:
Como (veja o problema da Basiléia).
Agora, pode-se usar a desigualdade de Chebyshev para limitar a probabilidade desejada:
Estimativas de cauda
Um limite superior diferente pode ser derivado da seguinte observação. Seja um evento em que o -ésimo cupom não foi escolhido nos primeiros ensaios. Então:
Assim, para , temos .
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.
- 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:
- 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:
- No caso geral de uma distribuição de probabilidade não uniforme, de acordo com Philippe Flajolet,[1]
Ver também
Notas
Referências
- ↑ Flajolet, Philippe; Gardy, Danièle; Thimonier, Loÿs (1992), «Birthday paradox, coupon collectors, caching algorithms and self-organizing search», Discrete Applied Mathematics, 39 (3): 207–229, doi:10.1016/0166-218x(92)90177-c
- Blom, Gunnar; Holst, Lars; Sandell, Dennis (1994), «7.5 Coupon collecting I, 7.6 Coupon collecting II, and 15.4 Coupon collecting III», Problems and Snapshots from the World of Probability, ISBN 0-387-94161-4, New York: Springer-Verlag, pp. 85–87, 191, MR 1265713 .
- Dawkins, Brian (1991), «Siobhan's problem: the coupon collector revisited», The American Statistician, 45 (1): 76–82, JSTOR 2685247, doi:10.2307/2685247 .
- Erdős, Paul; Rényi, Alfréd (1961), «On a classical problem of probability theory» (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, pp. 194–195 .
- Newman, Donald J.; Shepp, Lawrence (1960), «The double dixie cup problem», American Mathematical Monthly, 67 (1): 58–61, JSTOR 2308930, MR 0120672, doi:10.2307/2308930
- Flajolet, Philippe; Gardy, Danièle; Thimonier, Loÿs (1992), «Birthday paradox, coupon collectors, caching algorithms and self-organizing search», Discrete Applied Mathematics, 39 (3): 207–229, MR 1189469, doi:10.1016/0166-218X(92)90177-C .
- Isaac, Richard (1995), «8.4 The coupon collector's problem solved», The Pleasures of Probability, ISBN 0-387-94415-X, Undergraduate Texts in Mathematics, New York: Springer-Verlag, pp. 80–82, MR 1329545 .
- Motwani, Rajeev; Raghavan, Prabhakar (1995), «3.6. The Coupon Collector's Problem», Randomized algorithms, ISBN 9780521474658, Cambridge: Cambridge University Press, pp. 57–63, MR 1344451 .
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 .