Предельные теоремы для некоторых случайных комбинаторных структур Черепанова Елена Владимировна

Содержание к диссертации

Введение

1 Обобщенная схема размещения 12

1.1 Определение и основные свойства обобщенной схемы размещения 12

1.2 Примеры комбинаторных задач, сводимых к обобщенной схеме размещения 14

1.3 Леса Гальтона — Ватсона 20

2 Предельные распределения числа циклов заданной длины в случайной подстановке с известным числом циклов 24

2.1 Формулировки результатов 24

2.2 Предельные распределения сумм вспомогательных случайных величин при N/\nn -> со 33

2.3 Предельные распределения сумм вспомогательных случайных величин при N/\nn = 0(1) 49

2.4 Доказательства теорем 2.1.5-2.1.16 54

3 Предельное поведение компонент малого объема в случайных подстановках и лесах 69

3.1 Постановка задач и формулировки результатов 69

3.2 Вспомогательные утверждения 75

3.3 Доказательства теорем 3.1.1-3.1.4 83

3.4 Доказательства теорем 3.1.5-3.1.8 90

3.5 Доказательства теорем 3.1.9, 3.1.10 93

4 Предельные распределения числа пар в обобщенной схеме размещения 99

4.1 Формулировки результатов 99

4.2 Предельные распределения (CN^N) 102

4.3 Доказательства теорем 4.1.1—4.1.3 113

5 Некоторые статистические приложения 115

5.1 Асимптотика статистики типа х2 в некоторых комбинаторных задачах 115

5.2 Доказательства теорем 5.1.1-5.1.5 118

5.3 Критерий пустых ящиков для случайных лесов 121

5.4 Доказательства теорем 5.3.1, 5.3.2 128

Литература 131

• Примеры комбинаторных задач, сводимых к обобщенной схеме размещения
• Предельные распределения сумм вспомогательных случайных величин при N/\nn -> со
• Вспомогательные утверждения
• Предельные распределения (CN^N)

Введение к работе

В настоящее время в комбинаторном анализе широко применяются хорошо развитые в теории вероятностей методы. Впервые вероятностный подход при изучении комбинаторных объектов был использован В.Л. Гончаровым в статьях [6,7]. Среди многочисленных работ, опубликованных с тех пор по этой тематике, отметим только несколько важнейших (на наш взгляд) книг [15,21,24,25,29,39-41,57,59, 64,67]. Возможность применения вероятностных методов при решении комбинаторных задач обеспечивается заданием распределения вероятностей на множестве изучаемых комбинаторных объектов, поскольку в этом случае их числовые характеристики можно рассматривать как случайные величины. При этом, задание равномерного распределения позволяет исключить из рассмотрения ту небольшую часть исследуемых объектов, которые обладают нетипичными свойствами. В современных работах по дискретной математике значительное внимание уделяется изучению случайных комбинаторных структур (см., например, [24]). Примерами таких структур являются случайные графы, случайные подстановки, урновые схемы.

К настоящему времени множество работ посвящено изучению случайных графов [21,22,24,29,40,43-45,57,61-64,68,70]. Графы являются удобным средством моделирования разнообразных объектов. Результаты, полученные для случайных деревьев, лесов, графов подстановок, находят применение в анализе вычислительных алгоритмов [64], статистических методах [8,26], мо- делировании транспортных и информационных систем [2,63,70], криптографии [38,65], теории случайных уравнений [23,24], исследовании эволюции случайных графов [3,22,24,45,56,57,67]. Изучение предельных свойств комбинаторных структур, проявляющихся при неограниченном росте числа элементов этих структур, является одним из важнейших направлений исследований. В последние три десятилетия при вероятностном подходе к решению комбинаторных задач широкое распространение получил метод, основанный на применении обобщенной схемы размещения, введенной и исследованной В. Ф. Колчиным [21,24,25]. В ряде задач этот подход позволяет выразить распределения характеристик рассматриваемых объектов через условные распределения сумм независимых случайных величин, что дает возможность использовать для их изучения асимптотические методы теории вероятностей, в том числе предельные теоремы для сумм независимых слагаемых. С помощью обобщенной схемы размещения решаются многие задачи, связанные с изучением равновероятных графов. Однако, как отмечено в [24], этот подход не удается применить в случае неравновероятных графов. Для таких графов известно немного работ, что объясняется, по-видимому, отсутствием достаточно хорошо развитых методов анализа этих структур. Разработка методов анализа неравновероятных графов является одной из важных задач, в том числе и в связи со статистическими приложениями таких графов.

Объектами исследования в диссертации являются случайные подстановки с известным числом циклов и рекурсивные леса, леса Гальтона — Ватсона, а также урновая схема с разноцветными шарами.

