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

00347ЭЭ21

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

На правах рукописи УДК 519.212.2, 519.214.5

Шибанов Олег Константинович

ПРЕДЕЛЬНЫЕ ТЕОРЕМЫ ДЛЯ МНОГОЭТАПНЫХ СХЕМ РАЗМЕЩЕНИЯ ЧАСТИЦ ПО ЯЧЕЙКАМ

01.01.05 — Теория вероятностей и математическая статистика

АВТОРЕФЕРАТ

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

1 5 0К

"ч Т.

Москва 2009

003479925

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

Научный руководитель:

Официальные оппоненты:

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

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

Ивченко Григорий Иванович.

Ведущая организация:

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

Белорусский Государственный Университет.

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

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

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

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

профессор И.Н. Сергеев

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

Актуальность темы

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

Классическая теорема Пуассона для схемы испытаний Бернулли 1 является примером применения аппроксимаций к суммам случайных индикаторов. Следует отметить, что эта теорема применима только к суммам независимых одинаково распределенных индикаторов, в то время как в большинстве практических задач участвуют суммы зависимых индикаторов, зачастую с разными распределениями. В таких случаях требуется применять иные методы пуассоновской аппроксимации, к примеру, предложенные в работах Б.А. Севастьянова 2, A.M. Зубкова 3, В.Г. Михайлова 4 или часто используемый в последнее время метод Чена-Стейна 5 е.

Одной из первых задач для сумм зависимых случайных индикаторов, полностью исследованной во всех областях изменения параметров, является классическая задача о размещении частиц по ячейкам. Пусть п частиц размещаются по N ячейкам независимо и равновероятно. Обозначим через ßr = ßr(n,N) число ячеек, содержа-

'См., например, Ширяев А.Н. Вероятность. В 2 кн. — М.: МЦНМО, 2004, т. 1, §G.

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

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

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

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

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

6Barbour A.D., Holst L, Jaiison S. Poisson Approximation. —- Oxford University Press, 2002

щих в точности V частиц. В зависимости от взаимного поведения п, N выделяются области, в которых предельное распределение )ir является распределением Пуассона или нормальным распределением

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

Будем считать, что множество ячеек разделено на слои и в j-м слое содержится Nj ячеек. На первом этапе No исходных частиц независимо размещаются по Ni ячейкам первого слоя в соответствии с распределением р'1' = На

втором этапе Ni ячеек первого слоя рассматриваются как частицы, и они независимо размещаются по N2 ячейкам второго слоя вместе с попавшими в них исходными частицами в соответствии с распределением р(2' = ••■iP/v])- Размещения

продолжаются аналогично т раз, то есть на последнем этапе ячейки (т— 1)-го слоя размещаются по ячейкам ш-го слоя. Такую схему размещения естественно называть m-этапной. Будем через firn\Na,Ni,..., Nm, р*1',..., р^) = обозначать число ячеек m-го слоя, в которые попало ровно г исходных частиц.

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

Пусть ячейки первого уровня размещаются по ячейкам второго уровня в соответствии с равномерным распределением; обозначим через Aj¡ событие jj-я ячейка 1-го слоя попала в i-ю ячейку 2-го слоя]. После этого частицы распределяются по ячейкам второго слоя в соответствии со случайным вектором вероятностей тг таким, что 7Г¿ = TT¡X(Aji), здесь Х(А) - индикатор события А. Полученное таким

образом размещение аналогично равновероятной на обоих этапах двухэтапной схеме размещения.

Для различных целых неотрицательных чисел п,..., г„ обозначим г = (п,..., г,),

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

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

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

и пусть х = (xi, ...,xs), а хк = х*'...х*". Введем производящую функцию k>0,m,n>0 Ь

В тсзисс 9 показапо, что

,п .__

- »Ъ Е

у"1т

'■'¿Го m!

№

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

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

11 cm., iianpiiwep, 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.

i2GoU W.M.Y., Hitczenko P., Schinutz E. Iterating random functions on a finite set. — preprint, 2006.

13Dalal A., Schinutz E. Compositions of random functions on a finite set. — Electronic Journal of Combinatorics, 2002, vol. 9, R2G.

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

preprint, September 2008.

Цель работы

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

Научная новизна

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

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

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

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

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

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

Методы исследования

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

Теоретическая и практическая ценность

Диссертация имеет теоретический характер. Полученные результаты могут быть использованы в математических моделях биологии и анализе алгоритмов. Разработанные в диссертации методы могут быть полезны специалистам МГУ им. М.В. Ломоносова и Математического института им. В.А. Стсклова.

Апробация работы

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

Публикации

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

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

Структура диссертации

Диссертация состоит из оглавления, введения, трех глав и списка литературы, насчитывающего 33 наименования. Общий объем диссертации - 96 страниц.

Краткое содержание диссертации

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

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

В случае равновероятной схемы векторы вероятностей на обоих этапах состоят из одинаковых чисел: р(5) = (7^, •••,7^), Р{2) = •

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

Теорема 1. Если в равновероятной двухэтапной схеме размещения частиц г > 1 фиксировано, N0, N1, N2 оо так, что Л^о = о(Л'г), Л*о = 0{Ы\) и

Е/42) А € (0, оо),

т.о

Р(/Д2) =к)-*~ е~\ к = 0,1,...

Для первого момента /¿}. получены явные асимптотические формулы с оценками остаточных членов.

Лемма 1. В равновероятной двухэтапной схеме при любом г > 2

„ (2) Щ Д ^ /м 1 п

ЕдГ =-2-ге «11+0^ + — + —

