miniaturadaimagem|400x400px| 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 . 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 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,

História O problema apareceu pela primeira vez em On measurement of change de 1708 do matemático francês Abraham de Moivre.

Aplicações O problema do colecionador pode ser aplicado aos jogos de loterias. Leite, Pereira e Rodrigues estudaram o seguinte problema: toda semana, uma casa lotérica sorteia um número de números distintos dos primeiros números naturais. Um apostador escolhe um conjunto de números. Se esse conjunto for o mesmo que os sorteados, o apostador vence o prêmio acumulado. Após algumas semanas, percebe-se que números, dentre os , não foram sorteados. Quantas semanas são esperadas até que todos os números sejam sorteados?

Outra aplicação seria buscar a quantidade de pacotes de figurinha para completar uma coleção de álbuns de figurinha. Sob esse problema, também é possível verificar a economia aproximada ao praticar a troca de cromos.

O problema também pode ser interpretado como um sistema propagador de rumores e possibilita o desenvolvimento de uma rede de grafos.

Ver também Paradoxo do aniversário Jogos gacha

Notas

 Bibliografia

. . . .

. . .

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 .

Categoria:Problemas matemáticos Categoria:Teoria das probabilidades