2017/12/04 by Joachim von zur Gathen, Gathen, Joachim von zur
Computer Science · Mathematics · Physics and Astronomy · #11K45 #37P25 #68W20 #94A60 #Computability, Logic, AI Algorithms #FOS: Mathematics #Mathematical Dynamics and Fractals #Number Theory (math.NT) #Statistical Mechanics and Entropy #math.NT #msc:11K45 #msc:37P25 #msc:68W20 #msc:94A60
paper · pdf · doi:10.48550/arxiv.1712.01407
In Version 2, the definition of iteration entropy is modified by subtracting log_2(n) from it. This simplifies some expressions
openalex publication_date 2017/12/04 · arxiv created 2017/12/19 · arxiv updated 2017/12/20 · openalex created_date 2022/09/16 · openalex updated_date 2026/07/28
We apply a common measure of randomness, the entropy, in the context of iterated functions on a finite set with n elements. For a permutation, it turns out that this entropy is asymptotically (for a growing number of iterations) close to log2(n) minus the entropy of the vector of its cycle lengths. For general functions, a similar approximation holds.