random cover of a range

[Bill Baxter]

On Fri, Feb 13, 2009 at 9:37 AM, Bill Baxter <wbaxter at gmail.com> wrote:
> On Fri, Feb 13, 2009 at 9:23 AM, Andrei Alexandrescu
> <SeeWebsiteForEmail at erdani.org> wrote:
>> Sean Kelly wrote:
>
>>> Skip ahead a random number of elements before performing the linear
>>> search.
>>
>> Can you prove this will yield a uniform cover?
>
> I don't see how it could.  If you have a linear search at all, then
> empty at the end of a row of filled elements will always have a higher
> probability of getting chosen.
>
> Pure dart throwing would clearly work though.  Just keep trying
> randomly till you hit an empty.  Won't perform very well, though.

If you count the total number of 1's that precede the 0 you've chosen,
you can tell how biased the choice was.  Say it was k/n when it should
have been just 1/m (n the total number, m the 0's remaining).  If you
know this,  you can systematically discard the choice and try again
with probability such that the combined probability of both choices
comes out to 1/m.  So that would be k/n * x = 1/m, thus x = n/(k*m).
So you keep the value found by linear probing with probability
n/(k*m), otherwise you try again.  Nice thing is as m is getting
smaller, typical k's are approaching n, and so towards the end you get
to keep more and more of your choices.  So it fixes the problem with
pure dart throwing where it takes a longer and longer time to find the
last few empty slots.

How's that sound?
--bb