[Trilinos-Users] Belos/Eptra: Seeding RNG

[Tom Anderson]

I have some idea what problem is solved by calling the pseudo random number
generator (PRNG) a bunch of times before using it.
Here is a story about it.
The TLDR; is "It is a work-around for a bad PRNG seed, but better solutions
exist."

A long time ago, I ran in to a problem with a Monte Carlo simulation.
One of the solutions to the problem involved repeated calls to the PRNG at
the beginning of the code.

The problem occurs when the seed to the random number generator does not
have sufficient entropy.
In my case, the seed was the system clock, with a time resolution of one
second.
When the simulations were launched in the same second, this started the
random numbers at the same place.
To fix this, I added a counter to the system clock, incrementing it by a
big number.

My Monte Carlo analysis was sensitive to any problems with the the random
number generator.
I wasn't just making histograms. I was also doing sensitivity analysis with
the Monte Carlo data.
The analysis was coded in a version of the language S called S+. This
language is now usually called R.
I called the pairs() graphing function on all the values in the simulation,
both input and output.
Any correlation between the input variables would show up in the input
pairs() graph.
Since the input was random, there wasn't supposed to be any correlation
between the inputs.
Obviously there was a lot of correlation when I used a duplicate seed,
because the values were right on top of each other.
Even after I fixed the problem by adding a counter, there was still a lot
of correlation between the inputs.
The amount of correlation was much higher for the first few values out of
the PRNG.
To fix the problem, I called the PRNG a bunch of times to get away from
this.
This also solved another problem, which is that the first few calls of the
PRNG tended to cluster around a small range of values.
This was because I had a lot of initial zeros in the PRNG state. It wasn't
getting filled well by the seed.

All was good for a while, but then I would occasionally still get
correlations.
For example, in one run, one of the input variables traced out a slightly
noisy staircase shape.

I became seriously annoyed, and got out the bigger hammer.

One of the good solutions that I found could be implemented purely in
software.
I saved the state of the random number generator between runs of the
program.
That way, when it generated values for the next random number, the PRNG
state started where it left off.
It took a while to find a good PRNG that had an API for saving the state.
Once I had this, it solved my simulation problem.

I don't remember which PRNG I used, but I can probably find it if anyone is
interested.

Doing a good job of setting the seed of a PRNG is also important.
All the bits of the seed should have entropy.

As John von Neuman said,
"Any one who considers arithmetical methods of producing random digits is,
of course, in a state of sin."
If you need true random numbers, you can get some from:
https://www.random.org/randomness/ .
Or, you can make your own true random numbers.
You are welcome to use this circuit that makes bits by comparing thermal
noise in two resistors:
https://www.google.com/patents/US6070178 . The patent has lapsed.

The existing commercial HW RNGs that I have looked at don't seem so great
to me.
They put out a lot of bits with some algorithm that is perturbed at a much
slower random data.

-Tom Anderson
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://software.sandia.gov/pipermail/trilinos-users/attachments/20150404/ae868d9e/attachment.html>