7
$\begingroup$

I am trying to see if there were any incidents in the past where using PRNG or not actual random scheme leaded to wrong conclusion in research.

For example, a lot of fields today use simulations to predict natural science results and I was wondering what are the best practices and if there were any flaws due to bad randomness in the past.

For security purposes it's clear that one has to use encrypt lib random function, but for science or simulation of physical systems I am not sure it's the case. My guts say it should be the same, but I am not sure how to justify it.

Are there flaws in (cryptographic) science/engineering/software/research due to pseudo random generators?

$\endgroup$
6
$\begingroup$

There are a few examples:

  • RANDU is probably the quintessential example of a bad pseudorandom generator. It consisted of the sequence $x_{i+1} = 65539\cdot x_i \bmod{2^{31}}$, which is always odd and whose sequential triples are highly correlated. It was implemented by IBM in its software, and so it was used all over the place. It has been suggested that research results relying on RANDU are not reliable, but I could not track down any concrete example of this.

  • Another interesting example is that of 1992 Ferrenberg et al., in which a pseudorandom number generator that passed the statistical tests common of the time, but nevertheless resulted in incorrect results in a real Monte Carlo Ising-Model simulation. The generator in question was R250, a very simple generalized feedback shift register.

There are most likely many other examples incorrect results that simply haven't been checked or reproduced.

$\endgroup$
5
$\begingroup$

I know of one engineering example: the standard pseudo random number generator for the Haskell programming language is the StdGen type in the System.Random module. The RandomGen class that this generator implements has a split method that takes a PRNG state and "splits" it into two:

split :: g -> (g, g)

The split operation allows one to obtain two distinct random number generators. This is very useful in functional programs (for example, when passing a random number generator down to recursive calls), but very little work has been done on statistically robust implementations of split ([1, 4] are the only examples we know of).

[1] FW Burton and RL Page, Distributed random number generation, Journal of Functional Programming, 2(2):203-212, April 1992.

[4] P Hellekalek, Don't trust parallel Monte Carlo, Department of Mathematics, University of Salzburg, http://www.cs.odu.edu/~yaohang/cs714814/Assg/DontTrustParallelMonteCarlo.pdf, 1998.

The actual source code for the standard generator is even less reassuring, with a comment saying "no statistical foundation for this!" at one point.

And indeed this generator has been shown to be flawed; the problem is that when you split it in two, the two subgenerators' outputs are correlated. And the problem has been illustrated with relatively simple unit test cases. Quoting from Claessen and Pałka's "Splittable Pseudorandom Number Generators using Cryptographic Hashing":

The property-based testing framework QuickCheck makes heavy use of splitting. Let us see it in action. Consider the following simple (but somewhat contrived) property:

newtype Int14 = Int14 Int
  deriving Show

instance Arbitrary Int14 where
  arbitrary = Int14 `fmap` choose (0, 13)

prop_shouldFail (_, Int14 a) (Int14 b) = a /= b

We define a new type Int14 for representing integers from 0 to 13. Next, we create a random generator for it that randomly picks a number from 0 to 13. Finally, we define a property, which states that two randomly picked Int14 numbers, one of which is a component of a randomly picked pair, are always unequal. Testing the property yields the following result:

*Main> quickCheckWith stdArgs { maxSuccess = 10000 } prop_shouldFail
+++ OK, passed 10000 tests.

Even though the property is false (we would expect one of every 14 tests to fail), all 10,000 tests succeed!

Claessen and Pałka's conservative solution to this problem is to build splittable pseudorandom generators out of cryptographic primitives, by applying a keyed hash function to a prefix-free encoding of a pair of a generator's path down the split tree and a sequential output counter. There are also proposed non-cryptographic generators aimed at this sort of scenario; Java 8 has a SplittableRandom class, which they describe as:

A generator of uniform pseudorandom values applicable for use in (among other contexts) isolated parallel computations that may generate subtasks.

There's more on this subject in this paper of Steele, Lea and Flood's: "Fast Splittable Pseudorandom Number Generators," OOPSLA '14.


The problems above are an instance of a larger pattern: PRNG quality testing often focuses on the statistics of the sequential output of individual instances of the PRNG, but much less so on relationships between the parallel outputs of multiple such instances. The result is that if you have a parallel system where you independently seed many PRNGs, their outputs may well exhibit mutual correlations nevertheless.

$\endgroup$
  • $\begingroup$ Are there similar issues like splitting while working on GPUS? $\endgroup$ – 0x90 Aug 13 '17 at 21:43
  • $\begingroup$ But what theorems have been show to be false as a result of bad random numbers? That was the actual question, not examples of bad RNGs per se... $\endgroup$ – Paul Uszak Aug 14 '17 at 13:53
  • $\begingroup$ @PaulUszak: The title of the question is "Are there flaws in (cryptographic) science/engineering/software/research due to pseudo random generators?" And I think my example counts as an engineering/software flaw. It would be nice to find an example where a real-life unit test produced a false positive result because of these flaws, however. $\endgroup$ – Luis Casillas Aug 14 '17 at 20:12
  • $\begingroup$ Clarification: the title was edited since I wrote this answer to add the "(cryptographic)" parenthetical that I quoted in my comment. $\endgroup$ – Luis Casillas Aug 14 '17 at 20:26
