Многомерные параметрические модели случайных подстановок и их вероятностно-статистический анализ тема автореферата и диссертации по математике, 01.01.05 ВАК РФ

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

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

МНОГОМЕРНЫЕ ПАРАМЕТРИЧЕСКИЕ МОДЕЛИ СЛУЧАЙНЫХ ПОДСТАНОВОК И ИХ ВЕРОЯТНОСТНО-СТАТИСТИЧЕСКИЙ АНАЛИЗ

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

АВТОРЕФЕРАТ

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

005549634

5 п;сн 2014

Москва-2014

005549634

Работа выполнена в федеральном государственном автономном образовательном учреждении высшего профессионального образования «Национальный исследовательский университет «Высшая школа экономики»

Научный руководитель Ивченко Григорий Иванович

доктор физико-математических наук, профессор

Официальные оппоненты Чистяков Владимир Павлович,

доктор физико-математических наук, профессор, Математический институт им. В.А. Стеклова, ведущий научный сотрудник

Ронжин Александр Федорович,

доктор физико-математических наук, профессор, Вычислительный центра им. A.A. Дородницына, главный научный сотрудник

Защита состоится 35 июня 2014 года в 16-00 на заседании диссертационного совета Д 212.048.17, созданного на базе федерального государственного автономного учреждения высшего профессионального образования «Национальный исследовательский университет «Высшая школа экономики», по адресу: 109028, Москва, Б. Трехсвятительский пер., д.З, зал заседаний ученого совета (к.217).

С диссертацией можно ознакомиться в библиотеке Национального исследовательского университета «Высшая школа экономики» по адресу: 101000, Москва, ул. Мясницкая, д.20, и на сайте http://www.hse.ru/sci/diss/.

Автореферат разослан 22 AfQ/j 2014 Г.

Ученый секретарь диссертационного Шнурков

Ведущая организация Федеральное государственное бюджетное

учреждение науки «Институт проблем информатики» Российской академии наук

2G

совета, к.ф.-м.н., доцент

Петр Викторович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность темы

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

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

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

заданным свойством, то адекватной является равномерная мера: P(i) = —-,

V.? е 5„. Такая равновероятная модель, которую принято называть классической, в основном и была главным объектом интереса в этой области.

