Cycles in random k-ary maps and the poor performance of random random number generation

2004/04/05 by Robin Pemantle, Pemantle, Robin
Computer Science · Mathematics · #65C10 #Algorithms and Data Compression #Chaos-based Image/Signal Encryption #FOS: Mathematics #Mathematical Dynamics and Fractals #Probability (math.PR) #math.PR #msc:65C10

paper · pdf · doi:10.48550/arxiv.math/0404103

18 pages

arxiv created 2004/04/05 · openalex publication_date 2004/04/05 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Knuth shows that iterations of a random function perform poorly on average as a random number generator. He proposes a generalization in which the next value depends on two or more previous values. This note demonstrates, via an analysis of the cycle length of a random k-ary map, the equally poor performance of a random instance in Knuth's more general model.

Related

• Period Lengths for Iterated Functions
• Periods of iterations of functions with restricted preimage sizes
• Uses of randomness in computation
• Relations between randomness deficiencies
• Random iterations of maps on ℝ^k: asymptotic stability, synchronization and functional central limit theorem