Предельные теоремы для дискретных статистик Гаас Валерий Владимирович

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

Введение

1 Размещения частиц двух типов 18

1.1 Предисловие 18

1.2 Постановка задачи 31

1.3 Многомерная Пуассоновская теорема 32

1.4 Сходимости статистик цГиг2 36

1.5 Свойства статистик /ІП,Г2 40

1.6 Заключительные замечания 46

2 Распределения N-цепочек 49

2.1 Постановка задачи 49

2.2 Построение цепи Маркова 50

2.3 Распределение фп< 1 57

2.3.1 Построение производящей функции 57

2.3.2 Вывод точных распределений 59

2.3.3 Предельные теоремы для 0пд 62

2.3.4 Случай пр(п) 64

2.3.5 Случай пр(п) 66

2.3.6 Случай пр{п) -> 0 73

2.3.7 Свойства функции F(c, t) 74

2.3.8 Сравнение асимптотических оценок 79

2.4 Предельные теоремы для фп,т при т>1 81

2.4.1 Индексные операторы 81

2.4.2 Случай пр(п) -> оо 90

2.4.3 Случай пр(п) —> сх) для 0П]2 100

2.4.4 Случай пр(п) - 0 102

2.5 Заключительные замечания 105

Приложение 1. Таблицы 106

Приложение 2. Графики 112

Литература 117

• Многомерная Пуассоновская теорема
• Свойства статистик /ІП,Г2
• Распределение фп<
• Сравнение асимптотических оценок

Введение к работе

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

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

Одной из наиболее характерных тем комбинаторной теории вероятностей является т.н. «классическая задача о дробинках» и многочисленные ее обобщения, разрабатываемые как отечественными, так и зарубежными авторами (см., например, [1], [2], [3], [4], [14], [15], [16], [24], [25], [26], [27]). Исследуемое в классической задаче независимое равновероятное размещение некоторого количества объектов, именуемых дробинками или частицами, по ячейкам имеет большое количество разного рода интерпретаций, в том числе так называемый «критерий пустых ящиков», позволяющий, в частности, проверять гипотезу о соответствии эмпирического распределения выборки заданному распределению. Критерий пустых ящиков и другие критерии, основанные на статистиках fi_r, считающих количества «ячеек» (иначе - «ящиков») в которые попало ровно г «частиц» (или «дробинок»), в силу простоты практического вычисления являются хорошей альтернативой критерию х².

Важной особенностью статистик ц_г является простота асимптотических

ВВЕДЕНИЕ 5

формул для их распределений при растущих числах ячеек и размещаемых частиц: в большом количестве работ показана сходимость их и их обобщений к нормальным и пуассоновским распределениям, причем в последнем случае достаточно часто вывод основывается на теореме Б.А. Севастьянова о сходимости распределений сумм зависимых индикаторов к распределениям Пуассона [10].

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

Еще одной обширной темой комбинаторной теории вероятностей являет
ся исследование последовательностей независимых испытаний. Пусть X =
Х\Х2Х%... — последовательность независимых одинаково распределенных
случайных величин, принимающих значения в множестве S; п-цепочками
называются все ее подпоследовательности вида Yt{n) = (X_t,... ,Xt+_n-i),
t — 1,2, Такие статистики являются частным случаем сканирующих ста
тистик, имеющих широкое применение в астрономии, молекулярной биоло
гии, археологии, географии, социологии, лексикографическом анализе, рас
познавании образов и теории надежности (см., например, [19], [20] и [22]). В
работах [7], [12] и [13] устанавливаются достаточные условия сходимости чис
ла повторений значений некоторых функций от п-цепочек к распределению
Пуассона.

В связи с п-цепочками естественно возникают задачи о моментах остановки и о значениях п-цепочек в эти моменты: пусть А - некоторое подмножество множества Sⁿ; рассмотрим величину

г = {mint > 0 \Y_t(n) Є А},

т.е. первый момент, когда цепочка Yt(n) оказывается во множестве А. Такой момент можно интерпретировать как момент возникновения «ложной трево-

ВВЕДЕНИЕ 6

ги», как момент какого-либо рода успеха, наступившего первым среди группы возможных вариантов, считающихся успешными, и т.п.

