random cover of a range

[Andrei Alexandrescu]

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).

> Given that O(n*log(n)) is the theoretical best you can do, having a
> result that is < O(n*log(n)) is highly suspect.  The sum 1/1 + 1/2 +
> 1/3 + 1/4 + 1/5 + ... is in fact O(log(n)).

Ever so pedantic. :o) I meant "<=" because I wasn't aware of the best
theoretical bound. Do you have a pointer? Thanks.

I have the feeling there is something clever to do after half of the
array was covered. After that, the probability of a random element being
uncovered falls below 0.5.

I also have the feeling that interesting things can be done if the
length of the range has certain values, such as the period of certain
generators with certain parameters. I don't have the time to look into
that now. Anyone versed in e.g. linear congruential generators with a
given period?

One way or another, I'll add RandomCover to std.random. Thanks Leonardo,
Denis, Steve, and Jason.


Andrei