Предельные теоремы для многоэтапных схем размещения частиц по ячейкам тема диссертации и автореферата по ВАК РФ 01.01.05, кандидат физико-математических наук Шибанов, Олег Константинович

• Шибанов, Олег Константинович
• кандидат физико-математических наук
• 2009

Оглавление диссертации кандидат физико-математических наук Шибанов, Олег Константинович

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

Глава IIуассоновская предельная теорема для двухэтапной схемы размещения

1.1. Равновероятная двухэтапная схема размещения

1.2. Полиномиальная двухэтапная схема размещения

Глава Центральная предельная теорема для двухэтапной схемы размещения

2.1. Уточнение статьи В.Г. Михайлова

2.1.2. Свойства величин Е/лг и Dfir

2.1.3. Оценки третьего и четвертого моментов

2.1.4. Центральная часть доказательства

2.1.5. Вычислительная часть доказательства

2.2. Центральная предельная теорема для двухэтапной схемы размещения

2.2.2. Доказательства

Глава Бесконечная схема размещения частиц

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

3.2. Предельное распределение момента объединения всех частиц

3.2.2. Доказательства

Введение диссертации (часть автореферата) на тему «Предельные теоремы для многоэтапных схем размещения частиц по ячейкам»

ч Диссертация посвящена исследованию многоэтапной схемы размещения частиц по ячейкам. Эта схема является новой и обобщает классическую схему размещения частиц по ячейкам. В диссертации мы рассматриваем два крайних случая - двухэтапную схему и схему с бесконечным числом этапов. Мы начнем введение с описания предмета исследования. Далее будут описаны полученные в работе результаты, и проведено их сравнение с аналогичными результатами для классической схемы размещения частиц по ячейкам, а также с современными результатами для схожих задач.Диссертация состоит из введения, трех глав, списка обозначений и списка используемой литературы. Формулы, леммы и теоремы будут иметь номер, состоящий из двух чисел. Первое соответствует номеру главы, а второе - номеру формулы (леммы, теоремы) в данной главе. Теоремы из введения, доказанные в работах других авторов, будут нумероваться одним числом. Ссылки на работы других авторов нумеруются по алфавиту, согласно фамилии первого из них.Статьи, в которых излагаются результаты, полученные автором, выделены в отдельный список.Многоэтапные схемы размещения частиц по ячейкам В данной работе мы рассматриваем следующую модификацию известной одноэташюй схемы размещения частиц по ячейкам (см., например, [3]).В случае, когда распределения на всех этапах размещения являются равновероятными, мы будем говорить о равновероятной схеме размещения, в противном случае - о полиномиальной схеме размещения.Для первой и второй частей диссертации мы приведем и обсудим предельные теоремы из [3]. которые имеют отношение к нашей работе. Для третьей части диссертации мы укажем, какие результаты являются новыми, а какие воспроизводят известные результаты в схеме размещения с бесконечным числом этапов.Обзор результатов по главам.Первая глава состоит из двух параграфов. В первом из них исследуется равновероятная, во втором - полиномиальная схема двухэтапного размещения-, частиц. Полиномиальная схема является более общей; для равновероятной схемы сходимость к распределению Пуассона доказана в условиях, которые не следуют из аналогичной теоремы для полиномиальной схемы. В связи с этим результаты, относящиеся к равновероятному распределению, выделены в отдельный параграф. Отметим, что доказательства в этой главе получены при помощи метода моментов.Сравним этот результат с классической схемой размещения частиц, в которой количество слоев равно т = 1, то есть исходные NQ = п частиц размещаются по N\ = N ячейкам, а дальнейшие размещения не производятся.Следующая теорема устанавливает условия, при которых распределение [л, в классической схеме сходится к распределению Пуассона ([3], теорема 5, с. 65).Для классической равновероятной схемы размещения получены предельные распределения для всех областей изменения параметров, мы же получаем предельные распределения только для "левой" области (когда No/'N2 —> 0, NQ/NI < а2, Eyu; —* Л) и части "левой промежуточной" области (когда N0/N2 - 0, ал < iVo/TVi < а2, Е/4-2) -> оо).Для первого момента /лг получены явные асимптотические формулы с оценками остаточных членов.Наконец, при условиях теоремы 1.4 можно найти распределение максимального заполнения ячеек.Сравним результаты, полученные в теоремах 1.4 и 1.6, с классической схемой. В случае полиномиальной схемы размещения в [3] установлена следующая пуассоновская предельная теорема (1, с. 118). Пусть pt, % = 1,..., N - вероятность попадания в г-ю ячейку в одноэтапной схеме.Таким образом, теорема 1.4 аналогична теореме 2, а теорема 1.6 - теореме 3 с учетом того, что мы доказываем ее в полиномиальной схеме размещения.Отметим также тезис [1], в котором автор рассматривает аналогичную нашей схему размещения.Пусть ячейки первого уровня размещаются по ячейкам второго уровня в соответствии с равномерным распределением; обозначим через А0-г событие [/-я ячейка 1-го слоя попала в г-ю ячейку 2-го слоя]. После этого частицы распределяются по ячейкам второго уровня в соответствии со случайным вектором вероятностей -к таким, что 7гг- = X)j=i Ж^(АУ*')> здесь Х(А) индикатор события А. Полученное таким образом размещение аналогично равновероятной на обоих этапах двухэтапной схеме размещения.Вторая глава диссертации состоит из двух параграфов. Она посвящена доказательству центральной предельной теоремы в двухэтапной схеме размещения частиц, в которой частицы на первом этапе размещаются в соответствии с полиномиальным распределением р^), а на втором этапе - в соответствии с равновероятным распределением р^2^ = (^-,..., -^- J.В первом параграфе мы устанавливаем уточнение статьи [4], необходимое для доказательства предельной теоремы для двухэтапной схемы размещения частиц.Пусть п частиц независимо размещаются по счетному множеству ячеек / = {1,2,...}, причем для каждой частицы вероятность попадания в i-ю ячейку равна рг и J2 Рг — 1- Пусть также цт ц, (г?: р,, ? el)- число ячеек, содержащих iei после такого размещения ровно по г частиц.Теорема 2.1. Пусть г > \, а параметры схемы изменяются так, что п —» ОО; D —> 0. Тогда р{цг) < A\{r)D, A\{r) = const.Данный результат является уточнением теоремы 2.1 статьи [4], правая часть неравенства в котором имеет вид 0(D). Мы выражаем постоянную А\(г) через другие постоянные.Для применения результата статьи к двухэтапной схеме размещения необходимо остановиться на одном частном случае.Определение. Будем говорить, что схема серий независимых размещений частиц по ячейкам с параметрами n,pi,i £ I, принадлежит центральной области изменения параметров, если Vr > 1, Зпо = По(г) такое, что для любых п > щ, ао(г) < — < Ьо(г), п где 0 < ao(r) < bo(r) < со - функции от г.В центральной области при условии (1) выполнено Р2 < ^\, и оценка теоремы 2.5 принимает вид Р^)^ 1^712 • Таким образом, мы уточняем оценку скорости сходимости предельной теоремы для \ir в центральной области. В статье [4] оценка, аналогичная оценке 1 /1 о в теореме 2.5, получена в виде 0(Р2 ).Во втором параграфе, пользуясь полученными результатами, мы доказываем (2) центральную предельную теорему для нормированной случайной величины /if в двухэтапной схеме размещения.Интерпретируем двухэтапную схему размещения следующим образом.Пусть ячейки первого уровня размещаются по ячейкам второго уровня в соответствии с равномерным распределением; обозначим через Ajt событие fj-я ячейка 1-го слоя попала в г-ю ячейку 2-го слоя]. После этого частицы распределяются по ячейкам второго уровня в соответствии со случайным вектором вероятностей 7г таким, что щ = Y2j=\Vj X{Aji)-> здесь Х(А) индикатор события Л, р"-' - вероятности ячеек первого слоя.Считая г > 2 фиксированным, обозначим о2 — D/4- '. Введем расстояние р(/42)) = sup \Р(а-\№ - Е/42)) <х)- Ф(аО|, X где Ф(ж)-функция стандартного нормального распределения.Третья глава диссертации состоит из двух параграфов. В ней изучается схема размещения частиц, в которой число этапов бесконечно. Мы находим неоходимые и достаточные условия, при которых предельное распределение числа объединенных частиц сосредоточено в 1, а также распределение времени ожидания до момента объединения всех частиц в частном случае, когда количество ячеек в каждом слое одинаково и равно числу изначально размещаемых частиц.Рассматривается процесс размещения частиц по слоям ячеек следующего вида. На первом этапе Лго исходных частиц независимо и равновероятно размещаются по N\ ячейкам первого слоя. Частицы, попадающие в одну и ту же ячейку первого слоя, объединяются в одну новую частицу; при этом в первом слое получается случайное число ф\ объединенных частиц (равное числу ячеек первого слоя, занятых исходными частицами). В общем случае на (к + 1)-м этапе фк объединенных частиц, находящихся в iVfc ячейках к-то слоя, независимо (друг от друга и от предыстории) и равновероятно размещаются по Nk+i ячейкам (к + 1)-го слоя; частицы, попадающие в одну и ту же ячейку (& + 1)-го слоя, объединяются, в результате чего получается фк+г объединенных частиц в (к + 1)-м слое. При сделанных предположениях последовательность 0о, Фи • • • образует цепь Маркова с невозрастающими траекториями.В первом параграфе главы 3 мы доказываем следующую теорему: Теорема 3.1. Еслу N* = min Nu > 2, mo А->0 оо 1 Р { lim фк > г] > о & У] — < оо.Таким образом, для того, чтобы предельное распределение числа объединенных частиц было невырожденным, необходимо, чтобы размеры слоев росли достаточно быстро. Эта теорема является новой и не доказывалась в известных автору источниках.Во втором параграфе мы изучаем бесконечную схему, в которой размеры слоев одинаковы и совпадают с числом изначально размещаемых частиц, то есть NQ = N\ = N2 — ... = п.Бесконечная схема размещения, в которой m = 00 и частицы, попавшие в одну ячейку на любом этапе, считаются склеившимися в новую частицу, была впервые упомянута в статье [22] в терминах моделей популяционной генетики.Эта схема изучалась на протяжении долгого времени, и первые доказательства предельной теоремы для времени ожидания до объединения всех частиц, которую мы устанавливаем в третьей главе, были получены как частный случай в моделях математической генетики [15]. Следует отметить, что доказательство в этих работах было весьма сложным и использовало специальные схемы слабой сходимости случайных процессов к марковским цепям. В дальнейшем более простое доказательство было получено в относительно недавней работе [18], которая также использовала результаты других авторов [14]. Более общее доказательство для неравиовероятных размещений было установлено в неопубликованной статье [23]. В отличие от приведенных работ, доказательство диссертации является более простым и использует новые оценки для «хвостов» распределения числа непустых ячеек в классической схеме размещения частиц.В силу теоремы 3.1 с вероятностью 1 все п исходных частиц объединяются за конечное число этапов, т. е. первый момент тп, когда все частицы объединяются в одну, имеет собственное распределение. Мы приводим новое доказательство следующего результата, который, как обнаружилось после публикации работы [32], был известен.Ломоносова в 2003-2006 гг.В совместных работах вклад научного руководителя A.M. Зубкова состоял в постановке задач и выборе метода, а диссертанта - в поиске и разработке доказательств.Автор выражает глубокую благодарность научному руководителю, доктору физико-математических наук A.M. Зубкову за постоянное внимание к работе и ценные советы, а также профессору, доктору физико-математических наук В.А. Ватутину и доктору физико-математических наук В.Г. Михайлову за многочисленные обсуждения и важные замечания.

