Содержание к диссертации
Введение
Глава 1 Равновероятная модель случайных подстановок: обзор результатов 9
1. Введение 9
2. Отображения 10
3. Подстановки и их цикловая структура 15
4. Случайные подстановки, распределение их цикловой структуры 18
5. Некоторые вспомогательные результаты 21
6. Число циклов случайной подстановки 27
7. Циклы конечной длины 30
8. Циклы большой длины 32
9. Длина максимального цикла 37
10. Общая картина 40
Глава 2 d -параметрическая модель случайных подстановок и её анализ 42
1. Модель и основные соотношения для неё 42
1.1. Мера и производящие функции 42
1.2. Моменты 44
1.3. Вектор чисел Aj- циклов 45
1.4. Максимальные длины Aj - циклов 46
1.5. Представление в виде условного распределения 47
1.6. Подстановки с рандомизированной степенью 48
2. Конкретизации d - параметрической модели 49
2.1. Двухпараметрическая модель 49
2.2. d-инволюции 54
2.3. Подстановки с кратными длинами циклов 55
2.4. Ar)-циклы 58 3. Асимптотическая нормальность чисел конгруэнтных циклов в
d -параметрической модели случайных подстановок 60
3.1. Конгруэнтные циклы подстановки 60
3.2. Асимптотическая нормальность чисел конгруэнтных циклов случайной подстановке (доказательство основного результата) . 65
Глава 3 Статистика d - параметрической модели случайных подстановок . 69
1. Асимптотическое оценивание 69
2. Многовыборочный случай 73
3. Критерий согласия 75
4.Критерий однородности 78
5 Статистические задачи для случайных подстановок с цензурированными данными 79
5.1. Случайные подстановки с цензурированными данными 79
5.2. Оценивание параметров 82
5.3. Проверка гипотез 84
5.4. Большие выборки 86
5.5. Гипотеза однородности 89
Список литературы 92
- Случайные подстановки, распределение их цикловой структуры
- Подстановки с рандомизированной степенью
- Асимптотическая нормальность чисел конгруэнтных циклов случайной подстановке (доказательство основного результата)
- Статистические задачи для случайных подстановок с цензурированными данными
Введение к работе
Актуальность темы
Предметом исследований в данной работе являются многомерные параметрические модели случайных подстановок и их вероятностно-статистический анализ. Подстановки степени и, п>2 (далее используется термин ««-подстановки»), то есть взаимно однозначные отображения конечного множества Хп={\,2,...,п} в себя, представляют собой один из
наиболее интересных и популярных в математической литературе объектов дискретной математики. Неослабевающий в течение многих лет интерес к ним со стороны многочисленных исследователей обусловлен как их разнообразными и глубокими аналитическими свойствами, так и широким применением их в различных областях научной и практической деятельности. Литература, посвященная подстановкам, практически необозрима, и поток соответствующих публикаций не истощается.
В последнее время все большую актуальность приобретают проблемы защиты информации, для решения которых во многих случаях вполне адекватными оказываются модели случайных подстановок, когда на множестве Sn всех п! и-подстановок вводится та или иная вероятностная мера Р, в
соответствии с которой каждая подстановка s є Sn может наблюдаться с
вероятностью P(s). Так возникает интереснейший объект вероятностной
комбинаторики - случайные подстановки. При этом для различных целей
адекватными оказываются различные варианты задания меры Р .
Так, если речь идет о комбинаторных, или перечислительных, задачах,
когда требуется определить число подстановок, обладающих некоторым
_, ч 1 заданным свойством, то адекватной является равномерная мера: "(s) = —,
\/s є Sn. Такая равновероятная модель, которую принято называть
классической, в основном и была главным объектом интереса в этой области.
В тоже время, внутренняя логика развития теории и запросы современной практики выдвигают на передний план задачи исследования и иных моделей случайных подстановок, учитывающих различного рода отклонения от равновероятности. Так, в частности, важнейшая статистическая проблема проверки адекватности, скажем, той же равновероятной модели, требует рассмотрения различного рода альтернатив и исследования поведения различных характеристик подстановки при тех или иных отклонениях меры Р от равномерности. Общий подход для конструирования и исследования неравновероятных моделей случайных и-подстановок был предложен в работах Г.И.Ивченко и Ю.И.Медведева1'. Ими была введена следующая параметрическая модель: если с(п) = {сх,с2,...,сп) есть цикловая структура
подстановки seSn (подстановка s имеет ct циклов длины /, /=1,...,и), то она наблюдается с вероятностью, пропорциональной ПД'' > где 6 = (61,...,6п),6т > 0, - параметр меры Р^:
?e(s) = I\bci =n\Wil Нп(в)> (1)
Здесь и далее /() - индикатор события А: 1(A) = 1, если А имеет место и О в противном случае, и Нп(6)- необходимый нормирующий множитель, называемый статистической суммой модели:
Нп (в) = п\ [z" ]expJ б>. — \ (2)
(здесь и далее [zn] f (z) = coe f n f (z)).
1 Ивченко Г.И., Медведев Ю.И. Случайные комбинаторные объекты. Доклады РАН. 2006. т. 396. № 2.
C. 151154.
2 Ивченко Г.И., Медведев Ю.И. Случайные подстановки: общая параметрическая модель. Дискретная
математика. 2006. т.18. №4. C.105112.
Далее, для производящей функции цикловой структуры с{п) = (сх,с2,...,сп) случайной подстановки в модели (1)
F„Q(t) = EQYltCi', t = (tl,t2,...,tn),
1=1
имеет место представление
F„e(t) = H„(txe)/H„(e), (3)
где txe = (tievt2e2,...,t„e„).
В свете сказанного, представляется естественным для продвижения в этой тематике рассмотреть различные конкретизации общей модели (1) при тех или иных ограничениях на число степеней свободы меры ~Рв, и при этом, как
обычно, акцентировать внимание на изучении основных характеристик подстановки типа чисел циклов заданных длин, общего числа циклов, длин максимальных циклов и т.д.
Специфика рассматриваемых в диссертационной работе моделей случайных подстановок в сравнении с известными в литературе состоит в следующем. Рассматривается d-мерная (d>2) параметрическая модель, определяемая некоторым разбиением множества Хп = {1,2,...,и}:
J-l и зависящая от свободного параметра Q = (Ql,...,Qd), в, >0, следующим
образом. Будем называть А, -циклами подстановки s є Sn те её циклы, длины которых являются элементами подмножества А,, а общее число А -циклов
подстановки s обозначать CA(n) = CA(n,s)=Ydсij,j = l,...,d, где символом с„
7 J isAj
обозначено число А,-циклов длины / в подстановке s (если подмножества А, имеют вид
Aj={k:k = ld + j,l>0}
для некоторых целых d>2 и l
величине
Такое сужение общей модели (1) делает её более конструктивной и поддающейся детальному анализу, и, в то же время, оставляет модели достаточное число степеней свободы, чтобы охватить большее число различных, представляющих практический интерес, вариантов постановок конкретных вероятностных и статистических задач для неравновероятных подстановок.
Вероятностная мера Рш(^), seSn, для произвольного разбиения принимает вид:
Pfi4 = /
d С . (и)
Z2X=w №J нпа(6), (4)
HnA (в) = n\[zn ]Qxp{h(z; в)}, (5)
y=l ієА '
В рамках такой модели можно рассматривать более детально структуризацию цикловой последовательности с(п) = (с1,с2,...,сп) подстановки,
именно, записывать её в виде с(«) = \су,і є Ajtj = \,...,d).
Предложенная модель обобщает в различных направлениях изучавшиеся ранее модели, включая их в себя в качестве частных случаев.
Цель работы
Целью диссертации является исследование вероятностных и статистических свойств случайных подстановок в d -параметрической модели. При этом внимание акцентируется на изучении модели с конгруэнтными циклами, в рамках которой решаются задачи оценивания неизвестных параметров модели и проверки соответствующих статистических гипотез об этих параметрах, в том числе и по неполным (цензурированным) данным.
Научная новизна
Основные результаты диссертации являются новыми и состоят в следующем.
1. Доказана асимптотическая (при и^-оо) нормальность вектора
C(n) = (CAi(n),...,CA d (n)) чисел конгруэнтных циклов случайной
подстановки, что является многомерным обобщением свойства асимптотической нормальности числа циклов случайной подстановки (с логарифмическим порядком роста этого числа) на достаточно широкий класс неравновероятных моделей.
-
Построен новый статистический критерий проверки гипотезы о равновероятности подстановок, и исследовано асимптотическое поведение его мощности при «близких» альтернативах.
-
Построены асимптотически несмещённые и асимптотически эффективные оценки для параметра модели в = {в„ ..., ва) и функций
от него, а также рассчитаны соответствующие асимптотические доверительные интервалы. 4. В предположении, что в наблюдаемой подстановке sgS„ для
каждого j = \,...,d доступно подсчёту лишь числа А -циклов с
длинами, не превосходящими заданного уровня, решены задачи точечного и доверительного оценивания по таким неполным данным
параметров в рассматриваемой модели и проверки
соответствующих статистических гипотез о них.
Методы исследования
В диссертационной работе используются методы теории вероятностей (в частности, метод моментов, метод производящих и характеристических функций), методы асимптотического анализа (в частности, метод перевала), асимптотические методы статистического оценивания неизвестных параметров и проверки статистических гипотез о них.
Теоретическая и практическая ценность
Результаты и методы диссертации вносят существенный вклад в современную теорию случайных подстановок и могут быть полезными как с теоретической, так и с практической точек зрения, специалистам в области защиты информации и криптографии.
Апробация работы
Результаты работы докладывались на следующих конференциях:
-
Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ, Москва, 17 февраля-2 марта, 2011;
-
XII Всероссийский симпозиум по прикладной и промышленной математике (осенняя открытая сессия), Сочи, 1-8 октября, 2011;
-
Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ, посвященная 50-летию МИЭМ, Москва, 17 февраля-2 марта, 2012;
-
VIII Международная Петрозаводская конференция "Вероятностные методы в дискретной математике", XIII Всероссийский симпозиум по прикладной и промышленной математике (летняя сессия), Петрозаводск, 2-9 июня, 2012;
-
XIII Всероссийский симпозиум по прикладной и промышленной математике (осенняя открытая сессия), Сочи, 1-8 октября, 2012;
-
Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ, Москва, 19 февраля-1 марта, 2013;
Публикации
По теме диссертации опубликовано четыре работы в журналах, входящих в утверждённый ВАК перечень ведущих рецензируемых научных изданий, в которых должны быть опубликованы результаты кандидатских диссертаций. Список публикаций приведён в конце настоящего реферата.
Структура и объем диссертации
Случайные подстановки, распределение их цикловой структуры
Обозначим Кп(а) число n-подстановок в цикловом классе Ylr-XMr=n. Тогда для случайной подстановки по классическому определению вероятности имеем следовательно, ключевую роль в этой проблематике играют числа К „(а). Для этих чисел известна формула Кэли Из формул (4.1) и (4.2) следует, что в противном случае. Если использовать индикатор: 1(A) = \, если A имеет место, и 0 в противном случае, то последнее соотношение удобно записывать в более компактном виде: Представление (4.3), хотя и дает ответ на вопрос о распределении цикловой структуры случайной подстановки, но из него трудно извлекать конкретную информацию об особенностях цикловой структуры. Для дальнейшего продвижения весьма эффективным является использование аппарата производящих функций. Введём производящую функцию цикловой структуры а = (а1 а2, ... , Рассмотрим теперь разложение экспоненты Uir J Это и есть итоговое и удобное для дальнейшего анализа представление для производящей функции цикловой структуры случайной равновероятной «-подстановки. Представление (4.6) можно записать и в несколько ином виде. Поскольку
Сформулируем полученный результат в виде следующего утверждения. Теорема 1. Для случайной п-подстановки производящая функция Fn{tx,...,tn) её цикловой структуры а = (ь 2, … , п) имеет вид (4.7). Соотношение (4.7) является базовым в теории случайных подстановок: из него можно извлечь всю информацию об особенностях и свойствах цикловой структуры «-подстановок, что и будет продемонстрировано в дальнейшем. Но предварительно мы напомним некоторые факты из комбинаторики и теории вероятностей, которые будут необходимы нам в качестве технического аппарата. 5. Некоторые вспомогательные результаты Биноминальные коэффициенты. Число Скт (используется также обозначение ), 0 к т, равное количеству / -подмножеств т \к ) множества, называется биномиальным коэ так как эти числа фигурируют в знаменитой формуле бинома Ньютона:
Для этих чисел можно использовать следующие представления: Эти формулы можно обобщить на случай, когда показатель степени т есть произвольное действительное число. Для этого разложим функцию (\ + х)а в окрестности точки JC=0 в ряд Тейлора Сравнивая коэффициенты в (5.3) с (5.2), можно записать, что Формула (5.4) и определяет биноминальные коэффициенты С для произвольного действительного а через, так называемую, убывающую факт =t(t-l)-(t-n + l), n \,(t)0=\. Используя эти формулы, также можем записать разложение возрастающая факториа В (5.5) представлены различные записи биномиальных коэффициентов, которые мы в дальнейшем будем использовать. Числа Стирлинга. Если разложить убывающую факториальную функцию по степеням аргумента ґ: то коэффициенты этого разложения s(n,k) есть, так называемые, числа Стирлинга первого Через эти числа записывается также и разложение возрастающей факториальной функции, определенной в (5.5):
Подстановки с рандомизированной степенью
Если степень подстановки является случайной величиной т/ с распределением типа степенного ряда:
где функция / (z) = exp{/z(z;6 )}, то элементы структуры с.(т7)будут независимыми пуассоновскими случайными величинами:
Здесь z 0 является свободным параметром рандомизации, значение которого можно подбирать специальным образом в зависимости от цели исследования. 2. Конкретизации d - параметрической модели
Пусть множество Хп состоит из двух подмножеств: А и
А = Хп \ А. Циклы подстановки s, длины которых являются элементами подмножества А (соответственно, подмножества А) будем называть А -циклами (соответственно, А -циклами). Обозначим СА{п) (Cj(n)) общее число ,4-циклов (А -циклов) подстановки s: и введём на множестве Sn вероятностную меру, приписывающую каждой подстановке seSn вес, пропорциональный в Ап)в {п) где = ,6 , 6Х 62 О -параметры меры. Эта мера представляет собой специальный случай общей меры (1.2) и имеет вид Здесь выражение в показателе экспоненты может быть заменено на Далее, для производящей функции пары [CA(n),Cj(n)) из представления (1.3) следует равенство: Получим распределения двумерной характеристики [СА(п),С2(п)) случайной подстановки в рассматриваемой (двухпараметрической) модели для различных вариантов заданий подмножества А с: Хп. Но прежде мы выделим некоторые, представляющие и самостоятельный интерес, следствия соотношений (2.3) и (2.4).
1. Положив tx=t2=t в (2.4), получаем производящую функцию важнейшей характеристики случайной подстановки - общего числа её циклов именно, нпА{е)
Если, кроме того, в1=в2=в 0, то приходим к известной однопараметрической модели Эвенса [23], когда каждая подстановка SGS„ наблюдается с вероятностью, пропорциональной вС(п). Для этого случая представление (2.3) принимает вид: (эта комбинаторная формула в дальнейшем будет неоднократно использоваться), и приходим к известному результату [4]: Этот случай (распределение числа циклов С(п) в модели Эвенса) детально исследован в литературе (см. [4]), в то же время представление (2.4) для двумерной случайной величины принимающее в данном случае вид является новым результатом и для модели Эвенса. 2. Если в модели (2.2) положить 92 =0,в1 = # 0, то получим меру, сосредоточенную на подмножестве подстановок, имеющих лишь А -циклы, такие подстановки называются А- подстановками [16] и их изучению в рамках классической (равновероятной) модели посвящена обширная литература (см. [21,22] и библиографию в них). Предложенная здесь модель позволяет, таким образом, изучать и неравновероятные -подстановки. Пусть Sn(A) обозначает подмножество -подстановок в Sn. Если на этом подмножестве задана параметрическая мера где теперь то производящая функция общего числа циклов СА(п) такой случайной -подстановки имеет вид нпА(е) (2.8) где НпА(6) дано в (2.7). Если здесь положить в = \, то получим равновероятную на Sn{A) модель: каждая подстановка sGSn(A) наблюдается с вероятностью Н \{\). Замечание 2. Случай в1=0,в2=в 0 соответствует симметричному варианту - А -подстановкам. 3. Отметим, что из представления (2.4) следует общая формула для смешанных факториальных моментов случайных величин СА(п) и САп): здесь и далее, напомним, Введя для краткости обозначение, отсюда, в частности, получаем следующие представления для первых двух моментов:
Эти общие представления могут быть основой для вычисления моментов рассматриваемых характеристик случайной подстановки при различных конкретизациях подмножества А.
Далее разберем ряд наиболее популярных в литературе классов А -подстановок в контексте изложенного подхода.
Асимптотическая нормальность чисел конгруэнтных циклов случайной подстановке (доказательство основного результата)
Как хорошо известно, в модели равновероятных подстановок, когда каждая подстановка из Sn наблюдается с вероятностью (и!)-1 (в нашей модели надо положить все в- = 1), общее число циклов С{п) случайной подстановки асимптотически нормально с параметрами (In п, 1пя)[1]. Обобщение этого результата на неравновероятный случай: подстановка с числом циклов С{п) наблюдается с вероятностью, пропорциональной вС(п, где в 0 - произвольный параметр, получено Эвенсом[23] (см.также Г.И.Ивченко, Ю.И.Медведев[4]). Именно, число циклов С(п) случайной подстановки в такой модели асимптотически нормально с параметрами (в In п, в In п). Модель Эвенса является частным случаем рассматриваемой в работе модели и получается из неё при 6x=... = 6d=6. А из приведённой теоремы следует, что в нашей модели число циклов CA{n) = YfA.{n) случайной подстановки асимптотически нормально с параметрами (в\пп, в\пп), 6 = — 2_Pj .
Таким образом, сформулированный в теореме результат обобщает свойство асимптотической нормальности числа циклов случайной подстановки (с логарифмическим порядком роста этого числа) на достаточно широкий класс неравновероятных моделей, давая одновременно информацию о более детальной структуризации циклов подстановки. В частности, теорема даёт ответ также и на вопрос о цикловой структуре подстановок с «запретами», т.е. когда какие-то Aj -циклы в подстановке «запрещены» (соответствующие параметры в надо положить равными нулю).
Полученный результат позволяет построить новый статистический критерий проверки гипотезы о равновероятности подстановок и вычислить его предельную мощность при «близких» альтернативах, что будет рассмотрено в Главе 3.
Выделим, в качестве следствия, случай d = 2. Здесь речь идёт о циклах чётной и нечётной длины, и из теоремы, в частности, следует, что в равновероятной модели (при в1 = в2 = 1) число тех и других в среднем асимптотически равно половине общего числа циклов In и -факт, в литературе ранее не отмечавшийся. Наконец, если акцентировать внимание лишь на одном каком-то классе конгруэнтности, скажем, Ad -циклах, то в рассматриваемой модели их число СА (п) асимптотически нормально d d ) и асимптотически не зависит от числа остальных циклов С j (и), также асимтотически нормального W —\п п, ln п 1 d d Замечание 4.(Схема серий.) Пусть параметры рассматриваемой модели имеют вид Л 9, = 1 Д, = const 0, / = l,...,d. (3.15) Представление (3.12) остаётся справедливым и в этом случае, и мы получаем, что в схеме серий (3.15) числа конгруэнтных циклов случайной подстановки асимптотически ведут себя как независимые пуассоновские случайные величины с параметрами соответственно AJd,j=\,...,d.
Статистические задачи для случайных подстановок с цензурированными данными
Ранее в исследовании предполагалась известной вся цикловая последовательность с(п) = (с1,с2,...,сп), т.е. имеется полная информация о наблюдаемой подстановке, и соответсвующие выводы имеют асимптотический (при п оо) характер. Но в этом случае не всегда является реалистичным предположение о том, что мы можем наблюдать всю цикловую последовательность с(«). Может быть и так, что наблюдению доступно лишь какое-то ограниченное число к её первых членов c1,c2,...,ck,- в этом случае говорят о цензурированных (неполных) данных. Статистические задачи для случайных подстановок с неполными данными в рамках однопараметрической модели Эвенса, когда подстановка seSn наблюдается с вероятностью, пропорциональной вс(п) (с(п) = с1+с2+... + сп -общее число циклов подстановки S), рассматривались в работе [9]. В настоящей работе аналогичный подход применяется к описанной выше d -параметрической модели с конгруэнтными циклами. Именно, мы будем предполагать, что в наблюдаемой подстановке seSn для каждого j = 1,...,d доступно подсчёту лишь число .-циклов с длинами, не превосходящими заданного уровня Кj. В таком случае, пусть есть наши исходные данные (количества наблюдаемых Aj -циклов).
Мы рассмотрим различные вопросы статистического вывода d-параметрической модели с конгруэнтными циклами именно по таким неполным данным (5.1). При этом мы будем предполагать, что порядок подстановки и—»оо, а параметры цензурирования К-, у = 1,..., /, фиксированы.
Основой для дальнейших выводов будет служить следующее утверждение об асимптотическом распределении наблюдаемых статистик с1,с2,..., т.е. начальных членов цикловой структуры подстановки.
Теорема 10. Для случайной подстановки s в общей параметрической модели с конгруэнтными циклами при п -со числа циклов ограниченной длины асимптотически независимы, и при этом число A j -циклов длины і имеет в пределе распределение Пуассона
Доказательство.
В теории случайных и-подстановок хорошо известен факт асимптотической (при п оо) независимости и асимптотической пуассоновости начальных членов цикловой последовательности c(n) = (cl,c2,...,c„) случайной равновероятной подстановки, при этом L{ci) — П - для любого конечного 7 . Аналогичное свойство имеет место и для модели Эвенса, причём в этом случае L(с.) - П Это свойство асимптотической независимости и пуассоновости чисел циклов конечной длины сохраняется и для общей параметрической модели, согласно которой произвольная подстановка SGS„ наблюдается с вероятностью, пропорциональной \\вСі, где в = (ви...,вп), в, 0, - параметр меры. В этом случае для і производящей функции цикловой структуры c(«) справедливо представление Отсюда следует, что производящая функция для произвольного конечного числа к начальных членов cl,c2,...,ck имеет вид Далее, используя стандартную технику метода перевала, нетрудно получить, что при и оои фиксированных 6 . к Г к п что означает асимптотическую независимость величин c1,...,ck и их пуассоновскую сходимость: Утверждение теоремы 8 является следствием этого результата, поскольку для всех А-- циклов параметры в, в рассматриваемой модели одинаковы. Следствие. Наблюдаемые статистики (5.1) асимптотически независимы, и при этом Из этих результатов следует, во-первых, что статистические выводы о каждом из параметров в- можно делать независимо по наблюдению лишь соответсвующей статистики у(и), и, во-вторых, исходная проблема в асимптотике сводится к соответствующим статистическим задачам для пуассоновской модели с неизвестным параметром, решение которых достаточно хорошо известно. Пусть имеется N независимых подстановок sl,...,sN, полученных при одном и том же значении неизвестного параметра Є = {Єх,...,Єа), и, тем самым, выборка (набор наблюдаемых статистик (5.1)) Как отмечено во п.5.1, компоненты этих векторов асимптотически (при п -со и фиксированных уровнях цензурирования К ) независимы и распределены в соответствии с (5.3), поэтому для суммарного числа наблюдаемых А- -циклов будет выполняться предельное соотношение Это соотношение сводит задачу оценивания параметров в нашей модели к задаче оценивания неизвестного параметра пуассоновской модели. Известно (см., напр., [10, 3.4]), что оптимальной (т.е. несмещённой с минимальной дисперсией) оценкой сходящегося при всех в 0 степенного ряда т{в) = аіві по наблюдению над случайной величиной X с пуассоновским распределением П( 9) является статистика т = аі(Х)і, где соотношение (5.6), мы можем сформулировать следующее общее утверждение для нашей модели.
