RUS  ENG
Full version
JOURNALS // Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography] // Archive

Mat. Vopr. Kriptogr., 2020 Volume 11, Issue 4, Pages 7–22 (Mi mvk337)

This article is cited in 1 paper

Asymptotic properties of the number of inversions in a random forest

V. A. Vatutin

Steklov Mathematical Institute of Russian Academy of Sciences, Moscow

Abstract: Let $\mathcal{F}_{n,N}=\left\{F_{n,N}\right\} $ be the set of all forests each of which is generated by $N$ labelled rooted trees $T_{1},T_{2},\ldots ,T_{N}$ having in total $n+N$ vertices (including the roots) with different labels (numbers from $1$ to $n+N$). Denote by $\lambda (u)$ the label assigned to the vertex $u$ of the forest $F_{n,N}$. We say that a vertex $u\in T_{i}$ is an ancestor of a vertex $v\in T_{i}$ and write $u\prec v$, if the path leading from the root of the tree to the vertex $v$ passes the vertex $u$. The number of inversions of a forest $F_{n,N}$ is the number of pairs of vertices $u,v$ in this forest such that $u\prec v$ and $\lambda(u)>\lambda(v)$. Assuming that $F_{n,N}$ is a forest selected randomly and equiprobably from $\mathcal{F}_{n,N}$ we find the limiting distribution of the random variable $n^{-3/2}\mathcal{l}(F_{n,N})$ as $n\rightarrow \infty $ and $2Nn^{-1/2}\rightarrow l\in \lbrack 0,\infty )$.

Key words: random forest, the height of a random forest, inversion, limit theorem.

UDC: 519.212.2+519.218.23

Received 15.V.2020

DOI: 10.4213/mvk337



Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024