RUS  ENG
Полная версия
ЖУРНАЛЫ // Математические вопросы криптографии // Архив

Матем. вопр. криптогр., 2020, том 11, выпуск 4, страницы 7–22 (Mi mvk337)

Эта публикация цитируется в 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



Реферативные базы данных:


© МИАН, 2024