Нахождение такого момента остановки приводит сразу к двум задачам: какое распределение имеет момент остановки т и каково распределение цепочки в момент остановки Y_T(n) на множестве А. В работах [18], [21] и [23] выведены системы функциональных уравнений, связывающие математические ожидания величины т и величин Т{ (минимальных времен попадания в А при условии, что в начальный момент цепь находится в состоянии А{ Є А). Если при этом множество А не является слишком сложным, с помощью этих систем можно вычислить Ет.

Однако даже в простых случаях вычисление распределений г и Y_T{n) приводит к очень громоздким формулам, если вообще оказывается возможным, не говоря уже о том, что получаемые формулы могут довольно сильно различаться даже в очень похожих ситуациях. По сути, общие формулы распределений этих величин для достаточно общих групп случаев отсутствуют, и, что еще хуже, отсутствует конкретная общая методика их получения даже в довольно простых ситуациях. Рассматривая какой-либо новый случай, исследователю приходится заново проделывать большой объем вычислений, получая существенно новые результаты. Использование асимптотических формул вместо точных ситуацию также не спасает — несмотря на упрощение результатов, их сколь-нибудь значимой общности добиться не удается.

Цель работы.

Основными целями диссертационной работы являются следующие: — исследование сходимости совместных распределений выборочных статистик /і_Гі,г₂ ^в схеме случайного размещения частиц двух типов к многомерным пуассоновским распределениям;

ВВЕДЕНИЕ 7

— получение асимптотических формул для рапределений первой появив
шейся п-цепочки с т > 1 единицами в последовательности Бернулли при
различных соотношениях между п и вероятностью появления 1.

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

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

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

Все результаты работы являются новыми.

Доказано обобщение теоремы Б.А. Севастьянова о сходимости распределений сумм зависимых индикаторов к пуассоновским распределениям на суммы случайных (ОД)-векторов.

Доказана сходимость совместных распределений считающих статистик fJ>n,r₂ ^к многомерным пуассоновским распределениям в правых, левых и смешанных областях.

Найдены точные и асимптотические распределения первой п-цепочки с одним успехом (с одной единицей) в последовательности Бернулли для различных способов изменения вероятности успеха р при п —» со.

Найдены предельные распределения первой п-цепочки с т успехами (единицами) при пр —» со.

Теоретическая и практическая значимость.

Многомерное обобщение теоремы Б.А.Севастьянова может использоваться при доказательстве сходимости к многомерным пуассоновским распределениям в различных задачах дискретной теории вероятностей. Теоремы, относящиеся к размещениям частиц двух типов, расширяют традиционный

ВВЕДЕНИЕ 8

круг задач, рассматривающихся в теории случайных размещений. Теоремы о предельных распределениях первой п-цепочки с малым числом единиц дают новые нетривиальные примеры распределений точки входа цепи Маркова в заданное множество состояний. Результаты диссертации могут использоваться при построении статистических критериев.

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

Основные результаты работы докладывались на «Всероссийском симпозиуме по прикладной и промышленной математике» (2002, 2003, 2005 и 2006гг.), на кафедральном семинаре кафедры математической статистики и случайных процессов (2006-2008гг., руководитель — д.ф.-м.н. Зубков A.M.), на семинаре отдела дискретной математики МИРАН им. Стеклова (2003-2008гг.), семинаре «Дискретные задачи теории вероятностей» (2003-2007гг., руководитель — д.ф.-м.н. Зубков A.M.).

Публикации.

Наиболее значимые результаты, представленные в диссертационной работе, опубликованы в работах [28] - [32].

Структура работы.

Работа состоит из введения, двух глав, двух приложений и списка литературы из 32 наименований. Нумерация формул, лемм и теорем в каждой главе своя.

Краткое содержание работы.

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

ВВЕДЕНИЕ 9

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

(і)

Пусть а\ — вероятность попадания частицы типа і в к-ю ячейку, где г = 1,2, Х^\щ) — число частиц типа г, попавших в к-ю ячейку после

/ \ def

размещения щ частиц типа г, и рассматриваются величины д_ГьГ2(пі,П2] =

J2 1{Х\,'{п\) = гі, ^(пг) ^{= Г2}1 ~~ количество ячеек, в которые попало г і частиц типа г = 1,2. В главе рассматриваются предельные распределения наборов таких величин и показана их сходмость к многомерным пуас-соновским распределениям при выполнении для каждого і = 1,2, условия limsup max iVal/ < С и одного из условий: либо щ max а' —> 0, либо

N-юо l^к k=l,...,N ^k

щ min ajj. —» oo. Для этого формулируется и доказывается обобщение тео-

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

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

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

В разделе 1.2 приводится постановка задачи. Отдельно для каждого типа

(г)

частиц г = 1,2 при щ,И —* со и limsup max Nai < С определяется при-надлежность к «левой» (случаи, когда щ max а —» 0) или «правой» (если щ min ajL —* со) области. Формулируется условие «корректности» для це-

K=l,...,iV

лочисленных наборов пар {(г/д, ^,2))-,-=1 f- набор называется корректным, если все величины Tjj являются неотрицательными при г = 1,2, j = 1,..., J,

ВВЕДЕНИЕ 10

а для любых различных 1 < ji,J2 < J выполняется хотя бы одно из условий:

^ГЛ,1 Ф r_j2il, ИЛИ r_ju2 ф T_h>

В разделе 1.3 формулируется и доказывается обобщение теоремы Б.А. Севастьянова о сходимости сумм зависимых индикаторов к пуассоновским распределениям на суммы случайных векторов.

Пусть ~ I si >---)0)~ последовательность случайных векторов с целыми неотрицательными компонентами, каждый из которых представлен в

