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

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

.

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

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

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

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

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

В связи с n-цепочками естественно возникают задачи о моментах остановки и о значениях n-цепочек в эти моменты: пусть, А — некоторое подмножество множества Snрассмотрим величину г = {mint > 0 | Yt (n) в А}, т. е. первый момент, когда цепочка Yt (n) оказывается во множестве А. Такой момент можно интерпретировать как момент возникновения «ложной тревоги», как момент какого-либо рода успеха, наступившего первым среди группы возможных вариантов, считающихся успешными, и т. п.

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

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

Цель работы.

Основными целями диссертационной работы являются следующие: исследование сходимости совместных распределений выборочных статистик /iri, r2 в схеме случайного размещения частиц двух типов к многомерным пуассоновским распределениямполучение асимптотических формул для рапределений первой появившейся n-цепочки с т > 1 единицами в последовательности Бернулли при различных соотношениях между п и вероятностью появления 1.

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

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

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

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

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

Доказана сходимость совместных распределений считающих статистик дГьГ2 к многомерным пуассоновским распределениям в правых, левых и смешанных областях.

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

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

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

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

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

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

Публикации.

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

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

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

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

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

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

Пусть, а — вероятность попадания частицы типа г в к-ю ячейку, где i = 1,2, — число частиц типа г, попавших в к-ю ячейку после размещения щ частиц типа г, и рассматриваются величины Дп, г2(п1) пг) == N.

I{X^ni) = r, X^ri2) = Г2} — количество ячеек, в которые попало.

А=1.

Ti частиц типа i = 1,2. В главе рассматриваются предельные распределения наборов таких величин и показана их сходмость к многомерным пуас-соновским распределениям при выполнении для каждого г — 1,2, условия limsup max < С и одного из условий: либо щ max —" 0, либо.

N^ofl оо. Для этого формулируется и доказывается обобщение теок ремы Б. А. Севастьянова о сходимости сумм зависимых индикаторов к пуас-соновским распределениям на суммы случайных векторов.

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

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

В разделе 1.2 приводится постановка задачи. Отдельно для каждого типа г) частиц г — 1,2 при —" оо и limsup max Nai < С определяется при.

N—+00 1 оо) области. Формулируется условие «корректности» для целочисленных наборов пар {(г/д, т²)}.=1 у. набор называется корректным, если все величины г^ являются неотрицательными при i = 1,2, j — 1,., J, а для любых различных 1 < ji, j2 < J выполняется хотя бы одно из условий: Ф ri2, b ИЛИ rju2 Ф Th> В разделе 1.3 формулируется и доказывается обобщение теоремы Б. А. Севастьянова о сходимости сумм зависимых индикаторов к пуассоновским распределениям на суммы случайных векторов, гг с (^) (т лю.

Пусть? ~ I si > ¦ • •) О) ~ последовательность случайных векторов с целыми неотрицательными компонентами, каждый из которых представлен в виде? — 5Jfc=i Щ = ylik ' • • • > rlj, k), fc = 1, • • •, где компоненты jfi U = lj-'-j-Л & — 1, • • •, А^) случайных векторов к — 1,., JV, принимают лишь значения 0 и 1. Для упрощения формул, верхний индекс (N), связанный с этой схемой серий, далее не используется.

Для произвольного мультииндекса т — (тi,., mj) € {0,1,. }J будем рассматривать упорядоченные наборы aj — («j (l),., a>j (mj)) 6 {1,., iV}77^ (aj — 0 при rrij = 0), j = 1,., J, и составленный из них набор, а = (oi, ., aj) = (ai (l),., ai (mi), 0:2(1),., aj (mj)). Пусть A = А (га, N) = {1 ,., iV}M множество всех наборов a, соответствующих мультииндексу Шздесь |га| = mH——-l-^j. Будем называть набор бесповторным, если среди его элементов нет совпадающих. Пусть В = В (га, iV) С, А — множество таких наборов а (т, N) = (cci,., oj), что каждый набор aj бесповторный, а С = C (fn, N) С В — множество бесповторных наборов, а = а (т, N). Пусть.

