Предельные теоремы в задачах о плотном вложении и плотных сериях в дискретных случайных последовательностях

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

Одной из таких задач является изучение статистических свойств специальных комбинаций в дискретных случайных последовательностях. В диссертации в качестве специальных комбинаций рассматриваются плотно вложенные последовательности. Понятие плотного вложения было введено в математическую литературу в работе (Golic, 1996]. Пусть ^ = {х,.}^ и.

Ym={yi}™1 — последовательности знаков алфавита Аы = {О,., N — 1}. Согласно (Golic, 1996), последовательность X плотно вкладывается в начало I последовательности Ym, eели п<�т и найдутся такие натуральные числа l = jl.

Понятие плотного вложения возникает при изучении свойств последовательностей, генерируемых конечными автоматами из нескольких параллельно функционирующих блоков, выходные последовательности которых соединяются в одну общую последовательность без нарушения порядка следования букв. Например, если генератор случайных' чисел состоит из двух блоков, в последовательность, вырабатываемую первы|ч блоком, добавляются знаки, выработанные вторым блоком, причем не более одного знака подряд, то выходная последовательность первого блока будет плотно вложена в выходную последовательность генератора. Роль этого свойства при изучении генераторов случайных чисел описана в работах (Zivkovic, 1991), (Golic, 1991), (Golic, 1996).

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

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

Первая интересующая нас задача состоит в определении вероятности плотного вложения Рт (Хп) заданной последовательности Хп в начало последовательности Ym, образованной независимыми случайными величинами, равномерно распределенными на множестве AN. В случае двоичных I последовательностей [N = 2) верхняя оценка вероятности Рт[Х") была получена в работе (Golic, 1996). В первой главе диссертации получено обобщение результата (Golic, 1996) на случай конечного алфавита AN с произвольным числом букв Рт[Х") — Также построена оценка снизу для вероятности Рт[Хп) и указаны классы последовательностей, на которых эти оценки достигаются. Приведены вытекающие из этих оценок предельные соотношения для вероятности плотного вложения, когда растут параметры п и т. В частности, получено предельное равенство для логарифма вероятности плотного вложения Рт[Хп] в схеме серий, когда размер алфавита также растет.

Нижняя оценка вероятности Рт (Х"] достигается на последовательностях.

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

Серии в достаточной для многих приложений, степени отражают статистические свойства случайной последовательности. Различные применения свойств серий в статистике хорошо известны.

Одним из наиболее известных примеров является статистика критерия однородности Вальда-Вольфовица, предложенного в работе (Wald, 1940). Показано, что статистика, равная числу серий в объединенном вариационном ряду, построенном по двум независимым выборкам с непрерывными распределениями, может быть успешно применена для обнаружения малых систематических различий в их распределениях.

Задача о числе серий успехов в последовательности Бернулли хорошо известна в литературе. Одно из первых упоминаний этой задачи в контексте пуассоновской аппроксимации содержится в статье (von Mises, 1921). В дальнейшем было изучено предельное распределение цепочек из единиц, длины максимальной серии из единиц, времени до первого появления серии заданной длины и ряда сопутствующих величин (см., например, (Arratia, 1990), (Arratia, 1989), (Godbole, 1991) и др.). Подробное освещение этих вопросов имеется в разделах, А и В книги (Balakrishnan N., 2002)). Рассматривались обобщения этих задач на более общие случайные последовательности, в частности, на цепи Маркова (см., например, (Самарова, 1981), (Савельев, 2003) и др.).

Понятие серии получило ряд обобщений. Например, в работе (Wolfowitz, 1944) было введено понятие монотонной серии как серии, образованной знаками последовательных разностей элементов случайной последовательности. Их изучению посвящены работы (Eagle, 1995), (Glaz, 1999), (Balakrishnan, 2002), (Chryssaphinou, 2001), (Меженная, 2007) и др.).

