Asymptotic properties of the number of inversions in a random forest

V. A. Vatutin

Matematičeskie voprosy kriptografii, Tome 11 (2020), pp. 7-22.

Résumé

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 )$.

Bibliographie

[1] Vatutin V. A., “Raspredelenie rasstoyaniya do kornya minimalnogo poddereva, soderzhaschego vse vershiny dannoi vysoty”, Teoriya veroyatn. i ee primen., 38:2 (1993), 273–287 | MR | Zbl

[2] Vatutin V. A., “Asimptoticheskie svoistva chisla inversii v raskrashennykh derevyakh”, Matematicheskie voprosy kriptografii, 10:4 (2019), 9–24 | MR

[3] Kharris T., Teoriya vetvyaschikhsya protsessov, Nauka, M., 1966, 355 pp.

[4] Kolchin V. F., Sluchainye otobrazheniya, Nauka, M., 1984, 207 pp. | MR

[5] Pavlov Yu. L., “Predelnye raspredeleniya vysoty sluchainogo lesa”, Teoriya veroyatn. i ee primen., 28:3 (1983), 449–457 | MR | Zbl

[6] Addario-Berry L., Devroye L., Janson S., “Sub-Gaussian tail bounds for the width and height of conditioned Galton–Watson trees”, Ann. Probab., 41:2 (2013), 1072–1087 | DOI | MR | Zbl

[7] Aldous D., Pitman J., “Brownian bridge asymptotics for random mappings”, Random Struct. Algor., 5 (1994), 487–512 | DOI | MR | Zbl

[8] Cai X. S., Holmgren C., Janson S., Johansson T., Skerman F., “Inversions in split trees and conditional Galton-Watson trees”, Comb., Probab. and Comput., 28:3 (2019), 335–364 | DOI | MR | Zbl

[9] Flajolet P., Poblete P., Viola A., “On the analysis of linear probing hashing”, Algorithmica, 22 (1998), 490–515 | DOI | MR | Zbl

[10] Chassaing P., Louchard G., “Reflected Brownian bridge area conditional on its local time at the origin”, J. Algorithms, 44 (2002, 29–51) | DOI | MR | Zbl

[11] Knight F. B., “The moments of the area under reflected Brownian bridge conditional on its local time at zero”, Int. J. Stoch. Analysis, 13:2 (2000), 99–124 | MR | Zbl

[12] Pitman J., Combinatorial Stochastic Processes, Lect. Notes Math., 1875, Springer-Verlag, Berlin–Heidelberg, 2006, 260 pp. | MR | Zbl

[13] Pitman J., “The SDE solved by local times of a Brownian excursion or bridge derived from the height profile of a random tree or forest”, Ann. Probab., 27:1 (1999), 261–283 | DOI | MR | Zbl