Thermodynamics of Random Number Generation
arXiv:1612.08459 · doi:10.1103/PhysRevE.95.062139
Abstract
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 (PRNG) that use wholly deterministic algorithms and from true random number generators (TRNG) 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.
arXiv comment13 pages, 4 figures; http://csc.ucdavis.edu/~cmg/compmech/pubs/torng.htm
References in corpus (19)
- Stochastic thermodynamics, fluctuation theorems, and molecular machines
- Information heat engine: converting information to energy by feedback control
- The Physics of Maxwell's demon and information
- A Fast and Compact Quantum Random Number Generator
- Certified randomness in quantum physics
- Work and information processing in a solvable model of Maxwell's demon
- Black hole thermodynamics and information loss in two dimensions
- Non-gaussian CMB temperature fluctuations from peculiar velocities of clusters
- Optical Quantum Random Number Generator
- Occam's Quantum Razor: How Quantum Mechanics can reduce the complexity of classical models
- An autonomous and reversible Maxwell's demon
- Identifying Functional Thermodynamics in Autonomous Maxwellian Ratchets
- Demon Dynamics: Deterministic Chaos, the Szilard Map, and the Intelligence of Thermodynamic Systems
- A Closed-Form Shave from Occam's Quantum Razor: Exact Results for Quantum Compression
- Leveraging Environmental Correlations: The Thermodynamics of Requisite Variety
- Towards Quantifying Complexity with Quantum Mechanics
- Statistical Signatures of Structural Organization: The case of long memory in renewal processes
- Black Hole Thermodynamics: Entropy, Information and Beyond
- Gambling with superconducting fluctuations
Cited by in corpus (6)
- Above and Beyond the Landauer Bound: Thermodynamics of Modularity
- Harnessing Fluctuations in Thermodynamic Computing via Time-Reversal Symmetries
- Block Ciphers Substitution Box Generation Based on Natural Randomness in Underwater Acoustics and Knights Tour Chain
- A precise bare simulation approach to the minimization of some distances. Foundations
- The Origins of Computational Mechanics: A Brief Intellectual History and Several Clarifications
- New Fluctuation Theorem on Maxwell's Demon