Предельные теоремы для некоторых случайных комбинаторных структур тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

Черепанова Елена Владимировна

ПРЕДЕЛЬНЫЕ ТЕОРЕМЫ ДЛЯ НЕКОТОРЫХ СЛУЧАЙНЫХ КОМБИНАТОРНЫХ СТРУКТУР

01.01.09 — дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

Петрозаводск 2004

Работа выполнена в Институте прикладных математических исследований Карельского научного центра РАН.

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

Официальные оппоненты: доктор физико-математических наук, профессор В. Ф. Колчин, кандидат физико-математических наук, доцент А. В. Соколов.

Защита состоится 22 июня 2004 г. в 16 часов 15 мин. на заседании диссертационного совета К 002.142.01 в Институте прикладных математических исследований Карельского научного центра РАН по адресу: 185610, Петрозаводск, ул. Пушкинская, И.

С диссертацией можно ознакомиться в библиотеке Карельского научного центра РАН.

Ведущая организация: Петрозаводский государственный университет.

Автореферат разослан "Ш иссия^ 2004

г.

Ученый секретарь диссертационного совета К 002.142.01 к.ф.-м.н., доцент

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

»•«С. НАЦИОНАЛЫ»-£ЫГ.Л ИПТР.КА

разноцветными шарами.

Методы исследования. Методами исследования в диссертации являются обобщенная схема размещения, методы получения локальных предельных теорем для сумм независимых решетчатых случайных величин, методы теории ветвящихся процессов, метод характеристических функций, алгебраические методы, методы комбинаторики, методы проверки статистических гипотез. Хотя в диссертации рассматриваются достаточно разные случайные комбинаторные структуры, проведенные исследования объединяет основной метод получения предельных теорем — обобщенная схема размещения. Этот метод введен и исследован В. Ф. Колчиным и является одним из наиболее известных и успешно применяемых вероятностных методов решения комбинаторных задач. Использование обобщенной схемы размещения приводит к необходимости доказательства предельных теорем для серий сумм независимых целочисленных случайных величин. Доказательства таких теорем, включая двумерный случай, составили основную сложность при получении результатов диссертации.

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

Основные положения диссертации, выносимые на защиту. На защиту выносятся:

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

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

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

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

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

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

Апробация результатов диссертации. Основные результаты докладывались на Workshop "Networking games and resource allocation" (Петрозаводск, 2002), Kalashnikov Memorial Seminar (Петрозаводск, 2002), III и IV Всероссийских симпозиумах по прикладной и промышленной математике (Сочи, 2002, Петрозаводск, 2003), X Всероссийской школе-коллоквиуме по стохастическим методам (Сочи, 2003).

Публикация результатов. Основные результаты диссертации опубликованы в девяти работах, из них две статьи в журнале "Дискретная

математика", две статьи в сборнике трудов Института прикладных математических исследований Карельского научного центра РАН, пять тезисов докладов на международных, всероссийских и региональных конференциях.

Структура и объем диссертации. Диссертация состоит из введения, пяти глав и списка литературы. Общий объем диссертации составляет 137 страниц. Список литературы содержит 70 наименований.

СОДЕРЖАНИЕ РАБОТЫ

Во введении приводятся обоснование актуальности темы диссертации, формулировка цели работы, основные научные положения, выносимые на защиту, и описание структуры диссертации.

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

Обобщенная схема размещения задается следующим образом. Пусть имеется набор целочисленных неотрицательных случайных величин Vif ->Vn таких, что щ +... + = п. Эти случайные величины можно рассматривать как заполнения ячеек при размещении п частиц в N ячеек, занумерованных числами 1,2,..., N, то есть T]i — число частиц, попавших в i-ую ячейку, 1 ^ i ^ N. Если совместное распределение случайных величин можно представить в виде

где ki,...,kff — произвольные целые числа, — независи-

мые неотрицательные целочисленные случайные величины, то говорят, что случайные величины образуют обобщенную

схему размещения.

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

Подстановку можно представить в виде ориентированного графа, состоящего из компонент связности, которые являются циклами и называются циклами подстановки. В диссертации рассматривается множество SnN подстановок степени п, имеющих N циклов, при равномерном распределении вероятностей на этом множестве, и изучается предельное поведение числа циклов заданной длины, минимальной длины цикла, а также числа путей в графах таких случайных подстановок.

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

вершиной дерева, еще не имеющего вершин. В работе рассматривается множество Д^п рекурсивных лесов, состоящих из N некорневых деревьев и имеющих п вершин, на котором задано равномерное распределение вероятностей.

