On the number of predecessors in constrained random mappings (Q1375862): Difference between revisions

The author considers random mappings of the set \(M_n= \{1,2, \dots, n\}\) into itself. It is obvious that each mapping \(f\) can be represented by a directed graph with vertex-set \(M_n\) and arc-set \(\{(i,f(i)); i\in M_n\}\). Given a set \(D\) of nonnegative integers with \(0\in D\), the set of mappings \(F^D_n\) is defined to contain those mappings only whose vertex-indegrees in their corresponding graph-representations belong to \(D\). Suppose that \(F^D_n\) is equipped with the uniform probability measure and let \(x\in M_n\) be chosen at random with probability \(1/n\). \(y\in M_n\) is called a predecessor of \(x\) in \(f\in F^D_n\) if there exists \(j>0\) such that the \(j\)th iterate of \(f\) applied on \(y\) yields \(x\). The author proves under mild conditions on \(D\) a local limit theorem for the distribution of the number of predecessors of a random point \(x\) as \(n\to\infty\). An asymptotic expression for the expected number of predecessors is also derived.