Cantidad de iteraciones de bucle esperadas al buscar una matriz por índice aleatorio

Question

Digamos que tenemos una matriz A de tamaño n.Tiene 1 como primer índice y n como último índice.Contiene un valor x, donde x aparece k veces en A donde 1<=k<=n

Si tenemos un algoritmo de búsqueda como este:

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

aleatorio (a, b) elige un número uniformemente de a a b

De esto sabemos que las posibilidades de encontrar x y terminar el programa son k/n con cada iteración.Sin embargo, lo que me gustaría saber es cuál sería el valor esperado para el número de iteraciones o, más específicamente, la cantidad de veces que se accedió a la matriz en este programa dada la matriz A como se describe anteriormente.

Answer 1

Dejar $N$ ser el R.V. geométrico.que devuelve el número de veces que se accedió a la matriz para buscar el elemento, $A[x]$ hasta que lo encontremos con éxito.Queremos saber $\mathbb{E}[N]$.

Podemos ver las iteraciones del bucle while como una secuencia de ensayos IID Bernoulli, cada uno con una probabilidad $p$ de tener éxito, y $q = 1 - p$ de fracaso.Ante la pregunta queremos saber cuantos ensayos se necesitan para obtener un "éxito" que sería encontrar el elemento $A[x]$ Por lo tanto, la while el bucle termina.

desde el $\Pr\{N = k\} = q^{k-1}p$, tenemos eso $\mathbb{E}[N] = \sum\limits_{k = 1}^\infty k \:q^{k-1}p$.

De este modo, $\mathbb{E}[N] = \dfrac 1p$ dónde $p = \dfrac kn$ entonces $\mathbb{E}[N] = \dfrac nk$.

Entonces, en promedio, se necesita $\dfrac nk$ accesos antes de encontrar el elemento, $A[x]$.