В тоже время, внутренняя логика развития теории и запросы современной практики выдвигают на передний план задачи исследования и иных моделей случайных подстановок, учитывающих различного рода отклонения от равновероятности. Так, в частности, важнейшая статистическая проблема проверки адекватности, скажем, той же равновероятной модели, требует рассмотрения различного рода альтернатив и исследования поведения различных характеристик подстановки при тех или иных отклонениях меры Р от равномерности. Общий подход для конструирования и исследования неравновероятных моделей случайных п-подстановок был предложен в работах Г.И.Ивченко и Ю.И.Медведева''2. Ими была введена следующая параметрическая модель: если с(п) = (сис2,...,сп) есть цикловая структура подстановки (подстановка 5 имеет с, циклов длины ¡', / = 1,...,«), то она

наблюдается с вероятностью, пропорциональной ГТ,^/' > где 6 = {в\у...,вп),в. > 0, - параметр меры Ре :

Здесь и далее /(■)- индикатор события А :1(А) = 1, если А имеет место и

0 в противном случае, и Нп(в)- необходимый нормирующий множитель, называемый статистической суммой модели:

Я„(0) = «![г"]ех р{|^,у} (2)

(здесь и далее [г"]/(г) = сое/г„/(г)).

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

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

Далее, для производящей функции цикловой структуры с(п) = (сх,сг,...,сп) случайной подстановки в модели (1)

/%о(')=ЕоП''', г = (/„/2,..,0.

1=1

имеет место представление

Р„в{1) = Нп{1*в)/Нп{0), (3)

г& 1хв = (11е1,12е2,...,1„ва).

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

Специфика рассматриваемых в диссертационной работе моделей случайных подстановок в сравнении с известными в литературе состоит в следующем. Рассматривается ^ -мерная (с! >2) параметрическая модель, определяемая некоторым разбиением множества Хп = {1,2,...,и}:

и зависящая от свободного параметра 0 = (9|,...,0^), в, >0, следующим образом. Будем называть -циклами подстановки 5 е 5„ те её циклы, длины которых являются элементами подмножества А), а общее число Л, -циклов

подстановки 5 обозначать Сл {п) = СА = = \,...,с1, где символом с,у

1 У

обозначено число А] -циклов длины / в подстановке ^ (если подмножества имеют вид

А1={к:к=Ш + у,/> 0} для некоторых целых с1> 2 и 1 < )<<!, то говорят о конгруэнтных циклах); тогда вероятность наблюдения произвольной «-подстановки пропорциональна М

величине 1'

У=1

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

Вероятностная мера РвА (.?), я для произвольного разбиения

А = {Ах,Аг,...,Аа) принимает вид:

д <* СА (") /

= я у (4)

где

Я^(0) = л![2"]ех р{йМ)}, (5)

= 0 = (в......0,)-

В рамках такой модели можно рассматривать более детально структуризацию цикловой последовательности с(п) = (с[,с2,...,сп) подстановки, именно, записывать её в виде с(п) = [с^,; е А},] = 1,).

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

Цель работы

Целью диссертации является исследование вероятностных и статистических свойств случайных подстановок в ¿/-параметрической модели. При этом внимание акцентируется на изучении модели с конгруэнтными циклами, в рамках которой решаются задачи оценивания неизвестных параметров модели и проверки соответствующих статистических гипотез об этих параметрах, в том числе и по неполным (цензурированным) данным.

Научная новизна

Основные результаты диссертации являются новыми и состоят в следующем.

1. Доказана асимптотическая (при л->со) нормальность вектора С (и) = (/?),..., С^ (о)) чисел конгруэнтных циклов случайной

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

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

3. Построены асимптотически несмещённые и асимптотически

эффективные оценки для параметра модели в = {в......0„) и функций

от него, а также рассчитаны соответствующие асимптотические доверительные интервалы.

4. В предположении, что в наблюдаемой подстановке 5 е для

каждого j = l.....^ доступно подсчёту лишь числа А1 -циклов с

длинами, не превосходящими заданного уровня, решены задачи точечного и доверительного оценивания по таким неполным данным

параметров в} рассматриваемой модели . и проверки соответствующих статистических гипотез о них.

Методы исследования

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

Теоретическая и практическая ценность

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

Апробация работы

Результаты работы докладывались на следующих конференциях:

1. Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ, Москва, 17 февраля-2 марта, 2011;

2. XII Всероссийский симпозиум по прикладной и промышленной математике (осенняя открытая сессия), Сочи, 1-8 октября, 2011;

3. Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ, посвященная 50-летию МИЭМ, Москва, 17 февраля-2 марта, 2012;

4. VIII Международная Петрозаводская конференция "Вероятностные методы в дискретной математике", XIII Всероссийский симпозиум по прикладной и промышленной математике (летняя сессия), Петрозаводск, 2-9 июня, 2012;

5. XIII Всероссийский симпозиум по прикладной и промышленной математике (осенняя открытая сессия), Сочи, 1-8 октября, 2012;

6. Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ, Москва, 19февраля-1 марта, 2013;

Публикации

По теме диссертации опубликовано четыре работы в журналах, входящих в утверждённый ВАК перечень ведущих рецензируемых научных изданий, в которых должны быть опубликованы результаты кандидатских диссертаций. Список публикаций приведён в конце настоящего реферата.

Структура и объем диссертации

Диссертация состоит из введения, трех глав, списка литературы, содержащего 23 наименования. Объём диссертации 94 стр.

Краткое содержание работы

Содержание введения

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

Содержание главы 1

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

В § 1-3 рассказывается о важнейшем объекте дискретной математики -подстановке и ее цикловой структуре.

В § 4 на множестве всех п-подстановок вводится равновероятная мера и рассматривается распределение цикловой структуры случайной подстановки.

3 Гончаров В.Л. Из области комбинаторики. Изв. АН СССР. Сер. матем. 1944. т.8. N91. С. 3-48.

В §§ 5-10 приводятся свойства и распределения основных характеристик цикловой структуры равновероятной подстановки.

Содержание главы 2

В § 1 рассматривается d -мерная (d> 2) параметрическая модель и устанавливаются основные соотношения для неё.

Вводится соответствующая производящая функция в модели (4)-(5).

и И (г;в) определено в (5).

Рассматривается такая характеристика случайной подстановки в модели (4)-(5) как вектор чисел её А -циклов (в дальнейшем будем его называть А -структурой подстановки):

Fne{t;A) = HnA(t*e)/нпА{в),

(6)

где теперь

c» = (c,>).....C,>)).

