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

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

Оглавление диссертации кандидат наук Солдаткина, Мария Васильевна

Оглавление

Введение

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

§1. Введение

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

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

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

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

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

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

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

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

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

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

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

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

1.2. Моменты

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

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

Введение диссертации (часть автореферата) на тему «Многомерные параметрические модели случайных подстановок и их вероятностно-статистический анализ»

Введение

Подстановки степени п, п> 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)

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

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

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

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

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

Как уже говорилось выше, «-подстановка - это взаимно однозначное отображение множества Х„ = {1,2,....,«} в себя, класс (множество) всех таких отображений обозначается = {б}, их число есть = «!. Стандартная запись подстановки б имеет вид:

2 к \ пЛ

5 = 1

\ 8к 1 )

(3.1)

где нижняя строка (яь б2, ... , представляет собой некоторую перестановку чисел (1,2,....,«). Отметим некоторые важные свойства подстановок (см., напр., [14]—[15]).

Для подстановок естественным образом определяется их произведение: если я и g произвольные «-подстановки то произведение sg есть «-подстановка, которая действует по правилу = g(s(k)), к <= Х„ .

Таким образом, произведение sg - это последовательное применение этих отображений (сначала применяется б, затем £). Эта операция

ассоциативна: = = ?(£))), но, вообще говоря, не

коммутативна.

Далее, в множестве имеется единичная подстановка е,

оставляющая все элементы Х„ на месте: е(к)=к для всех к е Xп; для нее таблица (3.1) принимает вид:

Л 2......п"

2......п)

Наконец, каждой подстановке я е Бп соответствует единственная подстановка я"1 е такая, что я"1 ^ = ад"1 = е.

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

Рассмотрим граф произвольной подстановки ,уе5и. Как уже

отмечалось раньше, этот граф состоит только из циклов вида / —>у —> к —> ... —> г —> /, которые записываются в виде строки (г, у, ... , г), называемой циклом подстановки л; длина этого цикла равна числу входящих в него элементов (числу соответствующих вершин в цикле графа ); при этом цикл длины 1 имеет вид (/) и соответствует петле в в вершине /.

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

5 = 0*1 Х'2 Хч и , кх ХЛ > к2 )-Ь'а2 >ка2)-

(3.2)

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

