Problema do colecionador de cupons

Origem: Wikipédia, a enciclopédia livre.
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 .[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[editar | editar código-fonte]

Calculando o valor esperado[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

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[editar | editar código-fonte]

  • 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[editar | editar código-fonte]

Notas[editar | editar código-fonte]

  1. Ao longo de todo artigo, log se refere à função logaritmo natural, isto é o logaritmo na base e . O uso de Θ se refere à notação grade big O.
  2. E(50) = 50 (1 + 1/2 + 1/3 + ... + 1/50) = 224.9603. A aproximação para este valor esperado fornece .

Referências

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

 

Ligações externas[editar | editar código-fonte]