(8)

Его производящая функция имеет вид

Кв (') = Е* П'Л= H ПА (' х в)/НпА (в),

(9)

где

В §2 проведен анализ различных конкретизации ¿/-параметрической модели. Именно, рассмотрена двухпараметрическая модель, когда множество Х„ состоит из двух подмножеств: А и А=Х„\А. Циклы подстановки я, длины которых являются элементами подмножества А (соответственно, подмножества А) являются А -циклами (соответственно, А -циклами). Величины СА(п) (С^(п)) обозначают общее число Л-циклов (Л-циклов) подстановки 5:

С» = £с,, С7(п)=1_с,. (10)

|<Е А

На множестве вводится вероятностная мера, приписывающая каждой подстановке вес, пропорциональный , где

в = (ви92), вивг >0,- параметр меры. Эта мера представляет собой специальный случай общей меры (4) и имеет вид

где

(12)

Далее, для производящей функции пары (СА(п),С^(п)) имеет место равенство

= (п)

с использованием которого получены точные распределения характеристики [СА(п),Сд(п)) случайной подстановки в рассматриваемой

(двухпараметрической) модели для различных вариантов заданий подмножества АсХп.

Предложенная модель позволяет, в частности, изучать и неравновероятные А-подстановки, так как при 62=О|01=б>О, получаем меру, сосредоточенную на подмножестве подстановок, имеющих лишь А-циклы.

Рассматривается такая А -подстановка, что длины всех её циклов кратны числу d> 2, то есть А = \kd.k = 1,2,...}. Получены явные формулы как для совместной производящей функции пары [СА(п),С-(п)), где в данном случае С/|(п)-число циклов, кратных й, в случайной подстановке, а С-(п)-число остальных её циклов, так и для производящей функции общего числа циклов случайной /4-подстановки. В последнем случае (при в2 =0,0, = в >0) формула (12) принимает вид:

если п кратно с!, и НпА(в) = 0 в противном случае.

Для частного случая, когда й = 1, для общего числа циклов случайной подстановки получено разложение на сумму независимых бернуллиевских слагаемых.

В рамках данной модели также изучаются А -подстановки, где множество А образуют решения уравнения

где с{— натуральное число, а е— единичная подстановка, эти решения называются с!-инволюциями: А = {/: /1 с/},с/ > 2, /1 с1 означает, что ; делит с1.

Производящая функция числа циклов в такой случайной А -подстановке имеет вид

ЩШ. (15)

аяА0) £ 0 "

jZn/ddi ¿¡(п- _/£/).'

Для случая, когда длины циклов ограничены некоторым числом (подмножество А имеет вид Л (г ) = {/:/'< г}, г > 2) формула (12) принимает вид

НпА(г){в) = nl[z"\l-z)-e>expj(<9, -в2=

(16)

Л

Рассмотренные примеры демонстрируют как достаточную универсальность предложенной методики, так и присущие ей сложности: точные решения в обсуждаемой проблематике имеют форму громоздких комбинаторных выражений, из которых проблематично извлечь конкретную информацию (хотя бы, например, вычислить средние и дисперсии величин С» и С»),

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

Этот подход применяется в §3 при исследовании числа конгруэнтных циклов в подстановке, т.е. когда подмножества Aj имеют вид

Aj={k:k = ld + j,l> 0} для некоторых целых d > 2 и 1 < j < d, где устанавливается следующий ключевой результат.

Теорема 7. Если п—>оо, а параметры в1, ..., 0d фиксированы, то компоненты вектора (8) асимптотически независимы и асимптотически

нормальны с параметрами соответственно

-^\пп,—\пп\, / = 1, ..., с1, при Л с1 )

этом параметры нормальных распределений являются асимптотическими значениями соответствующих средних и дисперсий компонент А -структуры, и эта асимптотика равномерна по в = (01,...,вс/) в любой конечной области изменения параметра.

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

Содержание главы 3

В § 1 полученные в главе 2 результаты применяются для асимтотического оценивания параметров модели.

Вводятся нормированные статистики

и для них доказываются следующие утверждения.

Теорема 8. Если я—»оо, то статистика СА (статистика т¿(СА (п)))

является асимптотически несмещённой и асимптотически эффективной оценкой для параметра в ¡(для гладкой параметрической функции г; (в])), и параметры ва оцениваются независимо друг от друга.

Теорема 9. Асимптотический у - доверительный интервал для параметра в 1 имеет вид

ас

А/

1п 71

1 + У

где ху определяется уравнением Ф(гу) = ——, и Ф(г) - стандартная нормальная функция распределения.

Аналогичное утверждение имеет место и для параметрических функций

В §2 рассматривается многовыборочный случай, когда наблюдается N>2 независимых подстановок при одном и том же (но неизвестном)

значении параметра в = {В.,...вЛ, и С^{п) = ..С^\п)) есть

I 2 ¿У

реализация Л-структуры С(п) = (СА (п),...,СА (п)) для /-й подстановки,

1

Получена асимптотически несмещённая оценка для в] с асимптотической дисперсией, в N раз меньшей, чем у оценки СЛ (п) в одновыборочном случае:

