За последние шестьдесят лет в исследованиях по теории вероятностей заметное место занимают вероятностные задачи комбинаторного характера. Одним из интенсивно развивающихся направлений таких исследований является изучение различных схем размещения частиц по ячейкам (см., например, [4.1]).
В настоящей работе рассматривается равновероятная схема размещения частиц комплектами: п комплектов по частиц (размеры комплектов являются независимыми копиями целочисленной случайной величины принимающей значения от I до Г) независимо друг от друга (Ь<�Ы) размещаются в N ячейках, частицы одного комплекта размещаются в ячейках по одной, причем все возможных размещений частиц ]-го комплекта равновероятны. Обозначим /7, — число частиц в ячейке с номером после размещения п комплектов частиц. Располагая в неубывающем порядке величины т]&bdquo-, построим их вариационный ряд т](1) <. < т]т.
Диссертация посвящена изучению предельного распределения крайних членов вариационного ряда т](Мт+1) и т](т) для любого фиксированного целого т > 1 при и, N-«00, аПпИ-ьх, 0 < я: < от,-» р, 0<р< —, где а- ^ среднее число частиц в ячейке, при выполнении для любого целого неотрицательного к дополнительного условия следующего вида на концентрацию распределения размера комплекта:
Щ)к (Е?)к N где (а)к = а{а — 1).(а — к +1).
При Р{% = 1} = 1 изучаемая схема представляет собой равновероятную схему размещения частиц по ячейкам, за которой утвердилось название классической [4.2].
Изучение вариационного ряда в классической схеме начато.
И.И.Викторовой и Б. А. Севастьяновым [5.1] и [5.2], а подробное исследование всех членов вариационного ряда в этой же схеме в случае, когда п/Ы1пЫ стремится к постоянной величине, проведено Г. И. Ивченко [5.5]. В этих работах исследование вариационного ряда сводится к изучению методом моментов асимптотического поведения случайных величин.
МГ+, (и, #)+. +//"(/!,#), где цк (и, АО — число ячеек, содержащих ровно к частиц, к= 0,1,. ., г.
В.Ф.Колчиным [5.10] для изучения классической схемы размещения частиц, и в том числе для изучения членов вариационного ряда, предложен другой подход, опирающийся на представление полиномиального распределения заполнении ячеек 77,77^ в виде условного распределения распределённых по закону Пуассона независимых случайных величин при условии, что их сумма равна п.
Поведение членов вариационного ряда в равновероятной схеме размещения частиц комплектами при п, Ыда и фиксированном размере комплектов изучено Е. Р. Хакимуллиным [5.19], при фиксированном п оно изучено С. Ю. Теребулиным [5.17].
Схема со случайным размером комплектов рассматривалась ранее Г. И. Ивченко [5.9], Т. М. Селке [5.28], Е. Р. Хакимуллиным и Н. Ю. Энатской [5.21]. В этих работах изучались характеристики, связанные со временем ожидания до заполнения всех или почти всех ячеек.
Многие характеристики в равновероятной схеме размещения частиц комплектами случайной длииы могут быть интерпретированы в терминах случайных гиперграфов с кратными гранями. Гиперграфом называется система.
Г = {Аг-А,., Ат}, где Хконечное множество, элементы которого называются вершинами, А] -подмножества X, называемые гранямикаждое А. содержит не менее двух вершин, у=1,., т. Говорят, что через вершину хеХ проходит грань Л], если хеЛг Число граней, проходящих через вершину х, называется степенью или кратностью вершины х.
Если число вершин в каждой грани равно s, то гиперграф называется sграфом, 2 — графы — это обычные графы.
Рассматриваемой в диссертации схеме размещения частиц комплектами соответствуют случайные s — графы с кратными гранями без петель. В дипломной работе изучается вариационный ряд степеней вершин таких sграфов. Обычно изучаются гиперграфы без кратных граней. Некоторые вопроса строения вариационного ряда степеней вершин обычных графов рассмотрены в статьях А. Эрдеша, и А. Реньи [5.24], [5.25], В. Е. Степанова [5.16], Г. И. Ивченко [5.7], H.H. Нурмеева [5.13], Е. Р. Хакимуллина [5.18].
Для изучения характеристик классической схемы размещения частиц применялись различные асимптотические методы теории вероятностей: метод моментов, метод перевала, метод сведения к суммам независимых случайных величин, метод оценки нулей производящей функции и другие. Многие из этих методов опираются на наличие простых выражений для производящих функций изучаемых характеристик. Для схемы размещения частиц комплектами отсутствие простых выражений для производящих функций ограничивает возможность применения перечисленных методов. В схеме размещения частиц комплектами нашли применений лишь метод моментов и метод «сопровождающих схем», предложенный Б. А. Севастьяновым. [5.14].
В диссертации распределение крайних членов вариационного ряда изучается методом моментов, при этом для исследования факториальных моментов приходится оценивать вероятности больших уклонении для суммы независимых векторов, компоненты которых принимают значения 0 и 1.
Обозначим — случайные величины, равные числу ячеек с более чем г частицами и не более чем г частицами соответственно.
В силу соотношений рг]{т)<�г)=р%>т основным при исследовании асимптотического поведения крайних членов вариационного ряда являются утверждения о сходимости распределений к распределению Пуассона при различных соотношениях между параметрами исследуемой схемы. Основное отличие от используемых ранее приемов при исследовании факториальных моментов заключается в использовании интегрального представления для этих моментов через производящую функцию совместного распределения .).
Производящая функция совместного распределения (//, .т]и) используется для оценки факториального момента порядка к и при изучении равновероятной схемы размещения частиц комплектами применяется в диссертации Хакимуллина Е. Р. [5.20].
Распределение случайных величин т](1).т](Ы) в схеме размещения частиц комплектами зависит от параметров схемы: числа ячеек >1, числа комплектов п и размера каждого комплекта .
Приведем таблицу, исчерпывающе описывающую поведения параметров.
Для максимальных членов.
Поведение параметра аПпЫ Поведение параметра 1N и номер теоремы, соответствующий данному случаю а! пИ -> оо Nр, 0< р<!2 Теорема 1.1 а —> X 0 Е?! И р, 0<�р< ½ х > -р/ 1п р х = —р Ни. р х<-р!Ъ.р
Теорема 1.2 Теорема 1.3 Теорема 1.4 Теорема 1.5 а ->0 р, 0 < р <½.
Теорема 1.6 Теорема 1.7.
Для минимальных членов а/ЫЫ -> оо р, 0<�р</2 Теорема 2.1 а Е%! N 0 р, 0<�р
—> X х > 1 Теорема 2.2 х = 1 Теорема 2.6 х < 1 Теорема2.7 х > —р / 1п (1 — р) Теорема 2.3 х = —р / 1п (1 — р) Теорема 2.4 х < —/ 1п (1 — р) Теорема 2.5.
Для каждого случая поведения параметров в таблице указана теорема, описывающая поведение членов вариационного ряда. При этом первый индекс в номере теоремы обозначает номер главы, а второй — номер теоремы, доказанной в этой главе, для указываемого случая соотношения между параметрами схемы.
В первой главе исследуются предельные распределения максимальных членов т]{Кт+Х) вариационного ряда, т>- фиксированное целое число. Для удобства дальнейшего изложения и сравнения полученных результатов с известными, приведем соответствующие теоремы, полученные в классической схеме (Р{% = 1} = 1). Обозначим.
Лк к а=—-, N.
— среднее число частиц в ячейке.
Предельное поведение 7(ЛГт+^ в классической схеме описывается следующими тремя теоремами.
Теорема 0.1. Если п, Ы, а/ 1пЫ-> со, то для любого фиксированного г.
Щы-т+1) -а-сш{а '(ln7V-2 1 lnlniv)).
4″ S z т-1. .
->2>*И к=0 а/гХпЫ 2 где и (м>) — положительная функция, заданная в интервале 0<�м><�оо уравнениемм + (1 + м)1п (1 + м) = ж (3).
Теорема 0.2. Если ->со, а1пЫ->х, и последовательность г = г{а, И) выбрана так, что г > а, Ы7гг{а) -" Л, где Л, хположительная постоянная, то.
— г.
1=0 i (л7.
1 -г где клюбое фиксированное целое число и / корень уравнения у+х (Ыу — у + 1) = 0 (4) в интервале 0 < у < 1.
Теорема 0.3. Если n, N->co, a/lnN->0, и последовательность г = r (a, N) выбрана так, что г > a, Nnr (а) -" Л, где Л — положительная постоянная, то к=О к=0 1 т~1 ='¦}-> 1−2>*(4.
Как и в классической схеме, в схеме размещения частиц комплектами вид предельного распределения максимальных членов зависит от поведения параметра а/пЫ.
Если а/ ->оо, то при соответствующей нормировке и центрировке максимальные члены вариационного ряда имеют в пределе распределения, обладающие плотностью дважды экспоненциального типа (теорема 1.1.).
Если а/пЫ->х, х>0, то предельное распределение т]{Ыт+Х) сосредоточено в счетном числе точек и разброс этого распределения растет с ростом х. При этом в случае N^ р, 0< р</2 на параметр х накладывается дополнительное ограничение х>-р/пр. Этому случаю соответствуют теоремы 1.2 и 1.3.
В случаях распределение т](Ыт+1) сосредоточено асимптотически в одной или двух точках. Этим случаям соответствуют теоремы 1.4.-1.7.
Следующие 7 теорем доказаны в главе I и описывают предельные распределения максимальных членов в схеме размещения частиц комплектами. Обозначим.
Теорема 1.1. Если п, Ы, а/пЫ -^оо, Е^/И р, 0 < < ½, выполнено условие (*), то для любого фиксированного х.
— а-оси а.
— 1.
1пЛГ-2-' 1п 1п7/),——.
-—+ ->2>Де Ь.
— 2- 2пЫ к=0 где и (м>, а) — положительная функция, задаваемая в интервале 0<�м><�оо уравнением.
1 + и)1п (1 + и)+—(1-аы)1п (1-аи) = у>, а > 0, иа < 1. (5) а.
Теорема 1.2. Пусть п, Ы -" со, а! пЫ -> х, Е^/Ы 0, выполнено условие (*) и последовательность г = г (а, Ы) выбрана так, что г>а, Ш> г, п, а N.
->Л, где Л, х — положительные постоянные. Тогда для любого фиксированного целого к = 0,±1,±2.,.
— т-1 / ук+1.
1−0 V, А — / где у корень уравнения (4) в интервале 0 < у < 1.
Теорема 1.3. Пусть п, Ы -«со, а! пЫ -> х, Е%/Ы р, выполнено условие (*) и последовательность г = г (а, Ы) выбрана так, что где Л, х, р — положительные постоянные 0 </><½, х>-р/пр. Тогда для любого фиксированного целого к = 0,±1,±2.,.
6).
0, -pyi-p где р корень уравнения рр + х{рпр-{р-р)ъ{р-р)-{р-р)п{-р)) = 0 в интервале р<�Р< 1.
Теорема 1.4. Пусть п, Ы -> со, а! пЫ -" х, Е%/Ы ->, выполнено условие (*) и последовательность г = г (а, И) выбрана так, что г>а, т (г, п,^-)->Л, где Л, х, рположительные постоянные 0<р</2, х = -р/пр. Тогда m-1 k=0 П-> 1 — £к к Mk=0.
Теорема 1.5. Пусть п, И -" оо, а/1п7/ N р, выполнено условие (*) и последовательность г = г (а, И) выбрана так, что r>a, Nb г, п,-{ N где Л, х, р — положительные постоянные 0<р< ½, х< —/?/1п/>. Тогда для любого фиксированного т > 1 ](Ы.т+1) = «}-> 1.
Теорема 1.6. Пусть -> оо, а/1п^У -" -> 0, выполнено условие (*) и последовательность г = г{а, Щ выбрана так, что.
Г ЕВЛ { N.
-> Л, где Л положительная постоянная. Тогда т-1.
П"7(*-&bdquo-+1) = г — Ц -> пк (Л), к=О к=О.
Теорема 1.7. Пусть ->оо, а/1пМ р, 0<р<½, выполнено условие (*). Тогда для любого фиксированного т > 1 Р{т]^.т+1) = и} —> 1.
В классической схеме распределение минимальных членов описывается следующими четырьмя теоремами.
Теорема 0.4. Если -" аз, а! пИ -«со, то для любого фиксированного г w)-„-m{“» 1(ln^-2−1lnlniv)) 1п4лг <" т-1 к=0 т-1. .
V"/21n7V 2 где v (w) — отрицательная функция на отрезке 0 < w < 1 задаваемая уравнением.
— v + (l + v) ln (l + v) = w. Теорема 0.5. Если n, N co, a/nN х>1 последовательность г = r (a, N) выбрана так, что г < у < со.Теорема 0.6. Если п, Ы-«оо, а/1п// ->1 и последовательность г = г (а, Ы) выбрана так, что г <�а, Мяг (а)-> Л где Я — положительная постоянная, то.
Во второй главе исследуются предельные распределения минимальных членов вариационного ряда в равновероятной схеме размещения частиц комплектами. Как и в классической схеме, в схеме размещения частиц комплектами вид предельного распределения зависит от поведения параметра а/пЫ. Минимальные члены г](т) ведут себя аналогично максимальным.
77(ла-ш+1) пРи фиксированном т. Если alnN -><х>, то при соответствующей центрировке и нормировке минимальные члены вариационного ряда имеют в пределе распределения, обладающие плотностью дважды экспоненциального типа.
Если а! Ъ. Ы -«х, то при 0 критическим для г]{т) является значениелс=1, а при р, 0<�р <½, я: = -р/1п (1-/?).
Если х>1,Е%/N 0,(х> -р/Ы (1- р), Е?/И р, 0< р<½), то распределение т](т) сосредоточено в счетном числе точек (теоремы 2.2,2.3).
Если ININ -" р, 0 < <½), то при х<1,(х<-р/Ы (1-р)) предельные распределения сосредоточены в одной или двух точках. Эти случаи описываются теоремами 2.4 — 2.7.
Сформулируем доказанные во второй главе теоремы, описывающие т-1.
4=0 т-1.
Теорема 0.7. Если п, Ы -><�х>, Ые, а ->оо, то Рр{т) =о}-«1. предельные распределения минимальных членов т](т) вариационного ряда в равновероятной схеме размещения частиц комплектами.
Теорема 2.1. Если п, И, а!пЫ->со, Е%/N ^ р, 0<р</2, выполнено условие (*), то для любого фиксированного г щт)-а-ау (рр Л.
1п4/г -2 ^ -> т~ 1.. 0 где (уе, а) — отрицательная функция, задаваемая на отрезке 0<м><1 уравнением.
1 + у)1п (1 + у)+—(1-ау)1п (1-ау) = м>, а > 0,|у|а <1. а.
Теорема 2.2 Пусть и,^-«оо, а/1п]У->0, выполнено условие (*) и последовательность г = г (а, Ы) выбрана так, что г < а, Щ г, п, N где Л х — положительные постоянные: х>1. Тогда для любого фиксированного целого к, 0 Г.
X У-К где у корень уравнения (4) в интервале 1 < у < со.
Теорема 2.3. Пусть п, Ы со, а/ЫЫ -> х, Е^/N -> р, выполнено условие (*) и последовательность г = г (а, Ы) выбрана так, что г <�а, ИЬ г, п, К N где А, р, х — положительные постоянные: Ос/? <½, х> -р/п (1-р). Тогда для любого фиксированного целого к,.
1=0 1рр (р -'VI.
1 р -1 1" — -р) где ркорень уравнения (6) в интервале 1 </3 <со.
Теорема 2.4. Пусть п, Ы -> оо, а1пИ -> х, Е%/И -> р, выполнено условие (*) и.
13 последовательность г = r (a, N) выбрана так, что.
-«А,.
Ер г < а, Ш г, п, N. где Я, х, р — положительные постоянные 0< р< ½, х = -р! 1п (1 — р). Тогда.
0 о.
Теорема 2.5. Пусть и, ЛГ -" оо, а/пЫ х, Е%/N р, выполнено условие (*) и последовательность г = г (а, Ы) выбрана так, что ' Е? г.
-> A, где А, х, р — положительные постоянные 0 < р <½, х<-р! 1п (1 -р)Тогда для любого фиксированного т > 1: Р{щт) = о}-> 1.
Теорема 2.6. Пусть и,]У-«оо, а/1п.М-"1,??///-"0, выполнено условие (*) и последовательность г = г (а, Ы) выбрана так, что.
N) г.
Теорема 2.7. Пусть n, N -> со, a/nNx<, EÇ-/N ->0, выполнено условие (*). Тогда для любого фиксированного m > 1 Р{т](т) = о} -> 1.
Как показано в заключении, при EC = o (N/nN), a/lnN>c>0 и выполнено условие (*), не только параметры предельных распределений, указанных в теоремах 1.1−1.2 и 2.1- 2.2, но нормирующие и центрирующие последовательности совпадают с соответствующими нормирующими и центрирующими последовательностями, указанными в теоремах 0.1, 0.2, 0.3, 0.5. То есть, при EC = o (N/nN), a/nN>c>0 предельные распределения крайних членов вариационного ряда в схеме размещения частиц комплектами зависят от величины комплекта только через параметр, а = пЕ%1Ы и совпадают с соответствующими предельными распределениями для соответствующих крайних членов в классической схеме, если число размещаемых частиц в этой схеме совпадает с целой частью ЕЕ,.
Внутри каждой главы нумерация соотношений сквозная. Например, на соотношение (2) из главы I мы будем ссылаться как на соотношение (2) в главе I и как на соотношение (1.2) в другой главе. Аналогично на лемму I в главе I мы ссылаемся как на лемму I и как на лемму 1.1 в другой главе.
ЗАКЛЮЧЕНИЕ
.
Проанализируем результаты, полученные в главах I и И, сравнив их с ранее известными для классической схемы [5.6, 5.10] и схемы размещения частиц комплектами фиксированной длины [5.20].
Заметим, что величина г удовлетворяет соотношению (1.5), представляет собой квантиль уровня 1 + о биномиального распределения с параметрами (п, Е%1К).
Разность таких квантилей биномиального распределения с параметрами пЕЕ п, Е%1Ы) и распределение Пуасона с параметрами есть.
ЕЕ I.
0{—ыапИ) (см. 5.8]). Поэтому при Е% = о (И ИпИ) в качестве N последовательности г можно взять последовательность квантилей тт пЕ% распределения Пуасона с параметрами, а =, которая определяется из соотношения г = а + <�хи (а4 (1п N- 2−11п 1п Щ + 4а1шЙ{х — 1п 44п + о (1)), где и (м>) — неотрицательная функция, задаваемая в интервале 0<�м><�а> уравнением.
— м + (1 + «)1п (1 + и) = н'. (1).
Величина г удовлетворяет соотношению г = пЫ — 2~11п 1п N, а + см.
I «а.
Ы-ЕV 2пЫ е’х (представляет собой квантиль уровня ~дГ + ° х — 1п + о (1) т 4 'г I биномиального N распределения с параметрами (п, Е%/Ы).
Разность таких квантилей биномиального распределения с параметрами пЕЕ п, Е%/Ы) и распределение Пуасона с параметрами «= —есть.
ОР^л/аЬгТУ) (см. 5.8]). Поэтому при = о (И ИпЫ) в качестве N последовательности г можно взять последовательность квантилей распределения Пуасона с параметрами а=——¦> которая определяется из соотношения г = а + ш (ах (1п N- 2″ 11п 1п #)) + V"/ 21пЫ (х — 1п 44л + о (1)), где и (м>) — неотрицательная функция, задаваемая в интервале 0<1 уравнением (1).
Таким образом, в условиях теоремы 1.1 и 1.2 асимптотическое поведение крайних членов вариационного ряда при = о (Ы/ 1пЫ) зависит от ЕЕ, только пЕЕ через параметр и, следовательно, при ЕЕ, = о (Ы/1пЫ) предельное распределение крайних членов вариационного ряда в схеме размещения частиц комплектами случайной длины? совпадают с предельными распределениями соответствующих крайних членов вариационного ряда в классической схеме, если число размещаемых частиц в этой схеме совпадает с целой частью ЕЕ,.
Если а/ЫИ -> х, Е? = о (Ы/1пЛГ), то как нетрудно показать (см., например,[5.8]), равномерно по к=0,1,.
Ъ (к, п, Е$ 1Ы) = як (а)(1 + о (1)), к < а.
Поэтому в условиях теоремы 2.3 совпадают не только предельные распределения минимальных членов в схеме размещения частиц комплектами и классической схеме, но и центрирующие последовательности, если число размещаемых частиц в этой схеме совпадает с целой частью ЕЕ,.
В условиях теорем 2.1, 2.2 при Е% = о (Ы!пЫ) нетрудно показать, что аналогичное утверждение справедливо и для максимальных членов вариационного ряда в схеме размещения частиц комплектами случайной длины ?
Таким образом, при Е^ =о (7У/1п7У), а/1пЛГ>с>0 и выполнении условия (*), не только параметры предельных распределений, указанных в теоремах 1.1 — 1.3 и 2.1 — 2.3, но нормирующие и центрирующие последовательности совпадают с соответствующими нормирующими и центрирующими последовательностями, указанными в теоремах для классической схемы.
Остается заметить, что при выполнение условия (*) на концентрацию размера комплекта предельные распределения изучаемых случайных величин в точности совпадают с аналогичными в равновероятной схеме размещения частиц комплектами фиксированной длины, совпадающей с целой частью математического ожидания длины комплекта.
.
