Геометрические функционалы от случайных множеств и случайных графов

• Автор: Мусин, Максим Маратович
• Шифр специальности: 01.01.05
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Москва
• Количество страниц: 97 с.

Содержание
Введение

Глава 1. Геометрические функционалы от точечных потоков

1.1 Закон повторного логарифма для последовательности объемов случайных множеств

1.2 Закон повторного логарифма для сумм экспоненциально стабилизирующихся функционалов

Глава 2. Геометрические функционалы от случайных графов

2.1 Каплинг случайного графа преимущественного присоединения и случайного графа Эрдёша-Реньи
2.2 Вероятность локализации диаметра случайного графа преимущественного присоединения

Глава 3. Статистическое исследование случайных графов

3.1 Статистический тест адекватности модели графа преимущественного присоединения

3.2 Компьютерное моделирование некоторых случайных графов

Список литературы

Список основных обозначений
— "положить по определению";
N — множество натуральных чисел:
Z — множество целых чисел;
R — множество действительных чисел; а V b = тах{а. Ь}, для а,Ьб1; а Л 6 = min{a, b}, для а, Ъ 6 R;
[а] - наибольшее целое, не превосходящее а 6 R;
[а] - наименьшее целое, не меньшее а 6 R; р(:г, у) = тах;=1..д |.Т; - у,| для х, у е р{А, В) — inf {р(х, у)х Е А, у е I?} для А. В с. с/(Б) = sup {р(х, у)х, у Е В}
|Л| — число элементов конечного множества Л, или мера Лебега для континуальных подмножеств WL,
дА — граница множества А в метрическом пространстве;
АМ = { 0: Qi = [0,1)(/ + i для г Е ЪА
dist(i. j) — длина кратчайшего пути, соединяющего две вершины ? и j данного графа;
dist(7, J) = inf {dist(f, j)|z € I,j E J} — для множеств вершин I и J; rlinrn(G) — диаметр графа G в метрике dist;
Д(G) - максимальная степень графа G
I (Е) — индикатор события Е;
ЕХ — математическое ожидание случайной величины X;
varX — дисперсия случайной величины X;
cov(X, Y) — ковариация случайных величин X и Y.

Введение
В диссертации расматриваются два основных типа случайных объектов: точечные процессы и случайные графы.
Точечный случайный процесс, иногда называемый также иногда точечным потоком, позволяет описывать конфигурации случайных точек в М‘г. Формально точечные процессы задаются дискретной! случайной мерой. Данная область широко исследуется и имеет обширные приложения в теории массового обслуживания, распознавании образов, пространственной статистике, различных задачах подсчета и др. В развитие теории точечных процессов весомый вклад внесли такие ученые, как Барбур, Бачел-ли, Бремо, Вир-Джонс, Добрушин, Дуб, Дэли, Жакод, Калленберг, Кер-стан, Кокс, Кэмпбелл, Ласт, Маттес, Матерой, Ньюмен, Пальм, Пенроуз, Сливняк, Юкич, Яглом и другие. Теория точечных случайных процессов изложена в ряде фундаментальных книг. Достаточно упомянуть .монографии Калленберга ([50]), Дэли и Вир-Джойса ([41, 42]), Мекке, Керстана и Маттеса ([5]). В диссертации исследуются модели, порожденные классическим иуассоновским точечным процессом, а также случайные множества и функционалы от точечных потоков.
Другим объектом исследований данной диссертации являются негеометрические случайные графы. В развитие теории случайных графов внесли свой вклад такие ученые, как Болобаш, Дюрретт, Колчин, Реньи, Риордан, Хохлов, Эрдёш и другие. Изложение основ данной теории можно найти, например, в книгах Болобаша [27], Колчина [3] и Дюрретта [47]. В последнее десятилетие внимание большого числа исследователей приковано к так называемым степенным законам. Степенные законы распределения степеней вершин некоторых эмпирически наблюдаемых графов породили бурный рост исследований моделей, отличающихся от классического графа Эрдёша-Реньи. В этом направлении работали такие исследователи, как Болобаш, Риордан, Спенсер, Тушиади [30], Лебедев [4], Уоттс, Строгатц [82], Павлов [11], Степанов [12] и многие другие. В диссертации изучается

Такую функцию всегда можно найти, рассматривая построение разбиений {Кил, и £ 17 }. Для краткости будем писать Г)п — г)п (£„).
Зафиксируем .у и элементарный исход ш £ Ап такой, что выполняется соотношение
I Ат Е /Зт |
(уи„1/2 ЧпИЖ для всех 1 < т < пи некоторой константы у. Пусть оценка
(аиЖ/2ГЧЗп(ш) - Е5п) < ап(с)
выполнена для положительной константы /3, значение которой будет выбрано ниже. Тогда
(фп1/2Гг Е (И-ЕУ(Ьи,п)) = ибО,п)
(У+0„и)кп
- ЕЯп - (З3 - ЕД-) - £ (Лш - ЕА„,) <
т=] +1 у
< ап(е) - 7 - /3 - а„(е) + г)п)кпу/(г}„и)кп) < -/3, 1 < ;; < п.
Воспользуемся теперь методами, аналогичными примененным в лем-
ме 1.1.4, чтобы получить цепочку соотношений
НАД2)-1 53 <Е1/(А,„) - ЕМУ = НАГГ'Е 53 (ПА,п) - 1А,„)
«€©(.7,™) «£©0,«)
= на11/2)-1е 53 {у{ьщп) - у(ьи<п)1Кп) = (йг|а|1/2)-1е 53 у(ьщп)1р <
舩0,п) «6©0,п)
< (ДА|1/2)Е 53 |А,п|% = НбД172)-11А| р (Ё1) = о (п-2) = О (п-'м'2).
«6©0,п)
Таким образом, получим
„|£/„|1/2 ~ ' для достаточно больших п. Из полученных утверждений следует неравен-