# Probability calculations

```>From: Scott Brickner <[email protected]>
>% k-space         random        sequential      percent
>searched          method          method        difference
[...]
>99.9             115892899       16760439       591

But you fail to take into account the probability that the search will
have to go that far.

This is how I compute the expected cost of the random search.

The probability of finding the key upon searching the k-th segment is:

k-1
p(k) = (1 - 1/n)    . 1/n

The expected cost is the sum of all possible costs, weighted by their
probability:
___                 ___
\                   \              i-1
e =  >  i p(i)    = 1/n  >  i (1 - 1/n)
/__                 /__
i = 1..oo           i = 1..oo

___        ___
\          \             i-1
= 1/n  >          >   (1 - 1/n)
/__        /__
i = 1..oo  j = 1..i

___
\            i-1
= 1/n  >  (1 - 1/n)
/__
{(i,j) | 1 <= j <= i}

___        ___
\          \            i-1
= 1/n  >          >  (1 - 1/n)
/__        /__
j = 1..oo  i = j..oo

___                 ___
\             j-1   \             i
= 1/n  >   (1 - 1/n)   .   >   (1 - 1/n)
/__                 /__
j = 1..oo           i = 0..oo
\_______________/   \_______________/
n                   n

e = n

This means that if you do many random searches (with a good RNG), the
average cost of one search must be n.

Any errors in the above ?

-- Damien

```