Re: rand("state")

[Paul Kienzle]

On Feb 16, 2006, at 9:46 AM, Mike Miller wrote:

> On Thu, 16 Feb 2006, Paul Kienzle wrote:
>
> > > If you will be producing many random replicates in a simulation 
> > > study, it is better to use the full 625-integer seed so that the 
> > > probability of any two replicates being identical is extremely 
> > > small.
> > > Do I have this right?
> >
> > All you have to worry about is the probability of your seeds 
> > colliding. If you are doing 10^6 simulations, an integer seed gives 
> > you a 1 in 4000 chance of this happening.  If even this is too high, 
> > you can either start at seed 0 and increment to get 10^6 independent 
> > sequences, or use two integers for the seed, giving you a 1 in 10^13 
> > chance of a collision.
> >
> > You will not need a full 624 integer seed.
>
> That helps a lot because I didn't know that consecutive integers 
> produce independent sequences.  How do we know that is true?

Here's what it says at the start of a paper on distributed MT on the MT 
web-site:

> The usual scheme for PRNG in parallel machines is to use one and the 
> same PRNG for every process, with different initial seeds.  However 
> this procedure may yield bad collision, in particular if the generator 
> is based on a linear recurrence, because in this case the sum of two 
> pseudorandom sequences satisfies the same linear recurrence and may 
> appear in the third sequence.  The danger becomes non-negligible if 
> the number of parallel streams becomes large compared to the size of 
> the state space.

They then go on to describe an algorithm for generating different 
twisters on different machines.  Code is available on their web site:

        http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/DC/dc.html

If you want to be safe you may want to wrap this code instead.

> Use of a short seed always causes the same longer state to be 
> generated, I assume, and this is not dependent on machine architecture 
> and it doesn't use urandom.  That will be especially helpful in saving 
> space if many states have to be stored.
>
> I don't agree with your collision probabilities.  How did you compute 
> them?

My calculations are bogus.  I will shut up now.

- Paul



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