где Т(М,и) = 1 £с<°(и) = (Г,(М,и),..., Г„ (ЛГ,"))•

Таким образом, при таком объединении информации точность оценивания возрастает. Также более узкими оказываются и соответствующие доверительные интервалы(точность локализации для неизвестных параметров возрастает): асимптотический ^-доверительный интервал для 6>;, основанный

на статистике Т] (Ы, п), имеет вид

В §3 построен критерий согласия типа хи-квадрат для гипотезы о рановероятности подстановок: Я,: б, =... = ва = 1, и вычислена его предельная

мощность при близких альтернативах. При заданной вероятности ошибки первого рода (уровня значимости) а критерий имеет.вид:

Я, отвергается <=> {Т/п) > Х^}, (17)

где х], а обозначает р-квантиль распределения %2(Л), а тестовая статистика есть

«"-¿Ц^-т)'

Рассчитывается асимптотическое значение мощности критерия (17) при «близких» альтернативах вида

Я,„:0у = 1 + -^,У = 1,...,Л, (18)

л/1пп

где Х] — произвольные фиксированные числа, одновременнно не равные нулю.

Мощность критерия (17) при альтернативах Ни вида (18) удовлетворяет следующему предельному соотношению:

(19)

л-ю>

где (х;Л2) - функция распределения нецентрального -распределения с

1 а

числом степеней свободы с1 и параметром нецентральности Я2 = — У^Д ,-.

в 1

В литературе уже рассматривалась задача проверки гипотезы о равновероятности подстановок с учётом возможных альтернатив. Так, в работе Ивченко Г.И. и Медведева Ю.И.4 в рамках модели Эванса, предложен соответствующий статистический критерий, основанный на общем числе циклов С(п) наблюдаемой подстановки (тестовая статистика), и определена его

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

предельная мощность при альтернативах вида в = \ + —== . Построенный нами

л/1п п

критерий "работает" против более широкого класса альтернатив (18) и к тому же использует "более богатую" статистику, т.е. он является более предпочтительным.

В §4 рассматривается задача проверки гипотезы однородности:

Н0-.9х=... = в„=в>й, (20)

где в - некоторый неизвестный параметр. На основе тестовой статистики

*>) = 7(") - ^гТ. = £с (П), (21)

С(л) у,| ^ 1 й ) ,,, >

предложен следующий асимптотический вариант критерия однородности: при заданном уровне значимости а

Н0 отвергается <=> {Га (п)> Х\-ам-\} ■ (22)

§5 посвящен статистическим задам для случайных подстановок с цензурированными данными. Ранее в исследовании предполагалась известной вся цикловая последовательность с(и) = (с1,с2,...,сп), т.е. имеется полная информация о наблюдаемой подстановке, и соответсвующие выводы имеют асимптотический (при п —» со ) характер. Но может быть и так, что наблюдению доступно лишь какое-то ограниченное число к её первых членов с],сг,-..,ск,- в этом случае говорят о цензурированных (неполных) данных. Статистические задачи для случайных подстановок с неполными данными в рамках однопараметрической модели Эванса, когда подстановка 5 £ 5„ наблюдается с

