WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

загрузка...
   Добро пожаловать!

Pages:     | 1 || 3 |

Апробация работы Результаты диссертации неоднократно докладывались автором на семинаре "Асимптотический анализ случайных процессов и полей" (мехмат МГУ, 2005-2008 гг., руководители – профессор А.В. Булинский и доцент А.П. Шашкин), на Большом семинаре кафедры теории вероятностей (мехмат МГУ, 2009 г., руководитель – член-корреспондент РАН А.Н. Ширяев), научно-исследовательском семинаре кафедры анализа данных (ФИВТ МФТИ, 2009 г., руководитель – профессор А.М. Райгородский), городском семинаре по теории вероятностей и математической статистике (ПОМИ РАН, 2009 г., руководитель – академик РАН И.А. Ибрагимов), семинаре института стохастики (Университет Ульма, Германия, 2009 г., руководители профессор Е. Сподарев и профессор Ф. Шмидт), международной конференции SGSIA (Блаубойрен, Германия, 2009 г.), международной конференции SARD (Львов, Украина, 2009 г.), XXVIII конференции молодых ученых механикоматематического факультета МГУ (Москва, 2006 г.).

Публикации Результаты диссертации опубликованы в 5 работах, список которых приведен в конце автореферата.

Структура диссертации Диссертация состоит из введения, трех глав и списка литературы, насчитывающего 85 наименований. Общий объем работы 97 страниц.

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ Во введении излагается история вопроса, формулируются основные определения и описывается структура работы.

Введем основные определения. Пусть |A| обозначает число элементов конечного множества A, или меру Лебега для континуальных подмножеств Rd. Положим (x, y) = supi=1,...,d |xi - yi|, x, y Rd. Обозначим Br(x) = y Rd : (x, y) r замкнутый шар радиуса r > 0 с центром в точке x Rd. Пусть log x = ln x 1 для x R.

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

Для процесса, задающего конфигурацию точек {xi}, выполняется i=равенство (B) = I (xi B), xi где B есть ограниченное борелевское подмножество Rd. Точечные процессы рассматриваются и как случайные меры, и как конфигурации случайных точек, что не вызывает недоразумений.

Функционалом от точечного процессса назовем измеримое отображение из пространства локально конечных мер в R. Определим понятие радиуса стабилизации для данного функционала, введенное Пенроузом и Юкичем.

Определение 1.2.1. Для любого локально конечного множества X Rd и любого x Rd назовем радиусом стабилизации функционала = (x, X ) величину R = R(x, X ) > 0 такую, что для любого натурального числа r > R выполняются равенства (x, {x} X Br(x)) = (x, {x} X ).

Если такого конечного R не существует, то положим R =.

Определение 1.2.2. Семейство функционалов = (x, ·), x Rd, экспоненциально стабилизируется, если его радиус стабилизации п.н.

конечен, причем для всех t 0 и некоторых положительных постоянных C и c справедливо неравенство (t) := sup P (R(x, {x} ) > t) < C exp {-ct}.

xRd Сформулируем определние графа преимущественного присоединения, введенное Болобашем и Риорданом.

Определение 2.1.1. Пусть m - натуральное число. Для m = зададим граф преимущественного присоединения Gn по индукции.

m Для n = 1 пусть G1 состоит из одной вершины и одной петли. Граф Gn 1 получается из графа Gn-1 добавлением вершины номер n и ребра между ней и вершиной со случайным номером tn, имеющим распределение dn l, 1 l n - 1, 2n-P (tn = l) =, l = n, 2n-где dn обозначает степень вершины номер l в графе Gn-1.

l Для m > 1 граф Gn получается из графа Gmn отождествлениm ем вершин с номерами 1,..., m в вершину 1 графа Gn, вершин m + m 1,..., 2m в вершину 2 и т.д.

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

Dx := {y Rd ({y}, lx ) x }, xi, i i i где lx – ребро графа ближайших соседей, соответствующее точi ке xi. Случайное множество D получается объединением всех маркировок точечного потока. При работе со случайным множеством мы использовали явную конструкцию пуассоновского процесса.

Для последовательности объемов Sn = D [-n, n)d данного случайного множества получен закон повторного логарифма.

Теорема 1.1.1. Пусть для некоторых, µ > 0 выполнено условие x µ п.н., xi.

i Тогда справедливы соотношения Sn - ESn lim sup = 1 п.н., (2d+1nd log log n)1/n Sn - ESn lim inf = -1 п.н., n (2d+1nd log log n)1/где – некоторая постоянная, не зависящая от n.

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

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

Исследуются суммы функционалов от точечного потока вида (x, X ), где x Rd, X – произвольное локально конечное множество на Rd.

