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

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

Меженная Наталья Михайловна

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

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

- 1 окт

Специальность 01.01.05 - «Теория вероятностей и

математическая статистика»

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

003478068

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

Научный руководитель:

доктор физико-математических наук, профессор, действительный член Академии криптографии РФ Ивченко Григорий Иванович

Научный консультант:

доктор физико-математических наук, ведущий научный сотрудник, действительный член Академии криптографии РФ Михайлов Владимир Гаврилович

Официальные оппоненты:

доктор физико-математических наук, профессор Хаметов Владимир Минирович доктор физико-математических наук Шойтов Александр Михайлович

Ведущая организация:

Московский государственный университет им. М.В. Ломоносова, механико-математический факультет

Защита состоится 20 октября 2009г. в 16 часов на заседании Диссертационного Совета Д 212.133.07 Московского государственного института электроники и математики по адресу: 109028, Москва, Большой Трехсвятительский переулок,

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

Автореферат разослан 18 сентября 2009г.

Ученый секретарь Диссертационного Совета Д 212.133.07

кандидат физико-математических наук.

Д.3/12.

доцент

П.В. Шнурков

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

Актуальность.

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

Понятие плотного вложения было введено в математическую литературу в работе (воИс, 1996). Пусть Хп = {х,}"_1 и = -последовательности знаков алфавита ЛЛ,={0,...,^-1}. Согласно (СоИс, 1996), последовательность Хп плотно вкладывается в начало последовательности Ут, если п<т и найдутся такие натуральные числа

1 = д < ]г <... < /„ < т, - ¡к е (1,2), к = 1,... ,п -1, [1) что хк=у^,к=1,...,п.

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

(Golic, 1996).

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

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

Серии в достаточной для многих приложений степени отражают статистические свойства случайной

последовательности. Задача о числе серий успехов в последовательности Бернулли хорошо известна в литературе. Одно из первых упоминаний этой задачи в контексте пуассоновской аппроксимации содержится в статье (von Mises, 1921). В дальнейшем было изучено предельное распределение цепочек из единиц, длины максимальной серии из единиц, времени до первого появления серии заданной длины и ряда сопутствующих величин (см., например, (Arratia, 1990), (Arratia, 1989), (Godbole, 1991), (Rajarshi, 1974), (Balakrishnan, 2002), (Савельев, 2003), (Barbour, 1987), (Barbour, 1992), (Barbour, 2002), (Chryssaphinou, 1989), (Chiyssaphinou, 2001), (Erchardsson, 2005), (Fuchs, 1965) и др.).

Понятие серии получило ряд обобщений (см., например,

(Wolfowitz, 1944), (Chryssaphinou, 2001)). Различнее применения теории серий в статистике хорошо известны (см., например, (Glaz, 2001), (Balakrishnan, 2002) и др.).

В работе (Golic, 1996) была получена оценка сверху для вероятности Рт{Х„) плотного вложения последовательности Хп в

