15
$\begingroup$

How and why are random number generators (RNGs) important in computational statistics?

I understand that randomness is important when choosing samples for many statistical tests to avoid bias towards either hypothesis, but are there other areas of computational statistics where random number generators are important?

$\endgroup$
  • 4
    $\begingroup$ Closely related: stats.stackexchange.com/q/135665/35989 $\endgroup$ – Tim Jan 31 '18 at 15:35
  • 1
    $\begingroup$ What are you asking? Your question doesn't really make much sense. $\endgroup$ – Carl Witthoft Jan 31 '18 at 15:52
  • 2
    $\begingroup$ It might be better to ask for areas in which they are not important. It would probably be a shorter list. $\endgroup$ – John Coleman Jan 31 '18 at 21:51
  • 2
    $\begingroup$ The question is broad but the title is appealing and Matthew's answer is a nice overview. I voted to reopen! $\endgroup$ – Benoit Sanchez Feb 5 '18 at 13:07
  • 3
    $\begingroup$ This is clearly too broad by conventional SE standards, & amounts to a 'big list' question that is likely to accrue lots of small, barely elaborated answers that often duplicate answers already provided. However, there does seem to be some real value here. A compromise is for this to be CW & protected. In the future, answers that mention something without elaboration &/or that duplicate uses already mentioned will be deleted promptly & without comment. $\endgroup$ – gung - Reinstate Monica Feb 5 '18 at 16:05
17
$\begingroup$

There are many, many examples. Way too many to list, and probably too many for anyone to know completely (besides possibly @whuber, who should never be underestimated).

As you mention, in controlled experiments we avoid sampling bias by randomly partitioning subjects into treatment and control groups.

In bootstrapping we approximate repeated sampling from a population by randomly sampling with replacement from a fixed sample. This lets us estimate the variance of our estimates, among other things.

In cross validation we estimate the out of sample error of an estimate by randomly partitioning our data into slices and assembling random training and testing sets.

In permutation testing we use random permutations to sample under the null hypothesis, allowing to perform nonparametric hypothesis tests in a wide variety of situations.

In bagging we control the variance of an estimate by repeatedly performing estimation on bootstrap samples of training data, and then averaging results.

In random forests we further control the variance of an estimate by also randomly sampling from the available predictors at every decision point.

In simulation we ask a fit model to randomly generate new data sets which we can compare to training or testing data, helping validate the fit and assumptions in a model.

In Markov chain Monte Carlo we sample from a distribution by exploring the space of possible outcomes using a Markov chain (thanks to @Ben Bolker for this example).

Those are just the common, everyday applications that come to mind immediately. If I dug deep, I could probably double the length of that list. Randomness is both an important object of study, and an important tool to wield.

$\endgroup$
  • $\begingroup$ This is all true but doesn't address the main problem: a PRNG with any sort of resultant structure or predictability in the sequence will cause the simulations to fail. $\endgroup$ – Carl Witthoft Jan 31 '18 at 15:51
  • 3
    $\begingroup$ One of the things that deserves mention are the computational and memory costs of generating large numbers of random or pseudorandom numbers. Some applications of RNGs in stats require hundreds to millions of random numbers, but some require many orders of magnitude more which bears on both these costs. $\endgroup$ – Alexis Jan 31 '18 at 17:26
5
$\begingroup$

This is all true but doesn't address the main problem: a PRNG with any sort of resultant structure or predictability in the sequence will cause the simulations to fail. Carl Witthoft Jan 31 at 15:51

If this is your concern then maybe the title of the question should be changed to "Impact of RNG choice on Monte Carlo results" or something like that. In this case, already considered on SE cross validation, here are some directions

  • If you are considering poorly designed RNGs like the infamous RANDU they will clearly negatively impact the Monte Carlo approximation. To spot deficiencies in RNGs, there exist banks of benchmarks like Marsaglia's Diehard tests. (For instance Park & Miller (1988) use of the Lehmer congruential generator with the factor 16807 has been found lacking, to be replaced with 47271 or 69621. Of course this has been superseded by massive period generators like the Mersenne Twister PRNG.)
  • A SE question on maths provides a link on the impact (or lack thereof) on estimation and precision, if not a very helpful answer.
  • Jeff Rosenthal (U Toronto) has a paper where he studies the impact on an RNG on the convergence of (Monte Carlo) Markov chains but I cannot find it. I recently ran a small experiment on my blog with no visible impact of the RNG type.
    • As an aside, a lottery scheme in Ontario used poorly designed random generation, which was spotted by a statistician, Mohan Srivastava of Toronto, Canada, who notified the Ontario Lottery and Gaming Corporation of the issue, rather than making a hefty profit out of this loophole.
  • Here is an illustration of a case where a classic network simulator is impacted by a poor default choice (linked to Park and Miller above).
  • There are specific issues with the structure of RNGs used in parallel computing. Using several seeds is usually not good enough, especially for linear congruential generators. Many approaches can be found in the computer literature, including the scalable parallel random number generation (SPRNG) packages of Michael Mascagni (including an R version) and Matsumoto’s dynamic creator, a C program that provides starting values for independent streams when using the Mersenne twister. This has also been addressed on SE stack overflow.
  • Last year, I saw a talk by Paula Whitlock on the impact of the GNU Scientific Library on the convergence of high dimension random walks, but cannot.
  • To end up on a light note, there also is some literature on the distinction between software and hardware RNGs, with claims that psychics can impact the later!
$\endgroup$

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