O Colecionador de Cupons. Uma marca de cereal coloca um de
tipos diferentes de brindes em cada caixa. Supondo que os brindes sejam distribuídos uniformemente, qual é o número esperado de caixas de cereal que uma pessoa deve comprar para conseguir a coleção completa dos
brindes?
Passo 1
O enunciado dá uma marca de cereal que coloca, em cada caixa, um brinde escolhido uniformemente entre
tipos distintos. Pergunta-se: qual é o número esperado de caixas que uma pessoa precisa comprar para conseguir pelo menos um exemplar de cada um dos
brindes?
Informações relevantes:
- Existem
tipos distintos de brindes. - Cada caixa contém exatamente um brinde, escolhido de forma independente e uniformemente entre os
tipos (ou seja, cada tipo tem probabilidade em cada caixa). - Deseja-se o valor esperado (esperança) do número total de caixas necessárias para obter todos os
tipos ao menos uma vez.
Passo 2
Modelagem por fases: vamos contar quantas caixas são necessárias até completar a coleção dividindo o processo em etapas. Defina as variáveis aleatórias:
- Seja
o número total de caixas que preciso comprar até ter todos os brindes. - Para
, defina como o número de caixas adicionais necessários para obter um novo tipo de brinde quando já tenho exatamente tipos distintos (ou seja, é o tempo até a próxima “novidade” a partir do estado com tipos diferentes).
Note que depois de começar com
tipos, preciso obter sucessivamente uma nova peça
vezes (da
-ª novidade até a
-ésima). Assim
Passo 3
Entendendo a distribuição de
: quando já tenho
tipos distintos, a probabilidade de que a próxima caixa contenha um brinde novo (um tipo que ainda não foi coletado) é
pois há
tipos ainda faltando entre os
possíveis, e cada um aparece com probabilidade
.
Cada tentativa (cada caixa) é independente com mesma probabilidade de sucesso
até surgir um novo tipo. Portanto
segue uma distribuição geométrica (contando o número de ensaios até o primeiro sucesso) com parâmetro
.
Lembrete importante sobre a geométrica: se
é geométrica com probabilidade de sucesso
em cada ensaio independente, então a esperança é
Breve justificativa:
. Uma maneira mais simples é usar
, pois isso é uma série geométrica com soma
.
Passo 4
Aplicando a fórmula geométrica a cada
: como
tem parâmetro
, segue que
Aqui cada
é o número médio de caixas que se espera comprar enquanto se está com
tipos já coletados até que apareça um tipo novo.
Passo 5
Usando a linearidade da esperança: a esperança da soma é a soma das expectativas independentemente de dependência entre as variáveis. Ou seja,
Substituindo o valor de
obtido no passo anterior,
Passo 6
Simplificação da soma: faça a mudança de índice
. Quando
temos
; quando
temos
. A soma fica
Define-se o
-ésimo número harmônico por
portanto a fórmula final é
Passo 7
Interpretação e aproximação para
grande: o valor exato é
. Para grandes
o número harmônico comporta-se como
mais uma constante:
onde
é a constante de Euler–Mascheroni. Logo, para
grande,
Uma forma levemente mais refinada é
Isto dá uma ideia de crescimento: a média cresce como
, ou seja, significativamente maior que linear.
Passo 8
Exemplos numéricos rápidos (para intuição):
- Se
: . - Se
: . - Se
: .
Dica para a prova: apresente a decomposição em fases
, calcule
usando a geométrica e então some usando linearidade da esperança para obter
. Isso é curto e elegante.