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

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

На правах рукописи УДК 519 21

Гаас Валерий Владимирович

ПРЕДЕЛЬНЫЕ ТЕОРЕМЫ ДЛЯ ДИСКРЕТНЫХ СТАТИСТИК

01 01 05 - теория вероятностей и математическая статистика

АВТОРЕФЕРАТ

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

003171729

Москва - 2008

Л

003171729

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

статисти-факультета

Научный руководитель- доктор физико-математических наук,

А М Зубков

Официальные оппоненты- доктор физико-математических наук,

профессор В М Круглов кандидат физико-математических наук, В И Хохлов

Ведущая организация: Московский государственный институт

электроники и математики (технический университет)

Защита состоится 27 июня 2008 года в 16 часов 45 минут на заседании Диссертационного Совета Д 501 001 85 при Московском государственном университете имени M В Ломоносова по адресу 119991, ГСП-1, Москва, Ленинские горы, МГУ, аудитория 16-24

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

Автореферат разослан 27 мая 2008 года

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

И H Сергеев

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

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

Исследование различных типов комбинаторных задач занимает весьма значимое место в проблематике теории вероятностей и математической статистики благодаря своему ярко выраженному прикладному характеру Взаимодействие большого числа дискретных, либо условно выделяемых объектов представляет большой интерес для многих задач техники, экономики, теории чисел, программирования, криптографии Одной из наиболее характерных тем комбинаторной теории вероятностей является так называемая «классическая задача о дробинках» и многочисленные ее обобщения, разрабатываемые как отечественными (В Ф Колчин, Б А Севастьянов, В П Чистяков1, Г И Ивченко и Ю И Медведев2), так и зарубежными авторами (Ми-зес3, Бекеши4, Реньи5, Барбур, Холст и Янсон6) Исследуемое в классической задаче независимое равновероятное размещение некоторого количества объектов, именуемых дробинками или частицами, по ячейкам имеет большое количество разного рода интерпретаций, в том числе так называемый «критерий пустых ящиков», позволяющий, в частности, проверять гипотезу о соответствии эмпирического распределения выборки заданному распределению Критерий пустых ящиков и другие критерии, основанные на статистиках ßr, считающих количества «ячеек» (иначе - «ящиков») в которые попало ровно г «частиц» (или «дробинок»), в силу простоты практического вычисления являются хорошей альтернативой критерию х2

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

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

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

3 Mises Я Uber Anfteilimgs und Besetzungs - Wahrscheinlichkeiten — Revu de la Faculté des Sciences de l'Umversitet d'Istanbul, 1939, N S 4, p 145-163

4Békéssy A On classical occupancy problems I, II — Magy tud akad Mat kutat<5 mt kôzl 8, № 1-2, 1963, p 59-71, 9, № 1-2, 1964, p 317-329

5 Renyi A Three new proofs and generalization of a theorem of Irving Weiss — Magy tud akad

Mat kutatö mt kozl, 1962, 7, № 1-2, p 203-214

6Barbour A D, Holst L , Janson S Poisson Approximation - Oxford, The Clarendon Press, 1992

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

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

Еще одной обширной темой комбинаторной теории вероятностей является исследование последовательностей независимых испытаний Пусть X = Х\Х^Хз

— последовательность независимых одинаково распределенных случайных величин, принимающих значения в множестве S, n-цепочками называются все ее подпоследовательности вида Yt(n) = {Xt, ,Xt+n_i), t = 1,2, Такие статистики являются частным случаем сканирующих статистик, имеющих широкое применение в астрономии, молекулярной биологии, археологии, географии, социологии, лексикографическом анализе, распознавании образов и теории надежности (см , например, Глад и Балакришнан8) В работах А М Шойтова9 и В Г Михайлова10 устанавливаются достаточные условия сходимости числа повторений значений некоторых функций от n-цепочек к распределению Пуассона

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

г = {mini > 0 | Yt(n) £ А},

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

Нахождение такого момента остановки приводит сразу к двум задачам какое распределение имеет момент остановки г и каково распределение цепочки в момент

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

