Geodesic
Compositions of random functions on a finite set
The electronic journal of combinatorics, Tome 9 (2002)
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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$.
DOI : 10.37236/1642
Classification : 60C05, 60J10, 05A05, 05A16
Mots-clés : composite function, number of compositions 
@article{10_37236_1642,
     author = {Avinash Dalal and Eric Schmutz},
     title = {Compositions of random functions on a finite set},
     journal = {The electronic journal of combinatorics},
     year = {2002},
     volume = {9},
     doi = {10.37236/1642},
     zbl = {0994.60003},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/1642/}
}
TY  - JOUR
AU  - Avinash Dalal
AU  - Eric Schmutz
TI  - Compositions of random functions on a finite set
JO  - The electronic journal of combinatorics
PY  - 2002
VL  - 9
UR  - http://geodesic.mathdoc.fr/articles/10.37236/1642/
DO  - 10.37236/1642
ID  - 10_37236_1642
ER  - 
%0 Journal Article
%A Avinash Dalal
%A Eric Schmutz
%T Compositions of random functions on a finite set
%J The electronic journal of combinatorics
%D 2002
%V 9
%U http://geodesic.mathdoc.fr/articles/10.37236/1642/
%R 10.37236/1642
%F 10_37236_1642
Avinash Dalal; Eric Schmutz. Compositions of random functions on a finite set. The electronic journal of combinatorics, Tome 9 (2002). doi: 10.37236/1642

Cité par Sources :