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

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

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

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

Пусть ячейки первого уровня размещаются по ячейкам второго уровня в соот ветствии с равномерным распределением;

обозначим через Aji событие [j-я ячейка 1-го слоя попала в i-ю ячейку 2-го слоя]. После этого частицы распределяются по ячейкам второго слоя в соответствии со случайным вектором вероятностей таким, N1 что 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. Введем производящую функцию s N N N 2 1 N1 0 k N 1 N N,r (x, y, z) = x y z P(µr1 = k1,..., µrs = ks ).

N1 !N0 !

k0,m,n В тезисе показано, что N s z ri y m mr z N,r (x, y, z) = eye + (xi 1).

ri ! m!

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

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

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

использовала результаты других авторов Более общее доказательство для 14.

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

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: ances tral 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 1 1 из одинаковых чисел: p(1) =, p(2) = N1,..., N1 N2,..., N2.

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

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

k!

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

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

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

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

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

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

k!

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

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

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

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

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

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

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

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

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

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

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

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

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

Теорема 6. Пусть l - фиксированное натуральное число, C0,, 1, 2 (1) некоторые постоянные и в схеме серий N0, N1, N2, p 0 так, что l+ N1 (1) C0 0, N0 p, l N N0 (2) 0 1 2, Eµr.

N Тогда 1 (2) (µr ) = O, a = min,.

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

N Тогда для любого фиксированного r 2 распределение случайной величины (2) (2) µr Eµr сходится к стандартному нормальному распределению.

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

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

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

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

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

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

Теорема 8. Если N = min Nk 2, то k P lim k 1 0.

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

n Теорема 9. При n распределения случайных величин n = сходятся к n распределению суммы = j=1 j, где случайные величины 1, 2,... независимы и P(j x) = 1 exj(j+1)/2, x 0, j = 1, 2,...

Для доказательства требуются две дополнительных леммы. Положим T (0) = 0, T (j) = min(t : t j), j = T (j) T (j + 1), j = n 1,..., 1.

Здесь j - время перехода от j + 1 объединенных частиц к j объединенным частицам, причем {j 0} = {min(t : t j) min(t : t j + 1)} = {T (j+1) = j + 1}.

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

Лемма 2. Если k n, то k P{k = 0}.

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

Лемма 3. Если k m n, то k P{µ1 (m, n) k} P{µ1 (m, n) = k}.

P{µ1 (m, n) k + 1} P{µ1 (m, n) = k + 1} 3(n k) Автор выражает глубокую благодарность научному руководителю, доктору физико-математических наук А.М. Зубкову за постоянное внимание к работе и ценные советы, а также профессору, доктору физико-математических наук В.А.

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

Работы автора по теме диссертации [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.

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