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

ч Диссертация посвящена исследованию многоэтапной схемы размещения частиц по ячейкам. Эта схема является новой и обобщает классическую схему размещения частиц по ячейкам. В диссертации мы рассматриваем два крайних случая — двухэтапную схему и схему с бесконечным числом этапов. Мы начнем введение с описания предмета исследования. Далее будут описаны полученные в работе результаты, и проведено их сравнение с аналогичными результатами для классической схемы размещения частиц по ячейкам, а также с современными результатами для схожих задач. Диссертация состоит из введения, трех глав, списка обозначений и списка используемой литературы. Формулы, леммы и теоремы будут иметь номер, состоящий из двух чисел. Первое соответствует номеру главы, а второе — номеру формулы (леммы, теоремы) в данной главе. Теоремы из введения, доказанные в работах других авторов, будут нумероваться одним числом. Ссылки на работы других авторов нумеруются по алфавиту, согласно фамилии первого из них. Статьи, в которых излагаются результаты, полученные автором, выделены в отдельный список. Многоэтапные схемы размещения частиц по ячейкам В данной работе мы рассматриваем следующую модификацию известной одноэташюй схемы размещения частиц по ячейкам (см., например, [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 Ж^(АУ*')> здесь Х (А) индикатор события А. Полученное таким образом размещение аналогично равновероятной на обоих этапах двухэтапной схеме размещения. Вторая глава диссертации состоит из двух параграфов. Она посвящена доказательству центральной предельной теоремы в двухэтапной схеме размещения частиц, в которой частицы на первом этапе размещаются в соответствии с полиномиальным распределением р^), а на втором этапе — в соответствии с равновероятным распределением р²^ = (^-,…, -^- 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® < bo® < со — функции от г. В центральной области при условии (1) выполнено Р2 <^, и оценка теоремы 2.5 принимает вид Р^)^ 1⁷¹² • Таким образом, мы уточняем оценку скорости сходимости предельной теоремы для 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. Зубкову за постоянное внимание к работе и ценные советы, а также профессору, доктору физико-математических наук В. А. Ватутину и доктору физико-математических наук В. Г. Михайлову за многочисленные обсуждения и важные замечания.

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⁴⁷.

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.