10
$\begingroup$

Recently, I came across a comment claiming that almost all researchers doing Monte Carlo methods are doing it wrong. It went on to elaborate that merely choosing different seeds for different instances of a PRNG such as the Mersenne Twister is not sufficient to ensure unbiased results as bad collisions can occur. The Wikipedia article on the Mersenne Twister seems to corroborate:

Multiple Mersenne Twister instances that differ only in seed value (but not other parameters) are not generally appropriate for Monte-Carlo simulations that require independent random number generators, though there exists a method for choosing multiple sets of parameter values.

I have to admit, I'm guilty as charged. But so are all the other implementations of parallel Monte Carlo libraries I've seen so far, in particular ALPS.

The Wikipedia article also references two papers offering remedy:

Both methods have been coautored by Matsumoto and Nishimura, the original authors of the Mersenne Twister algorithm.

I'm afraid I'm not very knowledgeable in number theory or algebra and do not fully grasp the above schemes or the maths behind the Mersenne Twister. My questions are primarily of practical nature:

  • How much do I really need to worry about introducing bias to my simulations when not employing such a scheme if next to nobody cares about it in practice (at least in my community)?
  • If I were to implement one of these counter-measures, am I right to assume that the Jump-Ahead one is better suited as it is based on a firm theory and is the more modern method?
Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Isn't this question specific to MT? Other PRNG's have rather simpler ways of generating independent streams, as described in Pierre L'Ecuyer's other work (see esp. his surveys, like iro.umontreal.ca/~lecuyer/myftp/papers/parallel-rng-imacs.pdf). $\endgroup$
    – Kirill
    Apr 1, 2016 at 15:01
  • $\begingroup$ Yes, it is somewhat specific to MT. I have only ever used MT in MC simulations and it is regarded as the slightly more expensive but most safe option by my colleagues. Not sure if this is true in general but it is what I have fathomed. $\endgroup$
    – Jonas Greitemann
    Apr 1, 2016 at 15:05

3 Answers 3

Reset to default
10
$\begingroup$

Like you say, using the Mersenne Twister for parallel computations is almost always done incorrectly, as the correct method is tricky to implement.

By far the easiest and best answer would be to move away from the Mersenne Twister entirely, and use something like the PCG family, which provides multiple streams out of the box.

The Mersenne Twister is known to fail several statistical tests, while also being slower than newer RNGs such as the PCG and XorShift+ families.

The reason the Mersenne Twister is so widely used today is mainly a result of the RNGs before it being far worse, both in performance and quality. It also helped that the original authors open sourced a highly performant implementation.

Improve this answer
$\endgroup$
6
  • 2
    $\begingroup$ It is worth noting that in the paper you linked to, MT only failed two linear complexity tests of its bit stream, so just that failure doesn't necessarily disqualify it from use, and I imagine there are many applications that aren't sensitive to that particular kind of failure. $\endgroup$
    – Kirill
    Apr 1, 2016 at 19:40
  • $\begingroup$ Certainly. It is perfectly suitable for many applications. For older applications, changing away from MT would most often be a wasted effort. For new ones however, or applications that need multiple streams of random numbers, there is no reason to use it. $\endgroup$
    – LKlevin
    Apr 1, 2016 at 19:45
  • 1
    $\begingroup$ The PCG generators sound awesome. Almost too good to be true. Maybe it is just an overdose of scientific scepticism or maybe it is the heavy sales pitch of the website. Either way, it is rather new. Are there any independent investigations which corroborate its claims? $\endgroup$
    – Jonas Greitemann
    Apr 2, 2016 at 0:01
  • 1
    $\begingroup$ They do have a very heavy sales pitch for the PCG, but that is also something inherited from the Mersenne Twister. Looks at the xorshift+ homepage to see another group doing the same. As for third parties, I guess I count, as I have no affiliation whatsoever with the PCG group, and I have verified their claims extensively (trying to prove my own RNG superior). You can also run TestU01 yourself on the PCG, to test the claims. $\endgroup$
    – LKlevin
    Apr 2, 2016 at 11:25
  • $\begingroup$ For my application/hardware I found xorshift+ to be about twice as fast as an "equivalent" PCG generator so try both if speed is important. The main PCG code has a lot of features builtin compared to the very lightweight xorshift+ code. $\endgroup$
    – horchler
    Apr 3, 2016 at 23:34
3
$\begingroup$

If you want to use MT, you can use SFMT as your PRNG and SFMT jump to generate multiple streams.

You can simply initialise MT with one seed, and then jump ahead by e.g. $1 \cdot 10^{60}$, $2 \cdot 10^{60}$, $3 \cdot 10^{60}$ … steps to generate multiple streams. Jumping is somewhat expensive, but you only need to do it once when you initialise your PRNGs.

Improve this answer
$\endgroup$
1
$\begingroup$

Really only you can answer the question about simulation bias and if it is acceptable in your application. The standard procedure I use:

Set a pseudo random sequence as a benchmark (standard Monte Carlo) using a high # of simulations (in risk management 10,000 is often used, in other fields 100,000 to 1M may be used).

Run your RNG over the same input data for a subset of data (we use 1 year but that is often overkill).

Compare the results using statistics which describe features of the data you actually use for making conclusions / decisions. We use percentiles (1,5,25,50,75,95,99), absolute error, standard deviation of the error. All of this is relative to your benchmark.

Now you have the analysis, you can use your own judgement as to if the RNG bias is acceptable.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.