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

На правах рукописи

Тихомирова.Маргарита Игоревна

Предельные теоремы для числа непоявившихся в-цепочек

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

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

Москва 1998

Работа выполнена на кафедре теории вероятностей и математической статистики факультета прикладной математики Московского государственного института электроники и математики (технического университета).

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

профессор Чистяков В.П.

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

профессор Медведев Ю.И., кандидат физико-математических наук, доцент Гладков Б.В.

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

Защита состоится " 10 " ноября 1998 года в 16 часов на заседании диссертационного совета К 063.68.05 в Московском государственном институте электроники и математики по адресу: 109028, ГСП, Москва, Б.Трехсвятительский переулок, д. 3/12, зал Ученого Совета.

С диссертацией можно ознакомиться в библиотеке института.

Автореферат разослан "С1 " октября 1998 года.

Ученый секретарь

диссертационного совета К 063.68.05 в МГИЭМ ^—.пц

кандидат физико-математических наук, ' <77

доцент Шнурков П.В.

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Среди многочисленных работ по комбинаторным задачам и методам теории вероятностей значительное место занимают работы, посвященые задачам размещения частиц по ячейкам. После опубликования книги В.Ф.Колчина, Б.А.Севастьянова, В.П.Чистякова1), в которой были собраны известные к тому времени результаты, количество новых работ по этой тематике продолжало расти. Интерес к ней объясняется многочисленными применениями схемы случайных размещений в самых различных областях: математическая статистика, теория автоматов, теоретическая криптография, статистическая физика, вычислительная техника, астрономия, биология и т.п. Среди задач этого направления наиболее известна классическая задача о дробипках: п дробинок независимо друг от друга бросают в N ящиков; исследуется случайная величина ро, равная числу ящиков, оставшихся пустыми. Формула для распределения числа пустых ящиков //0 даже в простейшем классическом случае (дробинки размещаются независимо и равновероятно) достаточно сложна. В таких случаях обычно используются предельные теоремы, где параметры изменяются каким-либо заданным способом. В классическом случае три основных типа поведения распределения величины цо определяются тремя областями изменения параметров п, N (п, N —> оо). 1°. Центральная область: а = n/N, 0 < «1 < а < а-> < оо. 2°. Правая область: а = n/N\ а = In N — In Л + о(1), А = const. 3°. Левая область: n2/(2N) —> А, 0 < А < оо.

В центральной области величина Цо асимптотически нормальна, а в правой и левой областях предельные распределения величин /Iq и (to — N + п имеют распределение Пуассона.

Выделяются также две промежуточные области: 4°. Левая промежуточная область: о —> 0, Na2/2 —оо. 5°. Правая промежуточная область: а —> оо, « — IniV —> —оо.

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

В этих областях случайная величина асимптотически нормальна.

В более сложных схемах размещения распределение зависит от большего числа параметров. Однако основные типы поведения величины цо сохраняются в более сложных схемах и определяются соответствующими аналогами областей изменения параметров 1°-5°. Эти аналоги областей легко установить для других схем размещения если условия, определяющие области 1°-5°, переписать в терминах поведения Ецо и D/i0.

Во всех изученных случаях наиболее сложными оказались исследования, относящиеся к центральной области изменения парам-тров. Достаточно полно проведены исследования асимптотического поведепия ßo Для случая, когда частицы размещаются по ячейкам по полиномиальной схеме. Для марковских размещений были получены лишь отдельные результаты в работах Беляева П.Ф., Колчи-на В.Ф., Чистякова В.П. и других авторов. Величины /хг являются частным случаем более общих величин (разделимых статистик), введенных в работах Медведева Ю.И.2\ Ивченко Г.И.;!) Исследования разделимых статистик были продолясепы в работах Михайлова В.Г., Karlin S., Ost F. и других авторов. Значительные результаты в исследовании поведения величин f.ir, равных числу ячеек, содержащих ровно г частиц, были получены Зубковым A.M. и Михайловым В.Г. Зубковым A.M.'1) была доказана асимптотическая нормальность ßr (г > 0) в левой и правой промежуточных областях для марковских размещений. Михайлов В.Г.5) в центральной области

2) Медведев Ю.И. Разделимые статистики в полиномиальной схеме. Теория вероятностей и ее применения. I, 1977, т. 22, в. 1, 3-17; И, в. 3, 623-631.

Ивченко Г.И., Медведев Ю.И. Об оценке скорости сходимости в предельных теоремах для разделимых статистик. Теория вероятностей и ее применения, 1986, т. 31, в. 1, 91-97.

