WWW.DISSERS.RU

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

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

Pages:     || 2 |
Московский государственный университет им. М.В. Ломоносова Механико-математический факультет

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

УДК 519.212.2, 519.214.5 Шибанов Олег Константинович ПРЕДЕЛЬНЫЕ ТЕОРЕМЫ ДЛЯ МНОГОЭТАПНЫХ СХЕМ РАЗМЕЩЕНИЯ ЧАСТИЦ ПО ЯЧЕЙКАМ 01.01.05 Теория вероятностей и математическая статистика

АВТОРЕФЕРАТ

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

Москва 2009

Работа выполнена на кафедре математической статистики и случайных процессов механико-математического факультета Московского Государственного Университета им. М.В. Ломоносова.

Научный консультант: доктор физико-математических наук, Зубков Андрей Михайлович.

Официальные оппоненты: доктор физико-математических наук, профессор, Ивченко Григорий Иванович.

кандидат физико-математических наук, Шабанов Дмитрий Александрович.

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

Защита диссертации состоится 30 октября 2009 года в 16 часов 40 минут на заседании диссертационного совета Д 501.001.85 при Московском Государственном Университете им. М.В. Ломоносова по адресу: 119991, ГСП-1, Москва, Ленинские Горы, МГУ, аудитория 16-24.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ (Главное здание, 14 этаж).

Автореферат разослан 29 сентября 2009 года.

Ученый секретарь диссертационного совета Д 501.001.85 при МГУ, доктор физико-математических наук, профессор И.Н. Сергеев

Общая характеристика работы

Актуальность темы Решение вероятностных задач, связанных с дискретными распределениями, часто приводит к изучению сумм случайных индикаторов, то есть сумм случайных величин, каждая из которых принимает значения из множества {0, 1}. Формулы для точного распределения суммы случайных индикаторов в большинстве случаев являются громоздкими и неудобными для практического использования.

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

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

В таких случаях требуется применять иные методы пуассоновской аппроксимации, 2 к примеру, предложенные в работах Б.А. Севастьянова, А.М. Зубкова, В.Г.

4 5 Михайлова или часто используемый в последнее время метод Чена-Стейна.

Одной из первых задач для сумм зависимых случайных индикаторов, полностью исследованной во всех областях изменения параметров, является классическая задача о размещении частиц по ячейкам. Пусть n частиц размещаются по N ячейкам независимо и равновероятно. Обозначим через µr = µr(n, N) число ячеек, содержаСм., например, Ширяев А.Н. Вероятность. В 2 кн. М.: МЦНМО, 2004, т. 1, § 6.

Севастьянов Б.А. Предельный закон Пуассона в схеме сумм зависимых случайных величин.

Теория вероятностей и ее применения, 1972, т. XVII, вып. 4, с. 733-738.

Зубков А.М. Неравенства для распределения суммы функций от независимых случайных величин. Математические заметки, т. 22, номер 5 (1977), с. 745-758.

Михайлов В.Г. Неторорые оценки точности пуассоновской аппроксимации для суммы зависимых случайных индикаторов. Обозрение прикладной и промышленной математики, 1994, вып. 4, т. Barbour A.D., Chen L.H.Y. An introduction to Stein’s method. World Scientific, 2005.

Barbour A.D., Holst L, Janson S. Poisson Approximation. Oxford University Press, щих в точности r частиц. В зависимости от взаимного поведения n, N выделяются области, в которых предельное распределение µr является распределением Пуассона или нормальным распределением.

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

Будем считать, что множество ячеек разделено на слои и в j-м слое содержится Nj ячеек. На первом этапе N0 исходных частиц независимо размещаются по Nячейкам первого слоя в соответствии с распределением p(1) = (p(1), p(1),..., p(1)). На 1 2 Nвтором этапе N1 ячеек первого слоя рассматриваются как частицы, и они независимо размещаются по N2 ячейкам второго слоя вместе с попавшими в них исходными частицами в соответствии с распределением p(2) = (p(2), p(2),..., p(2)). Размещения 1 2 Nпродолжаются аналогично m раз, то есть на последнем этапе ячейки (m - 1)-го слоя размещаются по ячейкам m-го слоя. Такую схему размещения естественно называть m-этапной. Будем через µ(m)(N0, N1,..., Nm, p(1),..., p(m)) = µ(m) обозначать число r r ячеек m-го слоя, в которые попало ровно r исходных частиц.

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

Пусть ячейки первого уровня размещаются по ячейкам второго уровня в соответствии с равномерным распределением; обозначим через Aji событие [j-я ячейка 1-го слоя попала в i-ю ячейку 2-го слоя]. После этого частицы распределяются по ячейкам второго слоя в соответствии со случайным вектором вероятностей таким, N1 что i = X(Aji), здесь X(A) - индикатор события A. Полученное таким j=Nобразом размещение аналогично равновероятной на обоих этапах двухэтапной схеме размещения.

Для различных целых неотрицательных чисел r1,..., rs обозначим r = (r1,..., rs), Колчин В.Ф., Севастьянов Б.А., Чистяков В.П. Случайные размещения. М.: Наука, 1976.

Зубков А. М., Шибанов О. К. Многоступенчатые схемы размещения частиц по ячейкам.

Обозр. прикл. и промышл. матем., 2002, т. 9, вып. 1, с. 115–116.

Агиевич С. В. Двухэтапные размещения и двойная Q-функция. Обозр. прикл. и промышл.

матем., 2003, т. 10, вып. 1, с. 82.