Результаты изучения случайных подстановок наиболее подробно изложены в [21,24]. В [24] получено полное описание предельного поведения числа циклов случайной подстановки степени п при n -> со. Поскольку характеристики случайных подстановок степени п с N циклами и случайных некорневых рекурсивных лесов с N деревьями и п вершинами можно изучать с помощью одной и той же обобщенной схемы размещения (см. [21,32]), предельные теоремы для максимальной длины цикла в таких подстановках при га,N -* со доказаны в [32].. В [12,14] изучалось предельное поведение р-го по величине цикла случайной подстановки с известным числом циклов, в [13,32] выявлены условия возникновения гигантской компоненты в таких подстановках. В статье [46] доказаны предельные теоремы для числа циклов длины г в случайной подстановке степени п с N циклами в некоторых зонах изменения параметров n,N,r.

Леса Гальтона — Ватсона образуются траекториями ветвящегося процесса Гальтона — Ватсона. Впервые этот термин встречается, по-видимому, в работе [69]. Среди многочисленных публикаций, посвященных исследованию этих объектов, отметим [4,17-19,43]. Систематически результаты о случайных лесах Гальтона — Ватсона изложены в монографиях [29,68]. В этих же работах получено полное описание предельного поведения максимального объема дерева, числа деревьев заданного объема и высоты леса при неограниченном росте числа деревьев и числа вершин леса. Некоторые другие характеристики лесов Гальтона — Ватсона изучались в [9,10,31,50,60,66]. Предельные распределения минимального объема дерева в лесе Гальтона — Ватсона до сих пор получены не были.

Рассмотрим следующую урновую схему с разноцветными шарами. Пусть из урны, содержащей по т ^ 2 различных шаров каждого N цветов, осуществляется равновероятный выбор без возвращения п шаров. В [1] изучалось предельное поведение числа пар извлеченных шаров одинакового цвета в этой урновой схеме при n,N"-+ со, и сформулирована локальная предельная те- орема для числа таких пар в случае, когда т фиксировано и О < «і ^ n/mN : аг < 1- Возможность применения обобщенной схемы размещения к указанной урновой схеме показана в [21]. Рассмотренная в [1] задача является частным случаем более общей проблемы изучения асимптотики числа пар в обобщенной схеме размещения частиц по ячейкам, где пара состоит из двух различных частиц, попавших в одну ячейку. Прежде в литературе такая задача не обсуждалась. Исключение составляет работа [20], в которой, в частности, получена асимптотика величины г} = »7»(^т/»~1)/2» где Tfc — число появлений г-го исхода в последо- вательности п независимых испытаний с равными вероятностями появления одного из N исходов, 1 ^ і ^ N. Поскольку такая полиномиальная схема соответствует равновероятной схеме размещения п частиц по N ячейкам [21], величина rj есть число пар в этой схеме размещения.

Целью диссертации является получение предельных теорем для важнейших характеристик случайных подстановок с известным числом циклов, лесов Гальтона — Ватсона и урновой схемы с разноцветными шарами. Хотя рассматриваются достаточно разные случайные комбинаторные структуры, проведенные исследования объединяет общий метод получения предельных теорем — обобщенная схема размещения. Этот метод требует доказательства предельных теорем для серий сумм независимых целочисленных случайных величин. Как отмечено в [24], известные в настоящее время достаточные условия локальной сходимости в схеме серий не дают полного ответа на вопрос, когда справедлива локальная предельная теорема. Поэтому в каждом конкретном случае приходится проводить отдельное доказательство таких теорем. В статье [28] приводятся достаточные общие условия справедливости локальных предельных теорем для решетчатых случайных величин, включая многомерный случай, однако их проверка часто оказывается весьма сложной задачей. В работах [11,16] получен ряд общих предельных теорем для обобщенной схемы размещения, которые могут применяться при решении комбинаторных задач с помощью этой схемы. В частности, некоторые результаты, изложенные в диссертации, являются следствиями этих теорем. Поскольку указанные работы появились позже, чем были получены результаты диссертации, в работе сохранены авторские доказательства. В большинстве рассмотренных в диссертации ситуаций, к сожалению, результаты работ [II, 16] неприменимы. В работе предельные теоремы доказываются стандартными методами и с использованием результатов статьи [28]. Кроме того, иногда требовалось получить локальные предельные теоремы для серий сумм двумерных векторов, а также с учетом скорости сходимости. Таким образом, доказательства таких теорем занимают значительное место в диссертации.

Диссертационная работа состоит из пяти глав. Первая глава носит вспомогательный характер. В ней приводятся определение и основные свойства обобщенной схемы размещения (раздел 1.1), примеры сведения комбинаторных задач к обобщенной схеме размещения (раздел 1.2) и описание класса лесов Гальтона — Ват-сона, рассматриваемых в диссертации (раздел 1.3). В примерах 2-5 раздела 1.1 содержится описание случайных комбинаторных структур, числовые характеристики которых изучаются в диссертации.