виде - Efc=i Щ >Щ = ylik' > т,к), А; = 1,..., ЛГ, где компоненты гп_к (j = 1,..., J, к — 1,..., TV) случайных векторов щ\ к — 1,..., N, принимают лишь значения 0 и 1. Для упрощения формул, верхний индекс (iV), связанный с этой схемой серий, далее не используется.

Для произвольного мультииндекса m — (mi,..., mj) Є {0,1,... }^J
будем рассматривать упорядоченные наборы щ — (q;j(1), .., OLj{rrij)) Є
{1,..., N}^m> (aj — 0 при rrij = 0), j = 1,..., J, и составленный из
них набор а — (скі,..., olj) = (ai(l),..., ai(mi), «2(1), , aj(mj)). Пусть
A = A(m, iV) = {1,..., JV}l^ml — множество всех наборов а, соответствующих
мультииндексу m; здесь |m| = гп\-\ \-mj. Будем называть набор бесповтор
ным, если среди его элементов нет совпадающих. Пусть В = B(m, iV) С А
— множество таких наборов a(m, N) = (а\,..., aj), что каждый набор ctj
бесповторный, а С = C(m, N) С В — множество бесповторных наборов
a = a(fn, N), Пусть

j тп

_ьї^]_{=pfe=і), ь.=пі№)}

j=l fc=l

&a = Pfe.a^ft) = 1, j = 1, , /, & = 1, . , 77lj)-

ВВЕДЕНИЕ 11

Теорема 1.3.1. Пусть для схемы серий (1.11) выполняются условия

max by —* 0, lim > vl = Л₇- при і — 1..... J,

k=l,...,N ^К N^00*-*/ ^к j г j

для любого мультииндекса т

aeB(m,N)\c(m,N) и существуют такие исключительные множества D = D(m,N) С С(т, N), что

аЄ-D аЄГ>

lim max

ЛГ-юо aeC\D

Ьа _ ₁

для любых наборов неотрицательных целых чисел (si,..., sj).

Доказательство теоремы проводится с помощью метода моментов.

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

Теорема 1.4.1 Если при N —* оо для каждого ъ=1,2 выполняется условие принадлежности либо правой, либо левой области, а для случайного вектора ? = (ъ ---,0) (где ^ = fJr_jA,r_jt2 и набор пар {(^,1,^,2)^=1,...,7 является корректным) выполнены условия

Е&-* Л,- Є (0, со), j = 1,...,7,

то для любого набора s = (si,..., sj) Є {1,..., N}

.7=1 ^

ВВЕДЕНИЕ

В разделе 1.5 рассматриваются некоторые свойства статистик /и_Г1,г₂'- ^их связь с некоторыми аналогичными статистиками, рассматриваемыми в других работах, и достаточные условия для одновременной сходимости математических ожиданий нескольких таких статистик к конечным положительным величинам.

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

Во второй главе исследуется задача о появлении первой цепочки длины п с не более чем т единицами в последовательности испытаний Бернулли. Пусть i, 2, 3, — р, Р(& = 0) = q = 1 —р, = 1,2,.... Для заданного т обозначим через Г_П]ГП множество целочисленных наборов 7 = (7ь7г> -,1т) таких, что

def 1 < 71 < 72 < * * < 1т < П, И Г_П)<_т = (J Г_п,ь

Для заданных n, т и 7 Є Г_ПіГП обозначим через е₇ вектор размерности п, у которого координаты с номерами 7fc> /с Є {1,... ,?n}, принимают значение 1, а все остальные - значение 0. Пусть Л_ПуТП - множество всех таких е₇, а

A_n^<_m — (J A_ntk- To есть A_n><_m - множество двоичных векторов размерности

п, в которых не более m координат имеют значение 1. Рассмотрим случайную величину

i~n,m = min{ > 1 : (&, f_t+1,..., _t+n-i) Є Ai,<_m}

- момент первого появления n-цепочки из множества А_Пу<_т в последовательности i, ^2, j и случайный вектор

m 0n,m = Є₇, ЄСЛИ r_n,_m+s-l = Yl ^{*=7k}> S = 1, 2, . . . , П,

ВВЕДЕНИЕ 13

- первый вектор из А_П}<_т, появившийся в последовательности i, г?

В главе доказываются предельные теоремы для ф_п>т при п — оо в схемах

серий, когда при изменении номера серии может изменяться величина р. В разделе 2.1 вводятся множества Г_П]ГП, Л_Пі<_т, случайные величины т_П)Ш,

фп,т и вводится постановка задачи.

В разделе 2.2 проводится построение вспомогательной цепи Маркова,

вводятся случайные величины z₁ = Р {ф_п,т = е₇} и индексные операторы

