Any one who considers arithmetical methods of producing random digits is, of course, in a state of sin. For, as has been pointed several times, there is no such thing as a random number- there are only methods to produce random numbers, and a strict arithmetic procedure of course is not such a method.-Von Neumann

Introduction:

Random number generators are critical to almost all high-performance computing applications ranging from scientific computing, machine learning, encrypted communications and financial engineering. In spite of this, a subtle definition of randomness that is both general and practical(for engineering) has so far proven elusive. To clarify this state of confusion, let’s turn to page 14 of the international standard for random number generators defined by NIST where we find the following precisions:

Random Number Generator(RNG): A RNG uses a non-deterministic source(i.e. entropy source) along with some processing function(i.e. the entropy distillation process) to produce randomness.

Entropy source: The entropy source typically consists of some physical quantity such as the noise in an electronic circuit…or the quantum effects in a semiconductor.

The authors then add the clarification: ‘For cryptographic purposes, the output of RNGs needs to be unpredictable.’ From the NIST document we may infer that when scientists and engineers speak of randomness they are implicitly talking about entropy production and uncertainty/predictability.

But, what of randomness? If this notion has any scientific merit then it must correspond to an observable physical process.

What is the role of randomness in a computable universe?

Since every computational process is a mathematical abstraction of a physical process, by definition the observable universe must be a computable universe. In particular, since all physical theories are used to make quantitative predictions they are all effectively computable. This includes the Schrödinger equation and Quantum Field Theory of course.

Furthermore, given that fundamental physics depends upon the assumption that the universe has a compositional structure, for any physical process we may conjecture the existence of a digital or analog computer which may be designed to simulate that process. From this correspondence, we may deduce that algorithmically random(and therefore uncomputable) processes are physically impossible and so any usage of the term ‘random’ is short-hand for pseudo-random(i.e. computable).

If the argument elaborated in the last paragraph is not completely clear, the reader may consider that an algorithmically random data generating process implies an incompressible dataset so it would need to be void of any structure…an absurdity if I ever heard one.

Good random number generators produce entropy, not randomness:

Having expressed doubts on the notion of randomness, we may clarify what is meant by random variable. Within the context of RNGs, a random variable is an entropy source which requires a probability distribution and a method for computing entropy.

If we consider probabilities from a frequentist point of view they are measurable observables, and if you are Bayesian probabilities are still data points. As for a well-defined notion of entropy, we may define the Shannon entropy from a combinatorial perspective where each probability \(p_i\) is a useful piece of relative information.

Shannon entropy from a combinatorial point of view:

Let’s suppose you have a small deck of cards in your hands with four kings, three aces, and two queens. If you’d like to consider the number of rearrangements of this deck you might want to know how many unique permutations are possible assuming that cards of the same type are indistinguishable from each other:

\begin{equation} W = \frac{9!}{4!3!2!} \end{equation}

and in general the multinomial coefficient is a solution of the general case:

\begin{equation} W = \frac{N!}{\prod_i N_i!} \end{equation}

where \(N\) is the total number of cards and \(N_i\) is the number of cards of a particular type.

Now, we may observe that all permutations may be enumerated and assigned a number(in binary) from 0 to W-1 so the string of \(\log_2(W)\) bits may be used to encode each permutation. This allows us to define the Combinatorial Entropy \(S_c\) as the average number of bits per permutation:

\begin{equation} S_c = \frac{\log_2(W)}{N} = \frac{1}{N} \log_2 \big(\frac{N!}{\prod_i N_i!}\big) \end{equation}

and the reader may infer that \(S_c\) is in some sense a measure of diversity as the magnitude of \(S_c\) varies inversely with the number of cards of the same type:

\begin{equation} \frac{\partial S_c}{\partial N_i} = -\frac{1}{N} \cdot \frac{1}{N_i} \end{equation}

and using Stirling’s log-factorial approximation:

\begin{equation} \ln N! \approx N \ln N - N \end{equation}

we have:

\begin{equation} S_c \approx \frac{1}{N} \big(\sum_i N_i \log_2 N - \sum_i N_i \log_2 N_i \big) \end{equation}

since \(\sum_i N_i = N\)

Simplifying, we find:

\begin{equation} S_c \approx -\big(\sum_i \frac{N_i}{N} \log_2 \frac{N_i}{N} \big) \end{equation}

and if we define the frequencies \(p_i = \frac{N_i}{N}\) we recover the usual Shannon entropy \(H(\cdot)\):

\begin{equation} H(X) = - \sum_i p_i \log_2 p_i \end{equation}

where \(X\) refers to the card deck and \(P=\{p_i\}_{i=1}^n\) is a discrete probability distribution.

Discussion:

If we summarise what has been demonstrated here, we may argue that a necessary and sufficient definition of randomness requires three components:

  1. Uncertainty, which may be either epistemic or statistical, which is the source of an information asymmetry between potential hackers and the generator.

  2. Physical processes whose statistical behaviour is well-understood, which we use as an entropy source.

  3. A method for computing entropy, which allows us to quantify the strength of an entropy source in statistical terms.

Regarding the second criterion, it is worth noting that even deterministic pseudo-random number generators are physical processes since digital computer programmers implicitly orchestrate a large number of electromagnetic interactions in a very precise manner. Now, given that the Shannon entropy is additive we may note that for a sequence of states \(\{a_i\}_{i=1}^n\) we have:

\begin{equation} H(a_1,…,a_n)= H(a_1,…,a_{n-1}) + H(a_n) \end{equation}

and the process is uninformative if:

\begin{equation} \forall i,j,k \in \mathbb{N}, H(a_i,a_j) = H(a_i,a_k) \end{equation}

and this holds true if, modulo the hacker’s epistemic uncertainty of the system’s behaviour, this hacker empirically observes a statistically uniform distribution over the state-space. As a corollary, the system’s behaviour appears ergodic.

References:

  1. Andrew Rukhin et al. A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications. NIST. 2010.

  2. G. E. Volovik. The Universe in a Helium Droplet. Oxford Science Publications. 2003.

  3. Pablo Arrighi and Gilles Dowek. The physical Church-Turing thesis and the principles of quantum theory. 2011.

  4. Edwin Jaynes. Information Theory and Statistical Mechanics I. The Physical Review. 1957.

  5. Edwin Jaynes. Information Theory and Statistical Mechanics II. The Physical Review. 1957.

  6. Marcus Hutter. Algorithmic information theory. Scholarpedia. 2007.