Введение к работе
Актуальность темы. Среди многочисленных работ по комби
наторным задачам и методам теории вероятностей значительное ме
сто занимают работы, посвященые задачам размещения частиц по
ячейкам. После опубликования книги В.Ф.Колчина, Б.А.Севасть
янова, В.П.Чистякова1-', в которой были собраны известные к то
му времени результаты, количество новых работ по этой темати
ке продолжало расти. Интерес к ней объясняется многочисленны
ми применениями схемы случайных размещений в самых различ
ных областях: математическая статистика, теория автоматов, тео
ретическая криптография, статистическая физика, вычислительная
техника, астрономия, биология и т.п. Среди задач этого направле
ния наиболее известна классическая задача о дробипках: п дроби
нок независимо друг от друга бросают в N ящиков; исследуется
случайная величина цо, равная числу ящиков, оставшихся пусты
ми. Формула для распределения числа пустых ящиков //0 даже в
простейшем классическом случае (дробинки размещаются незави
симо и равновероятно) достаточно сложна. В таких случаях обыч
но используются предельные теоремы, где параметры изменяются
каким-либо заданным способом. В классическом случае три основ
ных типа поведения распределения величины /Уо определяются тре
мя областями изменения параметров п, N (n,N —> сю).
1. Центральная область: a = n/N, 0 < «і < а < а-> < оо.
2. Правая область: a = n/N; a = h\N — In A + о(1), A = const.
3. Левая область: n2/(2N) -* А, 0 < А < оо.
В центральной области величина Цо асимптотически нормальна, а в правой и левой областях предельные распределения величин /1q и (to — N + п имеют распределение Пуассона.
Выделяются также две промежуточные области: 4. Левая промежуточная область: о —> 0, Nor/2 —- со. 5. Правая промежуточная область: а —> оо, а — lniV —> —оо.
х) Колчип В.Ф., Севастьянов Б.А., Чистяков В.П. Случайные размещения. Наука, Москва, 1976.
В этих областях случайная величина fj,Q асимптотически нормальна.
В более сложных схемах размещения расіфєделение ц0 зависит от большего числа параметров. Однако основные типы поведения величины цо сохраняются в более сложных схемах и определяются соответствующими аналогами областей изменения параметров 1-5. Эти аналоги областей легко установить для других схем размещения если условия, определяющие области 1-5, переписать в терминах поведения Е//о и D/i0.
Во всех изученных случаях наиболее сложными оказались исследования, относящиеся к центральной области изменения парам-тров. Достаточно полно проведены исследования асимптотического поведепия fio Для случая, когда частицы размещаются по ячейкам по полиномиальной схеме. Для марковских размещений были получены лишь отдельные результаты в работах Беляева П.Ф., Колчи-на В.Ф., Чистякова В.П. и других авторов. Величины /хг являются частным случаем более общих величин (разделимых статистик), введенных в работах Медведева Ю.И.2', Ивченко Г.И.'!' Исследования разделимых статистик были продолясены в работах Михайлова В.Г., Karliu S., Ost F. и других авторов. Значительные результаты в исследовании поведения величин /.ir, равных числу ячеек, содержащих ровно г частиц, были получены Зубковым A.M. и Михайловым В.Г. Зубковым A.M.4) была доказана асимптотическая нормальность Иг (г > 0) в левой и правой промежуточных областях для марковских размещений. Михайлов В.Г.5) в центральной области
2) Медведев Ю.И. Разделимые статистики в полиномиальной схе
ме. Теория вероятностей и ее применения. I, 1977, т. 22, в. 1, 3-17;
И, в. 3, 623-631.
3) Ивченко Г.И., Медведев Ю.И. Об оценке скорости сходимости
в предельных теоремах для разделимых статистик. Теория вероят
ностей и ее применения, 1986, т. 31, в. 1, 91-97.
4) Зубков A.M. Неравенства для вероятностей переходов с запре
щениями и их применения. Мат. сб., 1979, 109(151), No. 4(8), 491-532.
5) Михайлов В.Г. Асимптотическая нормальность разделимых
статистик от частот т-цепочек. Дискретная математика, 1989, т. 1,
в. 4, 92-103.
установил асимптотическую нормальность разделимых статистик от частот s-цепочек, заданных на последовательности независимых случайных величин со счетным множеством состояний. Последовательность .s-цепочек образует цепь Маркова, а случайные величины \і.т являются разделимыми статистиками. Таким образом, из результатов Михайлова В.Г. можно получить утверждение об асимптотической нормальности величин /<т. в центральной области для цепей Маркова, образованных s-цепочками. Однако проверка его теоремы о разделимых статистиках в ряде случаев сравнима по сложности с доказательством самой теоремы.
Знание распределения числа .s-цепочек Цо{В) из множества В С {(гі, ...,is): ik — 1, 2,..., N, к = 1,..., s} исполнившихся в различных схемах размещения необходимо при использовании fio(B) для исследования свойств дискретных случайных последовательностей.
Цель работы. Исследование предельных распределений числа непоявившихся s-цеіючек в полиномиальной схеме размещения и одной специальной марковской схеме размещения.
Методы исследования. При решении поставленных задач применялись вероятностные методы, общие предельные теоремы теории разделимых статистик, комбинаторные и асимптотические методы анализа.
Научная новизна. В диссертации получены следующие новые результаты:
1. В центральной области изменения параметров выведепы асим
птотические формулы для первых двух моментов величины /'о(й) —
числа .s-цепочек, отсутствующих в множестве В, и доказана асим
птотическая нормальность этих величин для полиномиальной схе
мы размещения.
2. Доказана асимптотическая нормальность числа//0 непоявивших
ся состояний в цепи Маркова, описывающей размещение частиц по
группам ячеек с полиномиальным размещением внутри групп. Эта
схема размещения обобщает схему размещения Колчипа В.Ф. и Чи
стякова В.п.6).
6' Колчин В.Ф., Чистяков В.П. Новые предельные распределения
-
Доказана асимптотическая нормальность числа непоявилшихся s-цепочек состояний в правой промежуточной области для схемы размещений, описанной в п. 2.
-
В левой промежуточной области для схемы размещений, описанной в п. 2, доказана асимптотическая нормальность числа s-цепочек состояний, появившихся ровно два раза.
-
Вычислены ошибки первого и второго родов статистических критериев, основанных на статистиках, описанных в пп. 1-4, при сближении конкурирующей гипотезы с основной.
Практическая значимость. Последовательность s-цспочек часто возникает при изучении конечных автоматов, предназначенных для выработки случайных последовательностей. Одним из распространенных узлов таких автоматов является регистр сдвига7^. Теоремы об асимптотическом поведении /іо(>) оказываются полезными при исследовании автоматов. Рассмотрение ограниченного множества s-цепочек В может быть полезным при построении некоторых статистических критериев8^.
Публикации и апробация работы. Основные результаты опубликованы в 1992, 1995, 1997 годах в работах, список которых приведен в конце автореферата.
Результаты диссертации докладывались на семинаре по вероятностным методам дискретной математики в Математическом институте имени В.А.Стеклова Российской Академии наук.
Структура и объем работы. Работа занимает 87 страниц, состоит из введения, трех глав и списка литературы, содержащего 19 наименований.
в задачах о размещении. Труды МИЭМ, 1973, т. 32, 65-72
7) Михайлов В.Г., Чистяков В.П. О задачах теории конечных ав
томатов, связанных с числом прообразоБ выходной последователь
ности. ОППМ, 1994, т. 1, в. 1, 7-32.
8) Башарин Г.П. Об использовании критерия согласия %2 в каче
стве критерия независимости испытаний. Теория вероятностей и ее
применения, 1957, т. 2, в. 1, 141-142.
