56
$\begingroup$

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$!

$\endgroup$
5
  • 4
    $\begingroup$ en.wikipedia.org/wiki/… $\endgroup$ Jun 3, 2010 at 18:37
  • 5
    $\begingroup$ Are there actually examples where commercial RNGs have led to false conclusions in a published paper? $\endgroup$ Jun 3, 2010 at 23:10
  • 1
    $\begingroup$ I doubt it. I personally am much happier believing a published proof (that I can't find an error in) than the output of some sort of RNG built by hand in the real world. $\endgroup$ Jun 4, 2010 at 1:01
  • 17
    $\begingroup$ There are cases where pseudorandom number generators can lead to incorrect simulation results (for example, see "Sensitivity of Ballistic Deposition to Pseudorandom Number Generators" by D'Souza, Bar-Yam, and Kardar (Physical Review E 57 (1998), 5044-5052), mae.ucdavis.edu/dsouza/Pubs/bdrng.final_pre.pdf). These aren't really good PRNGs, certainly not cryptographic ones, but a lot of simulations use whatever lousy PRNG happens to be implemented in their favorite programming language, so this can be a real issue. $\endgroup$
    – Henry Cohn
    Jan 17, 2012 at 13:52
  • $\begingroup$ I don't know if anyone has run $\pi$ through the standard RNG tests such as pcg-random.org/statistical-tests.html . It could be fun. $\endgroup$
    – Simd
    Nov 16, 2021 at 11:43

12 Answers 12

56
$\begingroup$

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.

$\endgroup$
3
  • 4
    $\begingroup$ I recently checked the literature and it looks like I slightly misspoke about an "explicit value of $n$". Salikhov proved that the irrationality measure of $\pi$ is less than $8$, which implies for example that there exists $n_0$ such that for all $n>n_0$, the $n$th through the $8n$th bits of $\pi$ cannot all be zero, but as far as I have been able to tell, there is no effective upper bound on the size of $n_0$. $\endgroup$ Dec 19, 2015 at 19:18
  • $\begingroup$ Is it really harder to compute additional digits of pi even when using the spigot algorithm based on the Bailey-Borwein-Plouffe formula? $\endgroup$
    – JohnEye
    Jun 10, 2020 at 13:49
  • 1
    $\begingroup$ @JohnEye : Yes. If you want the $n$th digit of $\pi$ then the complexity of the spigot algorithm increases quasi-linearly with $n$. You don't need to store the previous digits or increase the precision of your computations, but the amount of work needed to compute the $n$th digit does increase as $n$ gets bigger. $\endgroup$ Jun 10, 2020 at 15:32
26
$\begingroup$

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$.

$\endgroup$
5
  • $\begingroup$ see Steve's comment. $\endgroup$ Jun 3, 2010 at 22:16
  • 2
    $\begingroup$ but +1 anyway because I think this formula is really cool. $\endgroup$ Jun 3, 2010 at 22:22
  • 20
    $\begingroup$ I wish people wouldn't post naked links. I rarely follow them. $\endgroup$ Jun 4, 2010 at 0:17
  • 9
    $\begingroup$ I agree that it's a cool formula (and useful, to boot), but how does it indicate "predictability", aside from the fact that the computational complexity of computing a single digit or a string of digits using it is fairly low? $\endgroup$ Jun 4, 2010 at 3:59
  • 8
    $\begingroup$ @Victor: Isn't that what "predictability" means? $\endgroup$ Jan 5, 2013 at 16:13
21
$\begingroup$

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.

$\endgroup$
1
  • 2
    $\begingroup$ Yes, all this entropy must come from somewhere! In reverse, it was a big issue with ENIGMA decoding. $\endgroup$ Jun 4, 2010 at 3:53
8
$\begingroup$

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.

$\endgroup$
1
  • 1
    $\begingroup$ I agree. If you want to do a Monte Carlo experiment, $\pi$ may work, though it will probably be slower than, say, the Mersenne Twister. If you want to do crypto, it's a very bad idea. $\endgroup$
    – Charles
    Jun 3, 2010 at 18:47
7
$\begingroup$

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$.

$\endgroup$
3
  • $\begingroup$ ... or $\ln 2:$ there is an easy spigot algorithm for it $\endgroup$ Jun 4, 2010 at 4:01
  • 1
    $\begingroup$ mmm I wonder if there is a relationship between ease' of spigot algorithm and goodness' of equidistribution? $\endgroup$ Jun 4, 2010 at 7:52
  • $\begingroup$ Are there any rigorous quantitative results which say that $\pi$ equidistributes "slowly"? or just numerics? $\endgroup$ Jan 17, 2012 at 21:15
5
$\begingroup$

As several others have pointed out, $\pi$ obviously isn't actually random, since its digits are fixed in place forever.

But are the digits "as good as random"? The short answer is that, as far as anyone can tell, the answer seems to be empirically yes (See Marsaglia's On the Randomness of Pi and Other Decimal Expansions). That is, there are no known ways in which the digits of $\pi$ behave systematically unlike a random number.

There are several other answers here that I think are confusing on this point. Let me explain why some of the claims made by other answers (despite being technically correct and in certain ways very insightful) don't disprove the claim that the digits of $\pi$ are as good as random.

  • One answer points out that there exists $n_0$ such that for all $n > n_0$, the $n$-th through $8n$-th bits of $\pi$ are not all zero. However, this property is also true of any random bit string (with probability $1$). So the fact that the property holds is actually evidence for the randomness of $\pi$.
  • Another answer points out that $\pi$ doesn't seem to equidistribute as uniformly as, for example, $e$. This just means that if you look at the numbers $i \pi - \lfloor i\pi \rfloor$ for $i \in \{1, 2, \ldots, 10000\}$ and you round each number down to the nearest multiple of $0.05$, then the result is less smooth then if you do the same thing for the number $e$. But the quantities being graphed here depend only on the first six digits of $\pi$. They're not meant to tell us anything meaningful about how random the digits of $\pi$ are.
  • Finally, another answer correctly points out that the digits of $\pi$ do not fulfill the standard complexity-theory definition of a pseudorandom number generator. But that's mostly just because of a type mismatch: no individual bit string $x$ can fit the definition of a pseudorandom number generator. (Indeed, any algorithm that knows the first, say, 10 bits of $x$ can easily distinguish $x$ from a random bit string). In general, to construct a pseudorandom number generator, what you formally need is a set $S$ of bit strings with the property that no fast algorithm (i.e., no algorithm with running time substantially smaller than $|S|$) can distinguish a random element of $S$ from a truly random bit string (with probability at least, say, $2/3$). We could easily splice $\pi$ into multiple bit strings $S = \{x_1, \ldots, x_k\}$ where each $x_i$ consists of the $i$-th, $(i + k)$-th, $(i + 2k)$th, etc., bits of $\pi$; and I see no reason a priori to think that this wouldn't give a perfectly good pseudorandom number generator.
$\endgroup$
2
  • $\begingroup$ "No individual bit string 𝑥 can fit the definition of a pseudorandom number generator" -- Doesn't the notion of algorithmic randomness/complexity work on specific sequences though? Under such a definition (e.g. that no computable constructive martingale can succeed on the sequence), digits of pi wouldn't be considered "algorithmically random" precisely because there is a polytime algorithm to compute it $\endgroup$
    – 1110101001
    Mar 11 at 0:15
  • $\begingroup$ Although I suppose you could counter that we could use a definition similar to a CSPRNG where the sequence is only "algorithmically random" if the seed is unknown. $\endgroup$
    – 1110101001
    Mar 11 at 0:30
5
$\begingroup$

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

https://web.archive.org/web/20160303171837/http://interstat.statjournals.net/YEAR/2006/articles/0601001.pdf

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
3
  • 9
    $\begingroup$ Yet ... $\endgroup$ Jun 3, 2010 at 20:13
  • 4
    $\begingroup$ So when you run your simulation the next time, just pick up where you left off. $\endgroup$ Jun 3, 2010 at 21:10
  • $\begingroup$ Without a random seeding, it is impossible to answer the question whether the digits of $\pi$ appears random. For a constant seed, the digits of $\pi$ appear constant. $\endgroup$ Jan 17, 2012 at 13:44
4
$\begingroup$

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

$\endgroup$
6
  • 2
    $\begingroup$ Has ANY specific number been proven to be normal? $\endgroup$ Jun 3, 2010 at 21:16
  • $\begingroup$ @Paul: Yes. See Wikipedia. $\endgroup$ Jun 3, 2010 at 21:45
  • 9
    $\begingroup$ @Timothy, you aren't suggesting using .123456789101112131415... as a source of random digits, are you? $\endgroup$ Jun 4, 2010 at 1:54
  • 16
    $\begingroup$ @Gerry: I was suggesting that Paul Siegel consult Wikipedia for the answer to his question as to whether any specific number has been proven to be normal. It was Gerald Edgar, not I, who suggested that normality is a necessary (not sufficient) condition for a "random sequence." For my answer to Jim's question, see my answer to Jim's question. $\endgroup$ Jun 4, 2010 at 14:38
  • $\begingroup$ In trying to construct a less predictable normal number, are numbers using only a subset of the digits useful? Does Dirichlet''s theorem say that the number whose expansion consists of the last digits of successive primes > 5 gives a number with a normal occurrence of the digits 1,3,7,9? This is a variation on Davidac's comment. $\endgroup$
    – roy smith
    Jan 12, 2011 at 18:45
3
$\begingroup$

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.

$\endgroup$
-3
$\begingroup$

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.

$\endgroup$
1
  • 6
    $\begingroup$ How would your suggestions improve the randomness properties or practicality of the digit sequence? $\endgroup$
    – S. Carnahan
    Jan 1, 2013 at 9:15
-6
$\begingroup$
  1. Given all digits of a sequence S till a certain length say n ie di ( i = 1 to n) ; if the probability of any next block of digits B in next m digits ( m -> infinity ) can be ascertained as < 1/(b^w) where b is the base and w is the string length of the block , through an algorithm which is guaranteed to halt then S is NOT a random sequence.

  2. Just being a normal number is not "sufficient" say the sequence 1234..101102103..10001001 is a normal sequence yet not random.

  3. Based on above since using the spigot formula for Pi I can predict its digits, it is not random.

  4. Direction of analysis is also important. Suppose there is a civilization where constant Pi has not been discovered yet ( let alone its formula), here a only a reverse analysis would be possible and the probability of one chancing upon the spigot formula while analysing the digits of Pi cannot be ruled out though its remote. Other wise the equidistribution of digits would lead such a civilisation to take Pi sequence as random

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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