4) Зубков A.M. Неравенства для вероятностей переходов с запрещениями и их применения. Мат. сб., 1979, 109(151), No. 4(8), 491-532.

Михайлов В.Г. Асимптотическая нормальность разделимых статистик от частот m-цепочек. Дискретная математика, 1989, т. 1, в. 4, 92-103.

установил асимптотическую нормальность разделимых статистик от частот я-цепочек, заданных на последовательности независимых случайных величин со счетным множеством состояний. Последовательность «-цепочек образует цепь Маркова, а случайные величины \!.т являются разделимыми статистиками. Таким образом, из результатов Михайлова В.Г. можно получить утверждение об асимптотической нормальности величин /«,. в центральной области для цепей Маркова, образованных «-цепочками. Однако проверка его теоремы о разделимых статистиках в ряде случаев сравнима по сложности с доказательством самой теоремы.

Знание распределения числа л-цепочек //0(В) из множества В С {(¿1,..., г.5): г/, = 1, 2,..., ¿У, к = 1,...,пепоявившихся в различных схемах размещения необходимо при использовании /хц(В) для исследования свойств дискретных случайных последовательностей.

Цель работы. Исследование предельных распределений числа пепоявившихся в-цепочек в полиномиальной схеме размещения и одной специальной марковской схеме размещения.

Методы исследования. При решении поставленных задач применялись вероятностные методы, общие предельные теоремы теории разделимых статистик, комбинаторные и асимптотические методы анализа.

Научная новизна. В диссертации получены следующие новые результаты:

1. В центральной области изменения параметров выведепы асимптотические формулы для первых двух моментов величины //0(Б) — числа ,ч-цепочек, отсутствующих в множестве В, и доказана асимптотическая нормальность этих величин для полиномиальной схемы размещения.

2. Доказана асимптотическая нормальность числа //0 исполнившихся состояний в цепи Маркова, описывающей размещение частиц по группам ячеек с полиномиальным размещением внутри групп. Эта схема размещения обобщает схему размещения Колчипа В.Ф. и Чистякова В.п.6).

6' Колчин В.Ф., Чистяков В.П. Новые предельные распределения

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

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

5. Вычислены ошибки первого и второго родов статистических критериев, основанных на статистиках, описанных в пп. 1-4, при сближении конкурирующей гипотезы с основной.

Практическая значимость. Последовательность я-цепочек часто возникает при изучении конечных автоматов, предназначенных для выработки случайных последовательностей. Одним из распространенных узлов таких автоматов является регистр сдвига7^. Теоремы об асимптотическом поведении /ло(£>) оказываются полезными при исследовании автоматов. Рассмотрение ограниченного множества 5-цепочек В может быть полезным при построении некоторых статистических критериев8^.

Публикации и апробация работы. Основные результаты опубликованы в 1992, 1995, 1997 годах в работах, список которых приведен в конце автореферата.

Результаты диссертации докладывались на семинаре по вероятностным методам дискретной математики в Математическом институте имени В.А.Стеклова Российской Академии наук.

Структура и объем работы. Работа занимает 87 страниц, состоит из введения, трех глав и списка литературы, содержащего 19 наименований.

в задачах о размещении. Труды МИЭМ, 1973, т. 32, 65-72

Михайлов В.Г., Чистяков В.П. О задачах теории конечных автоматов, связанных с числом прообразов выходной последовательности. ОППМ, 1994, т. 1, в. 1, 7-32.

8) Башарин Г.П. Об использовании критерия согласия %2 в качестве критерия независимости испытаний. Теория вероятностей и ее применения, 1957, т. 2, в. 1, 141-142.

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

В первой главе изучается поведение распределений числа не-появившихся .s-цепочек, образованных из последовательности независимых случайных величин 71,72,.... 7п,.. ■ , принимающих значения 1,2,..., Лг с вероятностями р^ = Р{7„ = к}, к = 1,2,..., N, л = 1,2,...; 1 Рк = 1- Первые п, + s — 1 членов этой последовательности образуют п .s-цепочек г;ь i]2,.. .,?;„, где jjt = (7t,7i+1,. .., Тг+.s-1), t = 1,2, ...,n. Обозначим А множество всех возможных значений .у-цепочек А = {I = (ч, г2,..., г4): 1 < ik < N, к = 1, 2,..., ■•>}. Определим случайные величины /'r(i>) = Thi^B^P- v = "Л; ГДе