Рассмотрим случайное поле, порожденное экспоненциально стабилизирующимися функционалами.

Xi = (x, ), Qi = [0, 1)d + i, i Zd.

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

(A1) – трансляционно инвариантен;

(A2) – экспоненциально стабилизируется;

(A3) EX0 = 0;

(A4) E |X0|2+ < для некоторого (0, 1].

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

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

Напомним определение коэффициента сильного перемешивания для случайного поля. Для -алгебр A, B F обозначим (A, B) = supAA, BB |P (AB) - P (A) P (B)|. Для r > 0, u, v N {} и случайного поля X = Xi, i Zd определим коэффициенты сильного перемешивания (r, u, v) = sup ( {Xi, i I}, {Xj, j J}), где верхняя грань берется по всем конечным множествам I, J Zd таким, что (I, J) r, |I| u, |J| v.

Теорема 1.2.1. Пусть функционал удовлетворяет условиям (A1) и (A2). Тогда коэффициенты перемешивания поля X = {Xj, j Zd} допускают оценку (r, u, v) C(u v)e-cr, где положительные постоянные C и c не зависят от u, v и r; обозначает минимум из двух чисел.

Доказательство этого факта потребовало использования формулы Кэмпбелла-Сливняка. Напомним, что упомянутая формула является следствием свойств меры Кемпбелла для точечных процессов и распределения Пальма для пуассоновского процесса. Пусть B Rd ограниченное борелевское, f – ограниченная измеримая функция на произведении множеств Rd и пространства локально-конечных дискретных мер, – пуассоновский процесс в Rd постоянной интенсивности 1. Тогда выполняется соотношение E f(x, ) = Ef (x, {x}) dx.

B xB Формулировка закона повторного логарифма для случайного поля X потребует некоторых вспомогательных обозначений. Для фиксированного > 0 рассмотрим множество G = n = (n1,..., nd) Nd : ni > n, i = 1,..., d.

j j=i Далее запись n будет обозначать, что ni, i = 1,..., d.

Теорема 1.2.2. Пусть функционал обладает свойствами (A1)–(A4) и выполняется условие 2 := cov (X0, Xi) > 0.

iZd Тогда справедливо предельное соотношение Xi 1jn lim sup = 1 п.н., n, nG 2d2 n log log n где n = n1... nd.

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

Моментные оценки были получены за счет известных результатов для сильно перемешивающихся случайных полей (см., напр., книгу Дукана19).

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

Лемма 1.2.420. Пусть центрированное случайное поле X = {Xi, i Zd} таково, что L := supj E |Xj|2+ < и (r, u, v) (u + v)pe-cr, p > 0. Пусть Z Zd – произвольное конечное множество, S(Z) = Xi. Тогда для некоторой постоянной C, значение которой зависит iZ от величины p и не зависит от множества Z, верна оценка x S(Z) 1 sup P x - e-t /2dt xR VarS(Z) L |Z| L2/(2+) |Z|1/ C logd(1+) |Z| + log1+dp/(4+2) |Z|.

VarS(Z) (VarS(Z))1+/P. Doukhan, Mixing. Properties and examples, N.Y., Springer-Verlag, 1994.

Й. Сунклодас, Оценка скорости сходимости в центральной предельной теореме для слабозависимых случайных полей, Литовск. мат. сборн., 1985, 26(3), 541–559.

Максимальное неравенство для данного случайного поля было получено при помощи техники Вишуры21.

Лемма 1.2.7. Пусть последовательности (al)lN, (l)lN, таковы, что al (1 + ) 22dl log log l, для некоторого (0, 1); l = o (al);

l/l2 0, l, l N. Тогда при всех достаточно больших n G и некотором > 0 справедливо следующее максимальное неравенство.

P max |Sm| a n 2dP |Sn| a n - 2d n + C n, 1mn где C не зависит от n.

Во второй главе диссертации рассматривается модель графа преимущественного присоединения. В первой части второй главы оценивается вероятность каплинга данного графа и классического графа Эрдёша-Реньи. Следующая теорема является уточнением результата Болобаша и Риордана, где та же вероятность была оценена для случая постоянного значения параметра m.

Теорема 2.1.1. Пусть последовательность mn, mn n. Для любого 0 < < 1/2 существует такое вероятностное пространство и n определенные на нем графы Gn и G n, m, что mn n n mn n(m5 + Cmne-cm ) n n P G n, \ Gn m2 + ne-cm + Bn, mn n n Bn где Bn – произвольная последовательность положительных чисел.

