Комбинаторные методы изучения случайных индикаторов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

Введение

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

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

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

§3. Гомоморфизмы локально конечных полугрупп и колец производящих функций

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

1. Многие комбинаторные и вероятностные задачи естественным образом можно сформулировать на языке случайных индикаторов. Пусть (Q,3,P) -вероятностное пространство. Случайным индикатором называется случайная величина 1, определённая на этом пространстве, и принимающая только два значения - 0 и 1. Введём в рассмотрение событие А = {сое Q |/(со) =1}. Тогда / действительно является индикатором события А.

Случайные индикаторы подвергаются в последнее время интенсивному изучению в нескольких направлениях. Все вместе их можно объединить под названием «предельные теоремы, асимптотические формулы и явные оценки для распределений сумм случайных индикаторов». Существует также большое число работ, в которых изучение распределений сумм случайных индикаторов применяется к решению конкретных комбинаторных и вероятностных задач. Следует отметить, что в большинстве из этих задач изучаемые случайные индикаторы оказываются зависимыми. Способ описания зависимости случайных индикаторов и тип зависимости определяют при этом применяемый метод исследования. Если удаётся получить явный вид производящей функции для сумм соответствующих индикаторов, то применяются такие методы, как метод перевала. В общей постановке как правило накладываются ограничения на совместные распределения и моменты подвергаемых изучению случайных величин, а соответствующие предельные теоремы, асимптотические формулы и оценки зависят от тех или иных относительно просто вычисляемых или оцениваемых характеристик этих случайных величин. Наконец, в некоторых случаях удаётся свести изучение сумм зависимых случайных индикаторов к изучению сумм независимых случайных величин. Обзор методов и результатов, относящихся к суммам случайных индикатором, можно найти, например, в статье [11].

В настоящей работе рассматривается несколько методов изучения распределений случайных индикаторов, которые мы объединили под названием «комбинаторные». В первой главе - это метод производящих функций и метод включения и исключения. Во второй главе применяется несколько специфических методов, основанных на комбинаторных тождествах для характеристических функций, а также одной комбинаторной лемме, которая по существу представляет собой утверждение об эквивалентности систем линейных неравенств. Методы главы 2 имеют единую цель: выразить распределения сумм зависимых индикаторов через распределения сумм независимых случайных величин. Последнее позволяет для изучения асимптотического поведения и оценивания распределений сумм таких индикаторов применять известные результаты, относящиеся к суммам независимых случайных величин. Несколько примеров такого образа действий приводится в последнем параграфе главы 2. Далее мы перечислим источники, от которых мы отправлялись в своих исследованиях, и сформулируем основные результаты, полученные в работе.

2. Гессель в своей диссертации [21] решила следующую задачу. Пусть множество N2 всех упорядоченных пар натуральных чисел разбито на два непустых непересекающихся подмножества: N2=7t,U7t2. Рассмотрим множество всех конечных последовательностей натуральных чисел. Каждой такой последовательности cTj ,.,сти поставим в соответствие слово w в алфавите {0,1} следующим образом: если (о.,о,Ч1)е и,, то wt = 0, а если (а,.,ai+l)е п2, то w, = 1, i = \,2,.,n-\. Здесь wt есть i-я буква слова Пусть 5 = {ОД}, В* есть множество всех слов в алфавите В, Z{t1,t2,.} есть коммутативное кольцо всех формальных степенных рядов от переменных tl,t2,. с целыми коэффициентами. Определим функцию А: В*—> Z{tx,t2,.} следующим образом: слову we В* поставим в соответствие сумму по всем последовательностям <зх,.,ап, которым соответствует слово w, одночленов , где к; есть число элементов i в последовательности о,,.,сп; А(Л) = 1. Рассмотрим производящие функции а(у) = ]ГА(1)у, и I a0(y) = ^A0(l)y,, где А0(1) = (-1)5(1)А(0|") для всех I. (Здесь у = (у0,у],у2,.); 1

1 = (/0,/„.,гл); у, =ylQytl.yln-, А(1) = А(0/110,21.10''г); 0гесть слово из г нулей;

111=^ +l2 + . + ln+ п -1; 5(1) -п-1; суммирование ведётся по всем упорядоченным п-м 1 = (/0,/, ,.,/„) неотрицательных целых чисел для всех пе N .) Эти производящие функции представляют собой формальные степенные ряды с коэффициентами из кольца Z{/,,/2,.} от переменных у0,у},у2,., которые могут как коммутировать, так и не коммутировать друг с другом. Требуется определить производящую функцию а{у). Ответ даёт следующая теорема, которая носит название теоремы о максимальном цепном представлении (в формулировке мы используем свои обозначения; у Гессель они отличаются от наших).

Теорема о максимальном цепном представлении. ([21], [4]) Имеет место равенство производящих функций я(У) = ао(у)0--ао(у)У1 ■

Из этой теоремы путём подходящих подстановок вместо переменных y0,yvy2,. каких-либо выражений можно получить много конкретных результатов, относящихся к комбинаторике последовательностей. На русском языке изложение этих результатов имеется в [4].

3. В первой главе нашей работы даётся новое доказательство теоремы о максимальном цепном представлении и производится её обобщение. Именно, мы рассматриваем произвольные функции А: В* —> R, где R есть кольцо с единицей, не обязательно коммутативное, удовлетворяющие условию: для любых слов u,ve В*

A(w0v)4 A(wlv) = A{u)A(v). (1)

