|
Эта публикация цитируется в 1 научной статье (всего в 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 ).$
Ключевые слова:
случайный лес, высота случайного леса, инверсия, предельная теорема.
Получено 15.V.2020
Образец цитирования:
В. А. Ватутин, “Асимптотические свойства числа инверсий в случайном лесе”, Матем. вопр. криптогр., 11:4 (2020), 7–22
Образцы ссылок на эту страницу:
https://www.mathnet.ru/rus/mvk337https://doi.org/10.4213/mvk337 https://www.mathnet.ru/rus/mvk/v11/i4/p7
|
Статистика просмотров: |
Страница аннотации: | 211 | PDF полного текста: | 83 | Список литературы: | 30 | Первая страница: | 2 |
|