12

In my program I need to run N separate threads each with their own RNG which is used to sample a large dataset. I need to be able to seed this entire process with a single value so I can reproduce results.

Is it sufficient to simply sequentially increase the seed for each index?

Currently I use numpy's RandomState which uses a Mersenne Twister pseudo-random number generator.

Snippet of code below:

# If a random number generator seed exists
if self.random_generator_seed:
    # Create a new random number generator for this instance based on its
    # own index
    self.random_generator_seed += instance_index
    self.random_number_generator = RandomState(self.random_generator_seed)

Essentially I start off with a user-inputted seed (if it exists) and for each instance / thread I sequentially add the index (0 to N-1) of the instance running. I don't know if this is good practice or if there's a better way of doing this.

gung - Reinstate Monica
  • 132,789
  • 81
  • 357
  • 650
EricR
  • 223
  • 2
  • 4
  • 1
    Do you know in advance how many pseudo random values each thread will use--or at least can you obtain a good upper bound estimate? – whuber Sep 02 '16 at 16:04
  • No I cannot. It samples regions which are summed until a threshold is it. The sizes of the regions can vary significantly. – EricR Sep 02 '16 at 17:21

4 Answers4

10

It's not great practice, certainly. For example, consider what happens when you do two runs with root seeds of 12345 and 12346. Each run will have N-1 streams in common.

Mersenne Twister implementations (including numpy.random and random) typically use a different PRNG to expand the integer seed into the large state vector (624 32-bit integers) that MT uses; this is the array from RandomState.get_state(). A good way to do what you want is to run that PRNG, seeded with your input integer once, and get N*624 32-bit integers from it. Split that stream up into N state vectors and use RandomState.set_state() to explicitly initialize each RandomState instance. You may have to consult the C sources of numpy.random or _random from the standard library to get that PRNG (they are the same). I'm not sure if anyone has implemented a standalone version of that PRNG for Python.

Robert Kern
  • 216
  • 1
  • 3
  • I think this might be the best solution I've heard so far. I don't think it matters much on how I split the stream up though correct? It seems much more unlikely to have a duplicate sequence on 624 32-bit integers between instances no matter how they are picked from the initial PRNG and seed. – EricR Sep 02 '16 at 19:04
  • 1
    Actually, I'll walk this back a bit. It's not clear to me that the initializer PRNG is designed to have arbitrarily many values drawn from it. Consider using another quality PRNG (preferably unrelated to MT) to generate the state stream. One can implement an HMAC-DRBG (a PRNG using an HMAC as a cryptographic primitive) using only the standard library relatively straightforwardly. The cryptographic security is not a concern; just the ease of implementation and quality of the bitstream. You will need to ensure that no all-zero vectors get made, on the very rare off-chance. – Robert Kern Sep 02 '16 at 21:56
  • Or just use one of the newer `RandomState` implementations in development that uses an algorithm that has settable streams. That is, you initialize each `RandomState` instance with the same seed and different stream IDs (merely incremented is fine), and you are guaranteed independent streams. https://pypi.python.org/pypi/randomstate/ – Robert Kern Sep 02 '16 at 21:58
4

A solution that is used in parallel processing is to use your random generator $\Phi(u)$, where $u$ is your seed, by $N$-batches:

  1. generate $\Phi(u),\Phi^N(u),\Phi^{2*N}(u),...$
  2. generate $\Phi^2(u),\Phi^{1+N}(u),\Phi^{1+2*N}(u),...$
  3. ...
  4. generate $\Phi^{N-1}(u),\Phi^{N-1+N}(u),\Phi^{N-1+2*N}(u),...$

where $\Phi^n(u)=\Phi(\Phi^{n-1}(u))$. This way you use a single seed and your sequences are all uniform and independent.

Xi'an
  • 90,397
  • 9
  • 157
  • 575
2

There is now a Python package called RandomGen that has methods to achieve this.

It supports independent streams created from a single seed, as well as a jumping protocol for older random number generators such as MT19937.

Praveen
  • 121
  • 1
  • 4
0

Some people claim that there are correlations in the random numbers generated by sequential seeds. https://stackoverflow.com/questions/10900852/near-seeds-in-random-number-generation-may-give-similar-random-numbers I'm not sure how true that is.

If you are worried about it, why not use a single random number generator to choose the seeds for all of the other generators?

Community
  • 1
Aaron
  • 3,025
  • 14
  • 24
  • Simply because I do not want to have any chance of randomly generating the same seed for more than 1 generator. Of course I could do some programming work to prevent this from happening but then I don't know how that would be any better than picking seeds sequentially in the first place. – EricR Sep 02 '16 at 18:00
  • 1
    [Apparently](https://scicomp.stackexchange.com/questions/24916/#comment42165_24935), correlations are possible with sequential seeds... However, as the [article](https://www.johndcook.com/blog/2016/01/29/random-number-generator-seed-mistakes/) linked in that answer from John D Cook's blog shows, using one RNG to generate seeds for other generators is far far worse, because you run into the birthday problem! It says that generating 1000 16-bit unsigned seeds randomly has a 99.95% chance of overlap! – Praveen Feb 21 '19 at 23:43