Рассмотрим урновую схему с разноцветными шарами. Пусть из урны, содержащей по тп^2 различных шаров каждого N цветов, осуществляется равновероятный выбор без возвращения п шаров. В диссертации изучается предельное поведение числа пар извлеченных шаров одинакового цвета в этой урновой схеме при —► оо.

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

где и существует для которого В диссертации

рассматривается подмножество € лесов с N деревьями и п

некорневыми вершинами. Обозначим

Известно, что если уравнение гР\г) = имеет положительное решение, не превосходящее радиуса сходимости производящей функции то лес Гальтона — Ватсона Зту п можно считать сгенерированным ветвящимся процессом с N начальными частицами, в котором распределение числа прямых потомков каждой частицы задается равенствами

(2)

при этом = 1.

Частным случаем леса Зт/.п является множество корневых лесов с Ы+и помеченными вершинами, на котором задано равномерное распределение вероятностей. В диссертации изучается предельное поведение числа цепей в таком случайном лесе.

Во второй главе рассматривается множество 5п,лг случайныхпод-становок степени п, имеющих N циклов. На множестве Зп>м задается равномерное распределение вероятностей. Известно, что при изучении числовых характеристик таких случайных подстановок можно использовать обобщенную схему размещения (1), где щ — случайная величина, равная длине ¡-го цикла случайно выбранной подстановки, а независимые одинаково распределенные случайные величины £1,..., фу имеют распределение логарифмического ряда:

А*

-к1п(1 — А)

, А; = 1,2,..., 0< А<1.

(3)

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

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

Пусть Цг — случайная величина, равная числу циклов длины г в случайно выбранной подстановке из ¿"^./у, распределение независимых одинаково распределенных случайных величин задается

равенствами

Введем обозначения:

Слг=б+• • •+£лг, 4Г)=^Г)+•••+<&

Согласно хорошо известному свойству обобщенной схемы размещения, имеет место следующее утверждение.

Лемма 1.1.1. Для любого к = 0,1,..., ./V

t(r)

При помощи этой леммы получение предельного распределения случайной величины fir при n,N—tOO сводится к доказательству локальных предельных теорем для сумм C^i-k и независимых одинаково распределенных вспомогательных случайных величин и к оценке биномиальных вероятностей вида CjyPr (1 — Pr)N~k • При этом выбор параметра распределения (3) осуществляется наиболее удобным для доказательства способом. Во второй главе найдены предельные распределения случайной величины /|г во всех зонах изменения параметров n,N,r. В доказанных теоремах параметр А распределения (3) равен-А = 1 — п-1 при N/lnn = 0(1), а если N/lnn оо, то А — решение уравнения

из интервала (0,1). Ниже приводятся лишь некоторые из полученных в диссертации результатов.

Тогда

равномерно относительно k, для которых иг = (Ь — Npr)/arr■\/N находится в любом фиксированном конечном интервале, где

(5)

(6)

Теорема 2.1.6 Пусть выполнено одно из следующих условий:

(1) n,N,r -> оо так, что 1 < с ^ n/N ^ Ci < оо;

(2) n,N -»■ оо так, что n/N оо, N/\nn -> оо;

(3) п оо, N = 7 Inn + o(lnn), 7 — постоянная, 0 < 7 < оо;

(4) n,N 00 так, что n/N 1, п - N оо, г ^ 3. Тогда

равномерно относительно к, для которых находит-

ся в любом фиксированном конечном интервале.

Пусть [ж] означает целую часть числа х.

Теорема

В диссертации доказано, что для любых г при п —> оо, N/Inn —► О выполняются соотношения Р {¡iT = 0} —> 1, Р {/хг > 0} —^ 0 (теоремы 2.1.11-2.1.14), то есть предельным распределением является вырожденное, а если рассмотреть скорость сходимости к предельному распределению, то асимптотическое поведение распределений ßr можно описать с помощью закона Бернулли.

В третьей главе рассматриваются случайные подстановки из множества Sn,N и леса Гальтона — Ватсона с N деревьями и п некорневыми вершинами.

Легко видеть, что если n/N -4 1, то асимптотически в среднем каждый цикл подстановки из SniN состоит из одного элемента, и в этом случае можно считать все циклы компонентами малого объема. Из теорем 2.1.5, 2.1.6 следует, что при г ^ 3, n/N —¥ 1, Npr оо, где рг определено в (3), предельное распределение случайной величины цг, равной числу циклов длины г в случайно выбранной подстановке, одновременно описывается нормальным законом и распределением Пуассона. Естественно возникает вопрос о том, какое приближение для распределения лучше.