Основой всех приложений является доказанная нами теорема 1 §1 главы 1. Для её формулировки необходимы следующие определения и обозначения.

Определение. (Определение 1 §1 главы 1). Пусть В = {0,1}. По определению В* есть полугруппа с нулём, состоящая из всех слов в алфавите В, включая и пустое слово, и нуля, присоединённого к ней внешним образом, с операцией умножения ш, определяемой по формуле umv = ulv для всех слов u,veB* (ноль обозначается символом 0 и по определению словом не является), 0ши = ишО = 0 для всех ие В*-, Ве * по определению есть полугруппа с нулём, получаемая присоединением внешней единицы е к полугруппе В*, то есть Ве* = В*UM, где е£В*, и еще = е, щ не - emu =и для всех ие В*; единица е также по определению словом не является.

Кольцо RBe * определяется следующим образом.

Определение. Пусть R - кольцо с единицей, не обязательно коммутативное. Кольцом производящих функций полугруппы Ве * над кольцом R называется множество RBe * всех функций, определённых на множестве Ве * и принимающих значения из R. Операции над функциями определяются следующим образом: + g)(w) = f(w) + g(w), (/ * g)(w) = £ /(M)g(v) для всех we Bc*.

Кольцо RB * определяется как подкольцо кольца RBe *, состоящее из всех функций, принимающих нулевое значение на элементе ее Ве*. RBe * есть кольцо с единицей. Единицей этого кольца будет функция, принимающая значение 1 е R на элементе ееВе* и значение Об R на остальных элементах полугруппы Ве*. Эту функцию мы будем обозначать также символом 1. Кроме того, нам нужны обозначения: | w | - число букв в слове we В *; j'(w) - число единиц в слове we В*; Ае В* - пустое слово, не содержащее ни одной буквы; w" - слово, полученное п - кратным повторением слова we В*, пе N, = А. Теорема (теорема 1 §2 главы 1). Пусть Ае RB* и функция А0 определяется по формуле А0 (w) = (-1)!(w) А( 0м) для всех we Ве *\{0}. Тогда следующие условия эквивалентны.

1. Для любых слов u,vе В*

A(u0v) + A(ulv) = A(u)A{v).

2. Для любого слова we В*

A{w) - A(m)(-1)s(v) A(0|v| ) + (-1)s(w) А(0М). l]v=w

3. А = А * А0 +- А0.

4. Элемент 1 - А0 имеет обратный в кольце RBe * и А = А0 * (1 - А0).

5. Элемент 1 + А имеет обратный в кольце RBe * и А0 = А*(1+ А)"1.

6. Для любого слова we В*

Н+1