Список литературы диссертационного исследования кандидат физико-математических наук Шибанов, Олег Константинович, 2009 год

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

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

3. Колчин В. Ф., Севастьянов Б. А., Чистяков В. П. Случайные размещения. М., Наука, 1976.

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

5. Михайлов В.Г. Асимптотическая нормальность в схеме конечно-зависимого размещения частиц по ячейкам. — Математический сборник, 1982, т. 119(161), № 4(12), с. 509-520.

6. Михайлов В.Г. Некоторые оценки точности пуассоновской аппроксимации для суммы зависимых случайных индикаторов. — Обозр.прикл. и промышл. матем., 1994, вып. 4, т. 1

7. Петров В.В. Суммы независимых случайных величин. — М.: Наука, 1972.

8. Севастьянов Б.А. Предельный закон Пуассона в схеме сумм зависимых случайных величин. — Теория вероятностей и ее применения, 1972, т. XVII, вып. 4, с. 733-738.

9. Харди Г., Литтлвуд Дж., Полиа Г. Неравенства. — М., ИЛ, 1948.

10. Ширяев А.Н. Вероятность. В 2 кн. М.: МЦНМО, 2004, т. 1, §6.

11. Aldous D. Deterministic and Stochastic Models for Coalescence (Aggregation, Coagulation): a Review of Mean Field Theory for Probabilists. — Bernoulli, 1999, vol. 5, pp. 3-48.

