São colocadas n bolinhas numeradas em uma urna. Aleatoriamente é extraída uma bolinha e o seu número é anotado. O processo é repetido até que na k-ésima vez uma bolinha repetida é obtida. Determine os possíveis valores de k e a fórmula que expressa a probabilidade de cada um deles (em função de k e de n ).

Passo 1

Vou deixar muito claro o que o problema pede e quais informações estão dadas.
  • n bolinhas numeradas 1,2,\dots,n numa urna.
  • Extrai-se aleatoriamente uma bolinha, anota-se o número, e repete-se a extração várias vezes. Para que haja possibilidade de obter uma bolinha já vista em extrações subsequentes, assume-se que a cada extração a bolinha volta para a urna (amostragem com reposição).
  • Define-se k como o índice da extração em que aparece, pela primeira vez, um número que já tinha sido anotado em alguma extração anterior. Ou seja: a primeira repetição ocorre exatamente na k-ésima extração.
  • O que se pede:
    1. Determinar os possíveis valores de k.
    2. Dar uma fórmula para a probabilidade de cada um desses valores, em função de k e de n.

Passo 2

Definição precisa do evento e estratégia de contagem.
  • Seja K a v.a. que representa o instante da primeira repetição (o k pedido).
  • O evento \{K=k\} significa duas coisas simultâneas:
    1. Nas primeiras k-1 extrações não houve repetição: todos os números obtidos em 1,2,\dots, k-1 são distintos.
    2. Na k-ésima extração obtém-se um número que coincide com algum dos k-1 números já vistos.
  • Como as extrações são independentes e uniformes sobre as n bolinhas, vamos calcular probabilidades condicionais passo a passo (probabilidade de cada extração ser nova, dado que as anteriores foram todas distintas) e depois multiplicar.

Passo 3

Probabilidade das primeiras k-1 extrações serem todas distintas (sem repetição).
  • Na 1ª extração não há restrição, então a probabilidade é 1.
  • Dada a 1ª extração, para a 2ª ser distinta da 1ª a probabilidade é \dfrac{n-1}{n} (existem n-1 números distintos restantes entre n possibilidades).
  • Dadas 2 extrações distintas, para a 3ª ser nova a probabilidade é \dfrac{n-2}{n}.
  • Em geral, para que as primeiras k-1 extrações sejam todas distintas, multiplicam-se as probabilidades condicionais: \prod_{j=0}^{k-2}\frac{n-j}{n}.Aqui o produto começa em j=0 de modo que o fator para a 1ª extração é \dfrac{n}{n}=1, para a 2ª é \dfrac{n-1}{n}, etc., e o número de fatores é k-1. Outra forma de escrever este produto é o fatorial decrescente (fatorial com queda, “falling factorial”): \prod_{j=0}^{k-2}\frac{n-j}{n}=\frac{n(n-1)\cdots\bigl(n-(k-2)\bigr)}{n^{\,k-1}}=\frac{(n)_{k-1}}{n^{\,k-1}},onde (n)_{k-1} denota (n)_{k-1}=n(n-1)\cdots\bigl(n-(k-2)\bigr).

Passo 4

Probabilidade de que a k-ésima extração seja a primeira repetição, condicionada em que as primeiras k-1 foram distintas.
  • Se as primeiras k-1 extrações foram todas distintas, então exatamente k-1 dos n números já foram vistos.
  • Portanto a probabilidade de que a k-ésima extração repita um desses é \dfrac{k-1}{n} (há k-1 resultados “ruins” entre n equiprováveis).

Passo 5

Combinar as duas partes para obter P(K=k).
  • Pela regra do produto (probabilidade de intersecção de eventos encadeados), a probabilidade de que as primeiras k-1 sejam distintas e a k-ésima seja repetida é o produto das quantidades dos Passos 3 e 4: P(K=k)=\left(\prod_{j=0}^{k-2}\frac{n-j}{n}\right)\cdot\frac{k-1}{n}.
  • Em forma compacta usando o falling factorial: P(K=k)=\frac{(n)_{k-1}}{n^{\,k-1}}\cdot\frac{k-1}{n}=\frac{(n)_{k-1}\,(k-1)}{n^{\,k}}.

Passo 6

Determinar os valores possíveis de k e comentários finais simples.
  • O menor k possível é k=2 (a primeira repetição só pode ocorrer a partir da segunda extração).
  • Pelo princípio da casa dos pombos (pigeonhole), se fizermos n+1 extrações obrigatoriamente haverá repetição; logo a primeira repetição ocorre no máximo em k=n+1.
  • Portanto os valores possíveis são k\in\{2,3,\dots,n+1\}.
  • Observações rápidas de verificação:
    • Para k=2 a fórmula dá P(K=2)=\dfrac{k-1}{n}=\dfrac{1}{n}, que é a probabilidade da segunda extração coincidir com a primeira (faz sentido).
    • Para k=n+1 a fórmula dá P(K=n+1)=\dfrac{(n)_{n}\,(n)}{n^{\,n+1}} onde (n)_{n}=n! e o fator (k-1)=n cancela um dos n no denominador, ficando de forma equivalente ao produto das probabilidades de as primeiras n serem distintas; o valor coincide com \dfrac{n!}{n^{n}}, o que é a probabilidade de que nas primeiras n extrações não haja repetição (então a primeira repetição só pode ocorrer na n+1-ésima).
  • As probabilidades para k=2,\dots,n+1 formam uma distribuição de probabilidade (partem-se os resultados possíveis e cobrem todo o espaço amostral).

Resposta

k\in\{2,3,\dots,n+1\}
P(K=k)=\frac{(n)_{\,k-1}\,(k-1)}{n^{\,k}},\qquad k=2,3,\dots,n+1,
onde (n)_{k-1}=n(n-1)\cdots\bigl(n-(k-2)\bigr).

Exercícios relacionados