random cover of a range

[Christopher Wright]

Andrei Alexandrescu wrote:
> 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!

On a similar note, we previously suggested using merge sort with a 
random comparer in order to shuffle a list outside memory. My 
experimentation showed a heavy bias toward certain permutations, though; 
can anyone determine why that should be?