Compositions of random functions on a finite set
type: Item
instance of: scholarly article
title: Compositions of random functions on a finite set
zbMATH Open document ID: 0994.60003
author: Eric Schmutz
author: Avinash J. Dalal
published in: The Electronic Journal of Combinatorics
publication date: 2002-07-01T00:00:00Z
full work available at URL: https://eudml.org/doc/122057
full work available at URL: v9i1r26.html
review text: 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\).
Mathematics Subject Classification ID: 60C05
Mathematics Subject Classification ID: 60J10
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05A16
zbMATH DE Number: 1757092
zbMATH Keywords: composite function
zbMATH Keywords: number of compositions
MaRDI profile type: Publication
description: scientific article; zbMATH DE number 1757092