вероятностью, пропорциональной вс(п) (с(л) = с1+с2+... + сп - общее число циклов подстановки рассматривались в работе Ивченко Г.И. и Медведева

Ю.И5. В настоящей работе аналогичный подход применяется к описанной выше с!-параметрической модели с конгруэнтными циклами.

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

Теорема 10. Для случайной подстановки 5 в общей параметрической модели с конгруэнтными циклами при п -> то числа циклов ограниченной длины асимптотически независимы, и при этом число -циклов длины / имеет в

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

Заключение

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

Автор выражает глубокую благодарность своему научному руководителю, доктору физико-математических наук, профессору Ивченко

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

пределе распределение Пуассона П

Благодарность

Григорию Ивановичу за внимание и поддержку на протяжении всей работы на диссертацией.

Работы автора по теме диссертации

Работы, опубликованные автором в ведущих рецензируемых научных журналах и изданиях, рекомендованных ВАК:

1. Соболева М.В. Некоторые неравновероятные модели случайных подстановок // Дискретная математика. 2011. Т.23. №3. С. 23-31. 0,58 а.л. (в соавт. с Ивченко Г.И.); личный вклад автора 0.3 а.л.

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

3. Солдаткина М.В. Оценивание параметров в одной модели случайных подстановок // Труды Карельского научного центра РАН. No 5. Сер. Математическое моделирование и информационные технологии. 2012. № 3. С. 106-109.0.63 а.л.

4. Солдаткина М.В. Статистические задачи для случайных подстановок с цензурированными данными // Дискретная математика. 2012. Т.24. №4. С. 104-113. 0.6 а.л. (в соавт. с Ивченко Г.И.); личный вклад автора 0.3 а.л.

В других изданиях:

1. Соболева М.В. Неравновероятные А-подстановки. // Тезисы докладов. Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. 2011. Москва. С.7-8. 0.18 а.л.

2. Соболева М.В. Параметрическая модель случайных подстановок. // Обозрение прикладной и промышленной математики. Т. 18. №3. Научные доклады. XII Всероссийский симпозиум по прикладной и промышленной

3. Солдаткина М.В. Статистические критерии для случайных подстановок // Тезисы докладов. Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. 2012. Москва. С.8-10. 0.19 а. л.

4. Солдаткина М.В. Оценивание параметров в одной модели случайных подстановок // Обозрение прикладной и промышленной математики. Т. 19. №2. Научные доклады. VIII Международная Петрозаводская конференция «Вероятностные методы в дискретной математике». 2012. Петрозаводск. С. 222-223. 0.13 а.л.

5. Солдаткина М.В. Статистические задачи для случайных подстановок с цензурированными данными // Обозрение прикладной и промышленной математики. Т. 19. №4. Научные доклады. XIII Всероссийский симпозиум по прикладной и промышленной математике. 2012. С.567-568. 0.13 а.л. (в соавт. с Ивченко Г.И.) личный вклад автора 0.06 а.л.

6. Солдаткина М.В. Случайные подстановки: от B.J1. Гончарова до наших дней. // Тезисы докладов. Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. 2013. Москва. С.11-12. 0.23 а. л.

Лицензия ЛР № 020832 от 15 октября 1993 г.

Подписано в печать ч2 А> д г. Формат 60x84/16

Бумага офсетная. Печать офсетная.

Усл. Печ. Л 1 Тираж 120 экз. Заказ № 25

Типография издательства НИУ ВШЭ 125319, г. Москва, Кочновский пр-д, д. 3

Федеральное государственное автономное образовательное учреждение высшего профессионального образования Национальный исследовательский университет "Высшая школа

экономики"

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

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

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

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

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

математических наук

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

Москва - 2014

Оглавление

Введение...............................................................................................................4

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

§1. Введение................................................................................................10

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

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

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

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

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

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

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

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

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

Глава 2 Анализ с/ -параметрической модели случайных подстановок...41

§1. Модель и основные соотношения для неё.........................................41

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

1.2. Моменты..........................................................................................44

1.3. Вектор чисел А] -циклов...................................................................45

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

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

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

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

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

2.2. ¿/-инволюции..................................................................................54

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

2.4. А(г) -циклы......................................................................................58

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

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

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

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

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

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

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

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

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

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

5.2. Оценивание параметров.....................................................................80

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

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

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

Заключение.........................................................................................................91

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