— Теория вероятн и ее примен , 1972, т 17, в 4, с 223-237

BGlaz J, Balakrishnan N Scan Statistics and Applications Birkhauser Verlag AG, 1999

9Шойтов A M Сложное распределение Пуассона для числа повторений значений дискретной

функции от цепочек — Дискрет матем , 2007, т 19, в 2, с 6-26

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

остановки YT{n) на множестве А В работах Гербера11 и Гуибаса12 выведены системы функциональных уравнений, связывающие математические ожидания величины т и величин г, (минимальных времен попадания в А при условии, что в начальный момент цепь находится в состоянии А, е А) Если при этом множество А не является слишком сложным, с помощью этих систем можно вычислить Er

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

Цель работы

Основными целями диссертационной работы являются следующие

— исследование сходимости совместных распределений выборочных статистик ßri,r2 в схеме случайного размещения частиц двух типов к многомерным пуассонов-ским распределениям,

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

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

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

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

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

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

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

12Gmbas L J , Odlyzko A M String overlaps, pattern matchins, and nontransrtrve games — J Comb Theory, Ser A, 1981, v 30, p 183-208

(ОД)-векторов

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

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

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

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

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

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

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

Публикации

Результаты диссертации опубликованы в 5 работах, список которых приведен в конце автореферата, [1] - [5]

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

Работа состоит из введения, двух глав (каждая из которых разбита на разделы), двух приложений и списка литературы из 32 наименований Общий объем диссертации - 120 страниц Нумерация теорем в автореферате совпадает с нумерацией в

диссертации

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

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

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

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

fj,Tl r2(ni, 712) = IiX^foi) = ri Xj?\ri2) = Г2} — количество ячеек, в которые fc=i

попало г, частиц типа г — 1, 2 В главе рассматриваются предельные распределения наборов таких величин и показана их сходмость к многомерным пуассоновским распределениям при выполнении для каждого г — 1,2, условия lim sup max Naf1 < С

N—+00

и одного из условий либо —» 0, либо п,^rmn^a^ —» 00 Для этого

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

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

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

В разделе 1.2 приводится постановка задачи Отдельно для каждого типа частиц г = 1,2 при nuN —* 00 и lim sup max Naß < С определяется принадлежность

N—*oo l<k<N

к «левой» (случаи, когда n.^max^a^ —> 0) или «правой» (если п, ^mm^a^ —► 00) области Формулируется условие «корректности» для целочисленных наборов пар {(r: i,r,2)}J=1 j набор называется корректным, если все величины rJt, являются неотрицательными при г = 1,2, J = 1, ,J, а для любых различных 1 <ji,ji < J

ВЫПОЛНЯеТСЯ ХОТЯ бы ОДНО ИЗ УСЛОВИЙ Глд ф T:2t 1, ИЛИ 2 ф Г)2,2

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

Пусть = ~ последовательность случайных векторов с це-

лыми неотрицательными компонентами, каждый из которых представлен в виде = vlN} = ,<)> к = 1, ,N, где компоненты ^ (j =

1, , J, к = 1, ,N) случайных векторов fjjjf', к = 1, , N, принимают лишь значения 0 и 1 Для упрощения формул, верхний индекс (N), связанный с этой схемой серий, далее не используется

Для произвольного мультииндекса тп = (mi, ,mj) е {0,1, }J будем рассматривать упорядоченные наборы = (а^(1), ,а7(т;)) е {1, ,N}m> (а} = 0 при mj = 0), j = 1, , J, и составленный из них набор а = (ai, ,aj) = (ai(l), .aiimO.asil), ,aj(mj)) Пусть A = A(m,N) = {1, ,JV}H - множество всех наборов a, соответствующих мультииндексу m, здесь \т\ = rri\ + + raj Будем называть набор бесповторным, если среди его элементов нет совпадающих Пусть В = B(m, N) С А — множество таких наборов a(m,N) = (ai, ,aj), что каждый набор а, бесповторный, а С = C(m, N) с В — множество бесповторных наборов а = а(Ш, N) Пусть