t{l) = (7ъ---,7^-1,7^ + 1,7^-1,---,7^0, teN,

Pi(7) = (г, і + 7ь ...,г + 7т-і), і Є N,

т(т) = (72, ,7т)

В случае т — 1 величины z₇ также обозначаются как z^, если к = 7ь Лемма. "слм набор 7 Є r_n;Tn; mo

n-7,

- „т_,тг-т і \ ^л _ _тлг—1

z₁ = p q +2^ ^zPi(7)P^

г=1

Если t < m, mo

^Zl ~~ ^ZOt{l) ⁼ 2s РУ \^ZPi(l) ~ ^Z^t+iPi(-y)) '

г=1

а если t = m, mo

z₁ - z_atb) = pg"-⁷"¹-¹^.^^).

В разделе 2.3 рассматриваются распределения _пд

С помощью метода производящих функций находятся точные распределения 0_пд. Пусть

ВВЕДЕНИЕ 14

Теорема 2.3.1. Если х\ ф х₂, то

_pqn₊m-iⁿfl _Rt__{m + (1} _ _qn-l_)Rm
Zn-m - _n-1

t=l

где R_m = -L — ^ш; если же x\ — x₂, mo

^x2 ^1

_pqn+m-l "^ _Rt__{m + (1} _ _qn-l)R_m

_ t=l

Zn—m —

ra-1 '

t=i

где Rm = -.

Для ф_п<і, в зависимости от асимптотического поведения р — р(п), доказываются три предельные теоремы.

Теорема 2.3.2. Пусть р(п) изменяется так, что

р(п) < с < 1 и пр(п) —> со, п —> со.

ТЪгЛг

Р{0_пД = e_n__k(n)} = -Ц- + О (р₉^п),

п — -р

причем остаточный член допускает равномерную по к є {1,..., п — 1} ог^ен-

ош npw этом р(п) = о(1) г* к(п)р(п) — о(1), то

PWw = e_n__k(n)} = _Рї" + ^r + О (^ + прУ") .

Кроме того,

Р{0пд=е_о} = о(1).

ВВЕДЕНИЕ 15

Теорема 2.3.3. При предельном переходе q(n) = 1 — ^ + о Q), -^ —> _;

npn п —» оо, где і Є [0,1], существует

п—юо

lim (пР{0_пД = e_n__k(n)}) = F(c,t), причем при с > In 4

, _ч с, sh (^ + W)

при с < In(4)

F{c,t) = ce~*

_;Sin (fcZ + _Vt)

а при с = 1п(4)

sin(^) ' __t_₂2-c + 2tc

F(c, t) = c2

2-е '

где f/i = arcch (^-), С/г = arccos f^j-J и V = \/|l ^— 4e~^c|. Кроме того, Р{0_п,і = ^eo} = e~^c + o(l). Теорема 2.3.4. При предельном переходе р(п) = о Q)

Р{0пд = е_к(п)} = р(1 - (fc - 1)р + 0(пУ))

Р{Фп,1 = Є₀} = 1 - Пр + о(пр).

Кроме того, исследуются свойства функции F(c, t): доказывается ее ограниченность, непрерывность, монотонное возрастание и выпуклость по t и бесконечная дифференцируемость по обеим переменным везде, кроме множества с = 1п(4), а также сравнивается точность оценок, построенных по результатам теорем 2.3.2, 2.3.3 и 2.3.4.

В разделе 2.4 рассматриваются предельные распределения ф_п,т при т > 2. Исследуются свойства индексных операторов 0^(7), Рі{і), ^{і)і и опре-

ВВЕДЕНИЕ 16

деляется величина

П-Jm І ГС-7т-1 / ra-7i

ь=р^тЕ E — E (9"-^m)---

Теорема 2.4.1. Пусть n —> oo_; а величина p — p(n) изменяется таким образом, что

р{п)п —> оо и р{п) < 1 — С

для некоторого действительного О < С < 1.

Б этом случае при фиксированном т > 2 и^у Є Г_П]ГП справедливы асимптотические соотношения

т\ „/ 1 \

^Z7 = "^7 +

_nm \ri^m*Jpn_/

Доказательство теоремы использует асимптотические оценки и свойства индексных операторов. При этом в полученных формулах возможно улучшение точности. В качестве примера рассматривается случай т = 2.

Теорема 2.4.2. Пусть п —» оо, а для величины р = р(п) выполняется условие пр — оо.

В этом случае при 7 Є Г_П]2 справедливы асимптотические соотношения

/0-*у

р₇ + о(^у/³).

(п-1)(п-2)

Теорема 2.4.3. Ъш пр — 0 npw п —» оо то для 7 Є Г_ПіТО справедлива асимптотическая формула

