Random generators

A post on Revolutions discussed physical random generators against standard computer-based generators. It is interesting in that it reveals how “common sense” can get things wrong in this area. First, there is an almost atavistic misgiving that a sequence produced by a function

x_{n+1} = F(x_n) \text{ or } x_{n+1} = F(x_n,y_n), y_{n+1}=G(x_n,y_n)

—the second sequence corresponding to several seeds used in parallel, as possible with R RNGkind—cannot be a “true” random generator when F and G are standard functions. The criticism truly applies to the object, namely the sequence produced, that can be exactly reconstructed if F and G are known, but not to its uses in Monte Carlo simulation. When F (or G) is unknown, the null hypothesis

x_{n+1} | x_n \sim \mathcal{U}(0,1)

cannot be defaulted [rejected] by a statistical test, no matter how long the sequence is, no matter which aspect of uniformity is being tested. (Note that the post mentions randomness in many occurrences without precising this is about uniformity.) The difficulty with pseudo-random generators is rather that they are used for continuous distributions while being represented by a finite number of digits, i.e. with a certain precision. So a statistical test is bound to fail if you look far enough in the digits without adapting the random generator for an higher precision. The second criticism about standard random generators is related with this point, namely that exploring the sequence of values in a finite set with a deterministic function is necessarily periodic. This is correct, but using several seeds in parallel multiplies the size of the finite set to such an extent that it becomes irrelevant for all but purely abstract purposes! The third misconception is that “truly” random is better (“more random“!) than pseudo-random and that, if physical generators are available on a computer, this is much better than R runif. This is a wrong perception in that “truly” random generators are producing flows of numbers that are indeed unpredictable and “random”, but that the law of the random phenomenon cannot be exactly asserted. The example provided in the post of the dicing machine is typical: it produces a sequence of millions of dice values a day—R sample does the same in 0.012 seconds—but there is no reason the dice are exactly well-balanced and the outcome is perfectly uniform over 1,2,3,4,5,6…

5 Responses to “Random generators”

  1. […] producing “truly random” numbers… I already discussed this issue in an earlier post, namely that there is no reason physical generators are “more” random than congruential […]

  2. Anthony Says:

    As a matter of fact, a quantum rng should not suffer of “truncated randomness” as there are real, physical experiments that output a true binary number (for example, a single photon with a the right polarization sent through a polarizer will be either reflected or transmitted with a 50/50 probability). “True” randomness is a feature of quantum mechanics and does not seem to be illusory. This is in sharp contrast with any other physical randomness such as thermal noise where the randomness is simply due to the apparent impossiblity to track a (very) large number of parameters. For this reason, quantum randomness and statistical mechanics randomness are intrinsically different: the latter is apparent and due to the complexity of the physical model while the former seems to be genuine (“God plays dice”…).

    While I agree with you that for most mathematical applications, true randomness is probably unnecessary, I think it might be different for casino applications for instance.

    • Thanks for the precision. I did not have time to enquire more deeply about the quantum rng’s so they appear to me as perfect binary generators where no-one (human nor machine) can predict the outcome. I then see your point in casino-like applications, because trying to cheat by looking at the generator is meaningless.

  3. Anthony Says:

    And what about quantum random number generators, which are not as fast as pseudo-random generators, but not too bad either (4 Mbit/s for Quantis from Idquantique) ? At least, according to to the laws of physics as we know them, these generate “true” random numbers in the sense that you mention: “unpredictable” and “random”.

    • Sorry, I do not know about those quantum rng’s, but I fear they cannot but suffer from the same difficulty as regular rng’s, namely that the finite digit representation on the computers is truncating randomness. My main point is that “true” randomness is both unnecessary and illusory. Most of the discussions around randomness seem to use arguments that pre-date the formalisation of probability theory in the early 1900’s…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s