Can two PRNG's produce the same number with different seeds?

Question

I know if you use the same seed with two different PRNG's you'll receive the same sequence of numbers. Does anyone know if it's possible to generate the same number with two different seeds? If so, what are the odds?

I ran a test on this and received some strange results. If I have two instances of the same PRNG and I seed them with two different random seeds each time. The random number has to be between 0 and 1000. I get the same number 1046 times after 10,000,000 iterations. If I don't seed them each time I receive about the same number about the same number of times (1033). What am I not understanding? I would think the odds would be much greater if you don't re-seed each time (hmm, maybe not). Much like picking two cards from two decks. If I don't shuffle the cards each time I would think the odds would be different then if I do.

Thanks, Gary

Answer 1

The odds depend on the PRNG you're using. Assuming it generates numbers in an even distribution and your seed is chosen randomly* then it's just a function of the number of different numbers you can represent.

*Random means with no relation to the previous seed, and no knowledge of the algorithm being used.

For a 32 bit integer you have 2^32 different numbers you can represent, so given one integer, the odds of another sufficiently-random number being the same is 1/(2^32).

Answer 2

The answer to this will depend on exactly which PRNG you're using. Different implementations have different guarantees. If you're lucky, the documentation will tell you what those guarantees are.

However, any decent PRNG will have a long cycle for any valid seed. So the odds of two different seeds generating the same next number should be very small. (I'd expect on the order of 1/(2^N), where N is the number of bits in the datatype it's using.)

Finally, I wonder if this is really the information you need. It sounds like you have some kind of requirement for uniqueness rather than randomness. If what you care about is uniqueness, there are better solutions. The age-old classic is to keep an always-increasing counter somewhere that persists long enough. You can also use a GUID - many modern platforms have library code for creating them.