Федеральное государственное автономное образовательное

учреждение высшего профессионального образования

Национальный исследовательский университет "Высшая

школа экономики"

На правах рукописи

Солдаткина Мария Васильевна

Многомерные параметрические модели случайных подстановок и их

вероятностно-статистический анализ

Специальность 01.01.05-Теория вероятностей и математическая статистика (физико-математические наук

и) Диссертация на соискание ученой степени кандидата физикоматематических наук

Научный руководитель доктор физико-математических наук, профессор Ивченко Г.И.

Москва - Оглавление Введение

Глава 1 Равновероятная модель случайных подстановок: обзор результатов

§1. Введение

§2. Отображения

§3. Подстановки и их цикловая структура

§4. Случайные подстановки, распределение их цикловой структуры

§5. Некоторые вспомогательные результаты

§6. Число циклов случайной подстановки

§7. Циклы конечной длины

§8. Циклы большой длины

§9. Длина максимального цикла

§10. Общая картина

Глава 2 d -параметрическая модель случайных подстановок и её анализ §1. Модель и основные соотношения для неё

Мера и производящие функции

1.1.

Моменты

1.2.

1.3. Вектор чисел A j - циклов

1.4. Максимальные длины A j - циклов

1.5. Представление в виде условного распределения

1.6. Подстановки с рандомизированной степенью

§2. Конкретизации d - параметрической модели

Двухпараметрическая модель

2.1.

d -инволюции

2.2.

Подстановки с кратными длинами циклов

2.3.

Ar -циклы

2.4.

§3. Асимптотическая нормальность чисел конгруэнтных циклов в d -параметрической модели случайных подстановок

Конгруэнтные циклы подстановки

3.1.

3.2. Асимптотическая нормальность чисел конгруэнтных циклов случайной подстановке (доказательство основного результата).

Глава 3. Статистика d - параметрической модели случайных подстановок.

§1. Асимптотическое оценивание

§2. Многовыборочный случай

§3. Критерий согласия

§4.Критерий однородности

§5. Статистические задачи для случайных подстановок с цензурированными данными

5.1. Случайные подстановки с цензурированными данными.............. 5.2. Оценивание параметров

5.3. Проверка гипотез

5.4. Большие выборки

5.5. Гипотеза однородности

СПИСОК ЛИТЕРАТУРЫ

Введение Подстановки степени n, n 2 (далее используется термин « n подстановки»), то есть взаимно однозначные отображения конечного множества наиболее интересных и популярных в математической литературе объектов дискретной математики. Неослабевающий в течение многих лет интерес к ним со стороны многочисленных исследователей обусловлен как их разнообразными (можно даже сказать – неисчерпаемыми) и глубокими аналитическими свойствами, так и широким применением их в различных областях научной и практической деятельности. Литература, посвященная подстановкам, практически необозрима, и поток соответствующих публикаций не истощается.

В последнее время все большую актуальность приобретают проблемы защиты информации, для решения которых во многих случаях вполне адекватными оказываются модели случайных подстановок, когда на множестве S n всех n! n -подстановок вводится та или иная вероятностная мера P, в соответствии с которой каждая подстановка s S n может наблюдаться с вероятностью P(s). Так возникает интереснейший объект вероятностной комбинаторики – случайные подстановки. При этом для различных целей адекватными оказываются различные варианты задания меры P.

Так, если речь идет о комбинаторных, или перечислительных, задачах, когда требуется определить число подстановок, обладающих некоторым заданным свойством, то адекватной является равномерная мера: P s, s S n. Такая равновероятная модель, которую принято называть классической, в основном была (да и продолжает оставаться) главным объектом интереса в этой области. Краткому обзору основных известных результатов для этой модели посвящена глава 1 данной работы.

В тоже время, внутренняя логика развития теории и запросы исследования и иных моделей случайных подстановок, учитывающих различного рода отклонения от равновероятности. Так, в частности, важнейшая статистическая проблема проверки адекватности, скажем, той же равновероятной модели, требует рассмотрения различного рода альтернатив и изучения поведения тестовых характеристик подстановки при различных отклонениях меры P от равномерности.

неравновероятных моделей случайных n -подстановок был предложен в работах Г.И.Ивченко и Ю.И.Медведева [7,8]. Ими была введена следующая n - параметрическая модель: если cn c1, c2,..., cn есть цикловая структура подстановки s S n (подстановка s имеет ci циклов длины i, i 1,..., n ), то она наблюдается с вероятностью, Здесь и далее I () – индикатор события A : I ( A) 1, если A имеет место и 0 в противном случае, и H n ( ) – необходимый нормирующий множитель, называемый статистической суммой модели и имеющий вид Здесь и далее мы будем использовать следующее обозначение:

если функция f(z) имеет представление в виде степенного ряда:

с некоторым положительным радиусом сходимости, то для ее коэффициентов a n будем писать an z n f z.

cn c1, c2,..., cn случайной подстановки в модели (В.1) имеет место представление где t t11, t2 2,..., tn n Как отмечается в [8], соотношение (В.3) «может быть основой для изучения различных структурных свойств подстановок в рамках общей модели». В [8] также приводится ряд конкретных примеров подстановок, но при этом отмечается, что «более детальное исследование случайных подстановок в общей модели ждёт своего времени».

продвижения в этой тематике рассмотреть различные конкретизации общей модели (В.1) при тех или иных ограничениях на число конечномерными моделями при небольших значениях числа d свободных параметров ), и при этом, как обычно, акцентировать внимание на изучении основных характеристик подстановки типа чисел циклов конечной длины, общего числа циклов, длин максимальных циклов и т.д.

