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

Матем. вопр. криптогр., 2023, том 14, выпуск 1, страницы 85–97 (Mi mvk431)

Условия асимптотической нормальности числа кратных повторений цепочек в помеченных полных деревьях и лесах

В. Г. Михайлов, В. И. Круглов

Математический институт им. В.А. Стеклова Российской академии наук, Москва

Аннотация: Рассматриваются полные $q$-ичные корневые деревья высоты $H$, вершинам которых присвоены независимые случайные метки, выбранные из множества $\{1,2,\ldots, N\}$, и леса, составленные из таких деревьев. В обоих случаях изучается число наборов по $r\ge 2$ путей заданной длины $s$, для которых совпадают соответствующие $s$-цепочки меток вершин. Доказаны три теоремы, указывающие достаточные условия асимптотической нормальности рассматриваемых случайных величин при неограниченном увеличении высоты деревьев. Условия допускают рост параметров $s$ и $q$.

Ключевые слова: деревья с метками, леса деревьев, цепочки меток на дереве, повторения цепочек, условия асимптотической нормальности.

УДК: 519.214+519.212.2

Получено 12.V.2022

DOI: 10.4213/mvk431



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


© МИАН, 2024