Cantidad de iteraciones de bucle esperadas al buscar una matriz por índice aleatorio
Pregunta
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.
Solución
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]$.