Такой характер и имеет настоящая работа. Мы рассматриваем d мерную ( d 2 ) параметрическую модель, определяемую некоторым разбиением множества X n = 1,2,..., n следующим образом: будем называть A j - циклами подстановки подмножества A j, а общее число A j -циклов n -подстановки s обозначено число A j -циклов длины i в подстановке s ; тогда конструктивной и поддающейся анализу, и, в то же время, оставляет модели достаточное число степеней свободы, чтобы охватить большее число различных, представляющих практический интерес, вариантов постановок конкретных вероятностных и статистических задач для неравновероятных подстановок.

Вероятностному анализу (точному и асимптотическому при конкретизаций посвящена вторая глава работы. В третьей главе полученные результаты применяются для решения статистических задач оценивания неизвестных параметров и проверки гипотез в рамках этой модели.

Глава 1 Равновероятная модель случайных Теория случайных и равновероятных подстановок, когда каждая n-подстановка из симметрической группы наблюдается с вероятностью n! 1, берёт своё начало с классической работы В.Л.

Гончарова 1944г. «Из области комбинаторики» [1]. В этой работе с помощью вероятностного подхода проведено обстоятельное исследование структуры n-подстановок, включая их асимптотический анализ, когда степень подстановок n принимает большие значения (при С тех пор равновероятная модель случайных подстановок продолжает оставаться наиболее популярным объектом вероятностной комбинаторики. Их современная теория настолько многопланова, и посвящённая им литература настолько обширна, что и то и другое практически необозримы. Случайным (равновероятным) подстановкам уделено значительное внимание в монографиях [1-3,14где подробно изложена как соответствующая теория, так и история её развития (с библиографическими комментариями в [2,3]).

Интерес к исследованию как чисто комбинаторных, так и вероятностных свойств подстановок не ослабевает, о чём говорит большое число последних публикаций по теме, поток которых не истощается. Краткий обзор уже накопленных в рамках этой модели результатов приводится в данной главе.

Подстановки – это особый вид отображений конечного множества в себя, поэтому предварительно мы кратко напомним некоторые общие факты из теории отображений, которые понадобятся нам в дальнейшем.

Отображением множества X в Y называется любое правило (обозначим его символом s), ставящее в соответствие каждому элементу x X некоторый элемент y Y. Это записывается так:

который отображается x, называется его образом, а исходный элемент x – прообразом у (при отображении s).

При этом мы всегда будем предполагать выполненным свойство однозначности: образ всегда только один. Что касается числа прообразов данного отображения оно может быть своим, то есть это число является характеристикой отображения.

рассматриваются конечные множества. Если объем X n, то говорят об n-множестве и записывают его так: X n 1,2,..., n. Часто множество Y совпадает с X. В этом случае говорят об отображении множества Х в себя – именно этот случай и рассматривается в теории подстановок.

следующей таблицы:

где в верхней строке перечисляются элементы множества X n, а в sk sk X n, k 1,2,..., n.

ориентированный граф Г n s, множество вершин которого составляет направленными из k в sk, k 1,2,..., n..

Число дуг, входящих в вершину k в графе Г n s, равно числу прообразов элемента k при отображении s и называется кратностью вершины k.

Граф Г n s отображения s естественным образом разбивается на связные компоненты, при этом каждая связная компонента содержит ровно один контур (цикл) и, возможно, подходы к нему. Если какойто элемент k X n отображается в себя же: k sk (в этом случае говорят, что отображение s оставляет элемент k на месте), то в графе Г n s в вершине k имеется петля. Таким образом, петля - это цикл длины 1. Вершины графа Г n s, лежащие на циклах, называются циклическими, их число для конкретного цикла называется длиной этого цикла.

число связных компонент графа Г n s, число циклических точек, число циклов заданной длины, размер наибольшей компоненты (число вершин в ней) и т.д.

Приведем два важных примера конкретных отображений.

дополнительных ограничений (помимо однозначности), то есть в нижней строке таблицы (2.1) на каждом месте может стоять любой элемент множества X n, то мы получаем класс всех однозначных отображений множества X n в себя, обозначаемый Очевидно, число таких отображений Если отображение s взаимно однозначное, то есть для любого k X n имеется только один прообраз, то нижняя строка таблицы (2.1) содержит все элементы X n, как-то переставленные. Число всех перестановок из n элементов равно n!; таким образом, число различных взаимно однозначных отображений множества X n в себя равно n!. Такие отображения называются подстановками степени n n-подстановками, обозначается S n. Для любой подстановки s S n ее граф Г n s состоит только из циклов, кратности всех вершин равны 1 и все вершины являются циклическими.

Подстановки играют в математике и её приложениях исключительную роль, они и являются предметом нашего внимания.

В теории отображений основной интерес представляют, так называемые, перечислительные комбинаторные задачи, связанные с подсчетом числа отображений заданного класса, обладающих изучаемым свойством. Например, может представлять интерес вопрос: сколько существует n-подстановок, имеющих заданное число циклов определенной длины? При решении задач такого рода весьма эффективным оказался вероятностный подход, впервые примененный В.Л. Гончаровым в [1]. В настоящее время вероятностный подход успешно применяется при исследовании структуры различных отображений.

комбинаторных задач к соответствующим вероятностным задачам.

Пусть Fn ={s} - некоторый класс отображений множества X n в себя, и H есть некоторое свойство, которым каждое отображение s Fn может свойством H, обозначим Fn (H). Суть вероятностного подхода для определения объема Fn H состоит в следующем. На множестве Fn задается равномерная вероятностная мера, приписывающая каждому Тем самым получается конструкция случайного отображения.

Далее, по классическому определению вероятности, можем записать соотношение:

Если мы можем, используя вероятностные методы, вычислить (или хотя бы приближенно оценить) эту вероятность, то мы получаем ответ в виде:

Так перечислительная задача вычисления объема Fn H сводится к вероятностной задаче вычисления вероятности случайного события { s Fn H }. Для решения же последней задачи можно использовать мощный аппарат современной теории вероятностей и в особенности ее предельные теоремы. Дело в том, что для практических применений особо актуальны ситуации, когда параметр n принимает весьма большие значения ( n ). В этих случаях необходим асимптотический анализ, и предельные теоремы теории вероятностей как раз и являются эффективным инструментом проведения таких исследований.

§3. Подстановки и их цикловая структура Как уже говорилось выше, n-подстановка – это взаимно однозначное отображение множества Xn = {1,2,….,n} в себя, класс (множество) всех таких отображений обозначается Sn = {s}, их число есть S n = n!. Стандартная запись подстановки s имеет вид:

где нижняя строка (s1, s2, …, sn) представляет собой некоторую перестановку чисел (1,2,….,n). Отметим некоторые важные свойства подстановок.

произведение sg есть n-подстановка, которая действует по правилу sg(k) = g(s(k)), k Xn.

применение этих отображений (сначала применяется s, затем g). Эта операция ассоциативна: sghk sg hk h g sk, но, вообще говоря, не коммутативна.

Далее, в множестве Sn имеется единичная подстановка e, оставляющая все элементы Xn на месте: e(k)=k для всех k X n ; для нее таблица (3.1) принимает вид:

Наконец, каждой подстановке подстановка s-1 Sn такая, что s-1 s = ss-1 = e.

Тем самым n-подстановки Sn образуют группу, которая называется подстановок изучаются в алгебре; об их значении говорит, в частности, известная теорема Кэли о том, что любая конечная группа изоморфна симметрической группе подстановок или некоторой её подгруппе. Мы же будем акцентировать внимание на комбинаторных свойствах подстановок, связанных с их цикловой структурой.

Рассмотрим граф Г n s произвольной подстановки s S n. Как уже отмечалось раньше, этот граф состоит только из циклов вида i j k … r i, которые записываются в виде строки (i, j, …, r), называемой циклом подстановки s; длина этого цикла равна числу входящих в него элементов (числу соответствующих вершин в цикле графа Г n s ); при этом цикл длины 1 имеет вид (i) и соответствует петле в Г n s в вершине i. Таким образом, подстановки из Sn могут содержать циклы любой длины j, 1 j n, и любую подстановку s S n можно записать в виде произведения ее циклов:

Представление (3.2) означает, что подстановка s имеет 1 циклов длины 1, 2 циклов длины 2 и т.д.

Говорят, что подстановка sSn принадлежит цикловому классу (1, 2, …, n) называется цикловой структурой подстановки s. По неотрицательные числа, удовлетворяющие соотношению:

комбинаторных (перечислительных) задач в теории подстановок. При решении таких задач используется вероятностный подход, в соответствии с которым считается, что каждая подстановка s S n может наблюдаться с одной и той же вероятностью P(s)=.В этом случае говорят о равновероятных (или случайных) nподстановках.

Для случайной подстановки s S n ее цикловая структура = (1, 2, …, n) становится случайным вектором, и его распределение является основой для вероятностного анализа свойств случайной подстановки.

§4. Случайные подстановки, распределение их цикловой Обозначим K n a число n-подстановок в цикловом классе подстановки по классическому определению вероятности имеем следовательно, ключевую роль в этой проблематике играют числа Для этих чисел известна формула Кэли Из формул (4.1) и (4.2) следует, что Если использовать индикатор: I A 1, если A имеет место, и 0 в противном случае, то последнее соотношение удобно записывать в более компактном виде:

распределении цикловой структуры случайной подстановки, но из него трудно извлекать конкретную информацию об особенностях функций.

Введём производящую функцию цикловой структуры = (1, 2, …, Тогда, с учетом (4.3), она имеет вид:

Рассмотрим теперь разложение экспоненты Тогда Сравнивая (4.4) и (4.5), можем записать, что представление для производящей функции цикловой структуры случайной равновероятной n-подстановки.

Представление (4.6) можно записать и в несколько ином виде.

Поскольку то, вместо (4.6) для Fn t1,..., t n можно записать представление утверждения.

функция Fn t1,..., t n её цикловой структуры = (1, 2, …, n) имеет вид (4.7).

Соотношение (4.7) является базовым в теории случайных особенностях и свойствах цикловой структуры n-подстановок, что и будет продемонстрировано в дальнейшем. Но предварительно мы напомним некоторые факты из комбинаторики и теории вероятностей, которые будут необходимы нам в качестве технического аппарата.

§5. Некоторые вспомогательные результаты 5.1. Биноминальные коэффициенты. Число C m (используется также обозначение ), 0 k m, равное количеству k-подмножеств mk множества, называется биномиальным коэффициентом, так как эти числа фигурируют в знаменитой формуле бинома Ньютона:

Для этих чисел можно использовать следующие представления:

Эти формулы можно обобщить на случай, когда показатель степени m есть произвольное действительное число. Для этого разложим функцию 1 x в окрестности точки x=0 в ряд Тейлора Сравнивая коэффициенты в (5.3) с (5.2), можно записать, что Формула (5.4) и определяет биноминальные коэффициенты C для Используя эти формулы, также можем записать разложение возрастающая факториальная функция.

коэффициентов, которые мы в дальнейшем будем использовать.

5.2. Числа Стирлинга. Если разложить убывающую факториальную функцию по степеням аргумента t:

то коэффициенты этого разложения s(n,k) есть, так называемые, числа Стирлинга первого рода.

возрастающей факториальной функции, определенной в (5.5):

5.3. Нам понадобится также следующая асимптотическая (при n ) формула:

где C =0,5772.. – постоянная Эйлера, а также формула 5.4. Производящие функции. При исследовании целочисленных случайных величин (с. в.) удобно использовать аппарат производящих функций (пр. ф.). Напомним, что если с. в. имеет распределение то её пр. ф. определяется равенством Эта функция определена по крайней мере для единичного круга она аналитична; при этом распределение с. в. и пр. ф. x однозначно определяют друг друга, причем Напомним также следующие важные свойства пр. ф.:

если у с. в. существует конечный момент r-го порядка, то её факториальные моменты E s E 1... s 1, при s r, могут быть вычислены по формулам если 1,..., n - независимые целочисленные случайные величины, то для производящей функции их суммы 1... n справедливо соотношение P k ak, k 0, (то есть ak n ak для любого фиксированного k), что символически записывается в виде L n L, эквивалентна сходимости Пример. Пусть с. в. имеет распределение Пуассона с параметром 0 : L, то есть здесь В данном случае все моменты существуют и Известно, что распределение Пуассона однозначно определяется своими моментами, при этом сформулирована и как сходимость соответствующих моментов: если фиксированного s 0, то L n L.

Аналогичные свойства имеют место и для производящих 1,..., k независимы тогда и только тогда, когда 5.5. Центральная предельная теорема (ЦПТ). В дальнейшем мы вероятностей, поэтому мы напомним как ее общую формулировку в форме А.М. Ляпунова, так и некоторые ее важные частные случаи.

Теорема Ляпунова. Пусть дана последовательность серий kn, k 1,..., n, n 1,2,..., взаимно независимых случайных величин, Обозначим Тогда, если выполнено условие Линдеберга то при n нормированная случайная величина асимптотически нормальна с параметрами (0,1), т.е.

что кратко записывается так:

Отметим также некоторые следствия этой теоремы.

Следствие 1. Если с. в. 1n, 2n,..., nn взаимно независимы и принимают лишь значения 0 и 1, при этом Следствие 2. Если взаимно независимые с. в.

§6. Число циклов случайной подстановки характеристику – общее число циклов n r.

общей производящей функции (4.7) положить t1 t 2... t n t :

Воспользовавшись разложением (5.5), из (6.1) получаем искомое представление:

В (6.2) содержится вся информация о распределении случайной вероятностей P n k, достаточно разложить правую часть в (6.2) по степеням t. Такое разложение дано в (5.7), откуда получаем, что Вычислим теперь среднее и дисперсию этой характеристики.

Для этого перепишем соотношение (6.2) следующим образом:

Заметим теперь, что i-й сомножитель в правой части (6.4) есть производящая функция бернуллиевской случайной величины i, для которой а все произведение представляет собой производящую функцию их суммы, при этом они взаимно независимы (см. п.5.4 в §5). Таким образом, (n) можно представить в виде:

случайной величины (n). Так, из него сразу же получаем, учитывая, что E i pi, D i pi qi, формулы для среднего и дисперсии:

Рассмотрим теперь вопрос об асимптотическом поведении (n) при n. Воспользовавшись формулами (5.8) и (5.9), из (6.6) получаем важный результат, что как среднее, так и дисперсия числа циклов (n) при больших значениях n ведут себя асимптотически как ln n :

Более того, из представления (6.5), на основании ЦПТ (см.

Следствие 1 в п.5.5 §5), можно сделать вывод о том, что при n Суммируя изложенное, можно сформулировать следующее утверждение.

Теорема 2. Число циклов (n) в случайной n-подстановке имеет распределение (6.3), моменты которого даны в (6.6). Если n, то случайная величина (n) асимптотически нормальна с параметрами ln n, ln n :

Этот результат позволяет приближённо оценивать число §7. Циклы конечной длины Рассмотрим теперь вопрос о том, сколько может быть в случайной n-подстановке циклов произвольной фиксированной длины любого i получается из общей производящей функции (4.7) при Как использовать представление (7.1) для анализа свойств величины i ? Проще всего найти ее факториальные моменты:

Таким образом (см. пример в п.5.4 §5), первые (целая часть) факториальные моменты случайной величины i совпадают с аналогичными моментами распределения Пуассона П.

Если n, то отсюда следует, что для любого фиксированного Но это означает, что справедлива Теорема 3. Если n, то при любом фиксированном i число i циклов длинны i в случайной n-подстановке асимптотически Замечание 1. Если рассматривать любой набор ( i1, i2,…, ik ), 1i1 0 функции Предположим, далее, что для достаточно больших значений n единственный корень rn уравнения (этот корень есть растущая функция от n и lim rn = 1).

Применим этот метод к функции G(z ), определённой в (3.3). В данном случае формулы (3.6) принимают вид:

Уравнение же (3.7) можно переписать в форме откуда следует,что при n С учётом этого находим:

В итоге формула (3.8) принимает вид где ( ) -независящая от n, непрерывная функция от.

Заметим, далее, что если в формуле (3.11) заменить вектор на вектор t = (t11,, t d d ), то, в соответствии с (1.1)-(1.2), мы производящей функции:

Асимптотика моментов Ограничимся анализом средних значений (3.5) (анализ старших моментов чрезвычайно трудоёмок и предполагает использование, вместо (3.8), соответствующих асимптотических разложений).

Повторяя проделанный выше путь для функций находим, что Такая же асимптотика имеет место и для дисперсий D C A (n), что является прямым следствием основного результата, поскольку из сходимости к нормальному распределению следует и сходимость соответствующих моментов.

Асимптотическая нормальность чисел конгруэнтных 3.2.

циклов случайной подстановке (доказательство основного результата).

Теорема 7. Если n, а параметры 1,, d фиксированы, то компоненты вектора C(n) асимптотически независимы и Доказательство.

Введём нормированные случайные величины Тогда для их совместной характеристической функции в соответствии с (3.12) имеем:

что и требовалось показать. Теорема доказана.

Добавим к этому результату некоторые комментарии.

Как хорошо известно, в модели равновероятных подстановок, когда каждая подстановка из S n наблюдается с вероятностью (n!) 1 (в нашей модели надо положить все j = 1 ), общее число циклов C (n) случайной подстановки асимптотически нормально с параметрами (ln n, ln n) [1]. Обобщение этого результата на неравновероятный вероятностью, пропорциональной C (n ), где > 0 - произвольный параметрами ( ln n, ln n). Модель Эвенса является частным случаем рассматриваемой в работе модели и получается из неё при 1 = = d =. А из приведённой теоремы следует, что в нашей модели число циклов C A (n) = C A (n) случайной подстановки асимптотически нормально с параметрами ( ln n, ln n), = j.

Таким образом, сформулированный в теореме результат обобщает свойство асимптотической нормальности числа циклов случайной подстановки (с логарифмическим порядком роста этого числа) на достаточно широкий класс неравновероятных моделей, давая одновременно информацию о более детальной структуризации циклов подстановки. В частности, теорема даёт ответ также и на вопрос о цикловой структуре подстановок с «запретами», т.е. когда какие-то A j -циклы в подстановке «запрещены» (соответствующие параметры j надо положить равными нулю).

статистический критерий проверки гипотезы о равновероятности подстановок и вычислить его предельную мощность при «близких»

альтернативах, что будет рассмотрено в Главе 3.

Выделим, в качестве следствия, случай d = 2. Здесь речь идёт о циклах чётной и нечётной длины, и из теоремы, в частности, следует, что в равновероятной модели (при 1 = 2 = 1) число тех и других в среднем асимптотически равно половине общего числа циклов ln n факт, в литературе ранее не отмечавшийся.

Наконец, если акцентировать внимание лишь на одном каком-то классе конгруэнтности, скажем, Ad -циклах, то в рассматриваемой N d ln n, d ln n и асимптотически не зависит от числа остальных Замечание 4.(Схема серий.) Пусть параметры рассматриваемой модели имеют вид Представление (3.12) остаётся справедливым и в этом случае, и мы получаем, что в схеме серий (3.15) числа конгруэнтных циклов случайной подстановки асимптотически ведут себя как независимые пуассоновские случайные величины с параметрами соответственно §1. Асимптотическое оценивание Возможности точного анализа в задачах оценивания для однопараметрической модели. Именно, в [6] обсуждаются вопросы оценивания и проверки гипотез о параметре модели Эвенса, когда произвольная подстановка s S n наблюдается с вероятностью, пропорциональной, где cs (n) - общее число циклов подстановки s и > 0 - неизвестный параметр. Это частный случай нашей модели при d = 1 и A1 = X n, и для него в [6] показано, что несмещённые оценки сущетсвуют лишь для параметрических функций вида степени не выше n, причём a(0) = 0. В частности, для самого параметра несмещённой оценки не существует. В [6] построены также оптимальные (несмещённые с минимальной дисперсией) оценки для таких параметрических функций, при этом базой для этого является известное точное распределение достаточной статистики cs (n). Также констатируется, что более широкие возможности в обсуждаемой проблематике предоставляет асимптотический подход, когда порядок подстановок n, и для этого случая развивается конструируются асимптотически несмещённые и асимптотически эффективные оценки не только для параметра, но и для широкого класса функций от него, а также рассчитываются соответствующие асимптотические доверительные интервалы.

В свете сказанного, при анализе нашей модели мы будем использовать асимптотический подход ( n ), поскольку точное использования форме получить весьма проблематично, в то время как её асимптотическое распределение, указанное в теореме 7, достаточно просто устроено.

нормированные статистики то они будут асимптотически независимы и нормальны:

Более того, на основании теорем сходимости для функций от случайных величин [13,c.335] можно заключить, что для любых утверждение для статистик j (C A (n)) :

сформулировать следующее утверждение.

асимптотически эффективной оценкой для параметра j (для дифференциируемой параметрической функции j ( j ) ), и параметры 1,…, d оцениваются независимо друг от друга.

асимтотический доверительный интервал для параметра j. Для этого прежде всего заметим, что (на основании теорем сходимости[13]) соотношение (1.2) останется справедливым, если в его правой части заменить параметр j, входящий в выражение дисперсии, оценкой C A (n). Таким образом, при n справедливо также соотношение Пусть теперь задан доверительный уровень, 0 < < 1.

нормальная функция распределения. Тогда из (1.4) следует, что Это означает, что справедлива Теорема 9. Асимптотический доверительный интервал для параметра j имеет вид Аналогично, на основании соотношения (1.3), строится асимптотический доверительный интервал для функции j ( j ).

Однако, чтобы получить в этом случае аналог соотношения (1.4)(с подстановкой в выражение диспресии статистики C A (n) вместо неизвестного параметра j ), необходимо дополнительно потребовать, чтобы производная 'j ( j ) была непрерывна [13]. При выполнении этого условия искомый -доверительный интервал асимтотически имеет вид В частности, для функции j ( j ) = j соответствующий интервал особенно прост:

§2. Многовыборочный случай независимых подстановок при одном и том же (но неизвестном) C Ai ) (n) = (C A (n), C A (n),C A (n)) есть реализация C(n) = (C A (n),, C A (n)) для i -й подстановки, i = 1,, N.

Введём статистику В условиях теоремы 7 компоненты этого вектора будут Следовательно, T j ( N, n) -асимптотически несмещённая оценка для j с асимптотической дисперсией, в N раз меньшей, чем у оценки C A (n) в одновыборочном случае. Таким образом, при таком объединении информации точность оценивания возрастает.

доверительные интервалы(точность локализации для неизвестных параметров возрастает): асимптотический -доверительный интервал для j, основанный на статистике T j ( N, n), имеет вид §3. Критерий согласия статистические критерии для случайных подстановок.

параметрами = (1,, d ), через H и называть её статистической гипотезой. Статистическая задача ставится следующим образом. Мы наблюдаем случайную подстановку s S n и подсчитываем для неё реализацию вектора C (n) = (C A (n),, C A (n)). Спрашивается, как по этой информации построить и рассчитать статистический критерий, подтверждающий либо опровергающий гипотезу H ? Если гипотеза H справедлива, то вектор C (n) имеет распределение, указанное в теореме. Отсюда следует, что в качестве тестовой статистики естественно в данном случае использовать статистику которая при справедливости гипотезы H имеет, как известно, предложить следующий стандартный критерий согласия хи-квадрат для гипотезы H : при заданной вероятности ошибки первого рода (уровня значимости) где 2,d обозначает p -квантиль распределения 2 (d ).

т.е. он в пределе имеет требуемый уровень значимости.

равновероятности подстановок H1 :1 = = d = 1. Соответствующая тестовая статистика принимает в этом случае вид:

а для критерия (3.1) можно вычислить и асимптотическое значение его мощности Wn = P{Td (n) > 12,d | H1n } при «близких»

альтернативах вида где j - произвольные фиксированные числа.

Для этого заметим, что при таком выборе (3.3) параметров j для величин C * (n) можно записать представление из которого следует, что при гипотезе H 1n случайные величины (C A (n) ln n/d )/ ln n/d, j = 1,, d, распределены асимптотически по нормальному закону со средними соответственно j / d, j = 1,, d, и единичной дисперсионной матрицей. Но тогда статистика (3.2) имеет, как известно (см.например, [10, c.144]), в качестве предельного распределение 2 (d ; 2 ) - нецентральное 2 -распределение с числом степеней свободы d и параметром нецентральности = j. Обозначив через Fd ( x; 2 ) функцию распределения этого закона, мы, следовательно, имеем, что мощность критерия (3.1) для гипотезы равновероятности H 1 удовлетворяет при альтернативах H 1n вида (3.3) следующему предельному соотношению:

В литературе уже рассматривалась задача проверки гипотезы о равновероятности подстановок с учётом возможных альтернатив. Так, в работе [6] в рамках модели Эвенса предложен соответствующий статистический критерий, основанный на общем числе циклов C (n) наблюдаемой подстановки (тестовая статистика), и определена его предельная мощность при альтернативах вида = 1 (аналог (3.3)). Построенный нами критерий (3.1) "работает" против более широкого класса альтернатив (3.3) и к тому же использует "более богатую" статистику (3.2), т.е. он является более предпочтительным.

§4. Критерий однородности В рамках нашей модели можно также ставить задачу проверки гипотезы однородности где -некоторый неизвестный параметр.

объединить, и статистика C (n) = C A (n) является асимптотически нормальной состоятельно оценивается величиной n = C (n)/ln n (см.[6]). Это позволяет заменить в статистике (3.2) (в случае справедливости гипотезы H 0 ) параметр его оценкой n, в результате чего мы получаем следующую статистику:

Из общих теорем сходимости для случайных величин(см., например, [10,c.229]) следует, что при гипотезе H 0 эта статистика распределена при предложить следующий асимптотический вариант критерия однородности: при заданном уровне значимости §5. Статистические задачи для случайных подстановок с цензурированными данными 5.1. Случайные подстановки с цензурированными данными Ранее в исследовании предполагалась известной вся цикловая информация о наблюдаемой подстановке, и соответсвующие выводы имеют асимптотический (при n ) характер. Но в этом случае не всегда является реалистичным предположение о том, что мы можем наблюдать всю цикловую последовательность c(n). Может быть и так, что наблюдению доступно лишь какое-то ограниченное число k однопараметрической модели Эвенса, когда подстановка рассматривались в работе [9]. В настоящей работе аналогичный подход применяется к описанной выше d -параметрической модели с конгруэнтными циклами.

подстановке s S n для каждого j = 1,, d доступно подсчёту лишь число A j -циклов с длинами, не превосходящими заданного уровня K j. В таком случае, пусть есть наши исходные данные (количества наблюдаемых A j -циклов).

Мы рассмотрим различные вопросы статистического вывода d параметрической модели с конгруэнтными циклами именно по таким неполным данным (5.1). При этом мы будем предполагать, что порядок подстановки n, а параметры цензурирования K j, j = 1,, d, фиксированы.

Основой для дальнейших выводов будет служить следующее утверждение об асимптотическом распределении наблюдаемых статистик c1, c2,, т.е. начальных членов цикловой структуры подстановки.

параметрической модели с конгруэнтными циклами при n числа циклов ограниченной длины асимптотически независимы, и при этом число A j -циклов длины i имеет в пределе распределение Пуассона Доказательство.

В теории случайных n -подстановок хорошо известен факт асимптотической (при n ) независимости и асимптотической пуассоновости начальных членов цикловой последовательности c(n) = (c1, c2,, cn ) случайной равновероятной подстановки, при этом L (ci ) для любого конечного i.

Аналогичное свойство имеет место и для модели Эвенса, причём в этом случае L (ci ).

Это свойство асимптотической независимости и пуассоновости подстановка s S n наблюдается с вероятностью, пропорциональной i i, где = (1,, n ), 0, - параметр меры. В этом случае для представление Отсюда следует, что производящая функция для произвольного конечного числа k начальных членов c1, c2,, ck имеет вид Далее, используя стандартную технику метода перевала, нетрудно получить, что при n и фиксированных что означает асимптотическую независимость величин c1,, ck и их пуассоновскую сходимость:

Утверждение теоремы 8 является следствием этого результата, поскольку для всех A j - циклов параметры в рассматриваемой модели одинаковы.

Следствие. Наблюдаемые статистики (5.1) асимптотически независимы, и при этом Из этих результатов следует, во-первых, что статистические выводы о каждом из параметров j можно делать независимо по наблюдению лишь соответсвующей статистики j (n), и, во-вторых, исходная проблема в асимптотике сводится к соответствующим статистическим задачам для пуассоновской модели с неизвестным параметром, решение которых достаточно хорошо известно.

5.2. Оценивание параметров полученных при одном и том же значении неизвестного параметра = (1,, d ), и, тем самым, выборка (набор наблюдаемых статистик (5.1)) цензурирования K j ) независимы и распределены в соответствии с (5.3), поэтому для суммарного числа наблюдаемых A j -циклов будет выполняться предельное соотношение Это соотношение сводит задачу оценивания параметров j пуассоновской модели.

несмещённой с минимальной дисперсией) оценкой сходящегося при случайной величиной X соотношение (5.6), мы можем сформулировать следующее общее утверждение для нашей модели.

сходящегося при всех j > 0 степенного ряда ( j ) = ai ij является статистика в частности, асимптотически оптимальная оценка параметра j имеет вид асимптотически имеет вид [10,с.287] где 2 p,r есть p -квантиль распределения хи-квадрат с r степенями свободы.

5.3. Проверка гипотез Если требуется проверить какие-то гипотезы о частных значениях параметров j в обсуждаемой ситуации, то, на основании соотношения (5.6), надо воспользоваться общей теорией для пуассоновской модели (учитывая при этом специфику тестовых статистик T j ( N, n) ) с тем лишь замечанием, что соответствующие алгоритмы в нашем случае будут иметь характер асимптотических утверждений.

Продемонстрируем это на конкретном примере проверки простой гипотезы H 0 : j = j 0 против правосторонней альтернативы H1 : j > j 0. Известно [10,§ 5.3], что в задачах такого типа существует равномерно наиболее мощный (РНМ) критерий, который 0 = j 0 N j и при заданной вероятности ошибки первого рода определим целое число t условием (асимптотически) Если же в (5.9) имеет место строгое неравенство ( < ' ), то критерий является рандомизированным и задаётся критической функцией В любом случае мощность этого критерия при произвольной альтернативе 1 = j N j > 0 вычисляется по формуле Замечание 5. В случае ( < ' ) вместо рандомизированного критерия можно также использовать нерандомизированные РНМ соответственно и (асимптотически).

Аналогично анализируется задача ( H 0, H1 ) с левосторонней альтернативой, а при двусторонней альтернативе критерий задаётся объединением двух односторонних критических областей, т.е. имеет вид Замечание 6. Случай j 0 = 1, j = 1,, d, соответствует наиболее важной для приложений гипотезе о равновероятности подстановок, и изложенная методика даёт новые критерии проверки этой гипотезы, учитывающие широкий класс специальных альтернатив, при которых j 1 для некоторых j.

5.4. Большие выборки Если число N наблюдаемых подстановок велико, то можно применить теорию больших выборок ( N ) и получить более сильные выводы. В этом случае из (5.5)-(5.6) следует, что для нормированной статистики справедлива нормальная аппроксимация и тем самым статистические выводы о параметрах j можно получать, используя соответствующую теорию нормальной модели [9]. Аналогичная ситуация рассматривалась в работе [6], поэтому, следуя ей, можно сформулировать для нашего случая следующие утверждения.

асимптотически несмещённой и асимптотически эффективной статистика (T j ) как оценка ( j ) для любой дифференциируемой функции.

Теорема 13. Асимптотическим - доверительным интервалом для параметрической функции ( j ) с непрерывной производной ' ( j ) является интервал где 1 (t ) -обратная функция к стандартной нормальной функции распределения (x).

Теорема 14. Критерий уровня значимости для проверки гипотезы H 0 : j = 1 при левосторонней альтернативе H1 : j < асимптотически задаётся критической областью "пороговыми" здесь являются альтернативы вида и мощность критерия (5.15) при таких близких альтернативах удовлетворяет при N соотношению значимости асимптотически имеет вид и его мощность при близких альтернативах асимптотически равна (t u ).

( H 0, H1 = H1 H1 ) критерий асимптотически имеет вид и его мощность при близких альтернативах асимптотически равна (t u/2 ) (t u/2 ).

контролировать значения отдельных координат параметрического вектора = (1,, d ). Вместе с тем желательно уметь также проверять гипотезы и о полном этом векторе. Важнейшей такой гипотезой является утверждение означающее, что подстановки выбираются равновероятно из S n.

Если эта гипотеза справедлива, то из (5.12)-(5.13) следует, что нормальны N (0,1), и они асимптотически независимы.

распределена по закону 2 (d ) :

Этот результат позволяет сформулировать следующий критерий согласия для гипотезы равновероятности H 0, учитывающий всю исходную информацию.

Теорема 15. При заданном уровне значимости 5.5. Гипотеза однородности Выше предполагалось, что в процессе наблюдения над остаётся неизменным, что на самом деле является гипотезой, которая сама должна быть подвергнута статистической проверке; такая гипотеза и называется гипотезой однородности. Здесь предлагается асимптотический (для больших выборок) вариант соответствующего критерия однородности (§4).

Итак, теперь мы считаем, что каждый из векторов (5.4) получен, вообще говоря, при своём (но неизвестном) значении параметра.

Обозначим значение этого параметра для подстановки s k через ( k ) = (1( k ),, dk ) ). Тогда гипотеза однородности есть утверждение В силу предположения о независимости подстановок и соотношения (5.3) можно считать, что при гипотезе H 0 данные Пуассона ( j j ) при некотором j > 0 (далее для краткости полагаем j = j j ); при этом, в силу Следствия из п. 5.1, для разных j выборки (5.19) асимптотически независимы.

