Seeding the Mersenne Twister Random Number Generator

Question

I am trying to understand how the Mersenne Twister random number generator works (in particular, the 32-bit TinyMT). I am still relatively new to the concept of RNG. As I read the source code, I noticed there were two ways to seed the MT: with a single integer seed or an array of integer seeds. What is the point in seeding with an array? Does it produce a better distribution or a longer period?

Also, I would appreciate it if somebody could explain to me what is meant by the "state" of the RNG, as I am seeing that word all over the source code. Is it like a finite state machine in a way?

Thanks for your time!

Answer 1

A random number generator has the following simplified pseudocode:

state S;

int random() {
  S = advance_state(S);
  return extract_integer(S);
}

The random number generator maintains an internal state, which in the case of MT consists of an array of words and an index. Every time you want to generate a new number, two things happen: (1) the state is modified in some devious way; (2) the state is compressed to the output word. The entire random number generator is thus a finite state machine which proceeds deterministically from state to state (there is no "input"), while also producing output.

MT is implemented slightly differently by generating several output words at once, but this is just an optimization - you can also implement it in just the way I described.

Here is a simple naive example. The internal state S is a 32-bit word. It is updated by increasing it by 1. The output is the least significant bit. If S is seeded by 0, then the first few outputs are 0, 1, 1, 0, 1, 0, 0, 1, ... (the first $2^{32}$ bits in the Thue-Morse sequence).

How does the internal state get initialized? There are two ways. One way is to give the entire internal state. The other way is to give a smaller "seed", and from the seed generating an internal state in some devious way. If we do it deviously enough, then the function associating a seed with the resulting internal state will look like a random function (in other words, it will seem as we're selecting $2^{32}$ different random internal states, when the seed is a 32-bit integer).

The cryptographic strength of the second way is only 32 bits - you only need to try all $2^{32}$ different seeds in order to complete a given sequence. If you care about that and the seed is too short for your taste, you can use the first method and come up with an entire internal state, though that's usually not necessary, and certainly isn't necessary if all you want is random numbers for simulation purposes. (If you want cryptographically secure random numbers, please don't use MT.)

Other ways of seeding a random number generator, which sit on top of these methods, include using a password or passphrase (which is converted to a seed using a hash function) and using random data from your computer (which again passes through a hash function which functions as a randomness extractor).

Answer 2

The answer from @Yuval is good, but does not describe TinyMT behavior and does not answer all questions, as it mostly focus on what is the state of a random number generator. You can see from https://github.com/MersenneTwister-Lab/TinyMT/blob/master/tinymt/tinymt32.c that

• An int seed will populate the state with random numbers based on this seed, using an implicit simple random number generator.
• An array of int seed will also populate the state with random numbers based on this array. The array size may be larger than the state size.

So there is no real difference between one or the other approach. Arguably, the single int seed is preferable, since the underlying algorithm to create the state is better understood/analyzed (same as Mersenne-Twister 2002).

In particular you won't have a better period or better distribution by seeding with an array.

Now to make the connection with @Yuval answer, for some random number generators, initialization with an array consisted in copying the array to the state. So you were effectively directly setting the initial state. This is dangerous for many random number generators, since then there is no guarantee that the state is properly initialized (for Mersenne Twister, it could have too many zero bits for example. More caveats @ Matsumoto Common defects in initialization of pseudorandom number generators).

The state is just an internal array, updated at each call to produce a next() random number.