s и пусть x = (x1,..., xs), а xk = xk...xk. Введем производящую функцию s N1 NN2 N1 N,r(x, y, z) = xkyN zN P(µr = k1,..., µr = ks).

1 s N1!N0! k0,m,nВ тезисе показано, что N s i z eye (xi - 1)zr ymmr N,r(x, y, z) = +.

ri! m! i=1 mБесконечная схема размещения, в которой m = и частицы, попавшие в одну ячейку на любом этапе, считаются склеившимися в новую частицу, была впервые упомянута в статье Кингмана в терминах моделей популяционной генетики.

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

Kingman J.F. The coalescent. Stochastic Proc. Appl., 1982, vol. 13, pp. 235-248.

см., например, Donnelly P. Weak convergence to a Markov chain with an entrance boundary: ancestral processes in population genetics. The Annals of Probability, 1991, vol. 19, no. 3, pp. 1102-1117.

Goh W.M.Y., Hitczenko P., Schmutz E. Iterating random functions on a finite set. preprint, 2006.

Dalal A., Schmutz E. Compositions of random functions on a finite set. Electronic Journal of Combinatorics, 2002, vol. 9, R26.

McSweeney J.K., Pittel B.G. Expected coalescence time for a nonuniform allocation process.

preprint, September 2008.

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

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

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

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

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

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

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

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

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

Разработанные в диссертации методы могут быть полезны специалистам МГУ им.

М.В. Ломоносова и Математического института им. В.А. Стеклова.

Апробация работы Изложенные в диссертации результаты неоднократно докладывались на семинаре "Дискретные задачи теории вероятностей" под руководством д.ф.-м.н. А.М. Зубкова в МГУ им. М.В. Ломоносова (2002-2006 гг.), а также на семинаре Отдела дискретной математики в Математическом институте им. В.А. Стеклова РАН (2005 г.), на Симпозиумах по Прикладной и Промышленной Математике, (2002 и 2003 гг., Сочи) и на конференции "Ветвящиеся процессы в случайной среде", Франкфурт, Германия (2004 г.).

Публикации Результаты диссертации опубликованы в 6 работах, список которых приведен в конце автореферата. В совместных работах вклад научного руководителя А.М. Зубкова состоял в постановке задач и выборе метода, а диссертанта - в поиске и разработке доказательств.

Михайлов В.Г. Центральная предельная теорема для схемы независимого размещения частиц по ячейкам. Труды Математического института АН СССР, 1981, т. 157, с. 138-Структура диссертации Диссертация состоит из оглавления, введения, трех глав и списка литературы, насчитывающего 33 наименования. Общий объем диссертации - 96 страниц.

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

Первая глава состоит из двух параграфов. В первом из них исследуется равновероятная, во втором - полиномиальная схема двухэтапного размещения частиц.

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

В случае равновероятной схемы векторы вероятностей на обоих этапах состоят 1 1 1 из одинаковых чисел: p(1) =,...,, p(2) =,...,.

N1 N1 N2 NУстановлен следующий результат:

Теорема 1. Если в равновероятной двухэтапной схеме размещения частиц r > 1 фикcировано, N0, N1, N2 так, что N0 = o(N2), N0 = O(N1) и Eµ(2) (0, ), r то k P(µ(2) = k) e-, k = 0, 1,...

r k! Для первого момента µ(2) получены явные асимптотические формулы с оценками r остаточных членов.

Лемма 1. В равновероятной двухэтапной схеме при любом r r NN0 N1 1 NEµ(2) = e- 1 + O + +, r r-N2 N0 Nr!Nесли N0, N0 = O(N1), N1 = O(N2), а если N0, N0 = o(min{N1, N2}), N2 = O(N1), то r N0 N0 1 NEµ(2) = 1 + O + +.

r r-N2 N0 Nr!NВо втором параграфе главы 1 мы изучаем полиномиальную схему двухэтапного размещения частиц, то есть такую схему, в которой распределения вероятностей на обоих этапах могут отличаться от равномерного.

Обозначим через p(1) = max(p(1),..., p(1)), p(2) = max(p(2),..., p(2)).

1 N1 1 NДоказана теорема Пуассона для такой схемы размещения:

Теорема 2. Если параметры двухступенчатой схемы размещения изменяют1-[r/2]-ся так, что min N0, N1 p(1) 0, min(N0, N1)p(2) 0, Eµ(2) (0, ), r то k P(µ(2) = k) e-, k = 0, 1,...

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

Теорема 3. При любых целых l, m 1, l + m < N0, справедливы неравенства m N1 l Eµl+m l Cl+m 1 - p(1) 1 - N1 N0 - m EµlEµm l l l- Cl+mN1 p(1).

2N1 - p(1) 1-(min(l,m))-В частности, если l, m 1 фиксированы, а min N0, N1 p(1) 0, то Eµl+m = o(EµlEµm).

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

Теорема 4. Если параметры двухступенчатой схемы размещения изменяются 1-[r/2]-так, что min N0, N1 p(1) 0, min(N0, N1)p(2) 0, Eµ(2) (0, ), то r P(max{j : µ(2) > 0} = r) 1 - e-, P(max{j : µ(2) > 0} = r - 1) e-.

j j Вторая глава диссертации состоит из двух параграфов. Она посвящена доказательству центральной предельной теоремы в двухэтапной схеме размещения частиц, в которой частицы на первом этапе размещаются в соответствии с полиномиальным распределением p(1), а на втором этапе - в соответствии с равновероятным распре1 делением p(2) =,...,.

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

Pages:     || 2 |






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