*у = P^mQⁿ~^m + (" - 7m)p^m+1 + О {(pn)^m+2) .

ВВЕДЕНИЕ 17

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

В первом приложении приводятся таблицы:

Значения F(c_:t) при с, принимающем значения 0,5, 1, 1п(4), 2, 4 и 8;

Значения р₇ при т — 1, п — 20 и р, принимающем значения 0, 05, 0,1, 0,2, 0,3, 0,4 и 0,5;

Значения ру при т = 2, п — 20 и р — 0, 3;

Точные значения Zk, их оценки и точность этих оценок при т = 1, п = 20 и р = 0, 3;

Точность оценок z₇ при 771 = 1.

Во втором приложении приводятся графики:

График функции F(c, t) при с = 0.5, с = 1п(4) и с = 4.0;

График функции F(c, ) при с < 4;

График величины р₇ при m = 1, п = 20 и р, принимающем значения 0,1, 0,2, 0,3 и 0,4;

График величины р₇ при т = 2, п = 20 и р = 0, 3;

График величины р₇ при m = 2, п = 50 и р = 0, 3.

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

Многомерная Пуассоновская теорема

Таким образом, в правой и левой областях асимптотически возникают пуассоновские распределения, а в центральной, правой промежуточной и левой промежуточной - нормальные распределения. В действительности же в правой промежуточной и левой промежуточной областях асимптотическое поведение величины /io( N) во многом аналогично поведению в правой и левой областях соответственно. На основе сходимости пространственных метрик можно даже утверждать, что соответствующие величины (в правой промежуточной области - fio(n, N), в левой промежуточной - fio(n: N) — (N—n)) также имеют пуассоновское распределение, но так как их математические ожидания и дисперсии растут с ростом N, то выполняется сходимость к нормальному распределению.

На основе классической схемы размещения частиц по ячейкам строится т.н. критерий «пустых ящиков»: пусть гипотеза Но состоит в том, что некоторая выборка, состоящая из независимых наблюдений х\,Х2,... )Хп взята из непрерывного распределения FQ; выберем точки ZQ = —со z\ - - ZN-I ZN = со таким образом, что Fo(zi) — Fo(zi-i) = 1/АГ, г — 1,...,7V. Далее подсчитывается fio(n,N) -количество таких полуинтервалов (zi, +і], в которые не попало ни одного из наблюдений {xi}i=i,...,n и в зависимости от выбранной квантили Ср строится критерий: гипотеза До принимается, если JIQ Ср, и отвергается в противном случае. Построенный таким образом критерий «пустых ящиков» пустых ящиков является довольно гибкой и удобной альтернативой критериям Колмогорова, х2 и некоторым другим в силу сравнительной простоты вычислений и возможности варьирования числа «ящиков».

Кроме этого, в работе [8] рассматривается случай 0 с\ nk/N С2 со, к = 1, 2, пі, П2, N — сю. В этих условиях показано, что вектор (/ , /4 А4 ) является асимптотически нормальным и получены явные формулы его вектора математических ожиданий и матрицы ковариаций. Стоит при этом отметить, что Cov (/4),/-4) = 05 в то время, как ковариаций fi0 и ц0 , к = 1, 2, могут быть не равными 0.

Условия, налагаемые теоремой 1.1.11 на величины пі, П2, iV, эквивалентны введенному ранее понятию принадлежности к левой области, но, по видимому, в случае размещения частиц нескольких типов, говороить об отношении всей схемы размещения к той или иной области не вполне разумно, так как это в значительной мере сужает количество возможных ситуаций и приводит к довольно искуственному отбрасыванию многих из них.

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

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

Одной из наиболее характерных тем комбинаторной теории вероятностей является т.н. «классическая задача о дробинках» и многочисленные ее обобщения, разрабатываемые как отечественными, так и зарубежными авторами (см., например, [1], [2], [3], [4], [14], [15], [16], [24], [25], [26], [27]). Исследуемое в классической задаче независимое равновероятное размещение некоторого количества объектов, именуемых дробинками или частицами, по ячейкам имеет большое количество разного рода интерпретаций, в том числе так называемый «критерий пустых ящиков», позволяющий, в частности, проверять гипотезу о соответствии эмпирического распределения выборки заданному распределению. Критерий пустых ящиков и другие критерии, основанные на статистиках fir, считающих количества «ячеек» (иначе - «ящиков») в которые попало ровно г «частиц» (или «дробинок»), в силу простоты практического вычисления являются хорошей альтернативой критерию х2.

Свойства статистик /ІП,Г2

