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