г.'Л^ V ^о Щ;

если N0 -> оо, N0 = 0(ЛГ1), N1 = О{N2), а если N0 -* оо, N0 = о^нп^ьЛ^}), N2 =

0(ЛГ1), тпо

£ц(2) . Щ Л , о , 1 , Ъ

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

Обозначим через р^ = тах^'1',..., Pw'), р^ = max(pf\ ...,

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

Теорема 2. Если параметры двухступенчатой схемы размещения изменяются так, что min (лг0, iV11_lr/2r') р!1' -> 0, min(Aro, Nijp^ -> О, Е/^2) —> Л € (0,оо), то

Р к = 0,1,...

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

Теорема 3. При любых целых l,m > 1, I + m < Nq, справедливы неравенства

м-(,!»)'

В частности, если l,m > 1 фиксированы, а iniri ^А'о, ./Vj1-'™11''''"" ^pi1' —► 0, то

Е/Ч+m = о(ЕщЩ1т).

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

Теорема 4. Если параметры двухступенчатой схемы размещения изменяются так, что min (ЛГ0, ЛГ11~[,'/2Г') 0, min(JV0) Nx)p^] 0, Е/42) —» Л е (0, оо), то

P(max{j : fif ] > 0} = г) -» 1 - e~\ P(max{j : ßf} > 0} = г - 1) -» е~А.

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

распределенном а на втором этапе - в соответствии с равновероятным распре-

,(2) :

(т^'-.тс)-

делением р

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

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

(2)

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

Интерпретируем двухэтапную схему размещения следующим образом. Пусть ячейки первого уровня размещаются по ячейкам второго уровня в соответствии с равномерным распределением; обозначим через Ар событие [j-я ячейка 1-го слоя попала в г-ю ячейку 2-го слоя]. После этого частицы распределяются по ячейкам второго уровня в соответствии со случайным вектором вероятностей тг таким, что щ = ^flipf^XlAji), здесь Х(Л) - индикатор события А, р^ - вероятности ячеек первого слоя.

Считая г > 2 фиксированным, обозначим а2 = D/42'. Введем расстояние

р(/<<2)) = sup |P(a-Vr2) - Е/42)) <х)~ Ф(®)|,

х

где Ф(ж)-функция стандартного нормального распределения.

Обозначим через jj!1' = maxfpj1',

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

Теорема 6. Пусть I - фиксированное, натуральное число, Cq,/3, аь«2 -некоторые постоянные и в схеме серий Nq,N\,N2 —» оо, pi1' —♦ 0 так, что

Тогда

vo

Из теоремы 6 следует

^ С0 > 0, JVopi1' </?<«>,

TVо (2}

О < «1 < — < «2 < ОО, Е/4 —> 00. Ni

p(/42)) = o(i^,a = mi„ (1,1).

Теорема 7. Пусть I - фиксированное натуральное, число, Со, /'?, аьаг -некоторые постоянные и в схеме серий No, Ni, N2 —> 00, pí'' —> 0 так, что

--• С0 > 0, iVopí1' < /5 < 00,

п Nn «I

О < 01 < — < «2 < 00, E/i). ' -> 00.

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

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

Рассматривается процесс размещения частиц по слоям ячеек следующего вида. На первом этапе Лго исходных частиц независимо и равновероятно размещаются по ЛГ1 ячейкам первого слоя. Частицы, попадающие в одну и ту же ячейку первого моя, объединяются в одну новую частицу; при этом в первом слое получается случайное число tpi объединенных частиц (равное числу ячеек первого слоя, занятых исходными частицами). В общем случае на (к + 1)-м этапе -фк объединенных частиц, находящихся в N¡¿ ячейках к-го слоя, независимо (друг от друга и от предыстории) и равновероятно размещаются по N¡¡+1 ячейкам (к + 1)-го слоя; частицы, попадающие в одну и ту же ячейку (к + 1)-го слоя, объединяются, в результате чего получается Фь+l объединенных частиц в (к + 1)-м слое. При сделанных предположениях последовательность фо, ... образует цепь Маркова с нсвозрастающими траекториями.

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

Теорема 8. Если N* = uúnNk >2, то к>0

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

Теорема 9. При п —< оо распределения случайных величин Qt = ^ сходятся к распределению суммы £ = > случайные величины £1, £2, • • • независимы и

Р<х) = 1- > О, j = 1,2,...

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

Здесь r/j - «время перехода» от j + 1 объединенных частиц к j объединенным частицам, причем

Ьц > 0} = {miu(f: il>t < j) > min(t : у'н <j + 1)} = {vVo+l) =3 + !}■

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

Лемма 2. Если к < п, тпо

Р{% = о}< к2

3(п - к) '

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

Лемма 3. Если к < т < п, то

Р{/1!(т, п) < к} Р{Щ(т,п) = к} к2

P{/Zi(m, 11) <к+ 1} - Р{Щ(т,п) = А; + 1} _ 3(п-к)

Автор выражает глубокую благодарность научному руководителю, доктору физико-математических наук A.M. Зубкову за постоянное внимание к работе и ценные советы, а также профессору, доктору физико-математических наук В.А. Ватутину и доктору физико-математических наук В.Г. Михайлову за многочисленные обсуждения и важные замечания.

Работы автора по теме диссертации

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

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

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

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

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

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

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

Для заметок

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

Глава 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. Зубкову за постоянное внимание к работе и ценные советы, а также профессору, доктору физико-математических наук В.А. Ватутину и доктору физико-математических наук В.Г. Михайлову за многочисленные обсуждения и важные замечания.

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.