Важной особенностью статистик цг является простота асимптотических формул для их распределений при растущих числах ячеек и размещаемых частиц: в большом количестве работ показана сходимость их и их обобщений к нормальным и пуассоновским распределениям, причем в последнем случае достаточно часто вывод основывается на теореме Б.А. Севастьянова о сходимости распределений сумм зависимых индикаторов к распределениям Пуассона [10]. В настоящей работе доказаны теоремы о сходимости к пуассоновским распределениям совместных распределений обобщений статистик \хт на размещения частиц двух (или нескольких) типов. Еще одной обширной темой комбинаторной теории вероятностей являет ся исследование последовательностей независимых испытаний. Пусть X = Х\Х2Х%... — последовательность независимых одинаково распределенных случайных величин, принимающих значения в множестве S; п-цепочками называются все ее подпоследовательности вида Yt{n) = (Xt,... ,Xt+n-i), t — 1,2, Такие статистики являются частным случаем сканирующих ста тистик, имеющих широкое применение в астрономии, молекулярной биоло гии, археологии, географии, социологии, лексикографическом анализе, рас познавании образов и теории надежности (см., например, [19], [20] и [22]). В работах [7], [12] и [13] устанавливаются достаточные условия сходимости чис ла повторений значений некоторых функций от п-цепочек к распределению Пуассона. В связи с п-цепочками естественно возникают задачи о моментах остановки и о значениях п-цепочек в эти моменты: пусть А - некоторое подмножество множества Sn; рассмотрим величину г = {mint 0 \Yt(n) Є А}, т.е. первый момент, когда цепочка Yt(n) оказывается во множестве А. Такой момент можно интерпретировать как момент возникновения «ложной трево ги», как момент какого-либо рода успеха, наступившего первым среди группы возможных вариантов, считающихся успешными, и т.п.