Во второй главе найдены предельные распределения случайной величины ц_г, равной числу циклов длины гв случайной подстановке степени п, имеющей N циклов, во всех зонах изменения параметров п,ЛГ,г. Все полученные предельные теоремы приводятся в разделе 2.1, а их доказательства — в разделах 2.2-2.4.

Третья глава посвящена изучению компонент малого объема рассматриваемых подстановок и лесов Гальтона — Ватсона. Распре- деление случайной величины ц? в случае, когда n/N -> 1, то есть когда каждый цикл подстановки в пределе состоит из одного элемента, сходится и к нормальному закону, и к распределению Пуассона. Естественно возникает вопрос о том, какое приближение для распределения /і_г лучше. В разделе 3.1 приводятся оценки скорости сходимости распределения fi_r к предельным законам и указано, какая асимптотика является лучшей. Также в этом разделе содержатся результаты о предельном поведении минимальной длины цикла случайной подстановки с известным числом циклов и минимального объема дерева в лесе Гальтона — Ватсона. Доказательства этих результатов приведены в разделах 3,2-3.5.

Как сказано выше, под парой в обобщенной схеме размещения будем понимать две различные частицы, попавшие в одну ячейку. Так, для подстановки, пару составляют два различных элемента подстановки, принадлежащих одному циклу, в корневом лесе с помеченными вершинами пара — две различные некорневые вершины, принадлежащие одному дереву. Нетрудно видеть, что каждой паре элементов подстановки соответствуют два различных пути в графе этой подстановки (путем в ориентированном графе называется маршрут, в котором все вершины различны [49]), а каждой паре вершин леса соответствует цепь (цепью в графе называется маршрут, в котором все ребра различны [49]). В четвертой главе получены предельные теоремы для числа пар шаров в описанной выше урновой схеме с разноцветными шарами, числа путей в графе случайной подстановки с известным числом циклов и числа цепей в корневом лесе с помеченными вершинами.

Пятая глава содержит некоторые статистические приложения. В разделе 5.1 получены асимптотики статистики типа х²* которые в некоторых случаях можно использовать для проверки гипотез о распределениях вероятностей, заданных на рассмотренных в диссертации множествах комбинаторных объектов. Эти результаты перечислены в разделе 5.1, доказаны в разделе 5.2. В разделах 5.3, 5.4 показана применимость критерия пустых ящиков для проверки статистической гипотезы о равномерности распределения вероятностей на множестве лесов Гальтона — Ватсона. Основными результатами диссертации являются:

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

Предельные распределения минимальной длины цикла случайной подстановки с известным числом циклов и минимального объема дерева в лесе Гальтона — Ватсона.

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

Получена асимптотика статистики типа х², предназначенной для проверки гипотез о распределении вероятностей в некоторых задачах, связанных с урновой схемой, случайными подстановками и случайными лесами.

Показана применимость критерия пустых ящиков для проверки статистической гипотезы о равномерности распределения вероятностей на множестве лесов Гальтона — Ватсона.

Основные результаты диссертации опубликованы автором в девяти работах [33-35,51-55,58], из них две статьи в журнале "Дискретная математика" [33,53], две статьи в сборнике трудов Института прикладных математических исследований КарНЦ РАН [54,55], пять тезисов докладов на международных, всероссийских и региональных конференциях [34, 35, 51, 52, 58]. Полученные результаты докладывались на Workshop "Networking games and resource allocation"(Петрозаводск, 2002), Kalashnikov Memorial Seminar (Петрозаводск, 2002), III и IV Всероссийских симпозиумах по прикладной и промышленной математике (Сочи, 2002, Петрозаводск, 2003), X Всероссийской школе-коллоквиуме по стохастическим методам (Сочи, 2003).

Результаты диссертации были получены в рамках темы плана научно-исследовательских работ Института прикладных математических исследований КарНЦ РАН "Вероятности на деревьях и лесах", №гос. регистрации 01.2.00 1 03997. В 2001-2002г. работа выполнялась при поддержке Российского Фонда Фундаментальных Исследований (грант 00-01-00233). В 2003г. исследования проводились по государственному контракту "Исследование случайных комбинаторных структур" по программе фундаментальных исследований РАН "Современные проблемы теоретической математики" (№100002-251/ОМН-01/018-026/090703-1029) и при поддержке гранта НШ 1758.2003.1 Президента Российской Федерации для государственной поддержки ведущих научных школ Российской Федерации (руководитель школы — академик Ю. В. Прохоров).

В диссертации разделы каждой главы имеют двойную нумерацию: сначала указывается номер главы, затем — порядковый номер раздела в этой главе; для теорем, лемм, замечаний и формул используется тройная нумерация: первым указывается номер раздела, затем — порядковый номер теоремы (соответственно леммы, замечания или формулы) в этом разделе.

Примеры комбинаторных задач, сводимых к обобщенной схеме размещения