Для доказательства данного результата применен последовательный каплинг. Граф Эрдёша-Реньи рассматрен как эволюционный граф, к которому на каждом шаге добавляется одна новая вершина и случайное количество новых ребер. На каждом шаге построено совместное распределение добавляемых ребер, произведена оценка математического ожидания и дисперсии количества получившихся на данном шаге лишних ребер в графе Эрдёша-Реньи. Суммарное количество таких ребер оценено с помощью неравенства Маркова.

M.J. Wichura, Inequalities with applications to the weak convergence of random processes with multi-dimensional time parameters, Ann. Math. Statist., 1969, 40, 681– 687.

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

Теорема 2.2.1. Пусть m 2 фиксировано и 0 < < 1/4. Тогда P (|diam(Gn ) log log n/ log n - 1| ) n-/m при всех достаточно больших n.

Для доказательства данного результата потребовалось применить линеаризованную диаграмму хорд, введенную Болобашем и Риорданом.

Введем набор X1,..., X2N независимых случайных величин, равномерно распределенных на (0, 1). Пусть Yi = X2i-1 X2i, Zi = X2i-1 X2i, i = 1,..., N. Рассмотрим вариационный ряд случайных величин Zi. Обозначим Ri = Z(i) правые и Li = Yj: Zj = Z(i) – соответствующие левые концы интервалов.

Рассмотрим случайные величины W0 := 0, Wk := Rmk, k = 1,..., n и wk := Wk -Wk-1. Для каждого k = 1,..., n введем набор случайных величин lk,1,..., lk,m по правилу {lk,i = j} = {Wj-1 < Lm(k-1)+i Wj}, j = 1,..., k, i = 1,..., m.

Пусть граф состоит из n вершин, и из каждой вершины i проведены ребера к вершинам с номерами li,1,..., li,m. Болобаш и Риордан показали, что следующий граф является графом преимущественного присоединения Gn. Весом вершины i Gn, мы будем называть слуm m чайную величину wi.

При доказательстве верхней оценки показано, что расстояние от некоторой случайной вершины до произвольной вершины графа не превосходит величины (1/2 + /2) log n/ log log n.

В ходе доказательства было использовано введенное Болобашем и Риорданом понятие полезной вершины.

Определение 2.2.1. Вершина i называется полезной тогда и только тогда, когда её вес wi (log n)2/n и i < n/(log n)5.

При доказательстве верхней оценки было показано, что с вероятностью 1 - O(n-3/4) расстояние от произвольной вершины графа Gn m до некоторой полезной вершины не превосходит 6 log log n, а расстояние от прозвольной полезной вершины до некоторой случайной вершины n, не превосходит (1/2 + /3) log n/ log log n. Существование n устанавливается в следующей лемме.

Лемма 2.2.3. Пусть константа C > 0 фиксирована. Пусть выполняется вспомогательное событие E1. Тогда для некоторой постоянной существует i (log n)1+ такое, что wi C/( n log n).

Третья глава диссертации посвящена моделированию случайных графов и их статистическому исследованию. В первой части третьей главы получен статистический тест адекватности модели случайного графа. Применено понятие среднего диаметра, использованное в работе Кумара и др.22 для исследования социальных сетей Flickr и Yahoo!360.

Определение 3.1.1. Средним диаметром AvgDiam(G) называется случайная величина, равная расстоянию между двумя случайно и равномерно выбранными вершинами графа G.

Теорема 3.1.1. Пусть H0 – гипотеза о соответствии графа G распределению графа Gn. Для m, n > 3 и уровня значимости имеет место m следующая оценка log n P AvgDiam(G) < - b(m, n, ) H0, log log n где 2 log (4m) log log n + log n - 2 log log log n b(m, n, ) =.

log log n + 2 log (4m) Вероятность ошибки первого рода удалось оценить при помощи техники, аналогичной той, которую мы применили при выводе нижней оценки в теореме о локализации диаметра случайного графа преимущественного присоединения (теорема 2.2.1).

Во второй части главы 3 прозведено моделирование некоторых случайных графов. Для этого был использован пакет igraph 0.5.2, разработанный Габуром Чарди. Пакет написан на языке C, но имеет имплементацию для языка анализа статистической информации R. В данном R. Kumar, J. Novak, A. Tomkins, Structure and evolution of online social networks, Proceedings of the 12th ACM SIGKDD international Conference on Knowledge Discovery and Data Mining, 2006, 611–617.

пакете имеются средства моделирования некоторых известных случайных графов. В диссертации представлены результаты моделирования графов Эрдёша-Реньи, Уоттса-Строгатца и графа преимущественного присоединения (модель Альберт-Барабаши). Для всех графов был вычислен диаметр и средний диаметр.

Pages:     | 1 || 3 |






© 2011 www.dissers.ru - «Бесплатная электронная библиотека»