J TUj 3=1к=1 И.

Ьа = Pfea^fc) = 1, J = 1, А: = 1,. , TTlj).

Теорема 1.3.1. Пусть для схемы серий (1.11) выполняются условия N max b^fi —> 0, lim = Л7- при j — 1,., J, k=l,., N К ДГ—юо к j г j.

3=К., J fc==1 для любого мулътииндекса т aeB (m, N) c (m, N) и существуют такие исключительные множества D = D (m, iV) С С (fn, N), что.

Г Ьа 0, ^ Ьа О, aeD aeD lim max N—*oo aeCD.

Ьа 1 лi.

Ьа.

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

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

Теорема 1.4.1 Если при N —> оо для каждого ъ=1,2 выполняется условие принадлежности либо правой, либо левой области, а для случайного вектора? = (£ъ ¦ • • Aj) (где = fJrjA, rjt3 и набор пар {(т^-д, т^)}^,^ является корректным) выполнены условия.

Е&Л, — Е (0,оо), j = l,., J, то для любого набора s = (si,., sj) Е {1,., N} j j j=l j•.

В разделе 1.5 рассматриваются некоторые свойства статистик /Лгьг2: их связь с некоторыми аналогичными статистиками, рассматриваемыми в других работах, и достаточные условия для одновременной сходимости математических ожиданий нескольких таких статистик к конечным положительным величинам.

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

Во второй главе исследуется задача о появлении первой цепочки длины п с не более чем т единицами в последовательности испытаний Бернулли. Пусть ?2, ?3, ?4, • • • - последовательность независимых случайных величин, = 1) — р, = 0) = q = 1 —р, t = 1,2,. Для заданного т обозначим через Гп>т множество целочисленных наборов 7 = (71,72, •• •, 7т) таких, что def.

1 < 71 < 72 < • • • < 7m < Щ и Гп,<�т = (J rn, fc. к<�т.

Для заданных п, т и 7 (Е Fn, m обозначим через е7 вектор размерности п, у которого координаты с номерами к 6 {1,., т}, принимают значение 1, а все остальные — значение 0. Пусть ЛПуТП — множество всех таких е7, а def.

ЛП!<�т — (J АщкТо есть Anj<�т п, в которых не более т координат имеют значение 1. Рассмотрим случайную величину.

Тп, т = rnin{? > 1: ., € АП)<�т}.

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

Фп, т = е7, если? Тп, т+з-1 = ^{s=7fc}> S = 1, 2,., n, k=1.

— первый вектор из АП}<�т, появившийся в последовательности? i,?2j—;

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

В разделе 2.1 вводятся множества ГП: ГП, Anj.

В разделе 2.2 проводится построение вспомогательной цепи Маркова, вводятся случайные величины z7 d= Р {фп, т = е7} и индексные операторы t{l) = (7ь—ч7"-1)7* + 1,7<-1}—->7т), te N, pf (7) = (г, г + 7Ь., г + 7т-1), г € N, тЫ = (72, •••, 7т) •.

В случае т — 1 величины z7 также обозначаются как z^ если к = 71. Лемма. ifc/ш набор 7 Е ГП-ТПто.

П-П/т.

— «шгг-т г л &bdquo-&bdquo-г—1 z7 = p q + • г=1 ifo/ш t < т, то n-Jm.

Zy — ^(7) — ^^ (гр/(7) ZcTM iPt (7)) ' г—1 а если t = m, то zi ~ zMi) = PvTl~lrn~lzPn-lm (i)-В разделе 2.3 рассматриваются распределения фщ.

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

XI, 2 — Y (1 + q — p2qn~1 ± у/{1 + q-p2qn-l)2-±q) .

Теорема 2.3.1. Если х ф Х2, то pqn+m-Е Ъ-т + (1 — qn~l)Rm.

Z М.

— n!

ZRt t=i где Rm = -ж — J™ — если же х — х2, то pqTi+m—l ^ + (1 qn-l)Rm t=1.

Е й i где Ят = -^г.

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

Теорема 2.3.2. Пусть р (п) изменяется так, что р (п) < с < 1 и пр (п) —" оо, п —>• сю.

Тогда.

1 — qk.

Р{0пД = enk (n)} =-V + 0, п р причем остаточный член допускает равномерную по k Е {1,., п — 1} оценку.

Если при этом р (п) = о (1) и к (п)р (п) — о (1) — то.

Р{фп, 1 = en-k (n)} = Р?" +^Т + О рУ + прУ") .

Кроме того,.

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

Теорема 2.3.3. При предельном переходе q (n) = 1 — ^ + о Q), ^^ —> t, при п оо, где t € [0,1], существует.