Введем сначала понятие случайного элемента (см., например, [21]). Пусть {ГЇ,С/, Р} — вероятностное пространство, в котором пространство элементарных событий П конечно. Функцию p(us)t определенную на П, значениями которой являются элементы некоторого множества К, называют случайным элементом множества Y. Случайный элемент — это обобщение понятия случайной величины. Приведем несколько примеров сведения комбинаторных задач к обобщенной схеме размещения. Примеры 1-3 взяты из книг [21,24], пример 4 — из статьи [32], а пример 5 — из [21,29], Диссертация посвящена изучению предельного поведения различных числовых характеристик случайных комбинаторных объектов, рассмотренных в примерах 2-5. Пример 1. Рассмотрим полиномиальную схему. Предположим, что имеется последовательность, состоящая из п независимых испытаний, в каждом из которых с вероятностью N 1 происходит одно из N событий, занумерованных числами от 1 до N. Пусть щ означает число появлений г-го события в данной серии испытаний, 1 і N. Тогда для любых неотрицательных целых чисел kit »кх таких, что к\ +... + кн = п, Пусть п различных частиц независимо одна от другой размещаются по N ячейкам с номерами 1,...,ЛГ так, что каждая частица с вероятностью N 1 попадает в одну из ячеек. В этом случае совместное распределение случайных величин щ,... ,7/лг, равных числу частиц, попавших соответственно в 1-ую,..., N—ую ячейку, задается равенством (1.2.1). При этом, соотношение (1.1.1) выполняется, если i имеет распределение Пуассона с произвольным параметром А 0: Таким образом, задачу, в которой возникает полиномиальное распределение (1.2.1), можно описать с помощью равновероятной схемы размещения частиц по ячейкам. Эту схему размещения принято называть классической. Наиболее полное исследование классической схемы размещения приведено в книге [25]. Пример 2. Из урны, содержащей по т различных шаров каждого из N цветов, осуществляется равновероятный выбор без воз вращения п шаров (n mN). Пусть гц случайная величина, равная числу извлеченных шаров г-го цвета, 1 і N. Тогда для любых неотрицательных целых чисел fci,...,fc/\r таких, что Пусть it... , jy — независимые одинаково распределенные случайные величины, имеющие биномиальное распределение с параметрами (т,р): Р = Р{й = } = СІУ(1-РГ" , = 0,1,..., 0 р 1.. (1.2.2)-Несложно показать, что Следовательно, для случайных величин r}it...tr}N, ъ..,N выполняется равенство (1.1.1), и туї,... ,7/лг можно рассматривать как заполнения ячеек в обобщенной схеме размещения, где i,.,.,&v имеют распределение (1.2.2). Пример 3. Пусть s — взаимно однозначное отображение множества Хп — {1,2,...,п} в себя. Отображение з можно записать в виде таблицы где Sk — элемент, в который отображается к, 1 к п. Отображение 5, или таблицу (1.2.3), называют подстановкой степени п. Подстановку s можно представить ориентированным графом Т$, вершинами которого являются элементы множества Л п, а дуги (к, Sk) направлены из к в s 1 к п.

Поскольку отображение s взаимно однозначно, из каждой вершины графа Г$ выходит одна дуга, и в каждую вершину входит также одна дуга. Поэтому граф Т$ состоит из компонент связности, которые являются циклами, и называются циклами подстановки. Обозначим через SntN множество всех различных подстановок степени п, имеющих N циклов. Будем считать, что циклы каждой подстановки упорядочены одним из N1 способов. Известно (см., например, [46]), что число подстановок в Sn равно N\\$(nfN)\, где б(п,ЛГ) — числа Стирлинга первого рода. На множестве Snjj зададим равномерное распределение вероятностей, то есть каждой подстановке 5 Є 5пд припишем вероятность (Nl\s(ntN)]) 1. Пусть щ — случайная величина, равная длине г-го цикла случайно выбранной подстановки, 1 і N. Поскольку число различных циклов с к помеченными вершинами равно (к — 1)!, несложно показать, что для любых натуральных чисел кі,...,кн таких, что проводится по всем натуральным /i,.. ,,/JV, для которых l\ +... + JJV = п. Исследование совместного распределения случайных величин VU - iVN можно свести, как нетрудно проверить, к изучению условного распределения независимых одинаково распределенных случайных величин ft,..., fty, для которых при условии, что ft + .. + ftv = п. Легко видеть, что равенство (1.2.4) выполнено и в том случае, если циклы подстановок неупорядочены. Следовательно, результаты, полученные с помощью обобщенной схемы размещения (1.1.1), (1.2.5), справедливы и для таких подстановок. В следующих двух примерах рассматриваются графы, являющиеся лесами. Приведем необходимые определения. Связный граф без циклов называется деревом. Лес — это граф без циклов, то есть граф, каждая компонента связности которого является дере вом. Дерево с п занумерованными вершинами называется рекурсивным, если п = 1 или оно построено последовательным присоединением г-ой вершины к одной из і — 1 предыдущих вершин дерева, 1 г п. Рекурсивный лес — это лес с занумерованными вершинами, который строится так, что очередная, г-ая, вершина либо присоединяется к одной из предыдущих г — 1 вершин леса, либо становится первой вершиной дерева, еще не имеющего вершин. Корневое дерево — это дерево с выделенной вершиной, называемой корнем. Пример 4. Пусть Rnfl — множество рекурсивных лесов, состоящих из N занумерованных некорневых деревьев и имеющих п вершин, и пусть на Rnjr задано равномерное распределение вероятностей. Обозначим через щ случайную величину, равную числу вершин в г-ом дереве, 1 г N. Поскольку число рекурсивных некорневых деревьев с к вершинами равно (к — 1)!, нетрудно показать, что число лесов в Rnjr равно

