Are the Digits of Pi Truly Random?
This article covers far more than the title suggests. It is written in simple English and accessible to quantitative professionals from a variety of backgrounds. Deep mathematical and data science research (including a result about the randomness of Pi, which is just a particular case) are presented here, without using arcane terminology or complicated equations.
The topic discussed here, under a unified framework, is at the intersection of mathematics, probability theory, chaotic systems, stochastic processes, data and computer science. Many exotic objects are investigated, such as an unusual version of the logistic map, nested square roots, and representation of a number in a fractional or irrational base system.
The article is also useful to anyone interested in learning these topics, whether they have any interest in the randomness or Pi or not, because of the numerous potential applications. I hope the style is refreshing, and I believe that you will find plenty of material rarely if ever discussed in textbooks or in the classroom. The requirements to understand this material are minimal, as I went to great lengths (over a period of years) to make it accessible to a large audience.
The randomness of the digits of Pi is one of the most fascinating, unsolved mathematical problems of all times, having been investigated by many million of people over several hundred years. The scope of this article encompasses this particular problem as part of a far more general framework. More questions are asked than answered, making this document a stepping stone for future research.
1. General Framework
We are dealing with sequences x(n) of positive real numbers defined by a recurrence relationship x(n+1) = g(n) for some function g, and initiated with a seed x(1) = x. We are interested only in functions g that produce chaos and preserve the domain. For instance, if x(n) is anywhere in [0, 1] we want x(n+1) to also be anywhere in [0.1].
We also study another sequence derived from x(n), and defined by a(n) = h(x(n)) for some function h. The function h is typically very simple and produces only small integer values such as (say) 0, 1, … , 9 regardless of x(n). The sequence a(n) is called the digits of x represented in the chaotic system defined by the function f.
Using appropriate functions for g, the sequence x(n) behaves as a realization of a stochastic (random) process, each term x(n) acting as a random deviate of some random variable X(n). To be of any value here, the function g must be associated with random variables that are identically distributed, though not necessarily independent. Instead of using the notation X(1), X(2) and so on, we simply write X as all these random variables have the same distribution. The distribution of X is called the equilibrium distribution (or fixed-point distribution) of the system, and it is the solution of a simple stochastic integral equation. Read this article for some illustrations, especially section 3. Likewise, the a(n) sequence has a statistical distribution associated with it, called the digits distribution, and easily derived from the equilibrium distribution.
Examples of functions g producing these patterns are investigated in details in this article. Such systems are usually referred to as chaotic systems. It is a special case of (ergodic) stochastic process or time series. Note that in practice, for a given chaos-inducing function g, not all seeds — the initial value x(1) — produce a sequence x(n) with the desired properties. Seeds failing to do so are called bad seeds and result in equilibrium and digits distributions that are degenerate. Even though all the systems discussed here have infinitely many bad seeds, these seeds are so rare in practice (compared with the good seeds) that the probability to stumble upon one by chance for a given chaos-inducing g, is zero.
At this point, the initiated reader probably knows what I am going to talk about, even though much of it is original research published for the first time. In the grand scheme of things, the randomness of Pi (and I will discuss it later in this article) appears as a very peculiar case, certainly not the most noteworthy result to prove, though still very fascinating.
Questions, Properties and Notations about Chaotic Sequences Investigated Here
For the remaining of this article, we are going to focus on the following, applied to a few different types of chaos-inducing functions g:
- The digits a(n) are denoted as [a(1), a(2), a(3)… ] or {a(n)} and uniquely represents the number x. We want to build sequences {a(n)} based on the functions h and g, such that if x and x’ are two distinct numbers, then the respective representations {a(n)} and {a’(n)} are different.
- There is a function f, usually straightforward (but not always) such that for a given chaos-inducing g and a given h, we have x = f(a(1), a(2), a(3)…).
- For a given g and h, can the algorithm producing {a(n)} generate any arbitrary {a(n)} or only some specific types of {a(n)} with some constraints on the digits? Sometimes yes (example: decimal representations), sometimes no (example: continuous fractions).
- Are the sequences {x(n)} and {a(n)} auto-correlated? Sometimes yes, sometimes no. What are the implications? For the representation of a number in any integer base b such as b = 10, {x(n)} is auto-correlated while {a(n)} is not. If the base b is not an integer, {x(n)} is much less auto-correlated, but {a(n)} becomes auto-correlated. Also if the base b is not an integer, the digits distribution is no longer uniform.
- Can we compute the equilibrium and digits distributions? Yes using an iterative algorithm, but in all the examples discussed in the next section, exact solutions in closed form are known and featured, and I will show you how they were obtained.
Potential Applications
The sequences {x(n)} and {a(n)} can be use for continuous / discrete number generation and in cryptographic applications. See also this article with applications to modeling population demographics, and physics. They can also be used for machine precision benchmarking, as numerical errors accumulate so fast that after 50 iterations, regardless of the sequence, all digits are wrong unless you use high precision computing.
2. Examples of Chaotic Sequences Representing Numbers
All the g functions presented here are chaos-inducing. This is necessary if one wants, with a given g, to represent all numbers, not just a small fraction of them. For each case, we present, whenever possible, the following features:
- The function f discussed earlier, to reconstruct the original number x (the seed)
- The (continuous) equilibrium distribution and its support domain
- The (discrete) digits distribution
- The functions g and h
- Other properties such as auto-correlations or exact formula for x(n) when available
Three types of chaotic processes are discussed
- Tradition representation of a number in base b, with b > 1 (integer or not) and denoted as Base(b)
- Logistic map of exponent p, denoted as LM(p)
- Nested powers of exponent q, denoted as NP(q)
In all cases, the seed x(1) = x is a positive real number. The equilibrium distribution (if it exists) is always solution of the stochastic integral equation
P(X < y) = P(g(X) < y).
A way to solve this apparently complex equation is described in details, and in very simple words, in this article, with an illustration for the logistic map LM(1/2) discussed below. It involves two steps:
- Data Science Step: Gather data to compute the empirical percentile distribution for x(n), and perform various regressions (polynomial, logarithmic and so on) until you discover one with an incredibly fantastic fit with data — like a perfect fit.
- Mathematical Step: Plug that tentative distribution into the stochastic integral equation, and see if it solves the equation.
Also, by definition, as discussed earlier, x(n+1) = g(x(n)) and a(n) = h(x(n)). This can be used to design a trivial algorithm to compute all the digits in any system powered a chaos-inducing function g. The seed x can be reconstructed using the formula x = f({a(n)}. Here the notation INT represents the integer part, sometimes called floor function. In the formula displayed as images, the floor function is represented by left and right brackets: this is the standard convention.
The recursions
Numbers in Base 2, 10, 3/2 or Pi
This system (the traditional decimal system in base b) is characterized by:
with b > 1. The seed x must be in [0,1] so that all x(n)’s are also in [0.1]. If x = Pi, use x-3 instead.
We distinguishes two cases:
- If b is an integer: The equilibrium distribution is uniform on [0,1] and the digits distribution is uniform on {0, 1, … , b} for all but very rare bad seeds x such as rational numbers. This fact has been “known” for millennia (at least for b = 10) and it is taken for granted; it can be proved rigorously by solving the stochastic integral equation P(X < y) = P(g(X) < y) attached to this system. However, in general, such systems do not produce a uniform distribution for the digits: this is the only exception in the examples discussed in this article. The auto-correlation between x(n+1) and x(n) is equal to 1 / b, while the auto-correlation between a(n+1) and a(n) is equal to 0. So the h function actually decorrelates the sequence {x(n)}, to use the vocabulary of time series theory.
- If b is not an integer: The equilibrium distribution is NOT uniform on [0,1]. The auto-correlation between x(n+1) and x(n) is not 0, but much closer to 0 than in the above case. This time, the auto-correlation between a(n+1) and a(n) is NOT equal to 0. The digits take values in {0, 1, … , INT(b)}. I did not test if the digits distribution was uniform on that domain, but my gut feelings tells me that this is not the case.
Computation details for a customizable base b, are available in this spreadsheet. Rather than computing auto-correlations based on a single seed (that is, one instance of the process) using large values of n, I computed them using a large number of seeds (all random numbers) computing the auto-correlations for a small, fixed n but across many seeds. Due to the nature of the process (it is ergodic) both computations yield the same conclusions. The reason for using many seeds and a small n is because large n (above 20) lead to total loss of numerical accuracy.
Nested Square Roots
This is a particular case of a far more general model described in section 3 in the following article. It is characterized by
This system is related to continued fractions, except that a(n) can only be equal to 0, 1, or 2, as opposed to taking any arbitrary positive integer value. The seed x must be in [1, 2] so that all x(n)’s are also in [1, 2]. If x = Pi, use x-1 instead.
The equilibrium distribution is given by the following formula:
The digits distribution is given by the following formula:
Again, these results are easily derived from the stochastic integral equation. Note that the sequence {x(n)} exhibits strong auto-correlations in this case, though auto-correlations for {a(n)} are close to (but different from) 0.
Logistic Map LM(p)
The logistic map has many applications, for instance in social sciences. Here we are interested in the logistic map of exponent p, with p = 1 corresponding to the standard, well known version. We also discuss the case p = 1/2, as these are two cases (possibly the only two cases) that provide a chaotic-inducing g covering all real numbers (one that meets the criteria outlined in section 1) with known equilibrium distribution that can be expressed with a simple closed form formula. The function h associated with this system was chosen arbitrarily, but this is also the simplest function h that one could come up with. I don’t know yet if there is a simple formula for the function f.
This system is characterized by
The seed x must be in [0,1] so that all x(n)’s are also in [0.1]. If x = Pi, use x-3 or x/4 instead. A remarkable fact, for the case p = 1, is that the auto-correlations for {x(n)} are all equal to 0, making it, in some way, more random than the decimal system or other systems discussed in this article. For the case p = 1/2 the auto-correlation between x(n+1) and x(n) is equal to -1/2, see proof here (check out section 3 after clicking on the link.) By contrast, it is equal to 1/2 for the decimal system in base 2.
The equilibrium distributions, defined for y in [0, 1], are equal to:
As usual, this applies to good seeds only (the vast majority of seeds). A proof of the formula for p = 1/2 can be found here. The integral for the case p = 1 can be explicitly computed, see here.
For the case p =1, the digits distribution is uniform on {0, 1}. The probability for a digit to be 0 is equal to P( X < 1/2) = 0.5, based on this computation. This is not true for the logistic map with p = 1/2.
3. About the Randomness of the Digits of Pi
The discussion here is not just about Pi, but about any number. The digits {a(n)} of a number x, in a specific system defined by g and h, are said to be random, if they have the proper digits distribution, as well as the proper auto-correlation structure associated with that system. In short, any finite set of digits of x must have the proper joint distribution that all but a tiny subset of numbers (of Lebesgue measure zero) have in that system. The target digits distribution can be computed from the equilibrium distribution, as discussed in the previous section. Numbers satisfying this criteria are called good seeds earlier this article.
For instance, in the decimal system of base b, if b is an integer, the distribution in question is uniform, auto-correlation between successive digits are zero, and the digits are independently distributed with that same uniform distribution. If the base b is not an integer (say b = 3/2), the theoretical auto-correlation between a(n+1) and a(n) is clearly not zero, the digits distribution is clearly not uniform, and both can be computed exactly using the same mathematical arguments as in this article (see section 3.)
In the literature, the randomness of the digits is defined as normalcy. For the traditional decimal system, the definitions (random digits, good seed, normal number) are similar though good seed is stronger in the sense that it takes the absence of auto-correlation into account. Anyway, for Pi or SQRT(2), even proving that the digit 5 appears infinitely many times — a very weak result indeed — would be a phenomenal discovery.
The Digits of Pi are Random in the Logistic Map System
We show here why Pi is a good seed in that system, with its digits behaving exactly like those of pretty much all numbers in that system. The result is based on the fact that for the standard logistic map (corresponding to p = 1 in the previous section), an exact formula is available for {x(n)} and thus for {a(n)} as well, see here. It is given by
It implies that bad seeds (all bad seeds?) are numbers x that make w(x) a rational number. Pi/4 is not one of them, so Pi/4 must be a good seed.
While this result about the randomness of the digits of Pi may seem spectacular at first glance, there are still big hurdles to overcome to formally prove it. In particular:
- Are the digits a(n) properly defined in the logistic map system? No function x = f({a(n)}) has been found yet, unlike in the decimal or nested square root systems. Can two different numbers have the same digits?
- Are the only bad seeds those that are very easy to spot in the exact formula for x(n)? If difficult to prove, we may be back to square one.
- Probably the biggest hurdle is to prove that w(Pi/4) is irrational.
Note that for the logistic map system, the digits distribution (for good seeds, that is for pretty much all numbers) is uniform on {0, 1} like for the decimal system of base 2. This was proved in the previous section. Also, the a(n)’s are independent since the x(n)’s are. Thus the digits produced by the logistic map system must be sound, solving hurdle #1. Finally, since x must be in [0, 1], here we use Pi/4, rather than Pi.
Paths to Proving Randomness in the Decimal System
The problem with the decimal system (in any base) is the opposite of the logistic map system. The function x = f({a(n)}) is known, but there is no explicit, closed-form formula for a(n). This makes things more complicated.
However, we could try one of the following approaches:
- Find an approximation for x(n) or maybe an infinite series involving terms similar to w(x), making it easier to spot the bad seeds — all of them. Today, the only bad seeds known are rational numbers and artificially manufactured numbers such as x = 0.101101110…
- Study the problem in a base b that is not an integer. Try a sequence of bases that converge to (say) b =2 or b = 10.
- Use a transformation of {x(n)} that more easily leads to a solution.
- The process {x(n)} is chaotic. In number theory, working with the cumulative process, in this case y(n) = x(n) + x(n-1), which is much smoother, sometimes makes things easier.
- Find a mapping between the logistic map and decimal system, for x(n). However, such mappings may be very complicated if they exist at all.
These are all very challenging problems.
Finally, the algorithm used here to compute the digits of Pi or any other number, in any system, is not practical. On must machines, x(n) becomes totally wrong in as little as 30 iterations due to round-off errors accumulating exponentially fast. This is discussed here. Nevertheless, it would be interesting to see how far you can go, with high precision computing, until the digits being computed are no longer correct. Better, use a pre-computed table of digits. For Pi, more than a trillion digits are known.
In this article, the focus was never on a single number like Pi, but on all numbers. The processes investigated here being all ergodic, it is easier to identify general statistical properties by focusing on a large collection of numbers, using small values of n and digits correctly computed, rather than on tons of digits computed for an handful of numbers, with pretty much all digits incorrectly computed due to round-off errors.
Randomness and The Bad Seeds Paradox
Bad seeds (or non-normal numbers) for the decimal system at least, are so rare (though there are infinitely many of them, including all rational numbers) that their set has a Lebesgue measure equal to zero. In other words, if you pick up a number at random, the chance that is is a bad seed is zero. Contrarily, the chance that all its digits are uniformly and independently distributed — the feature of a good seed — is one! Yet there are as many bad seeds as good ones. Any number with duplicated digits, such as 0.339955666677..is a bad seed (its digits are highly auto-correlated). Yet there is a one-to-one mapping (bijection) between these numbers and all real numbers in [0, 1]. So maybe, the Lebesgue measure is not a useful metric in this context.
For related articles from the same author, click here or visit www.VincentGranville.com. Follow me on Twitter at @GranvilleDSC or on LinkedIn.
DSC Resources
- Services: Hire a Data Scientist | Search DSC | Classifieds | Find a Job
- Contributors: Post a Blog | Ask a Question
- Follow us: @DataScienceCtrl | @AnalyticBridge
Popular Articles
Recent Comments