J т,

и

ba = P(Vj,a,(k) = 1. J = 1. ,J,/с=1, ,rn3) Теорема 1.3.1 Пусть для построенной схемы серий выполняются условия

N

шах Ьь' —» 0, hm Y^ = при j = 1, , J,

N—^oo J

1=1, ,J *=1

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

£

c,eB(m,N)\C(m,N)

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

Ьт тах

£-1

Ьа

•о,

■ е~х>

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

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

Теорема 1,4.1 Если при N оо для каждого г=1,2 выполняется условие принадлежности либо правой, либо левой области, а для случайного вектора ?= (£ь >0) (где = Мг^.г^ и набор пар ^ является коррект-

ным] выполнены условия

—► А; е (0, оо), 3 = \, ,7, то для любого набора в = (вх, € {1, , ИУ

'1

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

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

Во второй главе исследуется задача о появлении первой цепочки длины п с не более чем тп единицами в последовательности испытаний Бернул-ли Пусть £4, _ последовательность независимых случайных величин,

Р(6 = 1) =р, Р(£4 = 0) = <7 = 1 — р, 4 = 1,2, Для заданного т обозначим через Г„1ТП множество целочисленных наборов 7 = (71,72, ,7т) таких, что 1 < 71 < 72 < < 7т < п, и Г„,<т =' и Гп,к

к<т

Для заданных п, т и 7 6 Г„|т обозначим через е7 вектор размерности п, у которого координаты с номерами 7*, к 6 {1, ,т}, принимают значение 1, а все остальные - значение 0 Пусть Ап>т - множество всех таких е7, а Ап,<т у А^

к<та

То есть Ащ<т ~ множество двоичных векторов размерности п, в которых не более т координат имеют значение 1

Рассмотрим случайную величину

1~п,т — тт{4 > 1 ,6+п-0 е А.,<т}

- момент первого появления п-цепочки из множества в последовательности

, и случайный вектор

т

фп,т = если £т„т+о-1 = = 1,2, ,п,

*=1

- первый вектор из Ап,<т, появившийся в последовательности

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

В разделе 2.1 вводятся множества Г„,т, АП:<т, случайные величины гп т, фп<т и вводится постановка задачи

В разделе 2.2 проводится построение вспомогательной депи Маркова, вводятся случайные величины г1 "= Р {ф„,т = е7} и индексные операторы

^(7) = (71. ,7(-1,7£ + 1,7е-1, ,7т)^€М, РгЬ) = (г,1 + 7ь ,г + 7т-1), геК, тЬ) = Ы, .7т)

В случае т = 1 величины г7 также обозначаются как 2к, если к = 71 Лемма Если набор 7 6 Гп,т, то

"~7т

г7 = Рт<гт + £ ^мрв'"1 >=1

í < т, то

П—1т 1=1

а если < = т, то

¿1 - 7) = рдп"7т"12РП-,„(7) 8

В разделе 2 3 рассматриваются распределения фПуi

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

21 2 = Yq 0 + q ~ p2qn~1 ± \/(1 + -?-Р2?"-1)2-45) Теорема 2 3 1 Если ф Х2, то

pqn+m-inj2 Rt_m + (i _

__t=i_

¿n—m. ~ n—l >

Eft

1=1

где Rm = rW — zW, если же xi = X2, то 2 X1

+ (1 _ g-»)^

2 =_íñí_

E д£

t=l

где Rm--=-Zbt xi

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

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

р{п) < с < 1 и пр(п) —» оо, п -

Тогда

1-ак

Р{Фп,1 = en„k(n)} =-V + 0 №).

п~р

причем остаточный член допускает равномерную по к € {1, ,п — 1} оценку Если при этом р(п) = о(1) и к(п)р(п) = о(1), то

ПФпЛ = en_k(n)} = p<f + -^т + О + пруЛ га — -1 V га /

р \ /

Кроме того,

Р{^д = е0} = о(1)

