random cover of a range

[Andrei Alexandrescu]

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?

Andrei