Эта публикация цитируется в
1 статье
Асимптотические свойства числа инверсий в случайном лесе
В. А. Ватутин Математический институт им В.А. Стеклова
Российской академии наук, Москва
Аннотация:
Пусть
$\mathcal{F}_{n,N}=\left\{ F_{n,N}\right\} $ — множество всех лесов, каждый из которых образован
$N$ помеченными корневыми деревьями
$T_{1},T_{2},\ldots ,T_{N}$, имеющими в совокупности
$n+N$ вершин (считая корни), причем вершинам приписаны несовпадающие метки (числа от
$1$ до
$n+N$). Обозначим
$\lambda (u)$ метку, приписанную вершине
$u$ леса
$F_{n,N}$. Будем говорить, что вершина
$u$ дерева
$T_{i}$ является предком вершины
$v$ того же дерева и писать
$u\prec v$, если путь, ведущий по ребрам от корня дерева к вершине
$v$, проходит через вершину
$u$. Числом инверсий
$\mathcal{I}(F_{n,N})$ в лесе
$F_{n,N}$ называется число таких пар вершин
$u,v$ в этом лесе, что
$u\prec v$ и
$\lambda (u)>\lambda (v)$. При условии, что лес
$F_{n,N}$ выбирается случайно и равновероятно из множества
$\mathcal{F}_{n,N}$, найдено предельное распределение случайной величины
$n^{-3/2}\mathcal{I}(F_{n,N})$ при
$n\rightarrow \infty $ и
$2Nn^{-1/2}\rightarrow l\in \lbrack 0,\infty ).$
Ключевые слова:
случайный лес, высота случайного леса, инверсия, предельная теорема.
УДК:
519.212.2+
519.218.23 Получено 15.V.2020
DOI:
10.4213/mvk337