Re: rand("state")

[Mike Miller]

On Thu, 16 Feb 2006, Francesco Potorti` wrote:

> > Thinking about it a little more - the entire pseudorandom sequence has 
> > a length of about 4*10^6001, so if you are making numerous sequences of 
> > length 10^9 say, the probability that two or more are overlapping is 
> > always extremely small (assuming that the starting point in the 
> > sequence is always selected at random from all possible starting 
> > points).
>
> You just sent a calculation that can be used as the base to compute the 
> probability of having non-overlapping sequences, given the number of 
> sequences, their length, and the generator period, under the assumption 
> of uniformly choosing a random starting point for each sequence.
>
> I did not check it, but yes, it can be seen as an instance of a birthday 
> problem.
>
> Or else you can see it as this: have a generator of period P, from which 
> you have already taken N non-overlapping sequences of length L.  The 
> probability that one more sequence of lenght L starting from a random 
> point does not overlap with one of the already taken N sequences is 
> equal to the probability that no taken sequence starts in an interval of 
> length 2*L, that is, (1-N/P)^(2*L), under the assumption that N*L<<P, 
> which is true in our case.
>
> If what I wrote is correct, then you have the probability of choosing a 
> new good sequence, given that you have already chosen N.

I don't have time right now to figure out if it is correct, but I will 
add this:

(1-N/P)^(2*L) = ((1-N/P)^(P/N))^((N/P)(2*L)) = exp(-2*L*N/P)

That last equality is approximate, but it is very close whenever N/P is 
small, and it is always small.

Mike



-------------------------------------------------------------
Octave is freely available under the terms of the GNU GPL.

Octave's home on the web:  http://www.octave.org
How to fund new projects:  http://www.octave.org/funding.html
Subscription information:  http://www.octave.org/archive.html
-------------------------------------------------------------