Важным для приложений обобщением задачи о сериях является задача изучения свойств дискретных сканирующих статистик. В книге (Balakrishnan, 2002) сканирующая статистика определена как максимальное число успехов, содержащихся в скользящем окне заданной длины. Подробный анализ этой задачи содержится в книгах (Balakrishnan, 2002), (Glaz, 1999), (Glaz, 2001). Подобные статистики получили широкое применение в генетике, биостатистике, контроле качества и ряде других областей. В частностр, широкое применение получили статистики, являющиеся функциями от числа цепочек, обладающих некоторым свойством, которые появились в дискретной случайной последовательности. Интерес в таких задачах представляют как точные оценки для изучаемых величин, так и предельное поведение их распределений.

Задача об асимптотическом распределении числа цепочек, обладающих заданным свойством, рассматривалась многими авторами [см., например, (Arratia, 1990), (Barbour, 1987], (Barbour, 2002), (Chryssaphinou, 2001), (Erchardsson, 2005), (Fuchs, 1965), (Godbole, 1991), (Rajarshi, 1974), (Barbour, 1992) и др.).

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

Отрезок последовательности х1,., хк из знаков алфавита AN мы называем плотно запомненным знаком аеАы, если ае{х^х1+г}, i = l,., k — lt то есть пропуски между знаками, а в нем могут состоять не более чем из одного символа отличного от а, и на концах содержится не более одного знака из Ду{а}.

Распределение числа плотно заполненных отрезков в случайной последовательности можно вывести из распределения числа плотно заполненных серий. Плотно заполненный (знаком а) отрезок назовем плотно заполненной Сзнаком а) серией (или просто плотной асерией), если он не содержится ни в каком плотно заполненном отрезке большей длины. Длиной плотной а-серии назовем длину минимального отрезка, содержащего все знаки плотной асерии. Число входящих в плотную асерию знаков, а будем называть ее весом.

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

Постановки задач для плотных серий в настоящей работе аналогичны классическим постановкам задач для серий успехов в последовательности Бернулли (это используется в доказательствах). Нас интересовала возможность использования пуассоновской аппроксимации (в том числе и многомерной) для распределений числа плотных 1-серий.