Предельные распределения сумм вспомогательных случайных величин при N/\nn -> со

Пусть i ,... ,дг — независимые одинаково распределенные случайные величины, имеющие распределение (1.1.4), где распределения f!,...,w определяются равенствами (2.1.1), то есть В этом разделе будут получены предельные распределения случайных величин ffl при ntN,N/\nn -) оо и всех возможных значениях г, включая случай г — со. Через С, Сі, С2,... будем обозначать положительные постоянные. Напомним, что при N/\nn — оо параметр А распределения (2.1.1) является решением уравнения (2.1.2) в интервале (0,1). Тогда последовательность распределений сумм (jr) — жг) / rry/s слабо сходится к стандартному нормальному закону. Доказательство. Если выполнено условие (1) и, кроме того, n/N Сі оо, то решение уравнения (2.1.2) находится в интервале вида и для любого г справедлива оценка а если n/N - оо, то, как отмечено в [24J, уравнение (2.1.2) приближенно удовлетворяется при и из (2.2.1), (2.2.2) находим, что при всех г 1 При достаточно малых t имеет место равенство где 0 о и, как легко проверить, Из (2.2.1), (2.2.7), (2.2.9), (2.2.11) получаем, что при 0 С n/N Сі ооиг = 11...,п а при n/N — ос для г = 1,..., п Отсюда и из (2.2.5), (2.2.7), (2.2.9), (2.2.10) находим, что для любого фиксированного t откуда следует утверждение леммы при выполнении условия (1). Пусть n/N —» 1. Из уравнения (2.1.2) получаем, что где действительные функции аг(А, і), г = 1,2,..., удовлетворяют соотношениям Or(одинаково распределенные случайные величины, имеющие распределение (1.1.4), где распределения f!,...,w определяются равенствами (2.1.1), то есть В этом разделе будут получены предельные распределения случайных величин ffl при ntN,N/\nn -) оо и всех возможных значениях г, включая случай г — со. Через С, Сі, С2,... будем обозначать положительные постоянные. Напомним, что при N/\nn — оо параметр А распределения (2.1.1) является решением уравнения (2.1.2) в интервале (0,1). Тогда последовательность распределений сумм (jr) — жг) / rry/s слабо сходится к стандартному нормальному закону. Доказательство. Если выполнено условие (1) и, кроме того, n/N Сі оо, то решение уравнения (2.1.2) находится в интервале вида и для любого г справедлива оценка а если n/N - оо, то, как отмечено в [24J, уравнение (2.1.2) приближенно удовлетворяется при и из (2.2.1), (2.2.2) находим, что при всех г 1 При достаточно малых t имеет место равенство где 0 о и, как легко проверить, Из (2.2.1), (2.2.7), (2.2.9), (2.2.11) получаем, что при 0 С n/N Сі ооиг = 11...,п а при n/N — ос для г = 1,..., п Отсюда и из (2.2.5), (2.2.7), (2.2.9), (2.2.10) находим, что для любого фиксированного t откуда следует утверждение леммы при выполнении условия (1). Пусть n/N 1.

Из уравнения (2.1.2) получаем, что где действительные функции аг(А, і), г = 1,2,..., удовлетворяют соотношениям Or(\tt) = 0(Аі3), г 2, и а2(Л, ) = 0(А2 3). С помощью (2.1.4), (2.2.1), (2.2.2), (2.2.13), (2.2.14), (2.2.17)-(2.2.19) из (2.2.5) находим, что при выполнении условий (2), (3) леммы и Отсюда и из (2.2.14) следует, что при всех г 1, s = N (1 — рг + о{рг)) и любом фиксированном t справедливо соотношение что и завершает доказательство леммы. Лемма 2.2.2. Пусть выполнены условия леммы 2.2.1 и, кроме того, (п — N)3/N2 -+ оо при г = 2. Гогда равномерно по I, для которых z = (I — smr) loT\Js находится в любом фиксированном конечном интервале. Доказательство. По формуле обращения, Поскольку разность можно представить в виде суммы где положительные постоянные А, є будут выбраны позднее. Для доказательства леммы достаточно показать, что разность Rs можно сделать сколь угодно малой при больших п, N. В силу леммы 2.2.1, равномерно в любом конечном интервале справедливо соотношение (2.2.21), следовательно, Д -у 0 для каждого фиксированного А 0. Поскольку выбором достаточно большого А интеграл 1± можно сделать сколь угодно малым. Оценим І2. Если 1 с n/N = Сі со, то, как видно \tt) = 0(Аі3), г 2, и а2(Л, ) = 0(А2 3). С помощью (2.1.4), (2.2.1), (2.2.2), (2.2.13), (2.2.14), (2.2.17)-(2.2.19) из (2.2.5) находим, что при выполнении условий (2), (3) леммы и Отсюда и из (2.2.14) следует, что при всех г 1, s = N (1 — рг + о{рг)) и любом фиксированном t справедливо соотношение что и завершает доказательство леммы. Лемма 2.2.2. Пусть выполнены условия леммы 2.2.1 и, кроме того, (п — N)3/N2 -+ оо при г = 2. Гогда равномерно по I, для которых z = (I — smr) loT\Js находится в любом фиксированном конечном интервале. Доказательство. По формуле обращения, Поскольку разность можно представить в виде суммы где положительные постоянные А, є будут выбраны позднее. Для доказательства леммы достаточно показать, что разность Rs можно сделать сколь угодно малой при больших п, N. В силу леммы 2.2.1, равномерно в любом конечном интервале справедливо соотношение (2.2.21), следовательно, Д -у 0 для каждого фиксированного А 0. Поскольку выбором достаточно большого А интеграл 1± можно сделать сколь угодно малым. Оценим І2. Если 1 с n/N = Сі со, то, как видно из (2.2.10), (2.2.11), существуют такие є 0 и о» 0 о [ . что для Отсюда и из (2.2.5) получаем, что в области интегрирования 1ч справедливо неравенство для любого г. Тогда и интеграл /г можно сделать сколь угодно малым, выбрав А достаточно большим. Пусть n/N, N/lnn — оо. Представим /г в виде суммы трех интегралов І2 = /2+/2+-/2, гДе областями интегрирования -/2 » 2 ) 2 СООТВетСТВенНО ЯВЛЯЮТСЯ положительная постоянная 6 будет выбрана позднее, а область 5 пуста, если N/In (n/N) ear /s.