12. Barbour A.D., Chen L.H.Y. An introduction to Stein's method. — World Scientific, 2005.

13. Barbour A.D., Hoist L, Janson S. Poisson Approximation. — Oxford University Press, 2002

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

15. 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.

16. Dutko M. Central limit theorems for infinite urn models. — The Annals of Probability, 1989, vol. 17, no.3, pp. 1255-1263.

17. Gnedin A., Hansen B. and Pitman J. Notes on the occupancy problem with infinitely many boxes: general asymptotics and power laws. — Probability Surveys, 2007, vol. 4, pp. 146-171.

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

19. Karlin S. Central limit theorems for ceHain infinite urn schemes. — Journal of Mathematics and Mechanics, 1967, vol. 17, pp. 373-401.

20. Kingman J.F. Exchangeability and the evolution of large populations. — Exchangeability in probability and statistics, North-Holland, Amsterdam-New York, 1982, pp. 97- 112.

21. Kingman J.F. On the genealogy of large populations. — Journal of Applied Probability, 1982, vol. 19A, pp. 27-43.

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

23. McSweeney J.K., Pittel B.G. Expected coalescence time for a nonuniform allocation process. — preprint, September 2008.

24. Mohle M. Robvstness results for the coalescent. — J. Appl. Prob., 1998, vol. 35, pp. 438^47.

