On the distribution of the number of vertices in strata of a random mapping

G. V. Proskurin

Teoriâ veroâtnostej i ee primeneniâ, Tome 18 (1973) no. 4, pp. 846-852

Résumé

The set of mappings of a set $X_m$ of $m$ elements into itself is considered. For each mapping, all the vertices are distributed into strata with respect to the set of cycle vertices according to the lengths of the paths which connect them with the nearest cycle vertex. Let $\zeta_{m,j}$ be the number of vertices in the $j$th stratum of a random mapping. We prove that, if $m$ and $j\rightarrow\infty$ so that $j/\sqrt{m}\rightarrow\alpha, 0\alpha_1\leq\alpha\alpha_2\infty$, then the distributions of random variable $\zeta_{m,j}/\sqrt{m}$ converge to a limit distribution. Explicit expressions for moments and the density of the limit distribution are found. It follows that the distributions of the random variables $\eta_m/2\sqrt{m}$ converge to the Kolmogorov distribution, $\eta_m$ being the number of non-empty strata of the random mapping.