Леса Гальтона-Ватсона и случайные подстановки

В настоящее время широкое распространение в комбинаторном анализе получил теоретико-вероятностный подход. Хорошо развитые в теории вероятностей методы асимптотического анализа успешно используются при решении сложных комбинаторных задач. Впервые такой подход был использован В. Л. Гончаровым в статьях [6,7], применившим его к изучению случайных подстановок и (0, ^-последовательностей.

Применение вероятностных методов в решении перечислительных задач комбинаторики (см., например, [26,30,56,83]) связано с заданием вероятностей на множестве изучаемых комбинаторных объектов таким образом, чтобы эти вероятности определяли долю объектов с интересующими нас свойствами. Тогда, используя теоретико-вероятностный аналитический аппарат, можно получить точные или приближенные формулы для числа объектов, обладающих изучаемыми свойствами.

Одним из важнейших направлений исследований является изучение предельных свойств комбинаторных объектов, проявляющихся при неограниченном возрастании числа элементов, образующих такие объекты. Поэтому при анализе случайных структур использовались такие известные методы, как пуассоновская и гауссовская аппроксимации, производящие функции и их анализ методом перевала. В последние три десятилетия широкое распространение получил подход, основанный на применении обобщенной схемы размещения, введенной В. Ф. Колчи-ным [26,30,34]. Такой подход позволяет свести целый ряд комбинаторных задач к задачам о нахождении предельных распределений серий сумм независимых случайных величин.

Значительное внимание в работах по дискретной математике в настоящее время уделяется изучению случайных графов [30,31,34,50,56,58−60, 69,74−77,83]. С помощью обобщенной схемы размещения в этой области математики удается решать множество сложных и полезных в других областях науки задач. Так, случайные деревья, леса и подстановки находят применение в анализе вычислительных алгоритмов [77], статистических методах [11,38], моделировании транспортных [1,76] и информационных систем [76,86], генетике [81], криптографии [54,79], а также при решении собственно математических задач, например, в теории случайных уравнений [32,34] и проблеме эволюции случайных графов [3,31,60,69,82].

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

Так как к обобщенной схеме размещения сводится большое число задач комбинаторики, она представляет интерес как самостоятельный объект исследования. Свое название эта схема получила в связи с тем, что она является обобщением задачи о случайном равновероятном размещении п частиц в N ячеек, за которой утвердилось название классическая схема размещения. Терминология классической схемы размещения оказалась удобной для описания многих задач, в которых появляется полиномиальное распределение случайного вектора из N компонент. Классическая схема позволяет перейти от полиномиального распределения к распределению сумм независимых слагаемых с распределением Пуассона и усеченным распределением Пуассона.

Введение

обобщенной схемы размещения частиц не только расширяет область использования удобного языка для описания комбинаторных структур, но также дает возможность применять те методы, которые были развиты при анализе классической схемы [26]. Отметим, что все результаты, связанные с обобщенной схемой размещения, доказывались для каждого класса комбинаторных объектов отдельно. Однако некоторое сходство предельных теорем, получаемых в различных задачах с помощью обобщенной схемы размещения, позволяет надеяться на получение достаточно общих предельных теорем для обобщенной схемы размещения. В диссертации сделана попытка реализовать этот замысел, и доказан ряд достаточно общих теорем, не охватывающих однако тех зон изменения параметров Nun, интерес к которым в последнее время особенно велик в связи с понятием гигантской компоненты [35].

Леса Гальтона—Ватсона представляют собой случайные леса, соответствующие траекториям ветвящегося процесса Гальтона—Ватсона, откуда и происходит это название. Термин лес Гальтона—Ватсона впервые, по-видимому, встречается в работе [84]. Применению методов теории ветвящихся процессов для изучения случайных лесов предшествовало рассмотрение случайных деревьев с занумерованными вершинами и соответствующих им процессов Гальтона—Ватсона с пуассоновским распределением числа прямых потомков каждой частицы. Впервые на эту возможность указано в статье В. Е. Степанова [59], а систематически такое исследование проведено в работах В. Ф. Колчина [27−29]. В [4,43,44] была установлена связь между начинающимися с одной частицы процессами Гальтона—Ватсона с геометрическим распределением числа прямых потомков каждой частицы и посаженными деревьями [53] (т. е. плоскими деревьями с висячими корнями и непомеченными вершинами). Связь между лесами, состоящими из N посаженных деревьев, и начинающимися с N частиц ветвящимися процессами Гальтона-Ватсона с геометрическим распределением числа прямых потомков одной частицы, впервые рассматривается в работах [10,47]. В [45,46,48−51] рассматривались случайные леса, для которых предполагалась связь с условными ветвящимися процессами Гальтона—Ватсона, распределение вероятностей на множестве лесов при этом не было обязательно равномерным. Однако ограничения на вероятностную меру не позволяли использовать полученные результаты для многих классов случайных лесов. В работах [67,83] эти ограничения были сняты, однако осталось одно существенное ограничение на распределение числа прямых потомков каждой частицы в процессах Гальтона—Ватсона, соответствующих рассматриваемым лесам: ограниченность третьего момента этого распределения. В статье [16] удалось снять это ограничение для распределений максимального объема дерева, числа деревьев заданного объема и высоты леса Гальтона—Ватсона, показав, что оно может быть заменено более слабым, а именно, ограниченностью второго момента распределения числа прямых потомков каждой частицы. В статье [68] удалось обобщить эти результаты для распределений объемов наибольших деревьев. Кроме того, в диссертации с помощью общих результатов об обобщенной схеме размещения удалось получить также некоторые дополнительные результаты о предельном поведении объемов деревьев леса Гальтона—Ватсона.

Случайные подстановки занимают особое место в ряду комбинаторных задач, связанных с обобщенной схемой размещения. Как показано в статье [52], случайные подстановки с известным числом циклов соответствуют той же обобщенной схеме размещения, что и рекурсивные леса [87]. Как показано в [78], такие леса не могут быть изучены с помощью ветвящегося процесса Гальтона—Ватсона. Наиболее подробно результаты исследований случайных подстановок и история этих исследований изложены в [30,33,34]. Там же приведены теоремы о предельном распределении числа циклов случайной подстановки степени п при п —" оо с ограничениями на длины циклов и без ограничений. В статье [52] получено полное описание предельного поведения максимальной длины цикла случайной подстановки с известным числом циклов при п оо, а в работе [61] получены некоторые результаты о распределении числа циклов заданной длины для таких подстановок. В диссертации получено полное описание предельного поведения р-то по величине цикла при фиксированном р и в некоторых зонах изменения параметров — для р —> оо.

В последнее время в работах по случайным графам повышенный интерес проявляется к возникновению гигантской компоненты, т. е. такой компоненты, которая с вероятностью, стремящейся к единице, имеет порядок п, где п — число вершин графа, а следующая по величине компонента имеет порядок о (п) [35]. В работе [66] были найдены условия возникновения гигантского дерева в лесе Гальтона—Ватсона, а из результатов статьи [52] следует, что гигантский цикл в случайной подстановке степени п с N циклами при п оо возникает при условии N/ In п 0 и не возникает при условии N/nn оо. В диссертации доказано, что при N/ In п -" а > 0, где, а — константа, гигантский цикл также не возникает.

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

Основными методами исследования в диссертации являются обобщенная схема размещения, теория ветвящихся процессов Гальтона—Ватсона и методы получения предельных теорем для сумм независимых решетчатых случайных величин, включая локальную сходимость в схеме серий. В настоящее время известные достаточные условия такой сходимости не покрывают все зоны изменения параметров многих комбинаторных объектов (по этому поводу см. параграф 1.4 книги [30]). И хотя в последних работах (см., например, [39]) имеются определенные достижения в этом направлении, эта проблема по-прежнему остается актуальной, а проверка известных условий часто оказывается весьма трудной задачей. В диссертации удалось для некоторых случаев применить результаты статьи [39] и получить несколько общих теорем для обобщенной схемы размещения. Эти теоремы были использованы для достижения целей диссертации. Однако, возникающие здесь технические трудности, к сожалению, не позволили получить весь спектр предельных теорем для обобщенной схемы размещения. Кроме того, удалось получить несколько дополнительных результатов, а именно: а) предельные распределения всех компонент леса Гальтона—Ватсона с N корнями и п некорневыми вершинами при N оо и п = const, б) предельные распределения р-ой по величине компоненты леса Гальтона—Ватсона с N корнями и п некорневыми вершинами и случайной подстановки степени п с N циклами при N, n, p оо так, что п = O (N), с некоторыми ограничениями на скорость роста р.

