Entropy of Pseudo Random Number Generators

Abstract

Since the work of Ferrenberg et al.[PRL 69, (1992)] some pseudo random number generators are known to yield wrong results in cluster Monte Carlo simulations. In this contribution the fundamental mechanism behind this failure is discussed. Almost all random number generators calculate a new pseudo random number $x_i$ from preceding values, $x_i=f(x_{i-1},x_{i-2},...,x_{i-q})$. Failure of these generators in cluster Monte Carlo simulations and related experiments can be attributed to the low entropy of the production rule $f()$ conditioned on the statistics of the input values $x_{i-1},...,x_{i-q}$. Being a measure only of the arithmetic operations in the generator rule, the conditional entropy is independent of the lag in the recurrence or the period of the sequence. In that sense it measures a more profound quality of a random number generator than empirical tests with their limited horizon.

4 pages, 4 figures

References in corpus (8)

• A Portable High-Quality Random Number Generator for Lattice Field Theory Simulations
• Physical tests for Random Numbers in Simulations
• Analysis of Random Number Generators Using Monte Carlo Simulation
• Four-tap shift-register-sequence random-number generators
• Errors in Monte Carlo simulations using shift register random number generators
• The RANLUX generator: resonances in a random walk test
• On the quality of random number generators with taps
• Bit Level Correlations in Some Pseudorandom Number Generators

Cited by in corpus (8)

• Random numbers for large scale distributed Monte Carlo simulations
• Properties making a chaotic system a good Pseudo Random Number Generator
• Pseudo Random Coins Show More Heads Than Tails
• Non Sequential Recursive Pair Substitution: Some Rigorous Results
• Artificial Sequences and Complexity Measures
• Random Number Generators: A Survival Guide for Large Scale Simulations
• How Random Is Quantum Randomness? An Experimental Approach
• Narayana Sequences for Cryptographic Applications