Central limit theorem for u-statistics of tuples of vertex labels on a complete graph.pdf Исследование свойств выборочных характеристик и статистических критериев привело к необходимости изучения распределений функционалов от последовательностей случайных величин X1 , . . . , Xn вида Un = Un(Xi,...,Xn )= Е f (Xji ,...,Xjr), (1) называемых U-статистиками [1]. Число r называется порядком U-статистики. Функционалы вида (1) широко используются для проверки свойств случайных последовательностей, качества датчиков псевдослучайных чисел, наличия или отсутствия зависимости между членами последовательности, наличия образцов или повторений специального вида и в задачах, связанных с защитой информации. Основные результаты об асимптотическом поведении распределений U-статистик с непрерывными ядрами можно найти в [2]. Результаты для U-статистик от дискретных последовательностей, например для числа пар одинаковых знаков, пар одинаковых цепочек и пар эквивалентных цепочек, получены в [3] и [4] соответственно. В работе [5] установлено, что для последовательности случайных величин, удовлетворяющей условию абсолютной регулярности [6] с коэффициентом в(t) С t-h(t), где h(t) > 0 и h(t) то (t то) (например, для цепи Маркова), достаточным условием асимптотической нормальности является условие на дисперсию DUn Cn2(r-1')+K, где к > 0. Разумеется, это относится и к последовательности независимых случайных величин. Как известно [3], в последовательности независимых одинаково распределённых случайных величин на конечном алфавите при их неравновероятном распределе-2k 1 нии число k-кратных повторений s-цепочек имеет дисперсию порядка n 1 и сходится (при подходящей стандартизации) по распределению к нормальному распределению при n то. В настоящей работе приведён аналогичный результат для U-статистики от цепочек меток вершин на полном графе. Введём несколько определений. Пусть Kn - полный граф c n вершинами из множества V = {1,..., n} и СП рёбрами; а2,... ,ап - независимые в совокупности случайные величины, принимающие значения из множества AN = {0, 1, . . . , N - 1}, причём N-1 P[aj = k] = pk G (0;1), k G An, E Pk = 1k=0 Далее будем считать, что aj -метка вершины с номером j, j G V \\ {1}. Обозначим через {w(s)} цепь (связный путь без повторения рёбер) из s 1 рёбер в графе Kn, начинающийся из вершины с номером 1, не имеющей метки, и не проходящий через одну и ту же вершину дважды. Обозначим через a({w(s)}) соответствующую цепи {w(s)} последовательность из s меток вершин, через которые проходит цепь (с учётом их порядка). Число таких путей равно числу способов выбрать оставшиеся s вершин из n - 1 вершин графа (кроме вершины с номером 1) с учётом порядка, (n - 1)! поэтому в Kn всего T = АП_ 1 = ---------- цепей длины s с требуемыми свойствами. n-1 (n - s - 1)! Занумеруем их и будем писать {wu(s)}, u = 1, . . . , T. Пусть f - ограниченная по абсолютной величине константой F функция от k 2 s-мерных векторных аргументов, симметричная относительно их перестановки. Рассмотрим U-статистику вида (2) Uk(s) = f (a({wu1(s)}), . . . , a({wuk(s)})) . 1Cui

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