25. Mohle M. The time back to the most recent common ancestor in exchangeable population models. — Adv. Appl. Prob., 2004, vol. 36, pp. 78-97.

26. Mohle M., Sagitov S. A classification of coalescent processes for haploid exchangeable population models. — Ann. Prob., vol. 29, pp. 1547-1562.

27. S.Tavare Line-of-descent and genealogical processes and their applications in population genetics models. — Theoretical Population Biology, 1984, vol. 26, pp. 119-164.Работы автора по теме диссертации

28. Зубков A.M., Шибанов O.K. Многоступенчатые схе,мы размещения частиц по ячейкам. — Обозр. прикл. и промышл. матем., 2002, т. 9, вып. 1, с. 115-116.

29. Зубков A.M., Шибанов O.K. Двухступенчатая схема размещения частиц по ячейкам. — Обозр. прикл. и промышл. матем., 2002, т. 9, вып. 2, с. 378-379.

30. Зубков A.M., Шибанов O.K. Пуассоновская предельная теорема для двухэтапной равновероятной схемы размещения частиц по ячейкам. — Дискретная математика, 2006, т. 18, вып. 4, с. 99-104.

31. Зубков A.M., Шибанов O.K. Пуассоновская предельная теорема для двухэтапной полиномиальной схемы, размещения частиц по ячейкам — Обозр. прикл. и промышл. матем., 2007, т. 14, вып. 3, с.422-434.

32. Зубков A.M., Шибанов O.K. Время до объединения всех частиц при равновероятных размещениях по последовательности слоев ячеек. — Математические заметки, 2009, т. 85, вып. 3, с. 373-381.

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