Иш (пР{0пД = enk (n)}) = F (c,?), п—юо ' ' причем при с > In 4 ч с, sh + Vt).

F с t) = се" 2гс-?l ' j sh (^) ' при с < In (4).

Г1 Ь) — Ct, а при с = 1п (4).

F (c,*) = ce *. , sm (2).

F (c, *) = с2.

— с + 2tc.

2-е ' где L/i = arcch (^r)j = arccos (^p) uV — %y/l — 4e Кроме того, P{0n, i = eo} = e~c + o (l). Теорема 2.3.4. При предельном переходе р (п) = о Q).

Р{0пд = ек (п)} = р{1 -{к- 1) р + 0(п2р2)) и.

Р{Фп, 1 = е0} = 1 — пр + о (пр).

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

В разделе 2.4 рассматриваются предельные распределения фп<�т при т > 2. Исследуются свойства индексных операторов <тг (7), #(7), т (7), и определяется величина.

П-Jm / П-lm I / П-7! ь=ртЕ Е — Е (як~т)—im=1 ym-i=im+l гх=г2 + 1.

Теорема 2.4.1. Пусть п —>• ооа величина р = р (п) изменяется таким образом, что р{п)п —>¦ оо и р{п) < 1 — С для некоторого действительного 0 < С < 1.

В этом случае при фиксированном т > 2 «7 6 ТП: ТП справедливы асимптотические соотношения ш! Q / 1.

— nmPl + / '.

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

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

В этом случае при 7? ГП12 справедливы асимптотические соотношения 2 у п-1) (п-2).

Pl + 0(p2qn/3).

Теорема 2.4.3. Если пр —> 0 npw п —> сх) то для 7 6 TniTO справедлива асимптотическая формула (П — 7m) pm+1 + О (М&trade-+2).

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

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

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

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

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

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

• Точность оценок z7 при т = 1.

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

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

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

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

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

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

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

1. Ивченко Г. И., Медведев Ю. И. Некоторые многомерные теоремы в классической задаче размещения. — Теория вероятн. и ее примен., 1965, т. 10, в. 1, с. 156−162.

2. Ивченко Г. И., Медведев Ю. И., Севастьянов Б. А. Размещение случайного числа частиц по ячейкам. — Матем. заметки, 1967, т. 5, в. 1, с. 549−554.

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

4. Мирахмедов Ш. А. Случайные разложимые статистики в обобщенной схеме. — Дискретная математика, 1989, т. 1, вып. 4, с. 46−62.

5. Михайлов В. Г. О Предельной теореме Б. А. Севастьянова для сумм зависимых случайных индикаторов. — Обозр. пром. и прикл. матем., 2003, т. 10, в. 3.

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

7. Михайлов В. Г., Шойтов A.M. Структурная эквивалентность s-цепочек ' в случайных дискретных последовательностях. — Дискрет, матем., 2003, т. 15, в. 4, с. 7−34.

8. Попова Т. Ю. Предельные теоремы в одной модели размещения частиц двух типов. — Теория вероятн. и ее примен., 1968, т. 13, в. 3, с. 542−548.

9. Севастьянов Б. А. Предельный закон Пуассона в схеме сумм зависимых случайных величин. — Теория вероятн. и ее примен., 1972, т. 17, в. 4, с. 223−237.

10. Севастьянов Б. А., Чистяков В. П. Асимптотическая нормальность в классической задаче о дробинках. — Теория вероятн. и ее примен., 1964, т. 9, в. 2, с. 733−738.

