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

В настоящее время в комбинаторном анализе широко применяются хорошо развитые в теории вероятностей методы. Впервые вероятностный подход при изучении комбинаторных объектов был использован B.JI. Гончаровым в статьях [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, N оо доказаны в [32]. В [12,14] изучалось предельное поведение р-го по величине цикла случайной подстановки с известным числом циклов, в [13,32] выявлены условия возникновения гигантской компоненты в таких подстановках. В статье [46] доказаны предельные теоремы для числа циклов длины г в случайной подстановке степени п с N циклами в некоторых зонах изменения параметров n, iV, г.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1. Агиевич С. В. Об одной комбинаторной задаче о размещениях. // Компьютерный анализ данных и моделирование. Сб. научных статей V международной конференции, ч. З, Минск, 1998, с.28−31.

2. Борисов Г. А. Методы автоматизированного проектирования лесотранспорта. Петрозаводск, КФ АН СССР, 1978.

3. Бритиков В. Е. О структуре случайного графа вблизи критической точки. // Дискретная математика, 1989,1, № 3, с.121−126.

4. Ватутин В. А. Распределение расстояния до корня минимального поддерева, содержащего все вершины данной высоты. // Теория вероятностей и ее применения, 1993, 38, № 2, с.273−287.

5. Гнеденко Б. В. Курс теории вероятностей. М., УРРС, 2001.

6. Гончаров В. Л. О распределении циклов в перестановках. Докл. АН СССР. 1942, 35, вып.9, с.299−301.

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

8. Иванов В. А., Ивченко Г. И., Медведев Ю. И. Дискретные задачи в теории вероятостей. // Итоги науки и техники. Сер. теория вероятн., матем. стат., теор. кибернетика, 1984, 22, с. З-60.

9. Казимиров Н. И. О предельных распределениях для числа потомков процесса Гальтона — Ватсона. // Тр. Института прикл. матем. исслед. Карельского НЦ РАН, 1999, 1, с.7−20.

10. Казимиров Н. И., Павлов Ю. Л. Одно замечание о лесах Гальтона — Ватсона. // Дискретная математика, 2000, 12, № 1, с.47−59.

11. Казимиров Н. И. О некоторых условиях отсутствия гигантской компоненты в обобщенной схеме размещения. // Дискретная математика, 2002, 14, № 2, с.107−118.

12. Казимиров Н. И. Предельные распределения больших компонент в случайной подстановке с известным числом циклов. // Обозрение прикладной и промышленной математики, 2003, 4, в.1, с.166−167.

13. Казимиров Н. И. Возникновение гигантской компоненты в случайной подстановке с известным числом циклов. // Дискретная математика, 2003, 15, № 3, с.107−118.

14. Казимиров Н. И. Предельные распределения наибольших длин циклов случайной подстановки. // Тр. Института прикл. матем. исслед. Карельского НЦ РАН, 2003, 4, с.77−82.

15. Коваленко И. Н., Левитская А. А., Савчук М. Н. Избранные задачи вероятностной комбинаторики. Киев, Наукова Думка, 1986.

16. Колчин А. В. Предельные теоремы для обобщенной схемы размещения. // Дискретная математика, 2003,, №, с.148−157.

17. Колчин В. Ф. Ветвящиеся процессы, случайные деревья и обобщенная схема размещения. // Математические заметки, 1977, 21, № 5, с.691−705.

18. Колчин В. Ф. Момент вырождения ветвящегося процесса и высота случайного дерева. // Математические заметки, 1978, 24, № 6, с.859−870.

19. Колчин В. Ф. Ветвящиеся процессы и случайные деревья. // Вопр. кибернетики. Комбинаторный анализ и теория графов. М., Наука, 1980, с.85−97.

20. Колчин В. Ф. О распределении одной статистики в полиномиальной схеме. Труды Московского института электронного машиностроения, 1973, 32, с.73−91.

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

22. Колчин В. Ф. О поведении случайного графа вблизи критической точки. // Теория вероятностей и ее применения, 1986, 31, № 3, с.503−515.

23. Колчин В. Ф. Системы случайных уравнений. М., МИЭМ, 1988.

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

25. Колчин В. Ф., Севастьянов Б. А., Чистяков В. П. Случайные размещения. М., Наука, 1976.

26. Матула Д. В. Методы теории графов в алгоритмах кластерного анализа. В кн.: Классификация и кластер. М., Мир, 1980, с.83−111.

27. Медведев Ю. И. Некоторые теоремы об асимптотическом распределении статистики х2- Докл. АН СССР 1970, 192, № 4, с.987−989.

28. Мухин А. Б. Локальные предельные теоремы для решетчатых случайных величин. // Теория вероятностей и ее применения, 1991, 36, № 4, с.660−674.

29. Павлов Ю. Л. Случайные леса. Петрозаводск, КарНЦ, 1996.

30. Павлов Ю. Л. Асимптотическое распределение максимального объема дерева в случайном лесе. // Теория вероятностей и ее применения, 1977, 22, № 3, с.523−533.

31. Павлов Ю. Л., Чеплюкова И. А. Предельные распределения числа вершин в слоях просто генерируемого леса. // Дискретная математика, 1999, 11, № 1, с.97−112.

32. Павлов Ю. Л., Лосева Е. А. Предельные распределения максимального объема дерева в случаном рекурсивном лесе. // Дискретная математика, 2002, 14, № 1, с.60−74.

33. Павлов Ю. Л., Черепанова Е. В. Предельные распределения числа пар в обобщенной схеме размещения. // Дискретная математика, 2002, 14, № 3, с.149−159.

34. Павлов Ю. Л., Черепанова Е. В. О числе путей в случайной подстановке с известным числом циклов. // Обозрение прикладной и промышленной математики, 2002, 9, в.2, с.431−432.

35. Павлов Ю. Л., Черепанова Е. В. Предельные распределения минимальной длины цикла в случайной подстановке с известным числом циклов. // Обозрение прикладной и промышленной математики, 2003, 10, в.2, с.357−358.

36. Прохоров Ю. В. Асимптотическое поведение биномиального распределения. // Успехи матем. наук, 1953, 8, № 3, с.135−142.

37. Прудников А. П., Брычков Ю. А., Маричев О. И. Интегралы и ряды. М., Наука, 1981.

38. Ростовцев А. Г. О времени жизни общего и персонального открытого ключа. // Проблемы информационной безопасности. Компьютерные системы. СПб., № 4, 1999, с.57−61.

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

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

41. Сачков В. Н.

Введение

в комбинаторные методы дискретной математики. М., Наука, 1982.

42. Севастьянов Б. А. Ветвящиеся процессы. М., Наука, 1971.

43. Степанов В. Е. О распределении числа вершин в слоях случайного дерева. // Теория вероятностей и ее применения, 1969, 14, № 1, с.64−77.

44. Степанов В. Е. Предельные распределения некоторых характеристик случайных отображений. // Теория вероятностей и ее применения, 1969, 14, № 4, с.639−653.

45. Степанов В. Е. О некоторых особенностях строения случайного графа вблизи критической точки. // Теория вероятностей и ее применения, 1987, 32, № 4, с.633−657.

46. Тимашев А. Н. О распределении числа циклов заданной длины в классе подстановок с известным числом циклов. // Дискретная математика, 2001, 13, № 4, с.60−72.

47. Туманян С. X. Об асиптотическом распределении критерия х2> Докл. АН СССР, 1954, 94, № 6, с.1011−1012.

48. Туманян С. X. Асиптотическое распределение х2 при одновременном возрастании объема наблюдений и числа групп. Теория вероятностей и ее применения, 1956, 1, № 1, с.131−145.

49. Харари Ф. Теория графов. М., Мир, 1973.

50. Чеплюкова И. А. Возникновение гигантского дерева в случайном лесе. // Дискретная математика, 1998, 10, № 1, с. И1−126.

51. Черепанова Е. В. Распределение числа пар объектов в одной урновой схеме. // Тез. докл. науч. конф. «Карелия и РФФИ», Петрозаводск, 2002, с.99−100.

52. Черепанова Е. В. Одна задача о случайных подстановках с известным числом циклов. // Обозрение прикладной и промышленной математики, 2003, 10, в.1, с.251−252.

53. Черепанова Е. В. Предельные распределения числа циклов заданной длины в случайной подстановке с известным числом циклов. // Дискретная математика, 2003, 15, № 3, с.128−144.

54. Черепанова Е. В. Асимптотика статистики %2 в некоторых комбинаторных задачах. // Тр. Института прикл. матем. исслед. Карельского НЦ РАН, 2003, 4, с.129−135.

55. Черепанова Е. В. Критерий пустых ящиков для случайных лесов. // Тр. Института прикл. матем. исслед. Карельского НЦ РАН, 2003, 4, с.136−143.

56. Bollobas В. The evolution of random graphs. Trans. Amer. Math. Soc., 1984, 286, pp.257−274.

57. Bollobas B. Random graphs. London, Academic Press, 1985.

58. Cherepanova E. V. Limit distribution of number of chains in a random forest. // Information processes, 2002, 2, № 2, pp.165.

59. Erdos P, Spenser J. Probabilistic Methods in Combinatorics. Academic Press, Mew York, 1974.

60. Kazimirov N. I. Local limit theorems for an array scheme and Galton — Watson forests. // In: Probabilistic Methods in Discrete Math. Proc. of the Fifth Intern. Petrozavodsk Conf., Utrecht, VSP, 2002, pp.189−196.

61. Le Gall. Branching Processes, Random Trees and Superprocesses. // Proc. Math. J. PMV, Extra Volume ICM, 1998, III, pp.279−289.

62. Luczak Т., Pittel B. Components of random forests. // Combinatorics, Probability and Computing, 1992,1, 35−52.

63. Lyons R., Peres Yu. Probability on trees and networks. Book in preparation, available at http://php.indiana.edu/ rdlyons/prbtree/prbtree.html.

64. Mahmoud H. M. Evalution of random search trees. Wiley, New York, 1992.

65. Menezes A., P. van Oorschot, S. Vanstone. Handbook of applied cryptography. CRC Press, 1996, electronic version is available at http://www.cacr.math.uwateloo.ca/hac.

66. Myllari T. Limit distribunions for the number of leaves on a random forest. // Adv. Appl. Probab., 34, 2002, pp.1−19.

67. Palmer E. M. Graphical evolution: An introduction to the theory of random graphs. New York, 1985.

68. Pavlov Yu. L. Random Forests. VSP, Utrecht, 2000.

69. Reittu H., Norros I. On the power-law random graph model of massive data networks. // Performance Evaluation, 2004, 55, pp.3−23.