Re: rand("state")

[Mike Miller]

On Fri, 17 Feb 2006, Francesco Potorti` wrote:

> > If the use of /dev/random or /dev/urandom can produce all 19968 bits 
> > (624 32-bit integers) plus one integer in the range from 1 to 624, and 
> > these are truly random and not limited by the time when they were 
> > recorded, then I'm sure you are right.  But if the seed from 
> > /dev/urandom is only a 32-bit seed, there can be collisions.
>
> Consecutive seeds do not produce consecutive random sequences, so I 
> don't think that the probability of a collision increases if you choose 
> the initial state from a 2^32 sample rather than a 2^32^625 one.

We are talking about choosing seeds at random with replacement.  The 
probability that the same seed is chosen twice in a sample of size N is 
highly sensitive to the total population size.  2^32 is not a very large 
population size and the probability of a collision becomes worrisome when 
N gets to 10,000 or so, but (2^32)^625 is *very* large and it makes 
collisions nearly impossible.  It makes a lot of difference.


> Sure, if you want to be on the safe side, you will use a 625-integers 
> array chosen from a uniform distribution.  But I see no reason to think 
> that choosing it from a much smaller sample would cause any real 
> difference.
>
> Maybe someone on this list knows of studies on this topic?

We already did a bunch of math on the birthday problem yesterday.  The 
answer was given there.

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