Question

Part of what I do is study typical behavior of large combinatorial structures by looking at pseudorandom instances. But many commercially available pseudorandom number generators have known defects, which makes me wonder whether I should just use the digits (or bits) of $\pi$.

A colleague of mine says he "read somewhere" that the digits of $\pi$ don't make a good random number generator. Perhaps he's thinking of the article "A study on the randomness of the digits of $\pi$" by Shu-Ju Tu and Ephraim Fischbach. Does anyone know this article? Some of the press it got (see e.g. http://news.uns.purdue.edu/html4ever/2005/050426.Fischbach.pi.html ) made it sound like $\pi$ wasn't such a good source of randomness, but the abstract for the article itself (see http://adsabs.harvard.edu/abs/2005IJMPC..16..281T ) suggests the opposite.

Does anyone know of problems with using $\pi$ in this way? Of course if you use the digits of $\pi$ you should be careful not to re-use digits you've already used elsewhere in your experiment.

My feeling is, you should use the digits of $\pi$ for Monte Carlo simulations. If you use a commercial RNG and it leads you to publish false conclusions, you've wasted time and misled colleagues. If you use $\pi$ and it leads you to publish false conclusions, you've still wasted time and misled colleagues, but you've also found a pattern in the digits of $\pi$!

Answer 1

Strictly speaking, there are some known patterns in the digits of $\pi$. There are some known results on how well $\pi$ can be approximated by rationals, which imply (for example) that we know a priori that the next $n$ as-yet-uncomputed digits of $\pi$ can't all be zero (for some explicit value of $n$ that I'm too lazy to compute right now). In practice, though, these "patterns" are so weak that they will not affect any Monte Carlo experiments.

The main limitation of using the digits of $\pi$ may be the computational speed. Depending on how many random digits you need, computing fresh digits of $\pi$ might become a computational bottleneck. The further out you go, the harder it becomes to compute more digits of $\pi$.

If you are worried about the quality of random digits that you're getting, then you may want to use cryptographic random number generators. For example, finding a pattern in the Blum-Blum-Shub random number generator would probably yield a new algorithm for factoring large integers! Cryptographic random number generators will run more slowly than the "commercial" random number generators you're talking about but you can certainly find some that will generate digits faster than algorithms for computing $\pi$ will.

Answer 2

I think it depends upon your application.

I'd say no if you are using the random numbers to generate cryptographic keys, then you immediately open yourself to attacks, because the attacker can probably mimic your random number generator, and thus you add one weak link into the chain.

Answer 3

The obvious problem here is that a good pseudorandom number generator will generate a different sequence every time you run it, whereas the digits of pi have never been observed to change.

Answer 4

Actually, pi has not been proved to be a normal number, and that is surely the minimum requirement for its use as "random numbers".

Answer 5

In a technical sense, no. A good pseudorandom number generator would be one that you can plug into any randomized algorithm and expect to see the same behavior that you would from an actual random number generator. One way of making a technical definition out of this is to say that the pseudorandom number generator cannot be distinguished from truly random (with probability bounded away from 1/2) by any polynomial time test.

But the digits of π clearly can be distinguished from random by a polynomial time test, namely a test that computes the digits of π and compares them to your supposedly random sequence.

For the same reason, no fully deterministic sequence can be a good random sequence. Instead, to fit this definition, you need to use a pseudorandom number generator that takes some number n of truly random bits as an input seed and generates from them a longer sequence (polynomial in n) of pseudorandom bits that cannot be distinguished from random by a polynomial time algorithm.

Answer 6

Also relevant is the Bailey-Borwein-Plouffe formula

$$ \pi = \sum_{i=0}^{\infty} \frac1{16^i}\left( \frac{4}{8i+1}-\frac{2}{8i+4}-\frac{1}{8i+5}-\frac{1}{8i+6}\right),$$

which indicates a certain predictability in the base-16 digits of $\pi$.

Answer 7

It is known that $\pi$ doesn't equidistribute very well. I'm not sure what this says (if anything) about the `randomness' of its digits, but it might suggest the use of the golden ratio or Euler-Mascheroni constant over $\pi$.

Answer 8

Please note that the Tu and Fischbach analysis was challenged - I don't know of these concerns are valid. See below

Refutation of claims such as “Pi is less random than we thought”. George Marsaglia Professor Emeritus Florida State University

http://interstat.statjournals.net/YEAR/2006/articles/0601001.pdf

Answer 9

Why not construct your random numbers with non-sequential digits of pi? For example, digits which are 10 digits apart, on a rolling basis.

And you can buy or get a huge dictionary of the digits of pi which should suffice, along with some clever coding on how you grab your digits.

Answer 10

Cryptographic PRNG's are the gold standard since if you have a practical way to detect the slightest non-randomness in the output, that is considered a break against the generator, and a significant research result (in cryptanalysis) if the PRNG was considered any good (say if it was based on AES, the Advanced Encryption Standard, in some sensible way). It's easy to make them deterministic: for any key K, just take the encryptions E(0), E(1), E(2), ... where E is the encryption function.

Recent x86 computers have a hardware instruction for AES encryption, so it is very fast. It wouldn't surprise me if AES using the hardware instruction is faster than Mersenne Twister implemented in software.

The first edition of "Numerical Recipes" had some discussion of using DES (predecessor of AES) as an RNG, though they took it out of later editions.