Correlations in random number stream based on clock seeding
- Dominant language
- C++
- Stars
- 403
- Forks
- 154
- Avg merge
- 1d 12h
- Merged PRs (30d)
- 82
Description
I've noticed issues like this before, but the problem became clearer when performing the 1000x runs for #1067. Of the 1000x runs which should have been independent, fully 30% were carbon copy reproductions of others.
This came about for two reasons:
1) (1/3 of cases) The random offset, and hence the seed, appears to be set by the second (at least on the machine I ran on, so probably true for others). Since four runs could be executing at any given time in the queue I was in, occasionally a pair or more would start in the same second. This should have significant implications (statistical bias) for doing QMC in a "high-throughput" fashion on a larger machine.
2) (2/3 of cases) The random offset appeared to have a maximum range of 1024 (it rolled back to zero after this) so the available seeds would repeat every 20 minutes. Since the runs started over the course of about 45 minutes, some runs submitted much later also had the same seed profile as earlier ones and were identical to them.
In addition to the carbon copy problem, runs having a different, but similar random offset (say 1020 vs 1021) resulted in highly correlated runs. This effect is shown in the figure below, where the x axis is run number (0 to 999, zoomed in) which corresponds to different offsets, and each line is the value of the local energy from a particular MC block. As is evident from the figure, several similar offsets lead to similar, but not identical, results.

The effect of reduced statistics due to hidden correlations is also directly evident from using the 1000x runs to produce a mean that should be equivalent to a single run 1000x longer. The deviation between the two results is 2.6 sigma, with a probability of occurrence of 1/100.
Does anyone know where the offset range of 1024 comes from?
What could be done to avoid statistical bias in high-throughput runs?
Do we know that something like this is not already happening across MPI ranks?
Contributor guide
Assessment
This issue has not been assessed yet.