где рг, а2, т определены в (3), (5), (6). В главе 3 показано, что при Р = О (1/\/п — ТУ) лучшее приближение для распределения цг дает закон Пуассона; если \fNpr = о (Ре'1^) и 1/%/п - N = о(/3), то более точным приближением для распределения цТ является нормальный закон. При 1/\/п - N = о(/9), /Зе-1/^ = О (1/^г) распределение Пуассона является лучшим, если А < Аг, где

Пусть

(тп - г)2рг

1 + 4g ~3/2 3\/2к '

и если Л > Аг, то более точное приближение дает нормальный закон. В случае А = Лг расстояния между распределением цг и предельными распределениями асимптотически равны.

Как отмечено выше, при п -> оо, N/Inn —> 0 предельным распределением случайной величины (ir, равной числу циклов длины г в случайной подстановке из Sn>N„ для любого г является вырожденное, то есть = 0} —> 1. Получается, что, хотя любая случайная подста-

новка имеет свою цикловую структуру, вероятность того, что цг примет какое-то ненулевое значение, при любом г стремится к нулю. Нам представляется, что понять причину этого явления в какой-то степени может помочь изучение поведения случайной величины fj(i), равной минимальной длине цикла подстановки из S„tN. Эта характеристика ранее не изучалась. В диссертации доказаны следующие теоремы.

Теорема 3.1.5. Если n,N -)• оо так, что N/\an -> оо, то

Теорема 3.1.6. Если п оо, N — 7Inn + o(lnn), 0 < 7 < 00, то для г = 1,2,...

Теорема 3.1.7. Пусть n,N оо так, что n/N 00, N/ Inn 0, и пусть г = nz!N, где z — положительная постоянная. Тогда

Теорема 3.1.8. Если п оо, г = па, 0 < а < 1, то для фиксированных а и N ^ 2

Р{Ч(1) = 1} = 1 + о(1).

р0/(1) <г} = 1-е-ж + о(1).

= 1-(1-а)"-1+о(1).

Согласно теореме 3.1.8, при N = 2 и фиксированных а, 0 < а < 1.

то есть предельное распределение случайной величины 1с^п77(1) является равномерным на интервале (0,1). Отсюда получаем, что в 5П1г содержатся только такие подстановки, в которых циклы имеют длины вида п" йя-п", гО<ае<н, о при каждом фиксированном а вероятность наличия таких циклов стремится к нулю. Это объясняет, почему в этом случае Р {рг > 0} —> 0 для любого г. Аналогичные рассуждения можно провести и при N ^ 3.

Также в третьей главе доказаны предельные теоремы для случайной величины равной минимальному объему дерева в лесе Гальтона — Ватсона Зту|П. Пусть ] — наименьшее положительное целое число такое, что > 0, а 1 наименьшее натуральное, не кратное), удовлетворяющее условию > 0, если такого 1 нет, то положим / = 0. Пусть параметр А распределения (2) определяется равенством

при а если Пусть —

независимые одинаково распределенные случайные величины, равные объемам деревьев с корнями 1,...,]ЧГ, соответственно, в лесе Гальтона — Ватсона

Теорема 3.1.9 Пусть п,ЛГ со так, что МХ3+1 оо. Тогда

Теорема 3.1.10 Если п оа, то для фиксированных N ^ 2 и г

I • • •

р{ч(Ч=1} = 1 + о(1).

1,2,..

Теорема 3.1.9 показывает, что если N —> оо, то, сколь велико бы ни было п, минимальный объем дерева асимптотически равен единице. Этот результат можно объяснить, по-видимому, тем, что если n/N2 ^ С > 0, то, как известно, в лесе 3jv,n имеются деревья, объем которых имеет порядок п, а если n/N2 —00, то возникает так называемое гигантское дерево, содержащее п + о(п) вершин.

В четвертой главе изучается предельное поведение числа пар в обобщенной схеме размещения, где под парой понимаются две различные частицы, попавшие в одну ячейку. Так, для подстановки, пару составляют два различных элемента подстановки, принадлежащих одному циклу, в корневом лесе с помеченными вершинами пара — две различные некорневые вершины, принадлежащие одному дереву. Обозначим через число пар извлеченных шаров одинакового цвета в урновой схеме с разноцветными шарами, — число пар в случайном корневом лесе с помеченными вершинами, 1/3 — число пар в случайной подстановке из Sn,jv- Нетрудно видеть, что число различных цепей в случайном корневом лесе с помеченными вершинами равно т — U2 + n, а число различных путей в графе случайной подстановки из Sn>N равно В четвертой главе доказаны следующие теоремы.

Теорема 4.1.1 Пусть т > 2, 0 < п < mN, n,N 00 так, что n2/N оо, n/mN < С < 1. Тогда

равномерно относительно целых неотрицательных к, для которых (к — а)/а находится в любом фиксированном конечном интервале, где

= ~1)"2 2= (m-l)(mN-n)2n2 2mN ' ° ~ 2m3N3

