Amount of expected loop iterations when searching an array by random index

Question

Lets say we have an array A of size n. It has 1 as its first index and n as its last index. It contains a value x, with x occurring k times in A where 1<=k<=n

If we have a search algorithm like so:

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

random(a,b) picks a number uniformly from a to b

From this we know that the chances of finding x and terminating the program is k/n with each iteration. However what I would like to know is what would be the expected value for the number of iterations or more specifically the amount of times the array was accessed in this program given the array A as described above.

Answer 1

Let $N$ be the geometric R.V. that returns the number of times the array was accessed in order to search for the element, $A[x]$ until we successfully find it. We want to know $\mathbb{E}[N]$.

We can view the iterations of the while loop as a sequence of IID Bernoulli trials, each with a probability $p$ of succeeding, and $q = 1 - p$ of failure. Given the question, we want to know how many trials are needed to obtain a "success" which would be finding the element $A[x]$ thus the while loop terminates.

Since the $\Pr\{N = k\} = q^{k-1}p$, we have that $\mathbb{E}[N] = \sum\limits_{k = 1}^\infty k \: q^{k-1}p$.

Thus, $\mathbb{E}[N] = \dfrac 1p$ where $p = \dfrac kn$ so $\mathbb{E}[N] = \dfrac nk$.

So on average, it takes $\dfrac nk$ accesses before we find the element, $A[x]$.