Введение

Подстановки степени п, п> 2 (далее используется термин «п-подстановки»), то есть взаимно однозначные отображения конечного множества Хп = {1,2,...,п} в себя, представляют собой один из наиболее интересных и популярных в математической литературе объектов дискретной математики. Неослабевающий в течение многих лет интерес к ним со стороны многочисленных исследователей обусловлен как их разнообразными (можно даже сказать - неисчерпаемыми) и глубокими аналитическими свойствами, так и широким применением их в различных областях научной и практической деятельности. Литература, посвященная подстановкам, практически необозрима, и поток соответствующих публикаций не истощается (см., напр., [3]-[7], [11], [12])

В последнее время все большую актуальность приобретают проблемы защиты информации, для решения которых во многих случаях вполне адекватными оказываются модели случайных подстановок, когда на множестве 8п всех п1 п -подстановок вводится та или иная вероятностная мера Р, в соответствии с которой каждая подстановка ^ е наблюдается с вероятностью Р(б) . Так возникает интереснейший объект вероятностной комбинаторики — случайные подстановки. При этом для различных целей адекватными оказываются различные варианты задания меры Р.

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

мера: Р(^) = — е . Такая равновероятная модель, которую принято

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

В то же время, внутренняя логика развития теории и запросы современной практики выдвигают на передний план задачи исследования и иных моделей случайных подстановок, учитывающих различного рода отклонения от равновероятности. Так, в частности, важнейшая статистическая проблема проверки адекватности, скажем, той же равновероятной модели, требует рассмотрения различного рода альтернатив и изучения свойств тестовых характеристик подстановки при различных отклонениях меры Р от равномерности. Общий подход для конструирования и исследования неравновероятных моделей случайных «-подстановок был предложен в работах Г.И.Ивченко и Ю.И.Медведева ([5],[6]). Ими была введена следующая п-параметрическая модель: если с{п)-{с],с2,...,сп) есть цикловая структура подстановки 5 е (подстановка 5 имеет с1 циклов длины 1 = 1,...,п), то она наблюдается с вероятностью, пропорциональной Y\¡> гДе д = {вх,...,0п),вл>0{в, обозначает любой из 6? ,у = 1,...,п ) - параметр меры :

Здесь и далее /(•) - индикатор события А: 1(А) = 1, если А имеет место и 0 в противном случае, и Нп(6) - необходимый нормирующий множитель, называемый статистической суммой модели и имеющий вид

(В.1)

#„(<?) = и![*"]ехр|Иу}- (В.2)

Здесь и далее мы будем использовать следующее обозначение: если функция Дг) имеет представление в виде степенного ряда:

со и=0

с некоторым положительным радиусом сходимости, то для коэффициентов ап будем писать ап = [¿п]/(?)■

Далее, для производящей функции цикловой структуры с(п) = (с},с2,-,сп) случайной подстановки в модели (В.1)