Теорема 4,1.2 Пусть n,N -Л оо так, что n/N ^ С < 00, n2/N -> 00. Тогда

равномерно относительно целых неотрицательных k, для которых (к — о)/с находится в любом фиксированном конечном интервале,

Теорема 4.1.3 Пусть n,N оо так, что 1 < а ^ n/N ^ сг < оо.

равномерно относительно целых неотрицательных к, для которых находится в любом фиксированном конечном интервале,

А — решение уравнения (4) из интервала (0,1).

Пятая глава содержит некоторые статистические приложения. В частности, рассматривается следующая задача. Предположим, что из урны, содержащей К различных шаров, каждый из которых окрашен в один из N цветов, осуществляется равновероятный выбор без возвращения п шаров, 0 < п < К. Статистическая гипотеза состоит в том, что число шаров каждого цвета одинаково и равно m, то есть К = mN. Для проверки этой гипотезы естественно использовать статистику

где t]i — число извлеченных шаров i-го цвета, 1 ^ i ^ N.

Такую статистику можно использовать также для проверки статистических гипотез о равномерности распределения вершин по деревьям в случайном корневом лесе с помеченными вершинами и элементов подстановки из S„tn по циклам, г д»^ — случайная величина, равная числу некорневых вершин в i-ом дереве леса или, соответственно,

длине i-ого цикла подстановки, 1 ^ i ^ N. В случае, когда рассматриваемые гипотезы верны, асимптотики соответствующих статистик следуют из теорем 4.1.1-4.1.3 и легко проверяемого с помощью равенства T]i + • • • + ум = п соотношения

справедливого для любого х.

Статистический критерий пустых ящиков хорошо известен. Обычно он применяется для проверки гипотезы о том, что выборка, состоящая из п независимых наблюдений, взята из непрерывного распределения G(x). Критерий пустых ящиков основывается на классической задаче о размещении п дробинок по N ящикам, при этом N интервалам, на которые делится числовая ось, соответствуют ящики, а наблюдениям — размещаемые по ящикам дробинки. Критерий строится на основе статистики равной числу пустых ящиков при равновероятном размещении п дробинок по N ящикам. Следуя этим идеям и используя современные вероятностные методы дискретной математики, можно предложить аналогичные критерии для статистического анализа некоторых комбинаторных объектов. В разделах 5.3, 5.4 диссертации показана применимость критерия пустых ящиков для проверки статистической гипотезы о равномерности распределения вероятностей на множестве лесов Гальтона — Ватсона Sjv.n-

СПИСОК ОПУБЛИКОВАННЫХ РАБОТ ПО ТЕМЕ ДИССЕРТАЦИИ

Статьи

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

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

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

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

Тезисы докладов

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

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

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

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

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

Изд. лиц. № 00041 от 30.08.99. Подписано в печать 22.03.04. Формат 60х84'/1( Бумага офсетная. Гарнитура «Times». Печать офсетная. Уч.-изд. л. 1,0. Усл. печ. л. 1,0. Тираж 100 экз. Изд. № 34. Заказ № 421

Карельский научный центр РАН 185003, Петрозаводск, пр. А. Невского, 50 Редакционно-издательский отдел

Р11 7 7 3

Введение

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4.2 Предельные распределения (Cn,Vn).

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

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

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

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

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

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

В настоящее время в комбинаторном анализе широко применяются хорошо развитые в теории вероятностей методы. Впервые вероятностный подход при изучении комбинаторных объектов был использован 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 03997. В 2001-2002г. работа выполнялась при поддержке Российского Фонда Фундаментальных Исследований (грант 00-01-00233). В 2003г. исследования проводились по государственному контракту "Исследование случайных комбинаторных структур" по программе фундаментальных исследований РАН "Современные проблемы теоретической математики" (№Ю0002-251/ОМН-01/018-026/090703-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.