Compositions of Random Functions on a Finite Set
| Autor: | Eric Schmutz, Avinash Dalal |
|---|---|
| Rok vydání: | 2002 |
| Předmět: |
Composite function
Discrete mathematics Applied Mathematics Composition (combinatorics) Expected value Condensed Matter::Mesoscopic Systems and Quantum Hall Effect Theoretical Computer Science Combinatorics Mathematics::Probability Computational Theory and Mathematics Discrete Mathematics and Combinatorics Geometry and Topology Constant (mathematics) Finite set Mathematics |
| Zdroj: | The Electronic Journal of Combinatorics. 9 |
| ISSN: | 1077-8926 |
| DOI: | 10.37236/1642 |
| Popis: | 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$. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|