Thermodynamics of random number generation

We analyze the thermodynamic costs of the three main approaches to generating random numbers via the recently introduced Information Processing Second Law. Given access to a specified source of randomness, a random number generator (RNG) produces samples from a desired target probability distribution. This differs from pseudorandom number generators (PRNGs) that use wholly deterministic algorithms and from true random number generators (TRNGs) in which the randomness source is a physical system. For each class, we analyze the thermodynamics of generators based on algorithms implemented as finite-state machines, as these allow for direct bounds on the required physical resources. This establishes bounds on heat dissipation and work consumption during the operation of three main classes of RNG algorithms—including those of von Neumann, Knuth, and Yao and Roche and Hoshi—and for PRNG methods. We introduce a general TRNG and determine its thermodynamic costs exactly for arbitrary target distributions. The results highlight the significant differences between the three main approaches to random number generation: One is work producing, one is work consuming, and the other is potentially dissipation neutral. Notably, TRNGs can both generate random numbers and convert thermal energy to stored work. These thermodynamic costs on information creation complement Landauer's limit on the irreducible costs of information destruction.

Figure 1

Thermodynamically embedded finite-state machine implementing an algorithm that, from the source of randomness available on the input string, generates random numbers on the output string obeying a desired target distribution and an exhaust with zero entropy. Input string and output string symbols can come from different alphabet sets. For example, here the input symbols come from the set $\{A,B,C\}$ and the outputs from $\{D,E\}$. Exhaust line symbols all are the same symbols $\gamma$.

Figure 2

Lower bound on heat dissipation during the process of single fair sample generation via the von Neumann algorithm versus the input bias $p$.

Figure 3

Chemical reaction network (CRN) implementation of an RNG machine consisting of a box and a particle in it. The left wall acts as a membrane filter such that only input particles, 0 and 1, can enter, but no particles can exit through the wall. The right wall is also a membrane designed such that only output particles, 0, 1, and $\gamma$, can exit. At the beginning the only particle in the box is “machine particle” $A$, which is confined to stay in the box. Every $\tau$ seconds a new input particle enters the box from the left and, depending on the reaction between the input particle and the machine particle, an output particle may or may not be generated that exists through the right wall.

Figure 4

True general-distribution generator: Emit random samples from an arbitrary probability distribution $\left\{p_i\right\}$, $i=0,...,n-1$ where $p_1$ to $p_{n-1}$ sorted from large to small. It has one internal state $S$, and inputs and outputs can be 0, 1,..., $n-1$. All states have energy zero. The joint states $i\otimes S$ for $i\ne 0$ have nonzero energies $\mathrm{\Delta }{E}_i$. Heat is transferred only during the transition from state $0\otimes S$ to states $i\otimes S$. Work is transferred only during coupling the input bit to the machine's state and decoupling the output bit from the machine's state.