random cover of a range

[Sean Kelly]

== Quote from Andrei Alexandrescu (SeeWebsiteForEmail at erdani.org)'s article
> Sean Kelly wrote:
> > == 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.
> Can you prove this will yield a uniform cover?

Nope :-)  But it solves the problem of favoring adjacent elements.


Sean