Iterating random functions on a finite set

2002/07/29 by William M. Y. Goh, W. M. Y. Goh, P. Hitczenko +6
Mathematics · #05A05 #05A16 #60C05 #60J10 #Combinatorics (math.CO) #FOS: Mathematics #Mathematical Approximation and Integration #Mathematical Dynamics and Fractals #Probability (math.PR) #Stochastic processes and statistical mechanics #math.CO #math.PR #msc:05A05 #msc:05A16 #msc:60C05 #msc:60J10

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

update references and conjecture's status

openalex publication_date 2002/07/29 · arxiv created 2002/10/31 · arxiv updated 2009/11/30 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

Let f₁,f₂,..., be functions chosen independently and uniformly from the set of all functions from a set of cardinality n into itself. Let g_t be the composition of the first t functions, and let T be the smallest t for which g_t is constant. We find the limiting distribution of T/n, as n --> infinity.

Related

• Limits of Boolean Functions on F_pⁿ
• SAMPLING ALMOST PERIODIC FUNCTIONS WITH RANDOM PROBES OF FINITE DENSITY
• Bowen's formula and the difference between random iterated function systems and random recursive constructions
• Distribution of Normalized Zero-Sets of Random Entire Functions with Small Random Perturbation
• The optimal sub-Gaussian normalisation for randomised monotone functions