Нахождение такого момента остановки приводит сразу к двум задачам: какое распределение имеет момент остановки т и каково распределение цепочки в момент остановки YT(n) на множестве А. В работах [18], [21] и [23] выведены системы функциональных уравнений, связывающие математические ожидания величины т и величин Т{ (минимальных времен попадания в А при условии, что в начальный момент цепь находится в состоянии А{ Є А). Если при этом множество А не является слишком сложным, с помощью этих систем можно вычислить Ет.

Однако даже в простых случаях вычисление распределений г и YT{n) приводит к очень громоздким формулам, если вообще оказывается возможным, не говоря уже о том, что получаемые формулы могут довольно сильно различаться даже в очень похожих ситуациях. По сути, общие формулы распределений этих величин для достаточно общих групп случаев отсутствуют, и, что еще хуже, отсутствует конкретная общая методика их получения даже в довольно простых ситуациях. Рассматривая какой-либо новый случай, исследователю приходится заново проделывать большой объем вычислений, получая существенно новые результаты. Использование асимптотических формул вместо точных ситуацию также не спасает — несмотря на упрощение результатов, их сколь-нибудь значимой общности добиться не удается.

Таким образом, в схеме неравновероятного размещения при некоторых ограничениях асимптотические результаты аналогичны результатам схемы равновероятного размещения. Схему с неравновероятным размещением частиц также называют полиномиальной схемой. Но интерес представляет также изучение полиномиальных распределений несколько иного рода - рассмотрение не индивидуальных распределений /xr(n, TV), а всего вектора //o(n, TV),/ii(n, TV),... ,/in(n, TV), являющегося полиномиальным в допредельном случае. Естественно, что в силу значительного усложнения рассмотрение точных формул может быть лишено смысла, и разумным является рассмотрение асимптотических формул, что для центральной области было продемострировано в теореме 1.1.10 (впрочем, в ней рассматривается не весь вектор /io( , TV), Ді(п, TV),..., /in(n, TV), а некоторый его фиксированный подвектор).

Распределение фп<

Однако же если рассматривать не центральную область получающиеся асимптотические результаты могут также оказаться очень сложными и по формулировке и по методам доказательтв. В частности, как уже было отмечено ранее, если одна из величин дг(п, TV) относится либо к правой, либо к левой г—области, практически все остальные величины /is(n,TV), s ф г, к соответствующим областям относиться не будут, что приводит к необходимости комбинирования различных по типу областей и значительному усложнению методов, используемых при их исследовании. Основными целями диссертационной работы являются следующие: — исследование сходимости совместных распределений выборочных статистик /ІГІ,Г2 в схеме случайного размещения частиц двух типов к многомерным пуассоновским распределениям; — получение асимптотических формул для рапределений первой появив шейся п-цепочки с т 1 единицами в последовательности Бернулли при различных соотношениях между п и вероятностью появления 1. Все результаты работы являются новыми. — Доказано обобщение теоремы Б.А. Севастьянова о сходимости распределений сумм зависимых индикаторов к пуассоновским распределениям на суммы случайных (ОД)-векторов. — Доказана сходимость совместных распределений считающих статистик fJ n,r2 к многомерным пуассоновским распределениям в правых, левых и смешанных областях. — Найдены точные и асимптотические распределения первой п-цепочки с одним успехом (с одной единицей) в последовательности Бернулли для различных способов изменения вероятности успеха р при п —» со. — Найдены предельные распределения первой п-цепочки с т успехами (единицами) при пр —» со. Теоретическая и практическая значимость. Многомерное обобщение теоремы Б.А.Севастьянова может использоваться при доказательстве сходимости к многомерным пуассоновским распределениям в различных задачах дискретной теории вероятностей. Теоремы, относящиеся к размещениям частиц двух типов, расширяют традиционный круг задач, рассматривающихся в теории случайных размещений. Теоремы о предельных распределениях первой п-цепочки с малым числом единиц дают новые нетривиальные примеры распределений точки входа цепи Маркова в заданное множество состояний. Результаты диссертации могут использоваться при построении статистических критериев.

Основные результаты работы докладывались на «Всероссийском симпозиуме по прикладной и промышленной математике» (2002, 2003, 2005 и 2006гг.), на кафедральном семинаре кафедры математической статистики и случайных процессов (2006-2008гг., руководитель — д.ф.-м.н. Зубков A.M.), на семинаре отдела дискретной математики МИРАН им. Стеклова (2003-2008гг.), семинаре «Дискретные задачи теории вероятностей» (2003-2007гг., руководитель — д.ф.-м.н. Зубков A.M.).

Будем говорить, что последовательность параметров {N, щ, {ак }} лежит в левой области, если выполняется условие (1.8), и в правой, если верно (1.9). По аналогии с ситуацией размещения частиц одного типа можно ввести понятия центральной, левой и правой промежуточных областей. Сами же выборочные статистики fir 1іГ 2(пі,П2) будем называть двухтипными, а статистики вида fir(щ) — однотипными.

Но, по сути, без каких-либо значимых изменений приведенная схема может быть обобщена на размещение частиц произвольного числа типов. Замена пары (TJ-Д, г г) на вектор (г -д, г ,..., г ) в теореме 1.4.1 практически не приводит к изменениям доказательства, однако при этом получающиеся формулы и промежуточные выражения становятся в некоторых случаях длинней и запутанней, не становясь при этом качественно сложнее. Само по себе рассмотрение совместного распределения J статистик уже приводит к большому разбуханию используемых индексов величин и выражений, а добавление еще и произвольного числа типов частиц только усугубляет этот эффект.

Но в то же время нет принципиальной сложности в обобщении приводимых результатов и на этот случай. Как и в случаях с равновероятной и полиномиальной схемами, в описанной в этой главе схеме размещения частиц по ячейкам довольно выгодным оказывается использование асимптотических формул в качестве альтернативы точным: например, точное выражение для P(j = Sj,j — 1,..., J) может быть получено с помощью формулы включения-исключения на основе величин 3=1 aeC(s,N) где Ьа выражаются по формуле (1.30). При этом мало того, что сама формула (1.30) представляет из себя довольно сложный конгломерат произведений и сумм большого количества различных величин, так еще и сами эти выражения необходимо суммировать по нескольким множествам C(s, N), размер которых имеет порядок N . При этом такое суммирование практически не поддается сколь-нибудь значимому упрощению, а с ростом N оно формула получает резкий полиномиальный рост по объему вычислений.

Сравнение асимптотических оценок

Использование асимптотик в такой ситуации оказывается еще более оправданным, чем в случаях равновероятной и полиномиальной схем размещения частиц по ячейкам. И. возможно, оно является единственным разумным выходом при любом сколь-нибудь большом значении величины N. Относительно схемы размещения частиц нескольких типов стоит отметить еще одно обстоятельство. В реальной ситации количество бросаемых частиц разных типов может оказаться достоточно сильно различным, что может привести к затруднениям в рассмотрении считающих статистик АІГІ)Г2, так как асимптотики математических ожиданий нескольких таких величин в общем случае могут иметь довольно разные порядки (например, Е/ІГІ1)ГІ2 —» оо, а Е/ІГ21)Г22 —» 0 при N —» со), что существенно ограничивает круг совместно рассматриваемых статистик такого типа. В разделе 1.5 были найдены несколько достаточных условий, когда такое рассмотрение возможно, однако такого рода условия оказываются довольно узкими и в общем случае, скорее всего, не выполняются даже для двух различных статистик. Выходом из такой ситуации может быть регулирование количеств частиц (а именно, если число бросаемых частиц довольно велико, его можно уменьшить, не учитывая бросания нескольких последних частиц), либо же применить к статистикам /J n,r2 пР0ЦеДУРУ «случайного процеживания» - отбрасывания с некоторой вероятностью каждого из ящиков, в котором оказалось требуемое количество частиц. Последний вариант является более гибким для рассмотрения совместных распределений считающих статистик //ri)r25 однако его использование требует пересмотрения многих ключевых моментов настоящей главы.

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