A(w) = £ £(-1)5(№1)+'-'+5("*М(0ь,).А(0ы) м>(Фе здесь при k = l полагаем иуп.-ши^ =w).

Эта теорема допускает другую формулировку, одно из утверждений которой по форме совпадает с теоремой о максимальном цепном представлении. Чтобы привести её, нам понадобятся следующие построения.

Полугруппа Ве *\{0} есть свободная некоммутативная полугруппа с единицей над счётным множеством образующих. Эта полугруппа изоморфна полугруппе [[у0,у,,у2,.]]* всех слов в алфавите {Уо.УрЗ'г'-Ь включая и пустое слово, с операцией умножения слов, определяемой как приписывание одного слова к другому. Изоморфизм ср определяется по формуле ср(OhlOl2l.lQl") = yhyl2.y,n для всех п>О,

2,.,/„ >0 (при и = 0 элемент, стоящий под знаком (р считаем равным е, а слово, стоящее справа, считаем пустым и обозначаем символом 1). Изоморфизм ср индуцирует изоморфизм колец - RBe * и кольца всех формальных степенных рядов ^[[З'о'^мЗ'г'•••]] от бесконечного множества переменных {у0,у1,у2,.}, которые не коммутируют друг с другом. Этот изоморфизм по определению ставит в соответствие функции Fe RBe* степенной ряд, у которого коэффициент при (рО) равен F(w) для любого w & Ве* . Другими словами, если ввести обозначения: у = (Уо'Уп-Ь>•••); i = (zpz2,.,*„); у, = ;

F(l) = F(0',10'21.10'n) для любой функции F е RBe *; то функции Fe RBe * соответствует ряд /(у) = , где суммирование ведётся по 1 всем возможным упорядоченным п -м натуральных чисел для всех п > 0 (если п = 0, то \~е, у,=1). Равенства утверждений 1, 2 и 6 теоремы 1 можно записать, не употребляя язык полугрупп. Кроме того, используя изоморфизм кольца RBe * и кольца формальных степенных рядов, формулы утверждений 3, 4 и 5 можно записать в других обозначениях.

Теорема (теорема 1' §2 главы 1). Пусть функция А определена на множестве всех слов в алфавите {ОД}, включая и пустое слово, и принимает значения из кольца с единицей R , а(у) = ^Л(1)у,, и функция а0 определяется по формуле а0(у) = ^А0(1)у,,

1 1 где А0(1) = (-l)s(,) А(0|1') для всех I. (Здесь суммирование ведётся по всем упорядоченным п-м 1 = натуральных чисел для всех neN.J Тогда следующие условия эквивалентны:

1. Для любого пе N, /=1,2,.,и, и любого слова аха2.ап в алфавите {0,1} справедливо равенство

A(al.ai.all) + A(av.ar.an) = . .а,.,)А(ам .ап).

При / =1 полагаем al.ail - А, при i = n ам.ап - А.)

2. Для любого пе N и любого слова а1а2.ап в алфавите {0,1} справедливо равенство

А(ах.ап) = ^А^.л^аЛ-^-»^" А{0'") +■ А(0"). i=0

При г = п-1 полагаем а,.апм = А, яри / = 0 a„i+, + . + «„ =0.)

3. а0(у) = а(у)я0(у) + а0(у).

Элемент 1-а0(у) имеет обратный в кольце /?[[у0,у,,у2,.]] и а(у) = а0(у)(1-а0(у)У'.

5. Элемент 1 + а(у) имеет обратный в кольце i?[[y0, у,, у2'•••]] и

6. Для любого пе N и любого слова а]а2,.ап в алфавите {0,1} справедливо равенство

А{ау.ап) = ± £ ГГК ТпеО^—'^о^-,-.).

Г=0 0=/Q<i[<.</r<fr+l=« + l V -5-1 Л

V s=0

При г = 0 полагаем Y\ais = 1 > /v -t-l>/v+] -1 считаем й, + . + alj+i, = 0 J

4-1

Сформулированная теорема обобщает теорему о максимальном цепном представлении в следующем направлении. Вместо конкретной функции А: В* —>7j{t{,t2,.} мы рассматриваем произвольную функцию А, удовлетворяющую условию (1). За счёт выбора конкретного кольца R и функции А удаётся получить результаты, аналогичные теореме о максимальном цепном представлении в ряде задач, относящихся к последовательностям случайных индикаторов. Эти результаты можно рассматривать как обобщение соответствующих результатов из комбинаторики последовательностей, которые приведены в [21,4].

Наш метод доказательства теоремы 1 отличается от методов доказательства теоремы о максимальном цепном представлении, изложенного в [21, 4]. Метод доказательства из [21] использует формулу включения-исключения (он наиболее близок к выводу утверждения 3 теоремы 1 непосредственно из утверждения 6. Метод доказательства из [4] существенно использует специфику рассмотренной выше функции А\ B*-j>Z{t1,t2,.} и основывается на вычислениях с бесконечными матрицами. Наш метод доказательства состоит в прямом выводе утверждения 3 сформулированной выше теоремы 1 из §2 главы 1 из утверждения 2 этой теоремы. По существу этот вывод состоит в тривиальном применении определения операций в кольце RBe * . Утверждение, близкое к утверждению 2 для функции А : В* —> Z{/, ,t2,.} имеется в [4], однако теорема о максимальном цепном представлении выводится там не из этого утверждения, а иным, на наш взгляд более сложным путём. Более подробно доказательство из [4] и его отличия от нашего метода доказательства изложены в замечании 2 из §5 главы 1.

Утверждение 6 сформулированной выше теоремы 1 из §2 главы 1 имеет другой первоисточник по сравнению с остальными утверждениями этой теоремы. Оно является обобщением классической формулы включения и исключения, что продемонстрировано в пункте 1 §5 главы 1.

4. Теорема 1 из §2 главы 1, как и теорема о максимальном цепном представлении, позволяет получить много следствий как конкретного, так и более общего характера. (Для теоремы о максимальном цепном представлении большое количество таких следствий, относящихся к комбинаторике последовательностей, содержится в [21, 4]). Основных источников получения таких следствий два. Первый состоит в применении различного рода подстановок вместо переменных у0,у1,у2,. каких-либо выражений. Второй - в выборе конкретных колец и конкретных функций А: В* -> R, удовлетворяющих условию (1).

Первая линия развивается в §4 главы 1. Мы ограничились шестью конкретными подстановками описанного вида.

Первая позволяет получать рекуррентные соотношения, производящие функции и явные формулы для суммы значений функции А по всем словам we В*, содержащим к( максимальных по включению подслов из нулей длины i, i = 0,1,2,. Полученное таким путём утверждение (следствие 1 §4 главы 1) обобщает теорему о максимальном цепном представлении для случая, когда переменные у0,угу2,. коммутируют друг с другом так же, как теорема 1 из §2 главы 1 обобщает теорему о максимальном цепном представлении для случая, когда эти переменные не коммутируют друг с другом.

Вторая подстановка позволяет получать соответствующие результаты для суммы значений функции Л по всем словам we В* заданной длины, содержащим данное число нулей. Этот результат (следствие 2 §4 главы 1) содержит наиболее простое следствие из общей теоремы.

Третья подстановка позволяет получать соотношения для суммы значений функции А по всем словам we В* заданной длины, содержащим данное число максимальных по включению подслов из нулей. Эта задача является наиболее простой, в которой необходимо учитывать линейный порядок букв в слове we В*. Действительно, число максимальных по включению подслов из нулей we В* зависит не только от числа нулей в этом слове, но и от их взаимного расположения. В то же время данная задача наиболее близка к предыдущей, так что в ней удаётся продвинуться столь же далеко, как и в предыдущей (см. формулировки соответствующих результатов ниже).

Четвёртая подстановка, которую мы применяем, даёт соотношения для суммы значений функции А по всем словам we В* заданной длины, в которых каждое подслово из нулей имеет длину, не превосходящую данной (следствие 4 §4 главы 1). Мы выделили эту задачу потому, что она подвергается интенсивному изучению для последовательностей случайных индикаторов с различным типом зависимости (см. [12], [13], [14]).

Пятая подстановка позволяет найти производящие функции для множества всех слов we В*, имеющих заданный период (следствие 5 §4 главы 1). В комбинаторике последовательностей эта задача рассматривалась неоднократно и были предложены различные подходы к её решению (см. [4], [17].). Целью получения этого результата является демонстрация универсальности описанного выше метода подстановок. В [4] соответствующий результат не выводится из теоремы о максимальном цепном представлении, а даётся со специальным доказательством. Мы показываем, что его можно получить, не прибегая к новым средствам.

Сделаем ряд замечаний о языке, на котором ведётся изложение в первой главе работы. Здесь вводится в рассмотрение специальная категория колец производящих функций. Определённое выше кольцо RBe * принадлежит этой категории. Все рассмотренные кольца являются по существу полугрупповыми кольцами специальной категории полугрупп, удовлетворяющих некоторым естественным ограничениям, делающим корректной операцию умножения в рассматриваемых кольцах производящих функций. Частные виды таких колец применяются во многих комбинаторных исследованиях (см. [10], [6]). Выбор того вида производящих функций, который мы используем, определяется тем, что он наиболее удобен в задачах, рассматриваемых в первой главе нашей работы. Описанные выше подстановки при таком подходе мы интерпретируем как гомоморфизмы колец производящих функций, порождённые специальными гомоморфизмами лежащих в их основе полугрупп. Все проводимые построения выглядят естественно с точки зрения элементарных конструкций общей алгебры. Отметим, что в качестве колец производящих функций можно было бы использовать и алгебры инцидентности локально конечных частично упорядоченных множеств, а также соответствующие редуцированные алгебры (см. [6]). Это дало бы несколько большую общность результатов, однако привело бы к значительному усложнению проводимых построений.

5. Вторая линия получения следствий реализуется в §5 главы 1. В пункте 1 этого параграфа рассмотрены произвольные последовательности случайных индикаторов. Для них получаются результаты, обобщающие хорошо известную формулу включения и исключения. Сформулируем два наиболее интересных из этих результатов.

Следствие (следствие 3 §5 главы 1). Пусть /,,.,/„ - случайные индикаторы, определённые на одном вероятностном пространстве (QJk есть множество всех слов длины п в алфавите {0,1}, содержащих k непустых максимальных подслое из нулей. Тогда для всех п е N, к = 0,1,., [(п +1) / 2] : \

Г(л+1)/2]

2>{Л =*,,.,/, = «,}= £ r*c(u,),2 Z £ р ГН7;=0} • а\.апeJfr r=1 s+t=r p+q=n+l Пц +.+Щ =р, =0(mod2) j*>4+-~+"d njl+.+njt=q,„jm=i(mod2) \ d=l,.,r-l )

Следствие (следствие 4 §5 главы 1). Пусть 11,.,1п - случайные индикаторы, определённые на одном вероятностном пространстве (й,3, Р), и случайная величина W равна числу максимальных по включению непустых подслое из нулей в последовательности индикаторов /„. Тогда для всех n,k& N к-й биномиальный момент случайной величины W вычисляется по формуле: л вк=±(-1У-° I I Р

Если вероятности P{I h - 0,.,Ijk =0} не зависят от выбора множества {jx,.,jk}, а зависят только от к, то гдеР{/л = 0,.,Ijk =0} =qk.

Последнее следствие позволяет с помощью хорошо известного метода моментов доказывать сходимость распределения случайной величины W к предельным распределениям, например распределению Пуассона. В §5 главы 1 приведён соответствующий пример.

6. В пункте 2 §5 главы 1 рассматриваются последовательности 1-зависимых случайных индикаторов.

Определение (определение 1 §5 главы 1). Последовательность случайных величин {//г}~=1, определённых на одном вероятностном пространстве (Q,3,P) и принимающих только два значения - 0 и 1, называется стационарной последовательностью 1-зависимых случайных индикаторов, если выполнены два условия

1) при любом пе N и любых al,a2,.,an е {0,1} вероятность Р{1Ш =al,I2lrt =a2,.,In+t - anj не зависит от t, где t> 0 - любое целое число;

2) при любых гс, г е N и любых

Oj,., 1, С1

1,.,ап е {0,1} события =а1,.,/(.1 =<ягМ} и {/.+1 =ам,.,/„ =aj независимы.

По данной последовательности 1-зависимых случайных индикаторов {/„}"=1 определим функцию А: 5* —> {0,1} следующим образом:

А(а,д2.ап1} = Р{/1+1 =Д„/2+, = а2,.,/л,+( =«„,}, А(А) = 1. Так определённая функция А удовлетворяет условию (1). Следовательно, к ней применимы все результаты из §2, §4. Приводятся примеры применения этих результатов к последовательностям независимых одинаково распределённых случайных индикаторов, к последовательностям индикаторов перемен значений в них, к последовательностям индикаторов возрастаний в случайной равновероятной перестановке на конечном множестве. Приводится также пример, в котором рассматривается последовательность 1-зависимых случайных индикаторов, не имеющая 2-блочной структуры. Примеры таких последовательностей были построены недавно ([5], [20]). Этот пример демонстрирует применимость построений первой главы к произвольным последовательностям 1-зависимых индикаторов. Для последовательностей, имеющих 2-блочную структуру все соответствующие результаты в принципе можно получить предельным переходом, используя теорему о максимальном цепном представлении из [21, 4]. Доказательства, приведённые в [21, 4], по существу используют именно эту структуру соответствующих последовательностей. Для последовательностей, не имеющих 2-блочной структуры, этот метод неприменим. Однако, методом нашей работы мы показали, что аналог теоремы о максимальном цепном представлении справедлив и в этом случае.

В пункте 3 §5 приводится вывод теоремы о максимальном цепном представлении из [21, 4] нашим методом. Также производится сравнение методов работы [4] и настоящей работы.

7. Наконец, в пункте 4 §5 рассматриваются дискретные цепи Маркова. Доказан следующий результат.

Следствие (следствие 5 §5 главы 1). Пусть {Х„}~=0 - стационарная дискретная цепь Маркова с конечным или счётным множеством состояний Е, П -её матрица переходных вероятностей, к0 - начальное распределение этой цепи.

Пусть множество Е разбито на два непересекающихся подмножества Е - E0\J Elt последовательность случайных индикаторов (f„)~=1 определяется условием

К = е а матрицы П0 и П, определяются равенствами

П,, при je Е0] п0. = " п,=п-п0. и [0 в противном случае;

Тогда п-1

1. производящая функция а(х, у) = ^^А(п,к)х"ук, где и=1 к-О

А{п,к) = Р{1{ + . + /„, =к} равна а(х, у) = %0x(l - П0х(у -1))"1 (i - Пх(1 - П0х(у -1))"1е';

ОО п-\

2. производящая функция d(x,y) = ^^D(n,k)xnyk, где D(n,k) есть п=1 к=о вероятность того, что число максимальных по включению непустых серий из нулей в последовательности /,,.,/„] равно к,равна d(x, у) = п0а0 (х, у)(I - d0 (х, у))'1 ё, где d0(x,y) = fL „ r.-\-l L г.-Vi L г.-VI / г.-Vi ^ Пхд/l^y i - Прхуг^)"1 + (i 4 п0хуг^У (i- п0xjr^y - (i + 2-Jl^ 2

5. производящая функция аг(х) = Аг(гс)х", где Аг{п) есть вероятность того, п=1 что в последовательности /,,.,/„, все серии нулей имеют длину, не большую г, равна а' (х) = эт0 (х - U0r+1xr+2 \l - П0Г+V+2)"' (i - п(х - П0г+1х'*+2 \l - П0Г+V+2е'.

Здесь ё есть столбец, состоящий из одних единиц, I — единичная матрица.

Утверждение 3 этого следствия аналогично некоторым результатам работ [3], [12], [13], [14]. Именно, оно даёт решение задачи, решённой другими методами в [3] для случая последовательностей испытаний Бернулли и в [14] для случая дискретных цепей Маркова. Наши результаты относятся только к случаю стационарных цепей Маркова (в [14] рассматриваются произвольные цепи) и несколько отличаются по форме. Отметим, что в [14] рассмотрены только цепи с конечным множеством состояний. В наших рассмотрениях число состояний может быть как конечным, так и счётным.

8. Перейдём ко второй главе работы. Отправным пунктом здесь явились два очень частных результата. Первый из них установлен Танни [26] и заключается в следующем. Пусть (/;-)"=! - последовательность индикаторов возрастаний в случайной равновероятной перестановке % на множестве {1,2,.,и} (то есть 1к = 1{п(к) < %{к +-1)}). Тогда

Р(/, +. + /„, < к) = +-+. + < *}, к = 1,2,.,п, (2) где 1>х,Ъ>2,.,Ъ>п - независимые равномерно распределённые на промежутке [ОД] случайные величины.

Второй результат вытекает из некоторых результатов, сформулированных в [18] (см., например, т. 2, с. 73, примеры г, д). Пусть {Х„}~0, }~=0 - две не последовательности независимых и независящих друг от друга случайных величин. Пусть случайные величины первой последовательности имеют показательное распределение с параметром а, а случайные величины второй последовательности -показательное распределение с параметром р. Пусть далее (/„)Т=о последовательность независимых случайных индикаторов, имеющих распределение ос

Бернулли с параметром -. Тогда при всех п> 0, к = 0Д,.,я + 1 имеет место а + (3 равенство

Р{/0 +.+ /„< к} = Р{ Х0 +. + Х^ - Y0 -. - Yk < 0}. (3)

Эти результаты привели нас к общим построениям главы 2. Оказалось, что все они тесно связаны с двумя фактами. Первый связывает распределение времени пребывания некоторого случайного процесса на положительной полуоси с вероятностями, подобными той, которая стоит в правой части (3). Он сформулирован в §1 главы 2 как лемма 1. Второй факт заключается в том, что для некоторых характеристических функций удаётся установить их разложение в линейную комбинацию двух других характеристических функций, одна из которых является характеристической функцией распределения, сосредоточенного на положительной полуоси, а другая - распределения, сосредоточенного на неположительной полуоси. Такое разложение позволяет в ряде случаев получать комбинаторные тождества для совместных распределений последовательностей индикаторов, связанных с соответствующими случайными процессами. Наличие таких тождеств позволяет связывать эти последовательности индикаторов с конкретными комбинаторными и вероятностными задачами и тем самым устанавливать для последовательностей индикаторов, появляющихся в этих задачах, соотношения типа (2) и (3). Перейдём к формулировке результатов главы 2.

Определение (определение 1 §1 главы 2). Пусть на одном вероятностном пространстве определены случайная величина Z и две последовательности неотрицательных случайных величин v {Yn }~=1. Последовательность случайных величин [Zn }~=0, определённая по формулам fZ, , + Х- - , если Z„ , <0; Z - Z Z - \ /о+.+/и-1

- V-^,-,' если2„,>0; где In = I{Zn> 0}, = 1-/(! =/{Zn <0}, называется осцилирующим случайным блужданием, построенным по случайной величине Z и последовательностям {X п }~=1; пс,

Мы будем говорить, что случайное блуждание {Zn}~=0 построено по тройке (Z,{Xn}™=l,{YJ~=l). Последовательность случайных индикаторов {/„}~0 из этого определения мы будем называть последовательностью, порождённой случайным блужданием {Zn}~=0. Термин «осцилирующее случайное блуждание» взят из [2]. Там он имеет несколько иной смысл. Однако в случае, когда случайные величины в каждой из последовательностей {^„}Г=1>{^ЛГ=1 одинаково распределены, распределения случайного процесса {Z„}~=0 из нашего определения и соответствующего случайного процесса из [2] совпадают.

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

Лемма (лемма 1 §1 главы 2). Пусть {Zn}есть осцилирующее случайное блуждание, построенное по тройке (Z, {Х);}~=1,{У/г}7= i)> и {!„)Г=о естъ порождённая им последовательность случайных индикаторов. Тогда при всех п- 0,1,. и к = ОД,., и имеет место равенство событий

0 + .+ In<k} = {Z + Xl+.+ Хпк - Fj -. -Yk < 0}. (4)

В этом же параграфе даются некоторые приложения леммы 1. В качестве примера приведём следующее утверждение.

Следствие (следствие1 §1 главы 2). Пусть {/„}Г=о есть последовательность случайных индикаторов, являющаяся однородной цепью Маркова с начальным распределением (p,q) и матрицей переходных вероятностей Р = ^ . Тогда при

Р 2 Яг) всех п = ОД,. и k-Q,l,.,n имеет место равенство

Р{10 +. + /„ <k}=P{Z+Xl +.+ Xnk +Yi+.+ Yk <k}, где Z, Yl,Y2,. есть независимые в совокупности случайные индикаторы, причём Х1,Х2,., так же как и Yl,Y2,., одинаково распределены и

P{Z = l} = p, P{Z = 0} = q, P{X,=l] = p„ Р{Х1 = 0} = ql,P{Yl = 1}=р2, Р{Г,=0} = д2.

9. Во втором параграфе рассматриваются результаты, вытекающие из равенства (4) в случае, когда все случайные величины последовательностей {Х„}~=1, {У„}"=1 распределены показательно, a Z имеет вид Z = X0-F0, где X0,Y0 также распределены показательно и независимы. Кроме того предполагается, что все случайные величины Z, {Х„}~=1, {У„}~=1 независимы в совокупности. В начале параграфа описана общая идея применения характеристических функций к выводу тождеств для совместных распределений индикаторов последовательности {/„ }~=0, порождённой некоторым осцилирующим случайным блужданием. Дальше рассматриваются показательно распределённые величины.

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

X ]iji А + Х ji X-it ц + it k+\iX-it X + ц (Li + it' имеющего описанный выше вид, находятся явные формулы и рекуррентные соотношения для совместных распределений индикаторов последовательности {/„}~=0 и сумм этих индикаторов. Знание этих распределений позволяет установить совпадение распределения последовательности U„}7=o с распределением последовательности индикаторов, связанной с одной урновой моделью, которая является обобщением урновых моделей, рассмотренных в [18]. Приведём пример результатов, полученных в этом параграфе.

Пример (пример 1 §2 главы 2). (Обобщённая урновая модель Фридмана). Следующая урновая схема является обобщением модели, рассмотренной в [18] (с. 137-139).

Пусть {и>„}~=0 и {гя}~0 - две последовательности неотрицательных целых чисел.

Имеется урна, которая первоначально содержит w0 белых и г0 красных шаров. На очередном шаге из урны извлекается шар. Его цвет запоминается и шар возвращается в урну. Если извлечённый шар был белым, то в урну добавляются красные шары в количестве, равном очередному члену последовательности {гп}~=0. Если же извлечённый шар был красным, то в урну добавляются белые шары в количестве, равном очередному члену последовательности {w„}~=0. (Числа шаров берутся из последовательностей в порядке их номеров, без пропусков.)

В результате описанной процедуры мы получим последовательность цветов извлечённых из урны шаров. Полагая ю„ = 1, если извлечённый на п -м шаге шар красный, и сол = 0 в противном случае, получим последовательность {оо„ 0 случайных индикаторов. Положим

1 1 1 г0 +-+Л w0+. + w„

Тогда справедливо следующее утверждение.

Утверждение (утверждение 1 §2 главы 2). Последовательность случайных величин {сол}"=0 имеет то же распределение, что и последовательность случайных индикаторов {/„}Г=о> порождённая случайным блужданием {Z;1}~=0, построенным по тройке (Z,{Xn}"=l,{Yn}"=l), в которой все случайные величины независимы в совокупности, Z имеет вид Z = X0-Y0, где Х0 и F0 независимы, и случайные величины Хп, Yn имеют показательные распределения с параметрами Хп, р„ соответственно, п = 0,1,2,.

Следствие (следствие 1 §2 главы 2). Случайная величина оо0 + . + со„ имеет то же распределение, что и случайная величина 10 + . + 1п, где (соп}7=0 и {/„}Г=о естъ последовательности случайных величин из утверждения 1. Таким образом, при всех п = 0,1,. и к — 0,1,., я

Р{ш0 +. + а>„ < к} = P{Z + X, +. н- Хпк - Yx -. - Yk < 0}. Другие результаты этого параграфа обобщают сформулированные утверждение и следствие.

10. В третьем параграфе второй главы мы снова рассматриваем стационарные последовательности 1-зависимых случайных индикаторов. Устанавливается связь некоторых из таких последовательностей с осцилирующими случайными блужданиями специального вида. Очевидно, что всякое осцилирующее случайное блуждание является цепью Маркова. Пусть для случайного блуждания {Z„}~=0, построенного по тройке (Z,{X/1}~1,{7n}~=1), распределение случайной величины Z является стационарным распределением этой цепи Маркова, то есть все величины последовательности {Zn}~=0 одинаково распределены. Тогда мы называем {Z„}7=o стационарным случайным блужданием.

Основной результат §3 главы 2 состоит в следующем.

Теорема (теорема 1 §3 главы 2). 1). Пусть (/„)~=0 есть стационарная последовательность 1-зависимых случайных индикаторов. Пусть функции ср(А,) и \|i(X) определённы равенствами т=^ыгр{10 =1.-,/л1 =1Я\ у(Я)=2(-1)"р{/0=о, .,/„! =о}г. п=0 11=0

Предположим, что их можно продолжить до функций, аналитических в полуплоскости Re Л > 0 и непрерывных на границе этой полуплоскости, и что эти продолжения являются преобразованиями Лапласа некоторых неотрицательных случайных величин. Тогда распределение последовательности индикаторов (/„)™=0 совпадает с распределением последовательности индикаторов (/'„)Г=о> порождённой стационарным случайным блужданием {Z;I}~=0, построенным по тройке (Z,{Xn}™=l,{Yn}™=1), в которой все случайные величины независимы в совокупности, Z имеет вид Z = X0-Y0, где Х0 и У0 независимы, и все величины в каждой из последовательностей {Хп}™=0, {Yn одинаково распределены и имеют преобразования Лапласа ф(0 и \|/(г) соответственно.

2) Пусть последовательность случайных индикаторов (Гп )"=0 порождена стационарным случайным блужданием {Zn}"=0, построенным по тройке (Z,{Xn }™=1,{К(! }"=i), в которой все случайные величины независимы в совокупности, распределение случайной величины Z = Х0 - Y0, где Х() и F0 независимы, ЕХ0 +EF0 =1, является единственным абсолютно непрерывным стационарным распределением цепи Маркова {ZB}~=0, и все величины в каждой из последовательностей {Хя}~=0, {}~=0 одинаково распределены. Тогда последовательность (/„)~=0 является стационарной последовательностью 1-зависимых случайных индикаторов, причём имеют место равенства р(А) = J(-l)BP{/0 =l,.,/„-i =W> v|/(A) = J(-l)"P{/0 = 0,.= 0}А", п=О и=О в которых ср(0 w \|/(/) есть преобразования Лапласа случайных величин Х0 и Y0 соответственно.

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

Приводятся примеры применения сформулированной теоремы. Примеры 1 и 2 содержат новые доказательства результатов (3) и (2) соответственно. В замечании 2 этого параграфа даётся ещё одно новое доказательство результата Танни, которое также имеет комбинаторную природу и основано на рассмотрении сохраняющих меру линейных преобразований.

11. Наконец, в четвёртом параграфе второй главы даются некоторые приложения, которые можно получить, используя соотношения вида (4). В этом параграфе мы показываем, как результаты, получаемые с помощью основной комбинаторной леммы из § 1 главы 2, можно применять к доказательству предельных теорем, выводу оценок и асимптотических соотношений для распределений зависимых случайных индикаторов. Здесь используются уже не комбинаторные, а аналитические методы. Цель этого параграфа состоит в том, чтобы указать некоторые приложения полученных комбинаторных результатов. Сформулируем основные результаты этого параграфа.

Пусть {Zn }~=0 - осцилирующее случайное блуждание, построенное по тройке

Z,{^,X=p{yX=i)- Пусть {А„};=0,{5„}^0 - две последовательности действительных чисел. Эти последовательности мы будем использовать в качестве последовательностей нормирующих констант. Введём следующие обозначения:

Х0 = I{Z > 0}Z , F0 = -7{Z < 0}Z ; Sa =I0 + IX+ . + In;

Un=±x, ; V„ ; a. =EU„; bn =EV„; c„ =D£/„; dn =DV„; n 1=о 1=0 f(n) = [An + Bnx] ■ Snx = unf(n) - vJW; S'niX = ; y„,, = ES"

Обозначим через F'n и F\ix функции распределения случайных величин S\ и S'n x соответственно .

Теорема (теорема 1 §4 главы 2). 1) Пусть F - непрерывная, строго возрастающая функция распределения и h- неубывающая, непрерывная справа функция, принимающая значения из множества RUf-00^00}, пределы которой в точках и равны ц +оо соответственно. Пусть при любом фиксированном х последовательность функций распределения {F'nx }~=0 слабо сходится к F. Тогда для слабой сходимости последовательности {F'n }J=0 к F oh необходимо и достаточно, чтобы последовательность [упх)"=0 сходилась к h{x) во всех точках х непрерывности функции h.

2) Пусть выполнены условия:

1. при любом фиксированном х последовательность функций распределения {F'„ х )Г=о слабо сходится к F .

2. члены последовательности {Апначиная с некоторого места неотрицательны, а члены последовательности {Вп , начиная с некоторого места больше либо равны некоторой константы Ъ> 0 ;

3. последовательность {уп,х}™=0 сходится к х равномерно относительно х;

4. последовательность моментов {Е| S\x\r+a }™=1ограничена при некоторых г, а > 0 равномерно относительно х.

Тогда последовательность моментов {Е|5"п|г}^=1 сходится к r-му моменту распределения F.

Приводятся примеры применения этой теоремы к исследованию предельного поведения последовательностей случайных индикаторов, связанных с урновыми схемами из §1, и последовательностей 1-зависимых индикаторов из §3. Эти результаты аналогичны центральной предельной теореме и её уточнениям для индикаторов с указанным типом зависимости.

Заключение

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

Комбинаторика последовательностей с ограничениями на пары последовательных элементов находит применения в таких областях как теория вероятностей, теория особенностей дифференцируемых отображений, теория групп, порождённых отражениями в евклидовом пространстве. Приложения к последним двум вопросам рассматриваются в работе [1].

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

Урновые схемы типа Пойа-Фридмана могут рассматриваться как простейшие модели эпидемии и службы безопасности ([18], т.1, с. 137-139).

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

1. Арнольд В.И. Исчисление змей и комбинаторика чисел Бернулли, Эйлера и Спрингера групп Кокстера. // УМН.- 1992,- Т.47, №1.-с.З-45.

2. Боровков А. А. Теория вероятностей.-М.: Эдиториал УРСС, 1999.

3. Гончаров В. J1. Из области комбинаторики.// Известия АН СССР, Серия матем, 1944, 8, №1, с.3-48.

4. Гульден Я. Джексон Д. Перечислительная комбинаторика: Пер с англ. М.: Наука, 1990.

5. Де Вальк В. Процессы со свойством 1-зависимости и их представление в гильбертовом пространстве. // Теория вероятностей и её применения, 1992, с. 149-152.

6. Дубиле П., Рота Дж.-К., Стенли Р. Об основах комбинаторной теории (VI): идея производящей функции: Сб. Перечислительные задачи комбинаторного анализа. Библиотека кибернетического сборника. Сборник переводов. / Под ред. Г. П. Гаврилова.-М.: Мир, 1979.

7. Королюк В. С., Портенко Н. И, Скороход А. В., Турбин А. Ф. Справочник по теории вероятностей и математической статистике.-М.: Наука. Главная редакция физико-математической литературы, 1985.

8. Коршунов А. Д. О числе бинарных слов с заданной длиной максимальной серии, I. // Дискретный анализ и исследование операций, 1997, 4, №4, с. 13^4-6.

9. Косточка А. В., Мазуров В. Д., Савельев JI. Я. Число #-ичных слов с ограничениями на длину максимальной серии. // Дискретная математика, 1998 10, №1, с. 10-19.

10. Лаллеман. Ж. Полугруппы и комбинаторные приложения. Пер. с англ.-М.: Мир, 1985.

11. П.Михайлов В. Г. Явные оценки в предельных теоремах для сумм случайных индикаторов. // Обозрение прикладной и промышленной математики, 1994, 1,№4, с.580-615.

12. Савельев JI. Я. Максимум длин серий в обобщённых последовательностях Бернулли. // Дискретная математика, 1999, 11,№1, с.29-52.

13. Савельев JT. Я. Серии в марковских последовательностях. // Сибирский матем. ж.,1991, 32, №4, с.116-132.

14. Савельев JI. Я. Длинные серии в марковских последовательностях. Труды инст. математики, т.5 , Предельные теоремы теории вероятностей / Отв. Ред. А. А. Боровков, Новосибирск: Наука, сиб. Отд. - 1985.

15. Сачков В. Н. Вероятностные методы в комбинаторном анализе.-М.: Наука. Главная редакция физико-математической литературы, 1978.

16. Сачков В. Н. Комбинаторные методы дискретной математики.-М.: Наука. Главная редакция физико-математической литературы, 1977.

17. Стенли Р. П. Перечислительная комбинаторика: Пер. с англ. М.: Мир, 1990.

18. Феллер В. Введение в теорию вероятностей и её приложения. В 2-х.ф. томах. Т.1., Т.2. Пер. с англ.-М.: Мир, 1984.

19. Шергин В. В. О скорости сходимости в центральной предельной теореме для т-зависимых случайных величин. / Теория вероятностей и её применения, т. 24, 4, с. 781-794.

20. Aaronson J., Gilat D., Keane M., de Valk V. An algebraic construction of a class of one-dependent processes-Ann. Probab., 1989, v.17, №1, p.128-143.

21. Gessel, I. M. «Generating Functions and Enumeration of Sequences», Doctoral thesis, Massachusetts Institute of Technology, Cambridge, Massachusetts, 1977.

22. Jackson, D. M., and R. Aleliunas. Decomposition based generating functions for sequences, Canad. J. Math. 29, 1977, p.971-1009.

23. Jackson, D. M., and I. P. Goulden. A formal calculus for the enumerative system of seguences, I, II, III. Studies Appl. Math. 61, 1979, 1980, p.141-178, 245-277; 62, 113-142.

24. Jackson, D. M., and I. P. Goulden. Algebraic methods for permutations with prescribed patterns, Adv. Math. 42, 1981, p.l 13-135.

25. Stanley, R. P. Binomial posets, Mobius inversion and permutation enumeration, J. Comb. Theory (A) 20, 1976, p.336-356.

26. Tanny S. A probabilistic interpretation of Eulerian numbers, Duke math. J., 1973, Vol. 40, №4.