random cover of a range

[Sean Kelly]

== Quote from Andrei Alexandrescu (SeeWebsiteForEmail at erdani.org)'s article
> Bill Baxter wrote:
> > On Fri, Feb 13, 2009 at 7:21 AM, Andrei Alexandrescu
> > <SeeWebsiteForEmail at erdani.org> wrote:
> >> Jason House wrote:
> >>> Andrei Alexandrescu Wrote:
> >>> No.  Your wording sounds like you're doing
> >>> stuff that's way off, but the resulting math is correct.  My
> >>> calculation would be based on the average length of a sequence of 1's
> >>> (k/(n-k)).  That means the work is 1+k/(n-k) = n/(n-k).
> >> Well my wording means this: in an array of length n with k "holes"
> >> randomly distributed, the probability one slot is a a no-hole is
> >> (n-k)/n. What we want is to find the first no-hole starting from a
> >> random position in the array. How many steps do we do on average? That
> >> is the same as the average number of steps of rolling a fair dice with
> >> (n-k) faces until we obtain a particular face. And the average number of
> >> steps is IIRC 1/p = n/(n-k).
> >
> > Except your holes aren't randomly distributed, because you are more
> > likely to fill a hole next to an already filled slot.
> Oops, that makes me more likely to choose some slots than other. My
> algorithm stinks!
> Consider the array at the second iteration. There are n-1 zeros and one
> 1 in the bitmap. The random number selection selects a number in 0..n
> with probability 1/n each. That's already wrong because each element was
> supposed to be selected with probability 1/(n-1). That extra mass goes
> to the element right after the one selected in the first round. I suck.

Skip ahead a random number of elements before performing the linear
search.


Sean