Диссертация состоит из четырех глав. Первая глава носит вводный характер. В этой главе даются все основные определения и обозначения (параграфы 1.1 и 1.2), приводится ряд примеров применения обобщенной схемы размещения (параграф 1.3). В четвертом параграфе этой главы приводится описание изучаемых в дальнейшем в общем виде схем размещения. Такие схемы (названные для краткости каноническими) охватывают широкий спектр задач, сводимых к обобщенной схеме размещения. В этом же параграфе показано, что не все схемы размещения могут быть сведены к такому виду, но приведенные примеры являются скорее исключением, подтверждающим правило, т. к. большинство известных в литературе примеров обобщенной схемы размещения все же сводятся к такому виду, который рассмотрен в диссертации. В параграфе 1.5 дается описание рассматриваемых случайных подстановок степени п с N циклами и приводится ряд известных ранее результатов о цикле максимальной длины.

Вторая глава целиком посвящена исследованию обобщенной схемы размещения. Здесь для схем, определенных в параграфе 1.4, с N компонентами, сумма которых равна п, найдены предельные распределения всех компонент в случае п = const, а при N, п —> оо так, что п = O (N), найдены предельные распределения р-х по величине компонент, причем как для фиксированного р, так и для р —> оо так, что р3 = о (п). Кроме того, при усилении ограничений на рассматриваемые схемы размещения получены предельные распределения для р-х компонент при фиксированном р и n/N -" оо, причем на скорость роста дроби n/N также накладываются определенные ограничения. Эти результаты используются в последующих главах для получения теорем о лесах Гальтона—Ватсона и случайных подстановках. В первом параграфе главы 2 указывается также граница применимости полученных теорем: они не могут быть использованы, например, для получения предельных распределений объемов деревьев случайного леса из некорневых деревьев. В конце главы 2 (параграф 2.6) приводятся теоремы, дающие достаточные условия невозникновения гигантской компоненты в обобщенной схеме размещения. Эти теоремы получены из предыдущих результатов главы 2 и не охватывают всех зон изменения параметров.

