RandomStreams

A random number stream is a sequence of random numbers; multiple random number streams can be thought of as independent random number generators. Random number streams can be used to provide many independent high-quality random number generators, useful for example when running parallel simulations.

Introduction

Background

L’Ecuyer et. al describe the notion of streams and substreams in a random number generator (RNG) [1]. We ignore substreams in our implementation, instead treating each stream as an independent RNG. We do this because fully supporting both streams and substreams would be a significant departure from the way Julia (and most contemporary languages) handle random numbers.

Motivation

Suppose we are trying to run a large number of simulations. We want each simulation to use different random numbers, so how do we provide each simulation with a sequence of random numbers? If we know how many random numbers each simulation needs, we can start with a single random number generator and then create a new one by skipping ahead by the required number of numbers, repeating this for each simulation. This will give each simulation a sequence or stream of random numbers to use.

– image:: streams.png

However, you usually do not know how many numbers each simulation needs. To overcome this, we can instead simply skip ahead by a very large distance, e.g. skipping \(2^100\) numbers at a time. As long as each simulation requires fewer than this number of random numbers , no simulation will use the same sequence of random numbers.

Note that if we can efficiently compute these jumps, we can use these streams in a parallel environment.

Random numbers streams

With the previous motivating example in mind, we define a stream of random numbers to be a consecutive subsequence of random numbers generated by an RNG. To be useful, each stream must be longer than any reasonable program could consume. In turn, if we want an RNG to have many streams, the RNG must have a very long period

While the notion of jumping ahead in a random number generator to create multiple streams of random numbers is useful, the statistical properties of the resulting streams are not well-understood in general. To overcome this we need a random number generator with well-understood streams and a very large period, for example the MRG32k3a generator described in [2].

References

[1]	“An object-oriented random-number package with many long streams and substreams”, Pierre L’Ecuyer, Richard Simard, E. Jack Chen, W. David Kelton. Available `here<http://www.iro.umontreal.ca/~lecuyer/myftp/papers/streams00.pdf>`_.

[2]	“Good parameters and implementations for combined multiple recursive random number generators”, Pierre L’Ecuyer. Available `here<http://www.iro.umontreal.ca/~lecuyer/myftp/papers/combmrg2.ps>`_.