Probability calculations

[Damien.Doligez@inria.fr (Damien Doligez)]

>From: Scott Brickner <sjb@austin.ibm.com>
>% 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