1
$\begingroup$

On best practice

There's a Good Practice in (Pseudo) Random Number Generation for Bioinformatics Applications paper that gives some pointers to best practice. Although I'd be reluctant to follow the advice of implementing the referred to RNGs. Writing a RNG is tricky as they're difficult to test. Even when run through standard randomness tests, interpretation of the results is difficult as the results are not clear pass /fails, but statistical p values. The randomness of the RC4 key stream is an example in point. RC4 passes all standard randomness tests, yet is easily distinguished by custom tests. Thought provoking with deep implications.

I would expect all researchers to be using off the shelf RNGs. Two examples are the TRandom classes for the CERN guys or RandomGenerator class from the Commons Math package. It's probably going to be a Mersenne-Twister implementation, as it is also in R.

Three points from [Bioinformatics] that do seem relevant is:-

  1. Seed the generator well. Complex high state generators like the Twister or ISAAC can be pesky with respect to correct seeding.
  2. Warm them up by running and discarding the first part of the output. Again ISAAC, RC4 and probably the Twister /Spritz require this.
  3. Only use a limited part of the total output sequence. If you use all of it, you're just making a permutation rather than randomness. This might matter for long tests. [Bioinformatics] suggests in the most conservative case to only use the cube root of the possible output space. This limits usable Java SecureRandom output to only 1400 TB. Not a lot with which to unlock the secrets of the Universe.

On real world examples of fails

Going out on a limb, I'm going to say that there are no significant examples of randomness errors in the scientific /engineering press. I'm very happy to withdraw this part if someone proves me to the contrary. My evidence is inferred, but has some merit at least...

This question has remained unanswered since July. No one has provided evidence of significant false hypotheses being generated. There is evidence of minor things like odd butane expansion in simulations. There is also the minor Ferrenberg ferro magnetism example.

Weighed against these is that RANDU was a common linear congruential RNG of the 1960's. The Apollo programme was extensively simulated on IBM/360s using Fortran II. NASA probably either used it directly, or implemented something very similar as I don't think that RANDU is a Fortran II function. We made it to the moon (most believe). Randomness bias didn't seem to have had any deleterious effect. You could probably find out more by cross posting to fortran and the apollo 11 mission and asking there. There's three guys who actually worked on Apollo.

The other evidence is that science doesn't work like this. Someone publishes a paper. The experiment is then independently replicated all over the world. If you read these types of papers, you'll see that the technical implementation details are usually omitted or vaguely described. The consequence is that any further simulation trials would in all likelihood be done with independent RNGs, seeded independently. The central limit theorem and combined random errors kinda paper over RNG biases in this situation. Two poor but different RNGs combined together produce a much better one. A significant theory only gains traction after multiple researchers have agreed. One dodgy RNG won't have any significant effect in this context. [See retraction disclaimer at start].

$\endgroup$
  • 3
    $\begingroup$ This doesn't answer the question at all: ‘any incidents in the past where using PRNG or not actual random scheme leaded to wrong conclusion in research’. You've given general advice about random number generators, not citations to incidents of bogus research results. $\endgroup$ – Squeamish Ossifrage Aug 7 '17 at 14:06
  • 2
    $\begingroup$ @SqueamishOssifrage Do you think it might go some way to answering the "what are the best practices" bit..? $\endgroup$ – Paul Uszak Aug 7 '17 at 14:32
  • 2
    $\begingroup$ You sure have confidence in the reproducibility of scientific results! Of course, for stochastic results, there are two kinds of reproducibility: reproduction of bit-for-bit identical results, and reproduction of samples from the same distribution. Bit-for-bit reproduction reflects nothing about the quality of the PRNG: a terrible PRNG is just as reproducible as a cryptographic PRNG. Reproduction of samples from the same distribution is very hard to tell in general—if attempted in the first place, for which the replication crisis bodes ill. $\endgroup$ – Squeamish Ossifrage Aug 11 '17 at 23:05
  • $\begingroup$ I get you, but you should know from other answers that I'm cynical as hell. I'm waiting for medical advice to start smoking again. But what else is there available to us? We should at least be able to independently verify a RNG's Dieharder score from different seeds and in different languages. If we ignore reproducibility, that leads to cold fusion and UFOs. And I don't believe in cold fusion. $\endgroup$ – Paul Uszak Aug 12 '17 at 1:21
  • 1
    $\begingroup$ Lack of confidence in reproducibility of results does not mean accepting obviously fraudulent claims like practical cold fusion or nonsense like perpetual motion machines (note that UFOs certainly do exist: literally, aerial objects whose observers could not identify them). Rather, it means rejecting a large fraction of published research findings, though we don't know which. (Of course, under the intended meaning of the typical 5% statistical significance, 5% of published findings will be flukes anyway.) $\endgroup$ – Squeamish Ossifrage Aug 13 '17 at 3:25
1
$\begingroup$

Converting the comment by Squeamish Ossifrage into an answer (to clean up the comment area):

Standard answer is RANDU, derided in the canon of the computer science literature, Numerical Recipes and Knuth's TAOCP. But my copies aren't handy at the moment so I don't have citations for detectably wrong results that got published as a consequence, and most of the web search results are about how RANDU is wrong, not about what wrong results got published based on it.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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