Вспомогательные утверждения

Для доказательства теорем 3.1.1, 3.1.2 нам потребуются оценки скорости приближения распределений сумм вспомогательных независимых случайных величин Слг = i + . 4- лг, С = { + ... + W к предельным распределениям при п}N —у со, n/N - 1, п — N -» оо, г 3. Напомним, что случайные величины i, , jv имеют распределение (2.1.1), а распределение }г%..., fW определяется равенствами (1.1.4), (2.1.1). Через Сі,.. Сз,... будем обозначать положительные постоянные. Лемма 3.2.1. Пусть г 3, n, JV — оо так, что п/ЛГ - 1, п—iV — оо, параметр А распределения (2.1.1) равен корню уравнения (2.1.2) в интервале (О,1), и пусть e fy/n — N —» 0., где х = (I — Nm)l T\fN, I — натуральное число, а ст, т определены в (2.1.3), (2.1.4). Тогда Доказательство. Используя (2.2.3) и формулу Тейлора, нетрудно показать, что при А —V 0 и фиксированных t для характеристической функции p(t) случайной величины & справедливо равенство Учитывая (2.1.4), (2.2.16), отсюда находим, что при \t\ є 1 Пусть ф(і) — характеристическая функция случайной величины {C,N - Nm) /ay/N: Из (3.2.1), (3.2.2), (2.1.3), (2.1.4) получаем, что при t/a\/N- Q Отсюда и из (2.2.13), (2.4.9) находим, что при i?/o jN —У О По формуле обращения, имеет место равенство и, поскольку Отсюда и из (3.2.5), (3.2.7), (3.2.9) находим, что R = О (l/ay/W) . Из этого соотношения и из (3.2.4), (2.4.9) получаем утверждение леммы. Лемма 3.2.2. Пусть г 3, п, N -+ со так, что njN - 1, n—N -+ со, параметр А распределения (2.1.1) равен корню уравнения (2.1.2) в интервале (0,1), и пусть e jy/n — N - 0, где z = (I — smT)l jryf8, тг,аг определены в (2.2.1), (2.2.2), / — натуральное число, a s —У оо так, что a\s —» оо. Тогда