Построим выборочные среднее и дисперсию выборки (5.19):

асимптотически нормальна N (0,1), а так как для разных j такие статистики асимптотически независимы, то объединённая статистика будет иметь при гипотезе H 0 асимптотически распределение 2 (d ).

Тем самым, основываясь на статитсике TN, можно предложить следующий критерий согласия для гипотезы H 0.

Теорема 16. При заданном уровне значимости гипотеза однородности H 0 отвергается тогда и только тогда, когда TN 12,d

СПИСОК ЛИТЕРАТУРЫ

1. Гончаров В.Л. Из области комбинаторики. - Изв. АН СССР.

Сер. матем., т.8, №1, с. 3-48, 1944.

2. Колчин В.Ф. Случайные отображения. – М.: Наука, 1984.

3. Колчин В.Ф. Случайные графы. – М.: Физматлит, 2000.

4. Ивченко Г.И., Медведев Ю.И. Метод В.Л. Гончарова и его развитие в анализе различных моделей случайных подстановок.

– Теория вероят. и ее примен., т. 47, №3, с. 558-566, 2002.

5. Ивченко Г.И., Медведев Ю.И. О случайных подстановках. – Труды по дискретной математике, т.5, с.73-92, 2002.

6. Ивченко Г.И., Медведев Ю.И. Статистика параметрической модели случайных подстановок. – Труды по дискретной математике, т. 8, с.116-127, 2004.

