Enunciado

Uma urna contém \(n\) bolas numeradas \(1,2,\cdots,n\). Uma pessoa tira uma bola e a devolve, tira outra e a devolve, continuando até tirar uma bola pela segunda vez. Seja \(X\) o número total de retiradas necessárias para obter esta repetição. Mostre que

\[ \mathbb{E}[X]=2+\sum\limits_{j=1}^{n-1}\bigg(1-\frac{1}{n}\bigg)\bigg(1-\frac{2}{n}\bigg)\cdots \bigg(1-\frac{j}{n}\bigg). \hspace{4cm} (I) \]

Prova

Mostrar \((I)\) equivale a mostrar \[ \mathbb{E}[X] = 2 + \sum\limits_{k=2}^{n}\prod\limits_{j=1}^{k} \bigg(1-\frac{j-1}{n}\bigg). \hspace{7cm} (II) \]

Mostraremos \((II)\).

De fato, seja \(X\) o número total de retiradas. Considere os eventos \(A=\{\text{Selecionar, com reposição, $k$ bolas distintas dentre as $n$ bolas}\}\); e \(\{X>k\} = \{\text{número total de retiradas é maior que $k$}\}\).

Temos que \[ \{X>k\} \;\;\text{ocorre se, e somente se}, A \;\text{ocorre}. \]

O espaço amostral é dado por \[ \Omega = \{\omega: \omega=(b_1,\cdots,b_k), b_i=1,2,\cdots,n\}. \]

Existem \(n^k\) resultados igualmente prováveis . Com isso, a probablilidade do evento \[ A=\{\omega: \omega =(b_1,\cdots,b_k), \;b_i\neq b_j, \;i\neq j\}. \]

é

\[ \begin{align} P(A)=\begin{cases} \dfrac{A_{n,k}}{n^k}, & \text{se}\;\;0\leq k \leq n,\\\\ 0, &\text{caso contrário.} \end{cases} \hspace{7cm} (III). \end{align} \]

Como \(P(A)=P(X>k)\), pois os eventos \(A\) e \(\{X>k\}\) são equivalentes, então
\[ \begin{align} \mathbb{E}[X]=\sum\limits_{k=0}^{\infty}P(X>k) &=\sum\limits_{k=0}^{n}\dfrac{A_{n,k}}{n^k}\\ &=\sum\limits_{k=0}^{n}\dfrac{n!}{n^k(n-k)!}\\ &=\sum\limits_{k=0}^{1} \dfrac{n!}{n^k(n-k)!} + \sum\limits_{k=2}^{n}\dfrac{n!}{n^k(n-k)!}\\ &=2+\sum\limits_{k=2}^{n}\dfrac{\prod\limits_{j=1}^{k}\left(n-(j-1)\right)}{n^k}\\ &=2+\sum\limits_{k=2}^{n}\prod\limits_{j=1}^{k}\left(1-\dfrac{j-1}{n}\right). \end{align} \]

Implementação Computacional

#================================================
n <- 20       
b <- 1:n      # bolas numeradas de 1 a n
X <- NULL
amostra <- NULL
BD<- NULL
N <- 1e5

#================================================
#     Esperanca Estimada via Simulacao          #
#================================================

for (j in 1:N){
  BD <- NULL
 for (i in 1:(n+1)){
  amostra <- sample(b,1,replace = TRUE)
  BD[i]<- amostra
  if (TRUE %in% duplicated(BD)){
    break
   }
 }
 X[j] <- length(BD) 
}

Esp.est <- mean(X)

#================================================
#     Esperança Teórica (Exercicio)             #  
#================================================

esp.teo <- function(n){
  fator<- NULL
     for (j in 1:(n-1)){
      fator[j] <- (1-j/n) 
     }
  prod.acum <- cumprod(fator)
return(2+sum(prod.acum))
}

Esp.teo <- esp.teo(20)
list(c(Esp_Teorica=Esp.teo,Esp_Estimada=Esp.est))
## [[1]]
##  Esp_Teorica Esp_Estimada 
##     6.293585     6.304630