Quantità delle iterazioni del loop previste durante la ricerca di un array mediante indice casuale

Question

Diciamo che abbiamo un array A di taglia n.Ha 1 come primo indice e n come ultimo indice.Contiene un valore X, con X che si verifica k volte in un dove 1 <= k <= n

Se abbiamo un algoritmo di ricerca come:

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

.

casuale (A, B) seleziona un numero uniformemente da A a B

Da questo sappiamo che le possibilità di trovare X e la terminazione del programma sono K / N con ogni iterazione.Tuttavia quello che vorrei sapere è quale sarebbe il valore previsto per il numero di iterazioni o più specificamente la quantità di volte in cui è stato accessibile l'array in questo programma date l'array a come descritto sopra.

Answer 1

Let $ N $ Sii il Geometrico R.V. Ciò restituisce il numero di volte in cui è stato accessibile l'array per cercare l'elemento, $ a [x] $ finché non lo troviamo con successo. Vogliamo sapere $ \ mathbb {e} [n] $ .

Siamo in grado di visualizzare le iterazioni del ciclo mentre è una sequenza di prove di IID Bernoulli, ciascuna con una probabilità $ P $ di successo e $ Q= 1 - P $ di fallimento. Data la domanda, vogliamo sapere quante prove sono necessarie per ottenere un "successo" che troverebbe l'elemento $ a [x] $ quindi il ciclo while termina .

Dal momento che la classe $ \ PR \ {n= k \}= q ^ {k-1} p $ , abbiamo quella $ \ MATHBB {E} [N]=SUM \ LIMITS_ {K= 1} ^ \ INFTY K \: Q ^ {K-1} P $ .

quindi, $ \ mathbb {e} [n]=dfrac 1p $ dove $ p=dfrac kn $ così $ \ mathbb {e} [n]=dfrac nk $ .

Quindi in media, prende $ \ dfrac nk $ accessi prima di trovare l'elemento, $ a [x] $ .