11. Чистяков В. П. Дискретные предельные распределения в задаче о дробинках с произвольными вероятностями попадания в ящики. — Матем. заметки., 1967, т. 1, в. 1, с. 9−16.

12. Шойтов A.M. Пуассоновское приближение для числа повторений значений дискретной функции от цепочек. — Дискрет, матем., 2005, т. 17, в. 2, с. 56−69.

13. Шойтов A.M. Сложное распределение Пуассона для числа повторений значений дискретной функции от цепочек. — Дискрет, матем., 2007, т. 19, в. 2, с. 6−26.

14. Barbour A.D., Hoist L., Janson S. Poisson Approximation. — Oxford, The Clarendon Press, 1992.

15. Bekessy A. On classical occupancy problems. I. — Magy. tud. akad. Mat. kutato int. kozl. 8, № 1−2, 1963, p. 59−71.

16. Bekessy A. On classical occupancy problems. II. Sequential occupancy. — Magy. tud. akad. Mat. kutato int. kozl. 9, № 1−2, 1964, p. 317−329.

17. Bousquet-Melou M., Schaeffer G. Walks on the slit plane. — Probab. Theory Relat. Fields., 2002, v. 124, p. 305−344.

18. Gerber H.U., Li S.-Y.R. The occurence of sequence patterns in repeated experiments and hitting times in a Markov chain. — Stochastic Process. Appl., 1981, v. 11, p. 101−108.

19. Glaz J., Balakrishnan N. Scan Statistics and Applications. Birkhauser Verlag AG, 1999.

20. Glaz J., Naus J., Wallenstein S. Scan Statistics. Springer, 2001.

21. Guibas L.J., Odlyzko A.M. String overlaps, pattern matchins, and nontransitive games. — J. Comb. Theory, Ser. A, 1981, v.30, p. 183−208.

22. Kulldorff M. A spatial scan statistic. — Communications in Statistics: Theory and Methods, 1997, v.26, p. 1481−1496.

23. Li S.-Y.R. A martingale approach to the study of occurence of sequence patterns in repeated experiments. — Ann.Probab., 1980, v.8, 6, p. 1171−1176.

24. Mirakhmedov Sh.A., Saidova O.A. Estimates for remainder term on CLT for empty boxes statistics. — Turkish J. Math., 1998, 22, p. 47−52.

25. Mises R. Uber Anfteilungs und Besetzungs Wahrscheinlichkeiten. — Revu de la Faculte des Sciences de l’Universitet d’Istanbul, 1939, N.S.4, p. 145−163.

26. Renyi A. Three new proofs and generalization of a theorem of Irving Weiss. Magy. tud. akad. Mat. kutato int. kozl., 1962, 7, № 1−2, p. 203−214.

27. Weiss I. Limiting distributions in some occupancy problems. — Ann. Math. Stat. 29, 1958, № 3, p. 878−884.Публикации автора по теме диссертации.

28. Гаас В. В. О распределении первой n-цепочки с одной единицей в бернул-лиевской последовательности. — Обозр. прикл. и промышл. матем., 2003, т. 10, в. 1, с. 128.

29. Гаас В. В. Пуассоновская предельная теорема для совместных распределений в схеме случайного размещения частиц двух типов. — Обозр. при-кл. и пром. матем., 2006, т. 13, вып. 2, с. 284.

30. Гаас В. В. Пуассоновские предельные совместные распределения в схеме случайного размещения частиц двух типов. — Теория вероятн. и ее примен., 2007, т. 52, в. 2, с. 351−358.

31. Гаас В. В. Распределение первой цепочки с одной единицей в последовательности Бернулли. — Обозр. прикл. и промышл. матем., 2007, т. 14, в. 3, с. 435−448.

32. Гаас В. В., Зубков A.M. Распределение первой п-цепочки с малым числом единиц в бернуллиевской последовательности. — Обозр. прикл. и промышл. матем., 2002, т. 9, в. 2, с. 353.120.