В третьей главе рассматриваются леса Гальтона—Ватсона. Сначала (параграф 3.1) приводится определение леса Гальтона—Ватсона по схеме, предложенной В. А. Ватутиным [4]. Затем (параграф 3.2) перечислены все результаты о лесах Гальтона—Ватсона, для которых в дальнейшем (параграфы 3.3 и 3.4) будет установлена избыточность условия конечности третьего момента распределения числа прямых потомков каждой частицы в соответствующем процессе Гальтона—Ватсона. Здесь же (параграф 3.2) перечислены теоремы, доказанные на основе результатов главы 2 и дающие предельные распределения объемов деревьев леса Гальтона— Ватсона в тех зонах изменения параметров N, п, р, которые ранее не были изучены.

Четвертая глава посвящена случайным подстановкам с известным числом циклов. В параграфе 4.1 приводится список всех полученных в диссертации результатов об асимптотике наибольших длин циклов случайной подстановки, а в последующих параграфах 4.2−4.5 приводится их доказательство. В параграфе 4.6 доказывается, что только в последней зоне изменения параметров (N/ In п -" 0) возникает гигантский цикл.

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

1. Предельные распределения при N оо: а) всех компонент обобщенной схемы размещения п частиц по N ячейкам при п = constб) р-ых по величине компонент (р = 0 соответствует максимальной компоненте) при N, п оо, р3 = о (п), п = O (N), где р принимает значения из множества {0,1,., N — 1}- в) р-ых по величине компонент при р = const и n/N оо, с ограничением на скорость роста n/N.

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

3. Предельные распределения объемов всех деревьев леса Гальтона— Ватсона при постоянном числе п некорневых вершин.

4. Предельные распределения р-ых по величине объемов деревьев леса Гальтона—Ватсона при N, n, p оо так, что р3 = о (п), п = O (N).

5. Полное описание предельного поведения длин р-ых по величине длин циклов случайной подстановки степени п с N циклами при п -" оо, включая случай р -> оо при ограничениях п — N = O (N), р3 — о{п — N).

6. Доказательство того, что в случайной подстановке степени п с N циклами гигантский цикл возникает только при N, n оо так, что N/nn 0.

