Комбинаторные методы изучения случайных индикаторов

• Автор: Толовиков, Михаил Игоревич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2002
• Место защиты: Москва
• Количество страниц: 124 с.

Содержание
Введение

Г лава 1. Методы включения и исключения

§1. Предварительные сведения о производящих функциях

§2. Основная комбинаторная теорема

§3. Г омоморфизмы локально конечных полугрупп

и колец производящих функций

§4. Следствия из основной комбинаторной теоремы

§5. Приложения основной комбинаторной теоремы

Г лава 2. Представление последовательностей случайных индикаторов осцилирующими случайными блужданиями
§1. Осцилирующее случайное блуждание
и основная комбинаторная лемма
§2. Урновые схемы и показательно распределённые величины
§3. Последовательности 1-зависимых индикаторов и
осцилирующие случайные блуждания
§4. Предельные теоремы и асимптотические формулы
Заключение
Литература

Введение
1. Многие комбинаторные и вероятностные задачи естественным образом можно сформулировать на языке случайных индикаторов. Пусть ('О.З./у -
вероятностное пространство. Случайным индикатором называется случайная величина 1, определённая на этом пространстве, и принимающая только два значения - 0 и 1. Введём в рассмотрение событие А = {сое £2 |/(со) =1}. Тогда / действительно является индикатором события А.
Случайные индикаторы подвергаются в последнее время интенсивному изучению в нескольких направлениях. Все вместе их можно объединить под названием «предельные теоремы, асимптотические формулы и явные оценки для распределений сумм случайных индикаторов». Существует также большое число работ, в которых изучение распределений сумм случайных индикаторов применяется к решению конкретных комбинаторных и вероятностных задач. Следует отметить, что в большинстве из этих задач изучаемые случайные индикаторы оказываются зависимыми. Способ описания зависимости случайных индикаторов и тип зависимости определяют при этом применяемый метод исследования. Если удаётся получить явный вид производящей функции для сумм соответствующих индикаторов, то применяются такие методы, как метод перевала. В общей постановке как правило накладываются ограничения на совместные распределения и моменты подвергаемых изучению случайных величин, а соответствующие предельные теоремы, асимптотические формулы и оценки зависят от тех или иных относительно просто вычисляемых или оцениваемых характеристик этих случайных величин. Наконец, в некоторых случаях удаётся свести изучение сумм зависимых случайных индикаторов к изучению сумм независимых случайных величин. Обзор методов и результатов, относящихся к суммам случайных индикатором, можно найти, например, в статье [И].
В настоящей работе рассматривается несколько методов изучения распределений случайных индикаторов, которые мы объединили под названием «комбинаторные». В первой главе - это метод производящих функций и метод включения и исключения. Во второй главе применяется несколько специфических методов, основанных на комбинаторных тождествах для характеристических
функций, а также одной комбинаторной лемме, которая по существу представляет собой утверждение об эквивалентности систем линейных неравенств. Методы главы 2 имеют единую цель: выразить распределения сумм зависимых индикаторов через распределения сумм независимых случайных величин. Последнее позволяет для изучения асимптотического поведения и оценивания распределений сумм таких индикаторов применять известные результаты, относящиеся к суммам независимых случайных величин. Несколько примеров такого образа действий приводится в последнем параграфе главы 2. Далее мы перечислим источники, от которых мы отправлялись в своих исследованиях, и сформулируем основные результаты, полученные в работе.
2. Гессель в своей диссертации [21] решила следующую задачу. Пусть множество IV2 всех упорядоченных пар натуральных чисел разбито на два непустых непересекающихся подмножества: N2 = л, и я, • Рассмотрим множество всех
конечных последовательностей натуральных чисел. Каждой такой последовательности а,,...,а„ поставим в соответствие слово уу в алфавите {0,1} следующим образом: если (о,.,о|Ч1)е л,, то а если (а,.,ст,.+1)е п2, то щ =1,
г =1,2,...,«-1. Здесь есть г-я буква слова ю. Пусть В = {0,1}, В* есть множество всех слов в алфавите В, Z{t1,t2,...} есть коммутативное кольцо всех формальных степенных рядов от переменных ?рг2,... с целыми коэффициентами. Определим функцию Аследующим образом: слову и>е В* поставим в
соответствие сумму по всем последовательностям ах,...,оп, которым соответствует слово V/, одночленов г,*1?*2.../*", где к1 есть число элементов { в последовательности о,,...,сг„; А(А) = 1. Рассмотрим производящие функции д(у) = Х>а>У, и

ао(У) = ХЛ(1)У„ где А)(1)= (—1)г<,) А(0М) для всех 1. (Здесь у = (у0,у,, у2,...);

1 = (10,; у, = у,0у(, ...у1п; А(1) = А(0;110/21... 10г"); (Ресть слово из г нулей; |1|=/[ +1г + +п-1; 5(1) = и-1; суммирование ведётся по всем упорядоченным
п-м 1 = неотрицательных целых чисел для всех пс N .) Эти производящие
функции представляют собой формальные степенные ряды с коэффициентами из кольца Z{tl,t2,...} от переменных у0,у,,у2,—, которые могут как коммутировать, так и

полугруппы N каждый такой элемент представим в виде произведения ру, р,уеЛ?{0}, лишь конечным числом способов. Следовательно, число пар р. у таких, что ф(ру) = а', конечно. Получили противоречие. Этим доказано, что полугруппа 1тф локально конечна. Предложение доказано.
Предложение 2. Если ф: N -> N' изоморфизм полугрупп с нулём, переводящий нулевой элемент первой полугруппы в нулевой элемент второй полугруппы, ТО ф является локально конечным гомоморфизмом. В частности, тождественное отображение локально конечной полугруппы с нулём на себя является локально конечным гомоморфизмом.
Доказательство этого предложения очевидно.
Предложение 3. Композиция локально конечных гомоморфизмов полугрупп с нулём есть локально конечный гомоморфизм полугрупп с нулём.
Доказательство этого предложения очевидно.
Предложение 4. 1) Пусть ф - локально конечный гомоморфизм локально конечной полугруппы с нулём N в локально конечную полугруппу с нулём N'. Пусть отображение фЛ : /?/Г —> Ш', определено по формуле
ф* (/)(«’)= £/(«) с1)
а£ф-1(а’)
для любых /е Л/У, а’е N’40’} (если фч(а') пусто, то сумму считаем равной нулю). Тогда <р(( является локально конечным гомоморфизмом RN в /М'1.
2) Обратно, пусть ф - отображение локально конечной полугруппы с нулём N в локально конечную полугруппу с нулём N1, такое, что ф(0) = 0', где 0 и 0' -нулевые элементы полугрупп N и ЛГ соответственно, и отображение фк : NN —> /?/У", определённое по формуле (1), является локально конечным гомоморфизмом NN в Ж'. Тогда ф - локально конечный гомоморфизм N в ТУ'.
Определение 3. Определённый в первой части предложения 4 гомоморфизм ФЛ мы будем называть гомоморфизмом, порождённым гомоморфизмом ф.
Доказательство. 1) Пусть ф - локально конечный гомоморфизм локально конечной полугруппы с нулём N в локально конечную полугруппу с нулём N . Докажем, что фй является гомоморфизмом колец. Для любых /, # е NN, любого а'е ЛЛ{0’}