RUS  ENG
Full version
JOURNALS // Teoriya Veroyatnostei i ee Primeneniya // Archive

Teor. Veroyatnost. i Primenen., 1973 Volume 18, Issue 1, Pages 122–132 (Mi tvp2685)

This article is cited in 18 papers

Random mappings with bounded height

V. N. Sachkov

Moscow

Abstract: 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$.

Received: 01.03.1971


 English version:
Theory of Probability and its Applications, 1973, 18:1, 120–130

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2025