Основные результаты диссертации опубликованы автором в пятнадцати работах [13−24,71−73], из них 3 статьи в журнале «Дискретная математика» [16,18,22], 1 статья в трудах международной конференции [72], 5 статей в сборниках трудов [13, 14, 19,23,24], 6 тезисов докладов на международных, всероссийских и региональных конференциях [15, 17,20,21,71,73]. Результаты также докладывались на IV Санкт-Петербургской ассамблее молодых ученых и специалистов (1999 г.), V Петрозаводской международной конференции «Вероятностные методы в дискретной математике» (2000 г.), Kalashnikov Memorial Seminar (Петрозаводск, 2002 г.), научной конференции «Карелия и РФФИ» (Петрозаводск, 2002 г.), IV Всероссийском симпозиуме по прикладной и промышленной математике (Петрозаводск, 2003 г.), международной конференции «Колмогоров и современная математика» (Москва, 2003 г.). В 2000;2002 гг. автор являлся одним из исполнителей гранта РФФИ 0001−233 «Вероятности на деревьях и лесах». В рамках этого проекта создан интернет-ресурс «Случайные леса» [85].

Результаты диссертации были получены в ходе проработки темы «Вероятностные и алгебраические методы исследования дискретных объектов», входившей в 1997;2000 гг. в план научно-исследовательских работ Института прикладных математических исследований Карельского научного центра РАН (№ гос. регистрации 01.9.60 0 12 636) и выполнявшейся в рамках проекта «Интеграция высшего образования и фундаментальной науки Республики Карелия» ФЦП «Интеграция» (per. № 634). В 2001;2003 гг. исследования проводились в рамках темы плана научно-исследовательских работ этого же института «Вероятности на деревьях и лесах», № гос. регистрации 01.2.00 1 3 997. В 2003 г. работа проводилась также по государственному контракту «Исследование случайных комбинаторных структур» по программе фундаментальных исследований РАН «Современные проблемы теоретической математики» (госконтракт № 100 002−251/ОМН-01/018−026/90 703−1029).

В диссертации принята двойная нумерация параграфов и тройная нумерация теорем, лемм, формул и замечаний. Это значит, что параграф 3.4 является четвертым по порядку в главе 3, а теорема 2.1.2 является второй по порядку в параграфе 2.1.

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

2. Боровков А. А. Курс теории вероятностей. М., Наука, 1972.

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

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

5. Гнеденко Б. В., Колмогоров А. Н. Предельные распределения для сумм независимых случайных величин. М., Наука, 1949.

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

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

8. Грэхем Р., Кнут Д., Паташник О. Конкретная математика. М., Мир, 1998.

9. Дрмота М. Распределение высоты листьев корневых деревьев // Дискретная математика, 1994, 6, № 1, с.67−82.

10. Земляченко В. Н., Павлов Ю. Л. Леса из плоских посаженых деревьев, и ветвящиеся процессы. // Труды Петрозаводского ун-та. Сер. прикладная математика и информатика, 1992, 1, с.130−135.

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

12. Ибрагимов И. А., Линник Ю. В. Независимые и стационарно связанные величины. М., Наука, 1965.

13. Казимиров Н. И. Локальная сходимость в схеме серий и ветвящиеся процессы // Тр. Петрозаводского ГУ, сер. математика, 1997, 4, с.85−96.

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

15. Казимиров Н. И. Предельные теоремы для лесов Гальтона—Ватсона // IV С.-Пб. ассамблея молодых ученых и специалистов, СПб, 1999, с. 37.

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

17. Казимиров Н. И. Об асимптотике распределений числа потомков процесса Гальтона—Ватсона // Обозрение прикл. и пром. математики, 2000, 7, № 1, с. 105−106.

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

19. Казимиров Н. И. Один случай локальной предельной теоремы // Тр. Института прикл. матем. исслед. Карельского НЦ РАН, 2002, 3, с.58−66.

20. Казимиров Н. И. Об асимптотике больших компонент в обобщенной схеме размещения // Тез. докл. науч. конф. «Карелия и РФФИ», Петрозаводск, 2002, с.88−89.

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

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

23. Казимиров Н. И. Об асимптотике больших компонент обобщенной схемы размещения // Тр. Института прикл. матем. исслед. Карельского НЦ РАН, 2003, 4, с.61−76.

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

25. Калинина Н. Б., Павлов Ю. Л. Распределение кратностей вершин в случайном лесе. // Ветвящиеся процессы. Петрозаводск, КФ АН СССР, 1981, с.10−16.

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

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

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

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

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

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

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

