Compositions of random functions on a finite set
Summary: If we compose sufficiently many random functions on a finite set, then the composite function will be constant. We determine the number of compositions that are needed, on average. Choose random functions \(f_1, f_2,f_3,\dots \) independently and uniformly from among the \(n^n\) functions from \([n]\) into \([n]\). For \(t>1\), let \(g_t=f_t\circ f_{t-1}\circ \cdots \circ f_1\) be the composition of the first \(t\) functions. Let \(T\) be the smallest \(t\) for which \(g_t\) is constant (i.e. \(g_t(i)=g_t(j)\) for all \(i,j\)). We prove that \(E(T)\sim 2n\) as \(n\rightarrow\infty\), where \(E(T)\) denotes the expected value of \(T\).
- scientific article; zbMATH DE number 4096475
- scientific article; zbMATH DE number 4055527
- Period Lengths for Iterated Functions
- The expected degree of noninvertibility of compositions of functions and a related combinatorial identity
- On images and pre-images in a graph of the composition of independent uniform random mappings
- On the complexity of finite random functions
- Central limit theorem for the size of the range of a renewal process
- Stein's method for the Poisson-Dirichlet distribution and the Ewens sampling formula, with applications to Wright-Fisher models
- Images of a finite set under iterations of two random dependent mappings
- Distribution of the length of aperiodicity segment in the graph of k-fold iteration of uniform random mapping
- Слои в графе композиции независимых равновероятных случайных отображений
- Expected coalescence time for a nonuniform allocation process
- scientific article; zbMATH DE number 1471868 (Why is no real title available?)
- scientific article; zbMATH DE number 3994629 (Why is no real title available?)
- On the genealogy of populations: trees, branches and offspring
- The expected degree of noninvertibility of compositions of functions and a related combinatorial identity
- On estimations of distribution of the length of aperiodicity segment in the graph of k-fold iteration of uniform random mapping
- On images and pre-images in a graph of the composition of independent uniform random mappings
This page was built for publication: Compositions of random functions on a finite set
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1601113)