Доказательство. Следуя доказательству леммы 2.2.2, разность Re = л/2 ( ггл/2 Р {с = /} - е- !2) представим в виде суммы Н8 = її + I L + I3 + /4, где /і, /г, /зі А определены в (2.2.22), A = {aryfs) , постоянная є 0 будет выбрана позднее. Если \t\ А, то i?jary/s 4 0 и из (2.2,20) находим, что для характеристической функции фР(і) случайной величины (ffl — smr) І ГУ/S справедливо равенство С помощью этого соотношения, аналогично (3.2.5), получаем, что h = О (1/ л/і) Поскольку Л - оо, аналогично (3.2.6), (3.2.7), находим, что h - о (1/агу/) . Если \t\l rTy/s , при достаточно малом є из (2.2.32) следует, что для характеристической функции pr(t) случайной величины }г выполняется неравенство Из полученных оценок для /і, І2, /з, h следует, что R8 = 0(l/ary/s) откуда получаем утверждение леммы. Для доказательства теоремы 3.1.6 нам потребуется предельное распределение случайной величины (, f{ + ... + $} \ где Ат = {1,2,...,г}, распределение независимых одинаково распределенных случайных величин ft , .. ,# задается соотношениями (1.1.3), (2.1.1). Обозначим Учитывая (1.1.3), нетрудно показать, что где (p(t) определено в (2.2.3). Докажем несколько вспомогательных утверждений для PAr{t). Лемма 3.2.3. Пусть п, N — оо так, что iV/Inn - 7, 0 7 параметр распределения (2.1.1) равен А = 1 — 1/п. Тогда для любых фиксированных t и г = 1,2,... Доказательство, Из (3.2.11) получаем, что Используя (2.2.3), формулу Тейлора и равенство А = 1 — 1/п, находим, что при фиксированных і и п - оо и, учитывая (2.1.1), при фиксированных г 1 получаем оценку Отсюда и из соотношения N/ In п — j следует, что Из этого равенства, а также (3.2.12) и (2,3.1) получаем утверждение леммы. Лемма 3.2.4. Если выполнены условия леммы 3.2Д то существуют положительные постоянные є и С такие, что при t/n и г = 1,2,... Доказательство. Легко видеть, что найдется такое є 0, при 1 Тогда, учитывая соотношения (2.1.1), А = 1 — 1/n, N/\un —У у, получаем, что Отсюда и из (3.2.12), (2.3.4) следует утверждение леммы. Используя соотношения (3.2.11), (2.1.1), (2,3.6), находим, что при п — оо, г — 1,2,..., О є \t\ л-, где — постоянная, выполнены неравенства то есть справедливо следующее утверждение. Лемма 3.2.5. сли п — оо, параметр распределения (2.1.1) равен А = 1 — 1/п, то существует постоянная С 0 такая, что для О є jij 7г при достаточно больших п и г = 1,2,...

Предельные распределения (CN^N)

Введем обозначения: Через C\, C2,... будем обозначать положительные постоянные. Поскольку Х\ = (& — &, ті — гг), нетрудно показать, что где Легко видеть, что теореме 4 [28], имеет место следующее утверждение. Лемма 4.2.1. Пусть при N - оо последовательность распределений случайных величин (SN — AN) QN слабо сходится к абсолютно непрерывному распределению. Тогда для локальной схо-димости распределений SN К тому же распределению достаточно, чтобы для любого d Є fi (1/2,1/4) Лемма 4.2.2. Пусть fi,..., JV имеют распределение (1.2.2) с параметром р = n/mN, т 2, 0 п mN, n, N -+ оо так, что выполняется одно из следующих условий: (1) n/N - 0, rc2/iV - оо; (2) 0 ci n/iV с2 оо, п (1 - n/mN)3 -f со; (3) п/ЛГ - оо, (1 - п/тЛГ) Л 4/3/п _ . 7Ьгда последовательность распределений (SN — AN) QN слабо сходится к двумерному нормальному закону с плотностью (4.2.5). Доказательство. Для справедливости утверждения леммы достаточно, чтобы в каждой точке ($1,) выполнялось равенство Р ( i, h) = exp -i ( J + + 2р 1«а)} (1 + o(l)), (4.2.6) где p{tut2) — характеристическая функция случайной величины (Sjv — AN) QN. С помощью равенства Обозначим /( 1,) характеристическую функцию случайного вектора (fi — Efi,ri — En). Используя формулу Тейлора, получаем, что при достаточно малых 1, где IrpbiaJKgEdtiMu-Efil + felln-ETil) . Поскольку (x + y)3 — 4 (x3 + у3) = —3(x + /)(x — у)2, при x, 2/ 0, справедливо неравенство (x-\-y)z 4(x3 + j/3). С помощью этого соотношения и легко проверяемого для 0 неравенства Е 1С - Ef 3 Е3 + Е3 находим, что Учитывая (4.2.7) и равенство р = n/mN, при т 2 получаем, что и, как нетрудно видеть, при выполнении условий леммы aJiV — оо, a\N - оо. Поэтому из соотношений и (4.2.8) находим, что при фиксированных i, 2 Из (4.2.9) следует, что / 1 2 , (JiVN VN где ) (ii3A+i23B), (4.2.12) A = О (1/Ny/n), B = 0 (l/ny/N) при n/W - 0; A, В = О ((niV2(l - n/(miV))3) 1/2) при 0 сг n/N c2 oo; А, В = О ((n/(l - nl{mN))N2f12) при n/AT -+ oo. Из этих соотношений и (4.2.12) следует, что при выполнении условий леммы С помощью этой оценки и формулы Тейлора при п, N - со из (4.2.11) находим, что в каждой точке ($1,) Отсюда получаем (4.2.6),

Лемма доказана. Лемма 4.2.3. Пусть &,..., у имеют распределение (1.2.2) с /га-раметром р = njmN, т 2, 0 п miV, n, Учитывая (4.2.7) и равенство р = n/mN, при т 2 получаем, что и, как нетрудно видеть, при выполнении условий леммы aJiV — оо, a\N - оо. Поэтому из соотношений и (4.2.8) находим, что при фиксированных i, 2 Из (4.2.9) следует, что / 1 2 , (JiVN VN где ) (ii3A+i23B), (4.2.12) A = О (1/Ny/n), B = 0 (l/ny/N) при n/W - 0; A, В = О ((niV2(l - n/(miV))3) 1/2) при 0 сг n/N c2 oo; А, В = О ((n/(l - nl{mN))N2f12) при n/AT -+ oo. Из этих соотношений и (4.2.12) следует, что при выполнении условий леммы С помощью этой оценки и формулы Тейлора при п, N - со из (4.2.11) находим, что в каждой точке ($1,) Отсюда получаем (4.2.6), Лемма доказана. Лемма 4.2.3. Пусть &,..., у имеют распределение (1.2.2) с /га-раметром р = njmN, т 2, 0 п miV, n, iV -+ со так, что n2/iV -+ со, n/N : с\ со, n/miV сз 1. 7Ъгда равномерно по z = (&,/), гдб к,1 — целые неотрицательные числа, а о\ч cr, р определены в (4.2.7). Доказательство. По свойствам биномиальных вероятностей [5], вероятность рк = Ср (1 — р)т к возрастает при 0 к ко = р(т +1)-1 и убывает при к0 к т, при этом, если ко Є Z, то максимального значения рк достигает при к = ко, ко + 1, а если ко ф Z, то 2 принимает максимальное значение при к — [ко +1]. На основании лемм 4.2.1 и 4.2.2, для доказательства леммы достаточно показать, что для любого d Є fi (1/2,1/4) справедливы соотношения (4.2.4). Из равенств (4.2.2), (4.2.3) находим, что и, как нетрудно видеть, для векторов вида d = (0, () (1/2,1/4) а для d Є 2 (1/2,1/4), di Ф О, Учитывая (4.2.1), (4.2.7) и соотношение р = n/mN, получаем равенство и из (4.2.13)-(4.2.15) находим, что для каждого d Є О (1/2,1/4) Из (4.2.16), (4.2.18) и лемм 4.2.1, 4.2.2 получаем утверждение леммы. Лемма 4.2.4. Пусть &,,.. , имеют распределение (1.2.7), где n, iV -» оо /гедк, что п2/ЛГ - оо, n/iV2 - 0. Тогда последовательность распределений iV -+ со так, что n2/iV -+ со, n/N : с\ со, n/miV сз 1. 7Ъгда равномерно по z = (&,/), гдб к,1 — целые неотрицательные числа, а о\ч cr, р определены в (4.2.7). Доказательство. По свойствам биномиальных вероятностей [5], вероятность рк = Ср (1 — р)т к возрастает при 0 к ко = р(т +1)-1 и убывает при к0 к т, при этом, если ко Є Z, то максимального значения рк достигает при к = ко, ко + 1, а если ко ф Z, то 2 принимает максимальное значение при к — [ко +1]. На основании лемм 4.2.1 и 4.2.2, для доказательства леммы достаточно показать, что для любого d Є fi (1/2,1/4) справедливы соотношения (4.2.4). Из равенств (4.2.2), (4.2.3) находим, что и, как нетрудно видеть, для векторов вида d = (0, () (1/2,1/4) а для d Є 2 (1/2,1/4), di Ф О, Учитывая (4.2.1), (4.2.7) и соотношение р = n/mN, получаем равенство и из (4.2.13)-(4.2.15) находим, что для каждого d Є О (1/2,1/4) Из (4.2.16), (4.2.18) и лемм 4.2.1, 4.2.2 получаем утверждение леммы. Лемма 4.2.4. Пусть &,,.. , имеют распределение (1.2.7), где n, iV -» оо /гедк, что п2/ЛГ - оо, n/iV2 - 0. Тогда последовательность распределений (SV - AN) QN слабо сходится к двумерному нормальному закону с плотностью (4.2.5). Доказательство. Учитывая равенство [29] где &(х) определено в (1.2.8), легко видеть, что W аг(1-Є( )) С помощью этого соотношения и (1.2.7) нетрудно показать, что