Московский государственный университет им. М.В. Ломоносова

Механико-математический факультет

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

УДК 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, А.М. Зубкова 3, В.Г.

4 5 6.

Михайлова или часто используемый в последнее время метод Чена-Стейна Одной из первых задач для сумм зависимых случайных индикаторов, полностью исследованной во всех областях изменения параметров, является классическая задача о размещении частиц по ячейкам. Пусть 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 Scientic, 2005.

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

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

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

опубликован тезис 9, в котором был рассмотрен один вариант двухэтапной схемы.

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

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

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

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

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

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

и пусть x = (x1,..., xs ), а xk = xk1...xks. Введем производящую функцию Бесконечная схема размещения, в которой 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 nite set. preprint, 2006.

Dalal A., Schmutz E. Compositions of random functions on a nite 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. Если в равновероятной двухэтапной схеме размещения частиц r > 1 фикcировано, N0, N1, N2 так, что N0 = o(N2 ), N0 = O(N1 ) и Для первого момента µr получены явные асимптотические формулы с оценками остаточных членов.

Лемма 1. В равновероятной двухэтапной схеме при любом r если N0, N0 = O(N1 ), N1 = O(N2 ), а если N0, N0 = o(min{N1, N2 }), N2 = O(N1 ), то Во втором параграфе главы 1 мы изучаем полиномиальную схему двухэтапного размещения частиц, то есть такую схему, в которой распределения вероятностей на обоих этапах могут отличаться от равномерного.

Обозначим через p = max(p1,..., pN1 ), p = max(p1,..., pN2 ).

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

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

Теорема 3. При любых целых l, m 1, l + m < N0, справедливы неравенства При условиях теоремы 2 найдено распределение максимального заполнения ячеек.

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

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

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

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

Считая r 2 фиксированным, обозначим 2 = Dµr. Введем расстояние где (x)-функция стандартного нормального распределения.

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

Доказана следующая теорема.

Теорема 6. Пусть l - фиксированное натуральное число, C0,, 1, 2 некоторые постоянные и в схеме серий N0, N1, N2, p 0 так, что Тогда Из теоремы 6 следует Теорема 7. Пусть l - фиксированное натуральное число, C0,, 1, 2 некоторые постоянные и в схеме серий N0, N1, N2, p 0 так, что Тогда для любого фиксированного r 2 распределение случайной величины µr Eµr сходится к стандартному нормальному распределению.

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

Рассматривается процесс размещения частиц по слоям ячеек следующего вида.

На первом этапе N0 исходных частиц независимо и равновероятно размещаются по N1 ячейкам первого слоя. Частицы, попадающие в одну и ту же ячейку первого слоя, объединяются в одну новую частицу; при этом в первом слое получается случайное число 1 объединенных частиц (равное числу ячеек первого слоя, занятых исходными частицами). В общем случае на (k + 1)-м этапе k объединенных частиц, находящихся в Nk ячейках k-го слоя, независимо (друг от друга и от предыстории) и равновероятно размещаются по Nk+1 ячейкам (k + 1)-го слоя;

частицы, попадающие в одну и ту же ячейку (k + 1)-го слоя, объединяются, в результате чего получается k+1 объединенных частиц в (k + 1)-м слое. При сделанных предположениях последовательность 0, 1,... образует цепь Маркова с невозрастающими траекториями.

В первом параграфе главы 3 доказана следующая теорема:

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

распределению суммы = j=1 j, где случайные величины 1, 2,... независимы и Для доказательства требуются две дополнительных леммы. Положим Здесь j - время перехода от j + 1 объединенных частиц к j объединенным частицам, причем Следующая оценка является новой по сравнению с доказательствами в работах по математическим моделям эволюционной генетики (упомянутая выше статья 11 ), а также с доказательствами статей 1214.

Лемма 2. Если k < n, то Доказательство этой леммы использует новый результат для классической схемы размещения частиц. Обозначим через µ1 (m, n) число непустых ячеек при равновероятном размещении m частиц по n ячейкам в классической схеме размещения.

Лемма 3. Если k < m < n, то Автор выражает глубокую благодарность научному руководителю, доктору физико-математических наук А.М. Зубкову за постоянное внимание к работе и ценные советы, а также профессору, доктору физико-математических наук В.А.

Ватутину и доктору физико-математических наук В.Г. Михайлову за многочисленные обсуждения и важные замечания.

[1] Зубков А. М., Шибанов О. К. Многоступенчатые схемы размещения частиц по ячейкам. Обозр. прикл. и промышл. матем., 2002, т. 9, вып. 1, с. 115–116.

[2] Зубков А.М.,Шибанов О. К. Двухступенчатая схема размещения частиц по ячейкам. Обозр. прикл. и промышл. матем., 2002, т. 9, вып. 2, с. 378-379.

[3] Зубков А.М., Шибанов О.К. Пуассоновская предельная теорема для двухэтапной равновероятной схемы размещения частиц по ячейкам. Дискретная математика, 2006, т. 18, вып. 4, с. 99-104.

[4] Зубков А.М., Шибанов О.К. Пуассоновская предельная теорема для двухэтапной полиномиальной схемы размещения частиц по ячейкам. Обозр. прикл. и промышл. матем., 2007, т. 14, вып. 3, с. 422-434.

[5] Зубков А.М., Шибанов О.К. Время до объединения всех частиц при равновероятных размещениях по последовательности слоев ячеек. Математические заметки, 2009, т. 85, вып. 3, с. 373-381.

[6] Шибанов О.К. Предельные теоремы для двухступенчатой схемы размещения частиц по ячейкам. Обозр. прикл. и промышл. матем., 2003, т. 10, вып. 1, с.

253.

Во всех совместных работах А.М. Зубкову принадлежат постановка задач и выбор метода, а диссертанту - поиск и разработка доказательств.