Основными объектами исследования во второй главе диссертации являются случайные величины gsT и <^sT, равные числу плотных 1-серий, которые начинаются в моменты от 1 до Г и имеют длину s и не меньше s соответственно, и случайные величины g’wT и? wT, равные числу плотных 1серий, которые начинаются в моменты от 1 до Г и имеют вес w и не меньше W соответственно. Доказаны многомерные предельные теоремы Пуассона для случайных векторов [gStT>—-, gs+r-ltT,€s+rtT') и [g'wJ.

Т—>оо и согласованном изменении других параметров. В первом случае с помощью функциональной версии метода Чена-Стейна также получены явные оценки точности пуассоновской аппроксимации.

Из этих теорем и оценок выведено совместное предельное распределение нескольких старших членов вариационного ряда из длин (весов) плотных 1-серий. Этот результат может быть использован при построении критерия проверки качества случайной последовательности. Например, в работе (Balakrishnan, 2002) вектор из нескольких старших членов вариационного ряда длин обычных серий единиц и длин обычных серий нулей использовался для построения оценки изменяющейся вероятности успеха в последовательности Вернул л и.

Так как предельные теоремы и оценки точности применимы лишь при достаточно больших значениях параметров, интерес представляет разработка методов вычисления точных распределений изучаемых случайных величин при конкретных значениях параметров. В работах (Fu, 1994), (Fu, 2003), (Fu, 2001) для аналогичной задачи относительно числа серий в случайных последовательностях с двумя состояниями использовался подход, основанный на аппарате цепей Маркова. Этот метод оказался полезным и в нашем случае. В диссертации построены рекуррентные формулы для вычисления распределений случайных величин и ?'wT в неоднородной цепи Маркова с двумя состояниями. С их помощью удалось на конкретных примерах определить реальную точность пуассоновской аппроксимации для этих величин в равновероятной последовательности Бернулли, и, тем самым, продемонстрировать точность предельных теорем. ,.

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

В главе 1 диссертации получено обобщение верхней оценки вероятности плотного вложения Рт[Хп) работы (Golic, 1996] на случай конечного алфавита.

An с произвольным числом букв и показано, что эта верхняя оценка не улучшаема. Она достигается на последовательностях ^П="{Х}" =1, для которых xi^xi+1,i = 1,., П — 1. Построена также неулучшаемая оценка снизу для вероятности PW[X"), которая достигается на последовательностях Хп, I состоящих из П одинаковых знаков. В разделе 1.1 приведена формулировка задачи и вид верхней и нижней оценок вероятности Рт[Хп]. В разделе 1.2 приведены точные значения вероятности плотного вложения в некоторых частных случаях, а также приведены некоторые замечания о свойствах этой вероятности. Доказательства теорем из раздела 1.1 содержатся в разделах 1.3,1.4 и 1.5. В разделе 1.6 предложены несколько критериев проверки гипотезы о плотном вложении.

В главе 2 доказаны многомерные предельные теоремы пуассоновского типа для числа плотных серий единиц большой длины и многомерные предельные теоремы пуассоновского типа для числа плотных серий единиц большого веса в последовательности независимых одинаково распределенных случайных величин с конечным числом исходов. В доказательствах этих теорем используется функциональная версия известного метода Чена — Стейна. Необходимые сведения об этом методе и об особенностях его применения при изучении серий событий в последовательности независимых случайных величин приводятся в разделе 2.2. Там же демонстрируется методика применения метода Чена — Стейна при доказательстве многомерных теорем пуассоновского типа на примере задачи о числе обычных серий больших длин.

Плотные серии заданной длины изучаются в разделах 2.4 — 2.7. В разделе 2.3 выведена формула для вероятности появления плотной серии заданной длины в заданном месте последовательности. В разделах 2.4 и 2.5 при помощи метода Чена — Стейна найдены оценки расстояния по вариации между распределением вектора из числа плотных серий единиц заданных длин и сопровождающим многомерным пуассоновским распределением. Из этих оценок выведены предельные теоремы пуассоновского типа для числа плотных серий заданных длин и длины не меньше заданной, для числа плотно заполненных отрезков (раздел 2.6). В разделе 2.7 результаты предшествующего раздела используются для вывода предельной теоремы для максимальной длины плотной серии. В разделе 2.8 при помощи доказанной в разделе 2.2 многомерной предельной I теоремы для обычных серий выводится многомерная предельная теорема Пуассона для числа плотных серий единиц заданного веса.

Разделы 2.9 и 2.10 посвящены изучению на конкретных^{примерах} реальной точности пуассоновской аппроксимации в задачах о плотных сериях. В разделе 2.9 при помощи аппарата цепей Маркова выводятся рекуррентные формулы, позволяющие вычислить распределение числа длинных плотных серий единиц и распределение числа плотных серий единиц, имеющих вес не^еныпе заданного, в отрезке неоднородной цепи Маркова с двумя состояниями. В разделе 2.10 эти формулы используются для вычисления распределений этих величин в равновероятной последовательности Бернулли при разном выборе длины этой последовательности и при разных ограничениях на длину и вес плотной серии.

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

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

Завершает диссертацию список литературы из 54 наименований.

3 Заключение.

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

Результаты, полученные в настоящей работе, относятся к дискретной теории вероятностей. Для их вывода использовался ряд хорошо известных методов — метод рекуррентных уравнений, метод Чена-Стейна, метод производящих функций, аппарат цепей Маркова.

Диссертация посвящена изучению свойств статистик, возникающих в задачах, связанных с плотным вложением и плотными сериями. Плотные серии являются обобщение классического определения понятия серии. Решаемые в работе задачи во многом аналогичны классическим задача^ о сериях, однако требуют применения несколько более громоздких и сложных методов.

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

Глава 2 посвящена выводу многомерных предельных теорем пуассоновского типа для распределения числа плотных 1-серий большой длины и плотных 1-серий большого веса в последовательности независимых одинаково распределенных случайных величин с конечным числом исходов. Для этих целей был использован метод Чена — Стейна, позволивший в ряде случаев получить явные оценки точности пуассоновской аппроксимации. Основной целью диссертационного исследования был вывод предельных теорем для числа плотных серий большой длины и для числа плотных серий большого веса, аналогичных теоремам для числа обычных серий. Сравнение теорем 2.7 и 2.10 с теоремой 2.1, описывающей асимптотические свойства числа длинных серий одинаковых знаков, показывает, что эта цель полностью достигнута.

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

Кроме предельных соотношений в диссертации получены рекуррентные формулы, позволяющие непосредственно вычислить распределение числа длинных плотных 1-серий и распределение числа плотных 1-серий большого веса в отрезке неоднородной цепи Маркова с двумя состояниями. Эти формулы использованы в разделе 2.10 для демонстрации на конкретных примерах i реальной точности пуассоновской аппроксимации в предельных теоремах 2.7 и 2.10.

Результаты первой главы дополняет раздел 1.6, посвященный процедурам проверки гипотезы о том, что случайная последовательность X длины п является плотно вложенной в другую случайную последовательность Y (обе последовательности предполагаются равновероятными). Согласно теореме 1.1 вероятность ошибочного принятия гипотезы о плотно^ вложении убывает с ростом длины последовательности экспоненциально быстро, однако этот результат не предлагает конкретной процедуры проверки. В разделе 1.6 рассмотрены и исследованы несколько простых способов проверки гипотезы о плотном вложении, не использующие тотального опробования вариантов.

Наиболее неудобным для проверки этой гипотезы с помощью таких способов оказался двоичный случай. Однако для решения данной статистической задачи в случае N = 2 могут быть использованы результаты второй главы. Пусть проверяемая гипотеза состоит в том, что последовательность X плотно вложена в последовательность Y, причем при вложении добавление постороннего знака I на каждом шаге происходило или нет случайно и независимо с вероятностью 0,5.

Процедура в этом случае начинается с поиска в последовательности X самой длинной серии одинаковых знаков (скажем, единиц|. Зная место этой серии можно указать отрезок в последовательности Y длины O (Vn), с гарантированной вероятностью содержащей образ этой серии при вложении. После этого в данном отрезке ищется самая длинная или самая тяжелая плотная сери единиц. Если длина (или вес) заметно превосходит значения, ожидаемые для случайной последовательности, то гипотеза о наличии плотного вложения может быть рассмотрена как правдоподобная. Как вытекает из результатов второй главы, такая процедура будет успешной, если максимальная длина серии в последовательности X достаточно велика (больше типичных значений). Этот пример демонстрирует тесную связь предельных теоррм для числа плотных серий с исходной задачей о плотном вложении. ;

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

Естественным обобщением задач второй главы было бы исследование плотных серий с одновременными ограничениями на длину и вес серии. Это важно, например, в упомянутой задаче о плотном вложении со случайным шагом. I.

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

Результаты первой главы могут быть обобщены на случай плотного вложения с произвольным допуском (определение см. в разделе 1.4). В случае нижней оценки это обобщение делается полностью аналогично и проведено при доказательстве соответствующего результата в диссертации. С выводом верхней оценки в случае вложения с произвольным допуском d дело обстоит сложнее. Здесь также можно выписать систему рекуррентных соотношений, однако степень получаемого в результате уравнения равна d +1, поэтому при d> 2 найти ее решения в явном виде, как правило, не удается. И, таким образом, не удается выписать выражения для верхней оценки в явном виде.

При выводе предельных теорем второй главы были получены оценки для распределений наборов случайных индикаторов W и П. Наборы W (в разных теоремах их смысл несколько отличается) содержат информацию не только о наличии серий (плотных серий) с заданными свойствами, но и о местах этих серий в случайной последовательности. Следовательно, упомянутые оценки, вообще говоря, описывают свойства числа серий или плотных серий заданной длины с учетом их расположения в последовательности. Поэтому они могут быть полезны для расчета эффективности статистических процедур обнаружения разладки, учитывающих расположение в последовательности наиболее длинных серий (см., например, (Balakrishnan, 2002)).

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

Основными результатами диссертации являются:

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

2. Многомерная предельная теорема Пуассона для числа плотных серий большой длины с оценкой точности пуассоновской аппроксимации.

3. Многомерная предельная теорема Пуассона для числа плотных серий большого веса.

В заключение, пользуюсь случаем выразить искреннюю благодарность своему научному руководителю доктору физико-математических наук, профессору Ивченко Григорию Ивановичу и научному консультанту доктору физико-математических наук Михайлову Владимиру Гавриловичу.