random cover of a range

[Andrei Alexandrescu]

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.


Andrei