Говорят, что подстановка яе^« принадлежит цикловому классу \[а>2а2...па"}, если она содержит а, циклов длины у, 1< ] < и. Набор а = (а\, «2, ••• , ««) называется цикловой структурой подстановки По своему определению компоненты вектора а суть целые неотрицательные числа, удовлетворяющие соотношению:

1а\ + 2аг + ... + пап = п. (3.3)

Подсчет числа подстановок в5„с теми или иными характеристиками цикловой структуры и составляет круг комбинаторных (перечислительных) задач в теории подстановок. При решении таких задач используется вероятностный подход, в соответствии с которым считается, что каждая подстановка ^ е Бп может наблюдаться с одной и той же

вероятностью Р(^)=—. В этом случае говорят о равновероятных (или

п!

случайных) «-подстановках.

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

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

Обозначим Кп(а) число «-подстановок в цикловом классе {1а'2а\..па"), а = (а\, аг, ... , а„), гаг = п. Для случайной подстановки по классическому определению вероятности имеем

= (4.1)

п!

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

(4.2)

"г"

г=1

П аг1г°-

Из формул (4.1) и (4.2) следует, что

п

П |

-\ ТТ-, если > га=п,

О в противном случае.

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

Р(а = а)=1\Угаг =п П—-—•

(4.3)

Представление (4.3), хотя и дает ответ на вопрос о распределении цикловой структуры случайной подстановки, но из него трудно извлекать

конкретную информацию об особенностях цикловой структуры. Для дальнейшего продвижения весьма эффективным является использование аппарата производящих функций (см. [11], [16]).

Введём производящую функцию цикловой структуры а = (аъ «2, •• , ««)

рп (*, ,..,*„)=ЕП/Л =Ер(«=«Й'Л •

г=1 а г=1

Тогда, с учетом (4.3), она имеет вид:

*•„('......'.)= Е П(

а:^гаг=п

г=1

Л"

Г

*г/

(4.4)

Рассмотрим теперь разложение экспоненты

2Г } " 1 ехРт ^ [

(гг

\аг

Тогда

ехр<

00 г ^=1г

00 П Г + \ат 1

=ГМ^=2>" I П V

Г=1

я=0 - ^ г=1 V Г а:2_гат=п /•=1

«г'

(4.5)

Сравнивая (4.4) и (4.5), можем записать, что

_ tr (4.6)

r=1 Г

Это и есть итоговое и удобное для дальнейшего изложения представление для производящей функции цикловой структуры случайной равновероятной «-подстановки.

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

как

00 гтГ оо „Г

z i z

г=1 г г=1 Г

то, вместо (4.6) для можно записать представление

1 — z

" zr

(4-7)

lr=l Г

Сформулируем этот результат в виде следующего утверждения ([11], с. 57).

Теорема 1. Для случайной п-подстановки производящая функция Fn{tx,...,tn) её цикловой структуры а - (a¡, а.2, ... , ап) имеет вид (4.7).

Соотношение (4.7) является базовым в теории случайных подстановок: из него можно извлечь всю информацию об особенностях и свойствах цикловой структуры «-подстановок, что и будет продемонстрировано в дальнейшем. Но предварительно мы напомним некоторые факты из комбинаторики и теории вероятностей, которые будут необходимы нам в качестве технического аппарата (см. [15],[20]).

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

5.1. Биноминальные коэффициенты.

( т\

Число С^ (используется также обозначение

), 0<к<т, равное

количеству ^-подмножеств /«-множества, называется биномиальным коэффициентом, так как эти числа фигурируют в знаменитой формуле бинома Ньютона:

т

Л к

(1+*)"=!№*. (5.1)

¿=0

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

к= т! = т{т-\)---(т-к + \) = {т)к т к!(т-к)! к! к! ' Р ^

Эти формулы можно обобщить на случай, когда показатель степени

т есть произвольное действительное число. Для этого разложим функцию

(1 + х)" в окрестности точки в ряд Тейлора

(1 ч-.у -1 + у °(а-')-(«-* + У .У (5 3)

й к! ¿¡к! ( '

Сравнивая коэффициенты в (5.3) с (5.2), можно записать, что

= ^ОДД... (5'4) к!

Формула (5.4) и определяет биноминальные коэффициенты Ска для произвольного действительного а через, так называемую, убывающую факториальную функцию (¿)и = ф -1) • • • (^ - п +1), п > 1, (¿)0 = 1.

Используя эти формулы, также можем записать разложение

*=о к.

Ь к, 2 ~ 2Л/+*-12 - ь г, 2 >

к=О К! к=0 ¿=0 К!

где Щк = *(г + 1)-••(* + &-!), к> 1, И0=1, есть, так называемая, возрастающая факториальная функция.

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

5.2. Числа Стирлинга.

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

(0„=2>М>*, *М)=(-1Г* ЕА-1п-к> (5.6)

Ы1 1<(, <:<1„_к <П~ 1

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

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

И, =(-1)4-4 =±{-1)п+к *{п,кУ. (5.7)

к=1

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

= + |0|<1, (5.8)

"А: 2п ъп

где С—0,5772.. - постоянная Эйлера, а также формула

(5.9)

5.4. Производящие функции.

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

р(л = к) = ак, к=0,1,2...., то её пр. ф. определяется равенством

00

к

Эта функция определена по крайней мере для | х |< 1, а внутри единичного круга она аналитична; при этом распределение с. в. ц и пр. ф. (рл{х) однозначно определяют друг друга, причем

ак=—]-, А: = 0,1,2...

к!

Напомним также следующие важные свойства производящих функций:

1) если у с. в. а/ существует конечный момент г-го порядка, то её факториальные моменты Е^),. =Е/7(77-1)...(77-5 + 1) ? при 8<г, существуют и могут быть вычислены по формулам

EfoW^O);

2) если r)x,...,r\n — независимые целочисленные случайные величины, то для производящей функции их суммы т]х+... + г]п справедливо соотношение

<Pr,(x) = <P% М-^М;

3) сходимость последовательности распределений \?(il(n) = k) = ak{n),k = <),l>'2'.,.) при оо к распределению Р(/7 = к} = ак ,к = 0,(то есть ак(п)-^>ак для любого фиксированного к), что принято записывать в виде l(rj(n)) —» l(tj) , эквивалентна сходимости

Пример. Пусть с. в. г] имеет распределение Пуассона с параметром Л > 0: £,(?]) = П(Я), то есть

7l

Р(,7 = *) = е-А—,* = 0Д,2,..,

к=о к'.

В данном случае все моменты существуют и

Е(т/), = А',* = 1,2,...

Известно, что распределение Пуассона однозначно определяется своими моментами, и сходимость к распределению Пуассона может быть сформулирована как сходимость соответствующих моментов: если Е(jj(n))sÄs, п->оо, при некотором Л> О для любого фиксированного Ä > 0, то L{rj(n)) -> £(77) = П(Я).

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

целочисленными компонентами: <р-(х1,..,х1с)=1Ех^.....хкк; при этом T]v...,rjk

независимы тогда и только тогда, когда

<p-(xl,..,xk) = (pTJ](xl)....(prik(xk).

5.5. Центральная предельная теорема (ЦПТ).

В дальнейшем мы часто будем ссылаться на эту ключевую теорему теории вероятностей, поэтому мы напомним как ее общую формулировку в форме A.M. Ляпунова, так и некоторые ее важные частные случаи (см., например, [17],[20]).

Теорема Ляпунова. Пусть дана последовательность серий {¿)кп,к = \,...,п},п = \,2,..., взаимно независимых случайных величин, имеющих

математические ожидания дисперсии сг^ =D£kn и

абсолютные моменты Скп = - ¡иы |2+3, 5 > 0. Обозначим

2 _ Vй ГГ1 г2л Б — Vй г

ип - ¿¿k+l^kn'

Тогда, если выполнено условие Линдеберга

С

lim-*- = (), (5.10)

