Random mappings with bounded height

V. N. Sachkov

Teoriâ veroâtnostej i ee primeneniâ, Tome 18 (1973) no. 1, pp. 122-132

Résumé

The paper considers a family $\mathfrak G_n^h$ of mappings $\sigma$ of a finite set $\mathfrak A$ of $n$ elements into itself such that the height of trees in graphs $\Gamma(\mathfrak A,\sigma)$, $\sigma\in\mathfrak G_n^h$ does not exceed $h$. A collection of $a\in\mathfrak A$ is said to belong to the $i$-th layer of a mapping $\sigma$ if $i$ is the least number such that $\sigma^ia=\sigma^{i+p}$, $p>0$ is an integer. The asymptotics for the number of elements of $\mathfrak G_n^h$ as $n\to\infty$ is found. It is shown that the distribution of points of $\mathfrak A$ among the layers of a random mapping $\sigma\in\mathfrak G_n^h$ for an appropriate normalizations tends to a proper multi-dimensional normal distribution. The distribution of the number of components of $\Gamma(\mathfrak A,\sigma)$ for a random $\sigma\in\mathfrak G_n^h$ normalized in an appropriate way is asymptotically normal and the number of contours of a given length is asymptotically distributed according to a Poisson law. The number of images of an element $a\in\mathfrak A$ with respect to a random mapping $\sigma\in\mathfrak G_n^h$ has, in the limit, the uniform distribution. The parameters of all distributions are expressed in terms of a real solution of the equation $$ L_h(\rho)=1 $$ where $L_0(\rho)=\rho$, $L_k(\rho)=\rho e^{L_{k-1}(\rho)}$, $k=1,\dots,h$.