Однако, в силу сложности полученной функции и учитывая ее состаной характер (в зависимости от значения переменной с, функция выражается одной из 3-х формул) остаются неясными даже такие ее простые свойства, как ограниченность, непрерывность и дифференцируемость. И для того, чтобы хотя бы немного прояснить характер допредельных и пределных распределений фп,і, произведем аналитические иследования свойств функции F(c,t). В Приложении 1 приведена таблица значений (табл. 1) функции F(c,t) при с = 0.5, с = 1, с = 1п(4), с = 2, с = 4, и с = 8. В Приложении 2 приведены графики функции F(c,t): на рис. 1 в случаях с — 0.5, с = 1п(4) и с = 4, на рис. 2 в случае с 4. Лемма 2.3.9 F(c,t) является монотонно возрастающей и выпуклой вверх по аргументу t, 0 t 1, при любых с 0. Доказательство. Утверждение леммы получается в силу применения следствия 1 и предельного перехода. Исходя из аналитического вида (формулы (2.28), (2.29)) функции, можно сделать вывод, что единственной ситуацией, где F(c, t) либо ее частные производные имеют разрывы является множество {с : sh(/i(c) — V(c)) = 0}, либо {с : sin (С/г (с) — V(c)) = 0}, но как уже было показано в леммах 3.5.5, 3.5.6, это множество не входит в область {0 с In4} (J {с In 4}, а, следовательно и F(c, t) и все ее частные производные в этой облати не имеют разрывов. Существование бесконечного числа частных производных по t при с = In 4 следует из ее аналитического представления. В существовании конечной правой и левой производных по с при с = In 4 можно убедиться из формул (2.48), (2.49), и аналогичных формул, получаемых при рассмотрении области 0 с In 4. А так как обе они совпадают, то можно говорить о дифференцируемости F(c, t) по с при с = In 4. При этом скорее всего можно также говорить и о бесконечной дифференцируемости F(c, t) по с при с = In 4.

В теореме 2.3.1 были получены точные формулы для распределений z1 при т = 1, а в теоремах 2.3.2, 2.3.3 и 2.3.4 - их асимптотики при различных при различных предельных переходах. В теоремах 2.3.2 и 2.3.4 также приводились и оценки точности этих асимптотик, но, как и во всех подобных случаях, такие оценки дают лишь общее представление о характере близости точных значений и асимптотик. Это позволяет считать, что случаю п = 20 и р = 0,3 наиболее соответствует предельный переход р(п)п — со, а 2точ{к) наиболее точно оценивает величины zk. Для этого случая c — pn — Q. А какова ситуация в других случаях и, в частности, при меньших с? В таблице 5 приведены значения тах\Аточ\, тахА и maxA0UJ в некоторых случаях при различных значениямх параметров р и п. В случаях рп 1п(4) приведены значения тахДт0 ц, а в случаях рп 1п(4) значения max Д o l- Можно заметить, что во всех приведенных случаях при с 5 тахД max ІДто чІ и при фиксированном п величина тахД убывает с уменьшением р, в то время, как max [Д оч! возрастает и можно достаточно четко определить области, где более точной является оценка zmo4{k), а где zpik). Каждую из этих областей можно условно отнести либо к предельному переходу рп — со, либо к предельному переходу рп — с 0. В случае с 1п(4) величина max \Ар\ продолжает убывать с уменьшением р при фиксированном п, так же, как и тахД0 - Но во всех приведенных примерах последняя убывает быстрей и, скорее всего, здесь тоже возможно четкое разделение на области, где более точной является оценка Zp{k), а где %оц{к), и, в соответствии с ними, можно производить условное деление на принадлежность либо к предельному переходу рп — с О, либо к предельному переходу рп — 0. Таким образом, каждая из построенных асимптотических оценок ( точ(к), zp{k) и г0ц(к)) является лучшей в некоторой своей области параметров рип, скорее всего, бесконечной по п. Оценка же zynp(k) в силу своего построения имеет меньшую точность, уступая не только оценке zmou{k), но и зачастую оценке zp(k), даже в области рп — со.

Похожие диссертации на Предельные теоремы для дискретных статистик

Предельные теоремы для статистик, связанных с большим числом редких событий Мнацаканов Роберт Мушегович

Предельные теоремы для статистик от ассоциированных случайных величинЕкишева, Светлана Викторовна

Асимптотические разложения в центральной предельной теореме для квадратичных форм : Предельные теоремы для вейвлет-статистикЮрченко Владислав Александрович

Предельные теоремы для рандомизированных разделимых статистик и их приложенияБыков, Сергей Иванович

Вероятностные неравенства и предельные теоремы для обобщенных L-статистикБакланов Евгений Анатольевич

Оценки скорости сходимости в центральной предельной теореме для одновыборочных и многовыборочных U-статистик от разнораспределенных случайных величинГадасина Людмила Викторовна

Предельные теоремы и вероятностные неравенства для канонических U- и V-статистик от зависимых наблюденийВолодько Надежда Владимировна

Предельные теоремы для функционалов от случайных процессов и полей и их применения в статистикеБямбажав, Доржийн

Предельные теоремы и статистические процедуры для величин, связанных с рекордами и экстремальными порядковыми статистикамиСтепанов Алексей Васильевич