Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Iteration entropy

Author: Joachim von zur Gathen
Journal: Math. Comp. 88 (2019), 1991-2003
MSC (2010): Primary 11K45, 37P25, 68W20, 94A60
Published electronically: October 30, 2018
MathSciNet review: 3925494
Full-text PDF
View in AMS MathViewer New

Abstract | References | Similar Articles | Additional Information

Abstract: 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, this entropy turns out to be asymptotically (for a growing number of iterations) close to $ \log _2 n$ minus the entropy of the vector of its cycle lengths. For general functions, a similar approximation holds.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Mathematics of Computation with MSC (2010): 11K45, 37P25, 68W20, 94A60

Retrieve articles in all journals with MSC (2010): 11K45, 37P25, 68W20, 94A60

Additional Information

Joachim von zur Gathen
Affiliation: B-IT, Universität Bonn, Endenicher Allee 19c, 53115 Bonn, Germany

Received by editor(s): December 31, 2017
Received by editor(s) in revised form: May 10, 2018
Published electronically: October 30, 2018
Article copyright: © Copyright 2018 American Mathematical Society