Journal article
Compositions of Random Functions on a Finite Set
The Electronic journal of combinatorics, v 9(1 R)
01 Jan 2002
Abstract
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), ... independently and uniformly from among the n(n) functions from [n] into [n]. For t > 1, let gt = f(t) omicron f(t-1) omicron ... omicron 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) similar to 2n as n --> infinity, where E(T) denotes the expected value of T.
Metrics
Details
- Title
- Compositions of Random Functions on a Finite Set
- Creators
- Avinash Dalal - Drexel UniversityEric Schmutz - Drexel University
- Publication Details
- The Electronic journal of combinatorics, v 9(1 R)
- Publisher
- Electronic Journal Of Combinatorics
- Number of pages
- 7
- Resource Type
- Journal article
- Language
- English
- Academic Unit
- Mathematics
- Web of Science ID
- WOS:000209659700025
- Scopus ID
- 2-s2.0-4043118897
- Other Identifier
- 991019170598504721
InCites Highlights
Data related to this publication, from InCites Benchmarking & Analytics tool:
- Collaboration types
- Domestic collaboration
- Web of Science research areas
- Mathematics
- Mathematics, Applied