33. Колчин В. Ф. О числе подстановок с ограничениями на длины циклов. // Дискретная математика, 1989, 1, № 2, с.97−109.

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

35. Колчин В. Ф. О существовании гигантской компоненты в схемах размещения частиц. // Обозрение прикладной и промышленной математики, 2000, 7, в. 1, с. 112-ИЗ.

36. Лукач Е. Характеристические функции. М., Наука, 1979.

37. Маркушевич А. И. Теория аналитических функций. М., Гостехиздат, 1950.

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

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

40. Павлов Ю. Л. Предельные теоремы для числа деревьев заданного объема в случайном лесе. // Математический сборник, 1977, 103, в. З, с.392−403.

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

42. Павлов Ю. Л. Один случай предельного распределения максимального объема дерева в случайном лесе. // Математические заметки, 1979, 25, № 5, с.751−760.

43. Павлов Ю. Л. Некоторые свойства плоских деревьев с висячим корнем. // Тез. докл. Всесоюз. школы «Дискретная математика и ее применения при моделировании сложных систем». Иркутск, 1991, с. 14.

44. Павлов Ю. Л. Некоторые свойства плоских деревьев с висячим корнем. // Дискретная математика, 1992, 4, № 2, с.61−65.

45. Павлов Ю. Л. О случайных деревьях. // Тр. Петрозаводского ГУ, сер. математика, 1993, 1, с.47−53.

46. Павлов Ю. Л. Асимптотическое поведение высоты случайного леса. // Сборник трудов Отдела математики и анализа данных КарНЦ РАН, 1994, 1, с.4−17.

47. Павлов Ю. Л. Предельные распределения высоты случайного леса из плоских корневых деревьев. // Дискретная математика, 1994, 6, № 1, с. 137−154.

48. Павлов Ю. Л. Предельные распределения максимального объема дерева в случайном лесе. // Дискретная математика, 1995, 7, № 3, с. 1932.

49. Павлов Ю. Л. Предельные распределения числа деревьев заданного объема в случайном лесе. // Дискретная математика, 1996, 8, № 2, с.31−47.

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

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

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

53. Пойа Д. Комбинаторные вычисления для групп, графов и химических соединений. // Перечислительные задачи комбинаторного анализа. М., Мир, 1979, с.36−138.

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

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

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

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

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

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

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

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

62. Феллер В.

Введение

в теорию вероятностей и ее приложения. М., Мир, 1967.

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

64. Харари Ф., Палмер Э. Перечисление графов. М., Мир, 1977.

65. Харрис Т. Теория ветвящихся случайных процессов. М., Мир, 1966.

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

67. Чеплюкова И. А. Предельные теоремы для лесов Гальтона—Ватсона. Дисс. на соискание уч. степени канд. физ.-мат. наук, Петрозаводск, Кар НЦ РАН, 2000.

68. Чеплюкова И. А. К вопросу о возникновении гигантской компоненты. // Тр. Института прикл. матем. исслед. Карельского НЦ РАН, 2002, 3, с.114−123.

69. Bollobas В. Random graphs. London, Academic Press, 1985.

70. Eric Weisstein’s World of Mathematics (http://mathworld.wolfram.com/ CoinProblem. html).

71. Kazimirov N. I. On the asymptotics of big components in a generalized allocation scheme // Information Processes, 2002, 2, № 2, pp.209−210.

72. 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.

73. Kazimirov N. I., Pavlov Yu. L. On a giant component in random permutation with a known number of cycles. // Abstracts of Conf. Kolmogorov and Contemporary Math., MSU, 2003, pp.461−462.

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

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

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

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

78. Meir A., Moon J. W. On the altitude of nodes in random trees // Can. J. Math., 1978, 30, № 5, pp.997−1015.

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

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

81. O’Connel N. Branching and Inference in Population Genetics. // Proceedings of the IMA Workshop of Population Genetics. Dublin, 1994.

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

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

84. Random Forests, web-page at http://www.krc.karelia.ru/structure/math/ forests/index.html.

85. Reittu H., Norros I. On large random graphs of the «Internet type» // Information Processes, 2002, 2, № 2, pp.244−245.

86. Shapiro A. A generalized distribution model for random recursive trees // Acta Informatica, 1997, 34, pp.211−216.