Quantidade de iterações de loop esperadas ao pesquisar um array por índice aleatório

Question

Digamos que temos um array A de tamanho n.Tem 1 como primeiro índice e n como último índice.Ele contém um valor x, com x ocorrendo k vezes em A onde 1<=k<=n

Se tivermos um algoritmo de pesquisa como este:

while true:
  i := random(1, n)
  if A[i] == x
    break

random(a,b) escolhe um número uniformemente de a até b

A partir disso sabemos que as chances de encontrar x e encerrar o programa são k/n a cada iteração.Porém o que eu gostaria de saber é qual seria o valor esperado para o número de iterações ou mais especificamente a quantidade de vezes que o array foi acessado neste programa dado o array A conforme descrito acima.

Answer 1

Deixar $N$ seja o R.V geométricoque retorna o número de vezes que o array foi acessado para procurar o elemento, $A[x]$ até que o encontremos com sucesso.Nós queremos saber $\mathbb{E}[N]$.

Podemos ver as iterações do loop while como uma sequência de tentativas IID Bernoulli, cada uma com uma probabilidade $p$ de ter sucesso, e $ q = 1 - p$ de fracasso.Dada a questão, queremos saber quantas tentativas são necessárias para obter um “sucesso” que seria encontrar o elemento $A[x]$ Assim, o while o loop termina.

Desde o $\Pr\{N = k\} = q^{k-1}p$, temos isso $\mathbb{E}[N] = \sum\limits_{k = 1}^\infty k \:q^{k-1}p$.

Por isso, $\mathbb{E}[N] = \dfrac 1p$ onde $p = \dfrackn$ então $\mathbb{E}[N] = \dfracnk$.

Então, em média, leva $\dfracnk$ acessa antes de encontrarmos o elemento, $A[x]$.