п—>00 (J v

п

то при «->оо нормированная случайная величина —У]"1г_Х4кп~Мкп)

(7

п

асимптотически нормальна с параметрами (0,1) , т.е.

НшР

П—>00

Г

1 *

42л

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

\ап к=1 у

(5.12)

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

Следствие 1. Если с. в. взаимно независимы и

принимают лишь значения 0 и 1, при этом

ап = РкЧк

тдерк=рк(п) = Щкп=\),дк=дк{п) = Щкп=Ъ), рк+дк =1,то при со

( 1 п

\

уап к=1

Следствие 2. Если взаимно независимые с. в. £>\п>%2п>-~>%пп равномерно ограничены: <С,\<к<п,С >0, некоторая постоянная, и

5п = Ел=1 00' когда и->оо, то

' ! п ^

V" X (^ь - Мы)

->^(0,1).

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

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

п

общее число циклов а(п) = ^аг.

г=1

Чтобы найти производящую функцию <ра(п^) = Е^п\ надо в общей производящей функции (4.7) положить tx=t2=... = tn=t•.

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

(6-2)

п!

В (6.2) содержится вся информация о распределении случайной величины а(п). Например, чтобы получить выражения для вероятностей Р(а(п) = к), достаточно разложить правую часть в (6.2) по степеням Такое разложение дано в (5.7), откуда получаем, что

¡{п,к)\

п!

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

t +1 t + 2 (t + n-1) \

(Pa(n) (0= t■Г"" • ■■ ■*--1 = + M (6-4)

n i=l

где Pi = \ — qi — , z' = l,...,/i-l. 1 +1

Заметим теперь, что /-й сомножитель в правой части (6.4) есть производящая функция бернуллиевской случайной величины <5, для которой

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

= 2+■■•+ 5>=1- (6.5)

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

Е^ = Pi, Dg, = piqi, формулы для среднего и дисперсии:

и-1 п-1 1 п 1

/=о

/=о

/=0 г+1 /Ы ^ и-1 j и-1 | и j л j

и-1

(6.6)

Рассмотрим теперь вопрос об асимптотическом поведении а(п) при со. Воспользовавшись формулами (5.8) и (5.9), из (6.6) получаем

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

ж2

Еа{п) = \пп + С+0 - , Ъа{п) = \пп--+о(1) (6.7)

\п) 6

Более того, из представления (6.5), на основании ЦПТ (см. Следствие 1 в п.5.5 §5), можно сделать вывод о том, что при я->со

£

л/1п п

(а(л)-1пи) ->5УГ(0Д). (6.8)

Суммируя изложенное, можно сформулировать следующее утверждение (см., напр., [17], с. 298-299).

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

£(а(п)) ~ ЯГ(1п п, 1п п).

Этот результат позволяет приближённо оценивать число подстановок 5 е , для которых число циклов

а{п) е [1п п + ад/ 1п п, п п\ а < Р : это число приближённо равно

и/(Ф(/?)-Ф(а)).

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

Рассмотрим теперь вопрос о том, сколько может быть в случайной п-подстановке циклов произвольной фиксированной длины г (г-1,2,...). Производящая функция случайной величины аг для любого / получается из общей производящей функции (4.7) при tr—\,rФI,= /:

Список литературы диссертационного исследования кандидат наук Солдаткина, Мария Васильевна, 2014 год

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

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

2. Ивченко, Г.И. Метод В.Л. Гончарова и его развитие в анализе различных моделей случайных подстановок / Г.И. Ивченко, Ю.И. Медведев // Теория вероятностей и ее применения. - 2002. -т. 47, №3. — С. 558-566.

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

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

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

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

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

8. Ивченко, Г.И. Введение в математическую статистику / Г.И. Ивченко, Ю.И. Медведев. - Москва: ЛКИ/ШЮБ, 2010. - 600 с.

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

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

11. Колчин, В.Ф. Случайные отображения / В.Ф. Колчин. - М.: Наука, 1984.-209 с.

12. Колчин, В.Ф. Случайные графы / В.Ф. Колчин. - М.: Физматлит, 2000.-256 с.

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

14. Риордан, Дж. Введение в комбинаторный анализ / Дж. Риордан- М.: Издательство иностранной литературы, 1963. — 288 с.

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

16. Сачков, В.Н. Вероятностные методы в комбинаторном анализе / В.Н. Сачков. -М.: Наука, 1978. - 287 с.

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

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

19. Солдаткина, М.В. Оценивание параметров в одной модели случайных подстановок / М.В. Солдаткина // Труды КарНЦ РАН. No 5. Сер. Математическое моделирование и информационные технологии. — 2012.-Вып. З.-с. 106-109.

20. Феллер, В. Введение в теорию вероятностей и ее приложения: в 2 т. / В. Феллер. - М: Мир, 1984 -2 т.

21. Якымив, A.JI. Вероятностные приложения тауберовых теорем / A.JI. Якымив. - М.: Физматлит, 2005. - 256 с.

случайной А-подстановки / A.JL Якымив // Дискретная математика - 2010. -т. 22, №1.-С. 126-149.

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