Random number generators discussion

Random number generators | www.agner.org

 
thread Meaning of period = 2^19937-1 - Ngo Minh Toan - 2006-03-22
last reply Meaning of period = 2^19937-1 - Agner - 2006-03-23
 
Meaning of period = 2^19937-1
Author:  Date: 2006-03-22 08:47
Dear Agner,

Why MT RNG is said to have a period of 2^19937-1?
The 32-bit integer version of this MT can only generate 2^32-1 integer numbers only. And it is also true for floating point numbers (only 2^32-1 distinct numbers)!

So where comes the 2^19937 period! Does it mean that MT can generate this many DISTINCT random numbers?

What to do with the array of 624 words? Are the words also random numbers?

If MT has only 2^32-1~=4x10^9 numbers, why it is said to be better than ran2, which can generate 10^18 numbers!

I'm so confused now, and I think new users like me will misunderstand the term "PERIOD" like I do! Caution should be given prior to any use!

Please explain!

Thanks a lot.
Toan.

   
Meaning of period = 2^19937-1
Author: Agner Date: 2006-03-23 07:44
You are confusing the resolution and the period. The resolution is the number of different values that the function can generate. The period is the number of calls to the function before the whole sequence repeats.

Take as an example a very simple random number generator producing a 2-bit output. The resolution is 2^2 = 4. Assume that the output looks like this:

3-1-0-2 - 3-1-0-2 - 3-1-0-2 - 3-1-0-2 - 3-1-0-2 - 3-1-0-2 - ...

Here the resolution is 4 and the period is 4. We are not satisfied with knowing that after a 3 always follows a 1. That is not sufficiently random. So we make a better generator that makes the output:

3-1-0-2-0-3-3-2-1-1-1-2-0-3-2-0 - 3-1-0-2-0-3-3-2-1-1-1-2-0-3-2-0 - 3-1-0-2-0-3-3-2-1-1-1-2-0-3-2-0 - ...

This has a resolution of 4 but a period of 16.