Asymptotic normality of number of multiple coincidences of chains in complete q-ary trees and forests with randomly mark.pdf Введение Повторения событий могут свидетельствовать о наличии закономерностей, при анализе которых возникают задачи о вычислении или оценке значений вероятностей повторений событий в наборах независимых случайных величин. В исследованиях по этой тематике первоначально рассматривались задачи о повторениях цепочек случайных символов [1-4], естественным продолжением этих исследований стали работы, связанные с повторениями паттернов в деревьях со случайно помеченными вершинами. Распределения числа вхождений заданного поддерева в случайное дерево рассматривались в [5, 6], задачи такого рода возникают в компьютерных науках [7, 8] при анализе алгоритмов или, например, в связи с древовидной структурой XML-документов, которые используются, в частности, на портале Госуслуг. Подобные задачи также могут возникать в связи с построением статистических критериев и анализом генетических последовательностей. Предельные пуассоновские теоремы для числа совпадений меток цепочек в двоичном или q-ичном дереве, метки вершин которого независимы и имеют равновероятное распределение на конечном алфавите, получены в [9, 10], предельная пуассоновская теорема для числа совпадений паттернов в q-ичном дереве с равновероятными метками вершин доказана в [4]. В настоящей работе рассматриваются полные q-ичные корневые деревья и леса, составленные из таких корневых деревьев. Некорневым вершинам деревьев присвоены случайные метки, выбранные независимо из множества {1,2,..., N} в соответствии с некоторым вероятностным распределением. Изучается число наборов по r 2 путей длины s на одном или нескольких деревьях, для которых совпадают соответствующие цепочки меток вершин. Получены достаточные условия асимптотической нормальности этой случайной величины при неограниченном увеличении высоты деревьев. 1. Повторения цепочек на дереве Пусть Tr(H) -полное q-ичное корневое дерево высоты H и вершинам этого дерева присвоены незавимые в совокупности случайные метки, выбираемые из конечного множества {1, 2,. . .,N} в соответствии с положительными вероятностями p1,... , pN, где p1 + ... + pN = 1. Пусть s < H. Через W(H, s) будем обозначать множество цепочек длины s в дереве Tr(H), начало которых имеет высоту, не превосходящую H-s. Нетрудно показать [11], что q H - s +1 1 q H +1 q s |W

Скачать электронную версию публикации