Случайная величина ра{В) является числом пополнившихся ь-цепочек из множества В среди первых п + 5—1 членов последовательности {г;<}. При В = А и я = 1 /1о(В) является числом пустых ячеек.

Асимптотическое поведение ц0 (В) исследуется в центральной области, определяемой следующими условиями изменения параметров п, IV, {ра.}:

где «о, а\,С >0 — некоторые постоянные.

Основным результатом главы 1 являются асимптотические формулы в схеме серий (1) для моментов Е//.о(£>), Е//.0(£>)(/(о(Б) — 1), Б/ЦБ) (теоремы 1.1, 1.2, 1.3).

В С А. I = (i 1,.. .,гя),

.s-цепочка 1 встречается г раз; в остальных случаях.

Npk < С < оо, к = 1,2,..., Л/,

(1)

Приведем асимптотические формулы для Е/х0($) и ТУ/л^В) в двух частных случаях при р» = 1/7У(г = 1,...,^), когда В = Л, В = Аь, где А — множество всех я-цепочек,

Л., — {I- I € А, все ¿1,..., г., различны}.

Если выполнены условия (1), то при любом 6 > 0 справедливо следующие асимптотические формулы:

Е,0(А) = ЛГИе- - с- + О ,

О,10(А) = №оЪ(а) + 0(ЛГ"1+<), Б/хоМ) = + 0(М*~1+Ь),

где а%(а) = е'а{1 - (1 + а)е~а).

Асимптотические формулы позволяют установить асимтотиче-скую нормальность Цо(В) (теорема 1.5).

Сложность получения этих формул сравнима со сложностью доказательства теоремы Михайлова В.Г.

Асимптотическая формула для моментов ¡1о(А) была получена автором в работе [1] и основана на исследовании уравнений в конечных разностях для вероятности непоявления данной й-цепочки. В диссертации изложен более простой (комбинаторный) подход, основанный на анализе формул включения-исключения [2].

Во второй главе диссертации рассматривается марковская схема размещения, обобщающая схему размещения, предложенную Колчиным В.Ф., Чистяковым В.II. Предполагается, что частицы размещаются по г группам, содержащим N1,..., Ыг ячеек, согласно цени Маркова, а размещение час тиц, попавших в группы, остается полиномиальным. В работе Колчина В.Ф., Чистякова В.П. рассматривались только равновероятные размещения внутри групп. Рассматриваемые в диссертации размещения являются цепью Маркова, состояниями которой будут пары: номер группы и номер ячейки в группе. Распределение величины /.¿о — числа непоявившихся

состояний — изучается в центральной области (теорема 2.1). Таким образом, установлена асимптотическая нормальность цо в центральной области для более широкого класса марковских размещений; и правой промежуточной области исследуется число исполнившихся «-цепочек состояний (теорема 2.2); в левой промежуточной области изучается величина Ц2{Л) ~ число .5-цепочек состояний, появившихся ровно два раза (теорема 2.3). Приведенные во второй главе теоремы содержатся в работе [3].

Результаты, полученные в первой и второй главах, в третьей главе применяются к построению и исследованию статистических критериев, основанных на величинах /¿о и /¿2. По основной гипотезе Но последовательность {'/„} является независимой и равновероятной. В качестве конкурирующей гипотезы II1 о размещении частиц рассмотрены два случая: полиномиальное размещение и марковское размещение, описанное во второй главе, с дважды стохастической , матрицей вероятностей переходов, управляющей размещением но ячейкам. Изучаются характеристики критериев в том случае, когда распределения по гипотезам Но и Н\ сближаются. Показано, что критерий пустых ящиков не выявляет марковскую зависимость. В этом случае можно использовать критерий со статистикой, равной числу непоявившихся л-цепочек (я > 1). Критерий пепоявившихся л-цепочек (я > 1) и критерий пустых ящиков при различении полиномиальных и равновероятных размещений допускают одинаковую скорость сближения проверяемых гипотез, при которой возможно различение.

Автор выражает глубокую благодарность своему научному руководителю Чистякову В.11. за постоянное внимание к работе.

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

1. Тихомирова М.И. Об асимптотической нормальности числа непоявившихся .«¡-цепочек. Дискретная математика, 1992, т. 4, в. 2,

2. Тихомирова М.И., Чистяков В.П. Об асимптотике моментов числа непоявившихся л-цепочек. Дискретная математика, 1997, т. 9, в. 1, 12-29.

3. Тихомирова М.И., Чистяков В.II. Об одной схеме марковских размещений по группам ячеек. Дискретная математика, 1995, т. 7, в. 2, 131-139.

122-129.