7. Ивченко Г.И., Медведев Ю.И. Случайные комбинаторные объекты. - Доклады РАН, т. 396, № 2, с. 151-154, 2004.

8. Ивченко Г.И., Медведев Ю.И. Случайные подстановки: общая параметрическая модель. – Дискретная математика, т.18, №4, с.105-112, 2006.

9. Ивченко Г.И., Медведев Ю.И. Статистические выводы для случайных подстановок по неполным данным. – Труды по дискретной математике, т. 9, с. 66-76, 2006.

10. Ивченко Г.И., Медведев Ю.И. Введение в математическую статистику. – М: ЛКИ/URSS, 2010.

11. Ивченко Г.И., Соболева М. В. Некоторые неравновероятные модели случайных подстановок. – Дискретная математика, т.23, №3, с. 23–31, 2011.

12. Ивченко Г.И., Солдаткина М. В. Статистические задачи для случайных подстановок с цензурированными данными. – Дискретная математика, т. 24, №4,с. 104–113, 2012.

13. Рао С.Р. Линейные статистические методы и их применения. – М.: Наука, 1968.

14. Риордан Дж. Введение в комбинаторный анализ. – М.: ИЛ, 1963.

15. Сачков В.Н. Комбинаторные методы дискретной математики. – М.: Наука, 1977.

16. Сачков В.Н. Вероятностные методы в комбинаторном анализе.

– М.: Наука, 1978.

17. Сачков В.Н. Введение в комбинаторные методы дискретной математики. 2-е изд. – М.: МЦНМО, 2004.

18. Соболева М. В. Асимптотическая нормальность чисел конгруэнтных циклов в случайных подстановках – Дискретная математика, т. 24, №1,с. 123–131, 2012.

19.Солдаткина М.В. Оценивание параметров в одной модели случайных подстановок – Труды КарНЦ РАН. No 5. Сер.

Математическое моделирование и информационные технологии, Вып. 3, Петрозаводск: КарНЦ РАН, с. 106-109, 2012.

20. Феллер В. Введение в теорию вероятностей и ее приложения.

Т.1. – М: Мир, 1984.

21. Якымив А.Л. Вероятностные приложения тауберовых теорем. – М. : Физматлит, 2005.

22. Якымив А.Л. Предельная теорема для логарифма порядка случайной A-подстановки. – Дискретная математика т. 22, №1,с. 126-149, 2010.

23.Ewens W. J. The sampling theory of selectively neutral alleles. – Theor. Popul. Biol. v. 3, p. 87-112, 1972.