O Colecionador de Cupons. Uma marca de cereal coloca um de n 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 n brindes?

Passo 1

O enunciado dá uma marca de cereal que coloca, em cada caixa, um brinde escolhido uniformemente entre n 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 n brindes?
Informações relevantes:
  • Existem n tipos distintos de brindes.
  • Cada caixa contém exatamente um brinde, escolhido de forma independente e uniformemente entre os n tipos (ou seja, cada tipo tem probabilidade 1/n em cada caixa).
  • Deseja-se o valor esperado (esperança) do número total de caixas necessárias para obter todos os n 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 X o número total de caixas que preciso comprar até ter todos os n brindes.
  • Para k=0,1,\dots,n-1, defina T_k como o número de caixas adicionais necessários para obter um novo tipo de brinde quando já tenho exatamente k tipos distintos (ou seja, é o tempo até a próxima “novidade” a partir do estado com k tipos diferentes).
Note que depois de começar com 0 tipos, preciso obter sucessivamente uma nova peça n vezes (da 1-ª novidade até a n-ésima). Assim
X = T_0 + T_1 + \cdots + T_{n-1}.

Passo 3

Entendendo a distribuição de T_k: quando já tenho k tipos distintos, a probabilidade de que a próxima caixa contenha um brinde novo (um tipo que ainda não foi coletado) é
p_k = \frac{n-k}{n},
pois há n-k tipos ainda faltando entre os n possíveis, e cada um aparece com probabilidade 1/n.
Cada tentativa (cada caixa) é independente com mesma probabilidade de sucesso p_k até surgir um novo tipo. Portanto T_k segue uma distribuição geométrica (contando o número de ensaios até o primeiro sucesso) com parâmetro p_k.
Lembrete importante sobre a geométrica: se Y é geométrica com probabilidade de sucesso p em cada ensaio independente, então a esperança é
\mathbb{E}[Y]=\frac{1}{p}.
Breve justificativa: \mathbb{E}[Y]=\sum_{t=1}^\infty t(1-p)^{t-1}p. Uma maneira mais simples é usar \mathbb{E}[Y]=\sum_{t\ge1}\Pr(Y\ge t)=\sum_{t\ge1}(1-p)^{t-1}=\tfrac{1}{p}, pois isso é uma série geométrica com soma 1/(1-(1-p)).

Passo 4

Aplicando a fórmula geométrica a cada T_k: como T_k tem parâmetro p_k=(n-k)/n, segue que
\mathbb{E}[T_k]=\frac{1}{p_k}=\frac{n}{n-k}.
Aqui cada \mathbb{E}[T_k] é o número médio de caixas que se espera comprar enquanto se está com k 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,
\mathbb{E}[X]=\mathbb{E}\bigg[\sum_{k=0}^{n-1} T_k\bigg]=\sum_{k=0}^{n-1}\mathbb{E}[T_k].
Substituindo o valor de \mathbb{E}[T_k] obtido no passo anterior,
\mathbb{E}[X]=\sum_{k=0}^{n-1}\frac{n}{n-k}.

Passo 6

Simplificação da soma: faça a mudança de índice i=n-k. Quando k=0 temos i=n; quando k=n-1 temos i=1. A soma fica
\mathbb{E}[X]=\sum_{i=1}^{n}\frac{n}{i}=n\sum_{i=1}^{n}\frac{1}{i}.
Define-se o n-ésimo número harmônico por
H_n=\sum_{i=1}^{n}\frac{1}{i},
portanto a fórmula final é
\mathbb{E}[X]=n H_n.

Passo 7

Interpretação e aproximação para n grande: o valor exato é \mathbb{E}[X]=nH_n. Para grandes n o número harmônico comporta-se como \ln n mais uma constante:
H_n = \ln n + \gamma + o(1),
onde \gamma\approx 0{,}5772156649 é a constante de Euler–Mascheroni. Logo, para n grande,
\mathbb{E}[X] \approx n(\ln n + \gamma).
Uma forma levemente mais refinada é
\mathbb{E}[X]=n\left(\ln n + \gamma + \frac{1}{2n} + o\!\left(\frac{1}{n}\right)\right).
Isto dá uma ideia de crescimento: a média cresce como n\ln n, ou seja, significativamente maior que linear.

Passo 8

Exemplos numéricos rápidos (para intuição):
  • Se n=1: \mathbb{E}[X]=1\cdot H_1=1.
  • Se n=2: \mathbb{E}[X]=2\left(1+\tfrac{1}{2}\right)=3.
  • Se n=3: \mathbb{E}[X]=3\left(1+\tfrac{1}{2}+\tfrac{1}{3}\right)=\tfrac{11}{2}=5{,}5.
Dica para a prova: apresente a decomposição em fases T_k, calcule \mathbb{E}[T_k]=n/(n-k) usando a geométrica e então some usando linearidade da esperança para obter n\sum_{i=1}^n 1/i. Isso é curto e elegante.

Resposta

\displaystyle \mathbb{E}[X]=n\sum_{i=1}^{n}\frac{1}{i}=nH_n

Exercícios relacionados