^й<?(0 = ЕвШ', 1 =

г=1

имеет место представление

^(0 - Н„($*б)/Нп{в), (В.З)

где 1хв = {1хв1>^в1>..^пвп){сш. [6]) .

Как отмечается в [6], соотношение (В.З) «может быть основой для изучения различных структурных свойств подстановок в рамках общей модели». В [6] приводится ряд конкретных примеров применения такого общего подхода к изучению случайных подстановок, и при этом отмечается, что «более детальное исследование случайных подстановок в общей модели ждёт своего времени».

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

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

В настоящей работе мы рассматриваем ¿/-мерную (¿/>2) параметрическую модель, определяемую некоторым разбиением множества Хп ={1,2,...., я}

и зависящую от свободного параметра 9 = 0,>О, следующим

образом: будем называть ^ -циклами подстановки ^е^ те её циклы, длины которых являются элементами подмножества А -, а общее число

подстановке я; тогда вероятность наблюдения произвольной п -

и

(В.4)

.¿.-циклов п -подстановки 5 будем обозначать

С а (п)= С л (п>я) - = где с- - число А- -циклов длины I в

с А (")

подстановки пропорциональна величине Y]Oj 7 :

7=1

СаХ»)

^ 7=1

Такое сужение общей модели (В.1) делает её более конструктивной и поддающейся анализу, и, в то же время, оставляет модели достаточное

число степеней свободы, чтобы охватить большее число представляющих практический интерес вариантов постановок конкретных вероятностных и статистических задач для неравновероятных подстановок.

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

На защиту выносятся следующие результаты данной работы.

1. Доказана асимптотическая (при п—>оо) нормальность вектора С(п) = (С^(п),...,СА (п)) чисел конгруэнтных циклов случайной

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

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

3. Построены асимптотически несмещённые и асимптотически эффективные оценки для параметра модели 9 = {0Х, и

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

4. В предположении, что в наблюдаемой подстановке леЯ,, для каждого у = 1,...,£/ доступно подсчёту лишь числа ^.-циклов с

длинами, не превосходящими заданного уровня, решены задачи точечного и доверительного оценивания по таким неполным

данным параметров 0^ рассматриваемой модели и проверки соответствующих статистических гипотез о них.

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

результатов

§1. Введение

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

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

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

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

Пусть Х = и Г={у} — два произвольных множества. Отображением множества X в У называется любое правило (обозначим его символом 5), ставящее в соответствие каждому элементу хеХ

Б

некоторый элемент у&У. Это записывается так: X—или (более детально) >> = ¿■(л:), хеХ. Элемент у&У, в который отображается х, называется его образом, а исходный элемент х— прообразом у (при отображении я).

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

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

Любое отображение Хп ->Хп можно записать в виде следующей таблицы:

П 2 ! к !

5 к 1 8п ;

где в верхней строке перечисляются элементы множества Хп, а в нижней — соответствующие образы при отображении 5 : Бк =.?(&)еХп,к = \,2,...,п.

Наглядным представлением отображения 5 служит

ориентированный граф , множество вершин которого составляет Хп, а множество ребер (дуг) образовано п дугами (к,8к), направленными из к

Число дуг, входящих в вершину к в графе равно числу

прообразов элемента к при отображении 5 и называется кратностью вершины к.

Граф Г}^ отображения 5 естественным образом разбивается на связные компоненты, при этом каждая связная компонента содержит ровно один контур (цикл) и, возможно, подходы к нему. Если какой-то элемент к е Хп отображается в себя же: к = з(к) (в этом случае говорят, что

отображение £ оставляет элемент к на месте), то в графе в вершине к имеется петля. Таким образом, петля - это цикл длины 1. Вершины графа Г}^, лежащие на циклах, называются циклическими, их число для конкретного цикла называется длиной этого цикла.

Важнейшими характеристиками отображения л- являются: число связных компонент графа число циклических точек, число циклов

заданной длины, размер наибольшей компоненты (число вершин в ней) и т.д.

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

Класс всех однозначных отображений множества Хп в себя, обозначаемый Ъп> получается, если на отображение 5 не накладывается никаких дополнительных ограничений (помимо однозначности), то есть в нижней строке таблицы (2.1) на каждом месте может стоять любой элемент множества Хп. Очевидно, число таких отображений =п".

Для любого к е Хп имеется только один прообраз, если отображение в взаимно однозначное, и нижняя строка таблицы (2.1) содержит все элементы Хп, как-то переставленные. Число всех перестановок из п элементов равно «!; таким образом, число различных взаимно однозначных отображений множества Хп в себя равно п\. Такие отображения называются подстановками степени п или п-подстановками, множество всех таких подстановок обозначается Бп. Для

любой подстановки ее граф состоит только из циклов,

кратности всех вершин равны 1 и все вершины являются циклическими.

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

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

успешно применяется при исследовании структуры различных комбинаторных объектов, в том числе и различных типов отображений.

Приведем общую схему сведения перечислительных комбинаторных задач к соответствующим вероятностным задачам (см. [1]). Пусть - некоторый класс отображений множества Хп в себя, и Н есть некоторое свойство, которым каждое отображение sGFn может обладать или нет. Подмножество отображений, обладающих свойством Н, обозначим Еп (Н). Суть вероятностного подхода для определения объема \Рп(Н)\ состоит в следующем. На множестве Еп задается равномерная вероятностная мера, приписывающая каждому отображению вероятность его наблюдения

Р(*)= 1

Я

п

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

\рп\

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

(2.3)

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

вероятностной задаче вычисления вероятности случайного события

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

В этих случаях необходим асимптотический анализ, и предельные теоремы теории вероятностей как раз