последовательность ^1Я = {у(}21 независимых случайных величин, распределенных равномерно на множестве А2. В диссертации получено обобщение результата работы (Golic, 1996) на случай конечного алфавита AN с произвольным числом букв и показано, что эта верхняя оценка не улучшаема. Построена также неулучшаемая оценка снизу для вероятности Рт(Хп), которая достигается на последовательностях Хл, состоящих из п одинаковых знаков.

Это свойство минимальности вероятнрсти плотного вложения для последовательности из одинаковых знаков в контексте криптографических проблем, рассматривавшихся в работе (Golic, 1996), привлекает интерес к специальному изучению плотно заполненных отрезков в случайной последовательности. Отрезок последовательности х1,...,хк из знаков алфавита AN мы называем плотно заполненным знаком аеAn, если ae{x,,xi+1}, i = l,...,fr-l. Распределение числа плотно заполненных отрезков в случайной последовательности можно вывести из распределения числа плотно заполненных серий. Плотно заполненный (знаком а) отрезок назовем плотной а-серией, если он не содержится ни в каком плотно заполненном отрезке большей длины. Длиной плотной а -серии назовем длину

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

Цель работы.

Основные цели диссертационной работы:

1. вывод неулучшаемых верхней и нижней оценок вероятности плотного вложения заданной дискретной последовательности в последовательность независимых случайных величин Ут, равномерно распределенных на множестве Ан = {0,...,М~1},М>2;

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

Методы исследования.

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

Научная новизна.

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

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

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

6

пуассоновской аппроксимации.

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

Теоретическая и практическая значимость.

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

Результаты диссертации могут представлять интерес для специалистов, занимающихся приложениями теоретико-вероятностных методов в экономических, технических и других

областях. Разработанные в диссертации приемы реализации

i

метода Чена-Стейна могут быть полезны при доказательстве предельных теорем в задачах дискретной теории вероятностей.

Апробация работы.

Результаты диссертации докладывались на 5-8 Всероссийских симпозиумах по прикладной и промышленной математике (2005-2007 гг.), на VII Международной Петрозаводской конференции «Вероятностные методы в дискретной математике» (2008 г.), в Московском государственном институте электроники и математики (20062009 гг.), на семинаре отдела дискретно^ математики Математического института им. ВА Стеклова РАН (2009 г.).

Публикации.

Основные результаты диссертации опубликованы в 10 работах, работы [1] и [10] - в изданиях, входящих в утвержденный ВАК перечень ведущих рецензируемых научных

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

Структура и объем диссертации.

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

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ.

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

Глава 1 диссертации посвящена выводу оценок вероятности плотного вложения Рт(Хп) в случае конечного алфавита Ак с произвольным числом букв.

В разделе 1.1 приведены постановка задачи и формулировки результатов первой главы.

Теорема 1.1. Пусть знаки последовательности = распределены на множестве А„ независимо и равномерно. Тогда для любого т>п

рт(х„) < р2т < -^{(а/ - +[ы+(2)

Оценки в этой теореме при N=2 совпадают с оценками работы (СоНс, 1996).

Теорема 1.2. Пусть знаки последовательности Ут={у1}™_1 распределены на множестве Ан независимо и равномерно. Тогда для любого т>п

1 т-п ( 1

я1N° а ы

(3)

Из (3) следует, что при 2п-1<т

Теорема 1.3. Пусть последовательностьХп удовлетворяет условию

»=1,2,...,п-1. (4)

Тогда

^ Р2„С^П3 = - л/А^^)'1 + + л/Л^У)" С5)

Теорема 1.4. Если последовательность Ха состоит из п одинаковых знаков, то

А т~п ( А

• (Я

если п<т<2п-1, и

(7)

если 2п-1<т.

Получены предельные соотношения для логарифма вероятности плотного вложения при согласованном росте параметров п,т.

В разделе 1.2 приведены точные значения вероятности плотного вложения в некоторых частных случаях, а также

некоторые замечания о свойствах этой вероятности. Доказательства теорем из раздела 1.1 содержатся в разделах 1.3, 1.4 и 1.5. В разделе 1.6 предложены несколько критериев проверки гипотезы о плотном вложении Я0п, состоящей в том, что последовательность Хп =(xlf.элементов множества An = {0,...,JV-1) извлечена из начала последовательности независимых равномерно распределенных на множестве А„ случайных величин Ym = {у,}^ как ее плотная

подпоследовательность. Это означает, что существуют такие натуральные числа

1 = jx < j2 <... < j„ < т, jM - j\ e (1,2}, к = 1.....n-1, (8)

что xk=yh,k=l,...,n. Ясно, что извлеченная из начала последовательности Ym последовательность Хп всегда может быть плотно вложена в начало последовательности Ym.

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

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

В доказательствах предельных теорем главы 2 используется известный метод Чена - Стейна. Необходимые сведения об этом методе и об особенностях его применения при изучении серий событий в последовательности независимых случайных величин

приводятся в разделе 2.2. Там же демонстрируется методика применения метода Чена - Стейна при дрказательстве многомерных теорем пуассоновского типа на примере задачи о числе обычных серий больших длин.

Плотные серии заданной длины изучаются в разделах 2.3 -2.7. В разделе 2.3 выведена формула для вероятности появления плотной серии заданной длины в заданном месте последовательности.

Пусть Х = {Х_1Д0,Х1,...,ХГ,...} - последовательность независимых случайных величин, принимающих значения из множества {0,...,^—1} с вероятностями Будем

говорить, что в момент I началась плотная серия единиц длины 5>1, если 1,^ = ^ = 1, и

последовательность Хс,...,Х!+^1 плотно заполнена единицами.

Пусть событие Е( означает, что в момент Ь началась плотная серия единиц длины 5.

Пусть

,_ Р[1~Р)4 Р + УР(4-ЗР) р-Ур(4-Зр)

^рс^ад 2 2 • (9]

Теорема 2.3. При любых в>3, 1<£<Т и рер),1) выполнены соотношения

Р{ЕЛ=с(я°-Я1), (10)

Р{Е(Л>Р{Е,^}. (И)

Заметим, что формула (10) верна при любых 5 > 1, а именно Р{Е1Д}=р(1 - р)\ Р{ЕЦ}=р2(1 - р)4.

Кроме того, Р{Е13} = Р{Еез}..

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

При к > 1,5 £ 1 определим случайные величины

= (12)

со

кч

равные числу плотных серий единиц, которые начинаются в моменты времени от 1 до Г и имеют длину к ц не меньше 5 соответственно. Число плотных цепочек единиц длины 5 обозначим через 9!Т. Ясно, что при 5>3

*=0 1

Пусть

Лк =Ед„кх =ТР{Е1мк), к = 0.....г-1, (14)

Обозначим через независимые случайные

величины, распределенные по закону Пуассону с параметрами Пусть р(Х,У) - расстояние по вариации между распределениями случайных величин X и У.

Теорема 2.5. Пусть s > 3, г > 1. Тогда при любом d> О

<|(r+£/+l)^|'5+r+d+4+-lz£_]+2 J Лt. (15)

(1 -рУ

k=r+d+1

Здесь пк - случайная величина, распределенная по закону Пуассона

со

с параметром Лг = и не зависящая от случайных величин

Jc=r

Теорема2.6. Пусть s>3, г>1. Гог<Эа

.....^ ,7ГК в < (16)

<^(r+p(l-p)1 + (l-pr2)2(s+2r+2,5).

Доказательство второго варианта оценки (теорема 2.6) является более громоздким, но в ряде случаев оценка (16) оказывается более предпочтительной.

В разделе 2.6 из оценок (15) и (16) выведены предельные теоремы пуассоновского типа для числа плотных серий заданных длин и длины не меньше заданной, для числа плотно заполненных отрезков.

Теорема 2.7. Пусть s,T -»<»,

Лд Я, 0 < Л < со. (17)

Тогда при любом натуральном числе г случайные величины Gs.T>€n-i.T>-">Gs+r-iT'£s+rT асимптотически независимы в совокупности и имеют в пределе распределения Пуассона с параметрами A,ql,...,qr"1A,(l-q)"1qrA соответственно.

Теорема 2.8. В условиях теоремы 2.7 распределение

случайной величины в пределе совпадает с распределением

00

суммы + где як,к=ОД,..., - независимые случайные

величины, имеющие распределение Пуассона с параметрами цк~гЛ соответственно.

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

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

Пусть событие означает, что в момент £ началась

плотная серия единиц веса IV в последовательности У,

(=1

ф

ыо

Теорема 2.10. Пусть Т-> оо, т - целое неотрицательное число, а параметр w меняется так, что

Тр( 1 - р)2 р""1 Л, 0 < Л < оо, р = р+р(1 - р). Тогда случайные величины ^^Сг-Си-С-.г асимптотически независимы в совокупности и имеют в пределе

БтЛ

распределения Пуассона с параметрами —

1-р

соответственно.

Разделы 2.9 и 2.10 посвящены изучению на конкретных

примерах реальной точности пуассоновской аппроксимации в задачах о плотных сериях. В разделе 2.9 при помощи аппарата цепей Маркова выводятся рекуррентные формулы, дозволяющие вычислить распределение числа длинных плотных серий единиц и распределение числа плотных серий единиц, имеющих вес не меньше заданного, в отрезке неоднородной цепи Маркова с двумя состояниями. В разделе 2.10 эти формулы испрльзуются для вычисления распределений этих величин в равновероятной последовательности Бернулли при разном выбрре длины этой последовательности и при разных ограничениях на длину и вес плотной серии. Найденные распределения сравниваются с сопровождающими распределениями при конкретных значениях параметров, которые были получены ранее в разделах 2.4-2.8.

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

Благодарности.

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

СПИСОК РАБОТ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ.

1. Михайлов В.Г., Меженная Н.М. Оценки для вероятности плотного вложения одной дискретной последовательности в другую. Дискретная математика, 2005, т. 17, вып. 3., с. 19-27.

2. Меженная Н.М. Предельные теоремы для сэрий исходов в последовательности Бернулли с разладками. Обозрение Прикладной и Промышленной Математики, 2005, т. 12, вып. 2., с. 437-439.

3. Меженная Н.М. О скорости сходимости распределения числа

серий различной длины в случайной последовательности с

i

«разладками» к распределению Пуассона. Обозрение Прикладной и Промышленной Математики, 2007, т. 14, вып. 2., с. 248-249.

4. Меженная Н.М. Формулы для вычисления совместного распределения максимальных длин серий в конечной марковской цепи Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. Тезисы докладов. - М.: МИЭМ, 2007, с. 8-9.

5. Меженная Н.М. Многомерная нормальная теорема для числа монотонных серий заданной длины в равновероятной случайной последовательности. Обозрение Прикладной и Промышленной Математики, 2007, т. 14, вып. 3., с. 503-505.

6. Меженная Н.М. Предельные теоремы для ч^сла плотных серий в случайной последовательности. Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. Тезисы докладов. - М.: МИЭМ, 2008, с. 11-13.

7. Меженная Н.М. Предельные теоремы пуассоновского типа для числа плотных серий в случайной последовательности.

Обозрение Прикладной и Промышленной Математики, 2008, т. 15, вып. 3, с. 565-566.

8. Меженная Н.М. Многомерные предельные теоремы пуассоновского типа для обычных и плотных серий в бернуллиевской последовательности. Деп. в ВИНИТИ 11.12.2008, № 939-В2008,23с.

9. Меженная Н.М. Асимптотическое и точное выражения для распределения числа плотных серий большого веса. Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. Тезисы докладов. - М.: МИЭМ, 2009, с. 16-17.

10. Меженная Н.М. Предельные теоремы для числа плотных серий в случайной последовательности. Дискретная математика, 2009, т. 21, вып. 1, с. 105-116.

СПИСОК ЛИТЕРАТУРЫ

Arratia R., Goldstein L., Gordon L. Poisson Approximation and the Chen-Stein Method. Statistical Science, 1990,v. 5, No. 4, P- 403-424.

Arratia R., Goldstein L., Gordon L. Two Moments Suffice for Poisson Approximations: The Chen-Stein Method. The Annals of Probability, 1989, v. 17, No. 1, p. 9-25.

Balakrishnan N., Koutras M. V. Runs and Scans with applications. New-York, Wiley, 2002.

Barbour A. D., Hoist L., Janson S. Poisson Approximation. Oxford, Oxford Univ. Press, 1992.

Barbour A.D. Asymptotic Expansions in the Poisson Limit Theorem. The Annals of Probability, 1987, v. 15, No. 2, p. 748-766.

Barbour A.D., Cekanavifius V. Total Variation Asymptotics for Sums of Independent Integer Random Variables. The Annals of Probability, 2002, v. 30, No. 2, p. 509-545.

Chiyssaphinou O., Papastavridis S. A Limit Theorem for the Number of Non-Overlapping Occurrences of a Pattern in a Sequence of Independent Trials. Journal of Applied Probability, 1988, v. 25, No. 2, p. 428-431.

Chryssaphinou O., Vaggelatou E. Compound Poisson Approximation for Long Increasing Sequences. Journal of Applied Probability, 2001, v. 38, No.2, p. 449-463.

Erchardsson T. Stein's method for Poisson and cpmpound Poisson approximation. Из сборника An Introduction to Stein's Method. Barbour A.D., Chen L. H. Y. (ред), Singapore, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, 2005, v. 4.

Fuchs С. E., David Н. Т. Poisson Limits of Multivariate Run Distributions. The Annals of Mathematical Statistics, 1965, v 36, No. 1, p. 215-225.

Glaz J., Naus J., Wallenstein S. Scan Statistics. New York, SpringerVerlag, 2001.

Godbole A.P. Poisson Approximations for Runs and Patterns of Rare Events. Advances in Applied Probability, 1991, v. 23, No. 4, p. 851865.

Golic J. Dj. A generalized correlation attack on a class of stream ciphers based on Levenshtein distance. J. Cryptology, 1991, v. 3, p. 201212.

Golic J. Dj. Constrained embedding probability for two binary strings. SIAM J. Discrete Math.,v.9, No. 3,1996, p. 360-364.

Rajarshi M. B. Success Runs in a Two-State Markov Chain. Journal of Applied Probability, 1974, v. 11, No. 1, p. 190-192.

von Mises R. Das Problem der Iterationen. Z. Angew. Math. Mech., 1921, v. 1, p. 298-307.

Wolfowitz J. Asymptotic distribution of runs up and down. Ann. Math. Statist., 1944, v. 15, p. 163-172.

Zivkovic M.V. An algorithm for the initial state reconstruction of the clock controlled shift register. IEEE Trans. Inform. Theory, 1991, v. 37, p. 1488-1490.

Савельев Л.Я., Балакин C.B., Хромов Б.В. Накрывающие серии в двоичных марковских последовательностях. Дискретная математика, 2003, Т. 15, вып. 1, с. 50-76.

Подписано к печати" 11 " СеИТ$»£рЯ2009 г. Отпечатано в отделе оперативной полиграфии МИЭМ.

Москва, ул. М. Пионерская, д. 12. Заказ № 182 . Объем ЬО п.л. Тираж. 400 экз.

0 ВВЕДЕНИЕ

1 ОЦЕНКИ ДЛЯ ВЕРОЯТНОСТИ ПЛОТНОГО ВЛОЖЕНИЯ ОДНОЙ ДИСКРЕТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ В ДРУГУЮ

1.1 Постановка задачи и формулировки результатов

1.2 Точные значения вероятности плотного вложения

1.3 Доказательство теорем 1.1 и 1.

1.4 Доказательство теорем 1.2 и 1.

1.5 Доказательства вспомогательных утверждений

1.6 Проверка гипотезы о плотном вложении

2 ПРЕДЕЛЬНЫЕ ТЕОРЕМЫ ДЛЯ ЧИСЛА ПЛОТНЫХ СЕРИЙ В СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ

2.1 Предварительные замечания

2.2 О методе доказательства многомерных предельных теорем пуассоновского типа

2.3 Вероятность появления плотно заполненной серии заданной длины

2.4 Оценки расстояния по вариации

2.5 Оценки расстояния по вариации - 2 i

2.6 Предельные теоремы для числа длинных плотных серий

2.7 Асимптотическое поведение распределения наибольших длин плотных серий

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

2.9 Формулы для вычисления точных распределений числа плотных серий

2.10 Оценивание точности пуассоновской аппроксимации

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

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

Ym={yi}™1 - последовательности знаков алфавита Аы = {О,.,N — 1}. Согласно (Golic, 1996), последовательность X плотно вкладывается в начало I последовательности Ym,eели п<т и найдутся такие натуральные числа l = jl<j2<.<jn<mtjk+1-jksE{l,2})k = l,.,n-l, (0.1) что xk=yjk,k = l,.,n.

Понятие плотного вложения возникает при изучении свойств последовательностей, генерируемых конечными автоматами из нескольких параллельно функционирующих блоков, выходные последовательности которых соединяются в одну общую последовательность без нарушения порядка следования букв. Например, если генератор случайных' чисел состоит из двух блоков, в последовательность, вырабатываемую первы|ч блоком, добавляются знаки, выработанные вторым блоком, причем не более одного знака подряд, то выходная последовательность первого блока будет плотно вложена в выходную последовательность генератора. Роль этого свойства при изучении генераторов случайных чисел описана в работах (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. Многомерная предельная теорема Пуассона для числа плотных серий большого веса.

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

1. Arratia R., Goldstein. L., Gordon L. Poisson Approximation and the Chen-Stein Method. Statistical Science, 1990,v. 5, No. 4, p. 403-424.

2. Arratia R., Goldstein L., Gordon L. Two Moments Suffice for Poisson Approximations: The Chen-Stein Method. The Annals of Probability, 1989, v. 17, No. 1, p. 9-25.

3. Balakrishnan N., Brito M.R., Quiroz A.J. Using large order statistics of runs for tracking a changing Bernoulli probability. Commun. Statist.: Theory Meth., 2002, v. 31, No. 5, p. 719-732.

4. Balakrishnan N., Koutras M. V. Runs and Scans with applications. New-York, Wiley,2002.

5. Barbour A. D., Hoist L., Janson S. Poisson Approximation. Oxford, Oxford Univ. Press, 1992.

6. Barbour A.D. Asymptotic Expansions in the Poisson Limit Theorem. The Annals of Probability, 1987, v. 15, No. 2, p. 748-766.

7. Barbour A.D., Cekanavicius V. Total Variation Asymptotics for Sums of Independent Integer Random Variables. The Annals of Probability, 2002, v. 30, No. 2, p. 509-545.

8. Barbour A.D., Chen L. H.Y., Loh W.-L. Compound Poisson Approximation for Nonnegative Random Variables Via Stein's Method. The Annals of Probability, 1992, v. 20, No. 4, p. 1843-1866.

9. Buldi P., Rinott Y. On normal approximations of distributions in terms ofidependency graph. Ann. Probab., 1989, v. 17, No. 5, p. 1646-1650.

10. Chryssaphinou 0., Papastavridis S. A Limit Theorem for the Number of Non-Overlapping Occurrences of a Pattern in a Sequence of Independent Trials, journal of Applied Probability, 1988, v. 25, No. 2, p. 428-431. I

11. Chryssaphinou 0., Papastavridis S., Vaggelatou E. Poisson limit theorems for theappearances of attributes. Из сборника Stein's Method and Applications. Barbour A.D.,i

12. Chen L.H.Y.(peA.. Singapour, Lecture Notes Series, Institute for Mathematical Sciences, National University of Singapore, 2005, v. 5.

13. Chryssaphinou О., Vaggelatou Е. Compound Poisson Approximation for Long Increasing Sequences. Journal of Applied Probability, 2001, v. 38, No.2, p. 449-463. Eagle R. ARCH. Oxford, Oxford Univ. Press, 1995.

14. Fu J. C., Koutras M. V. Distribution Theory of Runs: A Markov Chain Approach. Journal of the American Statistical Association, 1994, v. 89, p. 1050-1058.

15. Fu J.C. Distribution of the Scan Statistic for a Sequence of Bistate Trials. Journal of Applied Probability, 2001, v. 38, No. 4, p. 908-916.

16. Fu J.C., Wang L., Wendy Lou W. Y. On Exact and Large Deviation Approximation for the Distribution of the Longest Run in a Sequence of Two-State Markov Dependent Trials. Journal of Applied Probability, 2003, v. 40, No. 2, p. 346-360.

17. Fuchs С. E., David H. T. Poisson Limits of Multivariate Run Distributions. Thei

18. Annals of Mathematical Statistics, 1965, v 36, No. 1, p. 215-225.

19. Golic J. Dj. A generalized correlation attack on a class of stream ciphers based on Levenshtein distance. J. Cryptology, 1991, v. 3, p. 201-212.

20. Golic J. Dj. Constrained embedding probability for two binary strings. SIAM J. Discrete Math.,v.9, No. 3,1996, p. 360-364.

21. Rajarshi M. B. Success Runs in a Two-State Markov Chain. Journal of Applied Probability, 1974, v. 11, No. 1, p. 190-192.

22. Shewhart A.W. The economic control of the quality of manufactured product. New-York, Macmillan, 1931.von Mises R. Das Problem der Iterationen. Z. Angew. Math. Mech., 1921, v. 1, p. 298-307.

23. Wald A., Wolfowitz J. On a test whether two samples are from the same population. Ann. Math. Statist., 1940, v. 2, p. 147-162.

24. Wolfowitz J. Asymptotic distribution of runs up and down. Ann. Math. Statist., 1944, v. 15, p. 163-172.

25. Zivkovic M.V. An algorithm for the initial state reconstruction of the clock controlled shift register. IEEE Trans. Inform. Theory, 1991, v. 37, p. 1488-1490.

26. Зубков A.M., Михайлов В.Г. Предельное распределние случайных величин, связанных с длинными повторениями в последовательности независимых испытаний. Теория вероятностей и ее применения, 1974, Т. 19, вып. 1, с. 173-181.

27. Ивченко Г.И., Медведев Ю.И. Математическая статистика. Москва, Высшая школа, 1992, 2-е издание.

28. Михайлов В.Г. Предельная теорема Пуассона для числа пар почти полностью совпавших цепочек. Теория вероятностей и ее применения, 2008, Т. 53, вып. 1, с. 59-71.

29. Михайлов В.Г. Предельные теоремы пуассоновского типа для числа неполных совпадений s-цепочек. Теория вероятностей и ее применения, 2002, Т. 47, вып. 2, с. 713-723.

30. Савельев Л.Я., Балакин С.В. Совместное распределение числа единиц и числа 1-серий в двоичной марковской последовательности. Дискретная математика, 2004, Т. 16, вып. 3, с. 43-62.

31. Савельев Л.Я., Балакин С.В., Хромов Б.В. Накрывающие серии в двоичных марковских последовательностях. Дискретная математика, 2003, Т. 15, вып. 1, с. 50-76.

32. Самарова С.С. О длине максимальной серии "успехов" для марковской цепи с двумя состояниями. Теория вероятностей и ее применения, 1981, Т. 26, вып. 3, с. 510-520.

33. Уилкс С. Математическая статистика. Москва, Наука, 1967.

34. Феллер В. Введение в теорию вероятностей и ее приложения. Москва, Мир, 1984, Т. 1.

35. Феллер В. Введение в теорию вероятностей и ее приложения. Москва, Мир, 1984, Т. 2.

36. Холл М. Комбинаторика. Москва, Мир, 1970.

37. Ширяев А.Н. Вероятность. Москва, Наука, 1989, 2-е издание.

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

39. Михайлов В.Г., Меженная Н.М. Оценки для вероятности тесного вложения одной дискретной последовательности в другую. Обозрение Прикладной и Промышленной Математики, 2004, т. 11, вып. 4., с. 884.

40. Михайлов В.Г., Меженная Н.М. Оценки для вероятности плотного вложения одной дискретной последовательности в другую. Дискретная математика, 2005, т. 17, вып. 3., с. 19-27.

41. Меженная Н.М. Предельные теоремы для серий исходов в последовательности Бернулли с разладками. Обозрение Прикладной и Промышленной Математики, 2005, т. 12, вып. 2., с. 437-439.

42. Меженная Н.М. Обнаружение «разладки» последовательности Бернулли по нескольким наибольшим длинам серий. Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. Тезисы докладов. М.: МИЭМ, 2006, с. 15-16. ;

43. Меженная Н.М. О скорости сходимости распределения числа серий различной длины в случайной последовательности с «разладками» к распределению Пуассона. Обозрение Прикладной и Промышленной Математики, 2007, т. 14, вып. 2., с. 248-249.

44. Меженная Н.М. Формулы для вычисления совместного распределения максимальных длин серий в конечной марковской цепи Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. Тезисы докладов. М.: МИЭМ, 2007, с. 8-9.

45. Меженная Н.М. Многомерная нормальная теорема для числа монотонных серий заданной длины в равновероятной случайной последовательности. Обозрение Прикладной и Промышленной Математики, 2007, т. 14, вып. 3., с. SOS-SOS.

46. Меженная Н.М. Предельные теоремы для числа плотных серий в случайной последовательности. Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. Тезисы докладов. М.: МИЭМ, 2008, с. 11-13.

47. Меженная Н.М. Предельные теоремы пуассоновского типа для числа плотных серий в случайной последовательности. Обозрение Прикладной и Промышленной Математики, 2008, т. 15, вып. 3, с. 565-566.

48. Меженная Н.М. Многомерные предельные теоремы пуассоновского типа для обычных и плотных серий в бернуллиевской последовательности. Деп. в ВИНИТИ 11.12.2008, № 939-В2008,23с.

49. Меженная Н.М. Асимптотическое и точное выражения для распределения числа плотных серий большого веса. Научно-техническая конференция студентов, аспирантов и молодых специалистов МИЭМ. Тезисы докладов. М.: МИЭМ, 2009, с. 16-17.

50. Меженная Н.М. Предельные теоремы для числа плотных серий в случайной последовательности. Дискретная математика, 2009, т. 21, в^ып. 1, с. 105-116.