1
$\begingroup$

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.

$\endgroup$

1 Answer 1

1
$\begingroup$

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]$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.