Теорема 2 3 3 При предельном переходе д(п) = 1 - ~ 4- о(^), ^ —► Ь, при п —* оо, где £ € [0,1], существует

причем при с > In 4

при с < 1п(4)

а при с = 1п(4)

lim (nP{<£„,i = en_k(n)}) = F(c,t),

п—> оо 4 '

F(c,t) - ce"'

А (И) >

sin

F(c,t) = c2-<->2—C+-2tc

2-е '

где U\ = arcch ^ = arccos (iTi) uV= IVI1 ~ 4е_с1

Кроме того, = е0} = 4- о(1)

Теорема 2.3.4 При предельном переходе р{п) = о

Р{Фп,1 = ек(п)} = р(1 - (к - 1)р + 0(п2р2))

и

Р{ф„,1 = е0} = 1 -пр + о(пр)

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

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

п-1 т / n-7m_l / п-71 \ \

* = Е Е (9n_m)

•m = l \wi=>m+l Ч Ч=>2 + 1 / J

Теорема 2.4.1 Пусть п —► оо, а величина р = р(п) изменяется таким образом, что

р(п)п —> сх> и р(п) < 1 — С 10

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

В этом случае при фиксированном т>2 и 7 € Гп т справедливы асимптотические соотношения

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

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

В этом случае при 7 б Гп.,2 справедливы асимптотические соотношения

Теорема 2 4 3 Если пр —> 0 при п —» оо то для 7 € Г„,т справедлива асимптотическая формула

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

В приложениях приводятся таблицы и графики значений функции ^(с, £), величины р7 при тп = 1 и т = 2, а также точных и приближенных значений г7 при т— 1

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

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

2

г7 = ртдп-т + (п - тт)рт+1 + О {(рп)т+2)

Публикации автора по теме диссертации

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

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

[4] Гаас В В, Зубков А М Распределение первой п-цепочки с малым числом единиц в бернуллиевской последовательности — Обозр прикл и промышл матем , 2002, т 9, в 2, с 353

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

Издательство ЦПИ при механико-математическом факультете МГУ им М В Ломоносова

Подписано в печать 26-ОЬ, 0£ Формат 60x90 1/16 Уел печ л 0,?5~ Тираж {00 экз Заказ

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета

Оглавление

Введение

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

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

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

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

1.4 Сходимости статистик ^Гьг2.

1.5 Свойства статистик /лП)Г

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

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

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

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

2.3 Распределение </>п>1.

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

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

2.3.3 Предельные теоремы для фпд.

2.3.4 Случай пр(п) —> оо.

2.3.5 Случай пр(п) —►с.

2.3.6 Случай пр(п) 0.

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

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

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

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

2.4.2 Случай пр{п) оо.

2.4.3 Случай пр(п) —> оо для фп>2.

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

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

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

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

Одной из наиболее характерных тем комбинаторной теории вероятностей является т.н. «классическая задача о дробинках» и многочисленные ее обобщения, разрабатываемые как отечественными, так и зарубежными авторами (см., например, [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.), на семинаре отдела дискретной математики МИРАН им. Стеклова (20032008гг.), семинаре «Дискретные задачи теории вероятностей» (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<k<N к J k=l,.,N L щ ^ min—> оо. Для этого формулируется и доказывается обобщение теок ремы Б.А. Севастьянова о сходимости сумм зависимых индикаторов к пуас-соновским распределениям на суммы случайных векторов.

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

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

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

N—+00 1 <k<N надлежность к «левой» (случаи, когда щ ^ ~* или «пРавой» (если щ min —> оо) области. Формулируется условие «корректности» для целочисленных наборов пар {(г/д,т^2)}.=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 aeC\D

Ьа 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<m - множество двоичных векторов размерности к<т п, в которых не более т координат имеют значение 1. Рассмотрим случайную величину

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

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

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

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

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

В разделе 2.1 вводятся множества ГП:ГП, Anj<m, случайные величины тП)77г, фп,т и вводится постановка задачи.

В разделе 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 Е ГП;ТП; то

П-П/т

- „шгг-т г \ л „„г—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 + О (М™+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