Quantité d'itérations de boucle attendues lors de la recherche d'une matrice par index aléatoire

Question

permet de dire que nous avons un tableau A de taille n.Il a 1 comme son premier index et n comme son dernier index.Il contient une valeur x, avec x survenant k fois dans un endroit où 1 <= k <= n

Si nous avons un algorithme de recherche comme si:

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

aléatoire (A, B) choisit un nombre uniformément de A à B

De cela, nous savons que les chances de trouver X et de terminer le programme sont K / N avec chaque itération.Cependant, ce que j'aimerais savoir est quelle serait la valeur attendue pour le nombre d'itérations ou plus spécifiquement le nombre de fois où la matrice a été accédée dans ce programme compte tenu de la matrice A comme décrit ci-dessus.

Answer 1

let $ n $ soit le R.V géométrique Cela renvoie le nombre de fois où la matrice a été accédée afin de rechercher l'élément, $ a [x] $ jusqu'à ce que nous le trouvions avec succès. Nous voulons savoir $ \ mathbb {e} [n] $ .

Nous pouvons afficher les itérations de la boucle tandis qu'une séquence d'essais IID Bernoulli, chacune avec une probabilité $ p $ de suivi et $ q= 1 - p $ de défaillance. Compte tenu de la question, nous voulons savoir combien d'essais sont nécessaires pour obtenir un "succès" qui trouverait l'élément $ a [x] $ donc la boucle while se termine .

depuis la $ \ pr \ {n= k \}= q ^ {k-1} p $ , nous avons cette $ \ mathbb {e} [n]=somme \ limites_ {k= 1} ^ \ \ \ k-1} p $ .

Ainsi, $ \ mathbb {e} [n]=dfrac 1p $ où $ p=dfrac kn $ donc $ \ mathbb {e} [n]=dfrac nk $ .

Donc en moyenne, il faut $ \ dfrac nk $ d'accéder avant de trouver l'élément, $ A [x] $ .