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

Московский Государственный Университет имени М.В.Ломоносова

Механико-математический факультет

На правах рукописи УДК 519.7

Смирнова Ольга Сергеевна

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

01.01.09 — математическая кибернетика

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

Москва - 1994

Работа выполнена на кафедре математической статистики и случайных процессов механико-математического факультета Московского Государственного Университета им. М.В. Ломоносова.

Научный руководитель — академик АН СССР

А.Н. Колмогоров

— кандидат физико-математических наук М.В. Козлов

Официальные оппоненты — академик АТН РФ,

профессор В.Б. Кудрявцев

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

Ведущая организация — Институт математики СО РАН

отдел теоретической кибернетики

Защита диссертации состоится £2 Ил^МиСк 1994 г. в 16 часов 05 мин. на заседании специализированного совета N2 по математике (Д.053.05.05) при МГУ им. М.В. Ломоносова по адресу: 119899, Москва, Ленинские Горы, МГУ, механико-математический факультет, ауд 14-08.

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ.

Яд ,

Автореферат разослан сЛ^Лс/гцт.-^ 1994 г

Ученый секретарь Совета специализированного совета

Д.053.05.05 при МГУ, профессор В.Н. Чубариков

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

Актуальность темы. Исследавания популярных датчиков случайных чисел, включенных в состав математического обеспечения многих вычислительных машин, показал неправомерность их мсполь-зования в качестве моделей последовательностей независимых случайных величин. Были обнаружены [13] и [2 из списка работ автора] закономерности их поведения, могущие существенно исказить результаты исследований, в которых они применяются. Это легко объяснимо с точки зрения хорошо известных фактов сложностного подхода алгоритмической теории вероятности, так как вычислимая последовательность имеет конечную сложность, следовательно в ней содержится бесконечно много закономерностей. Более того, чем дольше будет работать датчик, тем худший результат получится, так как, чем более длинные фрагменты псевдослучайной последовательности будут исследованы, тем большее число нетривиальных закономерностей можно будет в ней обнаружить, что плохо согласуется с интуитивным понятием случайной последовательности.

Однако во многих задачах прикладной математики (например, имитационном моделировании) необходимо использование таких "датчиков случайных последовательностей".

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

кажающих результаты исследований. То есть, для дискретных данных ЭВМ достаточно моделировть величины, принимающей значения »/2т, I* = 0,... ,2т с вероятностью 1/2т, где т — разрядность данной машины, Ьт(х). Чтобы строить датчики такого вида, достаточно научиться получать последовательности нулей и единиц, соответствующие закону Бернулли с р = 1/2.

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

Научная новизна. Доказано существование вычислимой последовательности двоичных слов, в некотором смысле приближающих случайную УЗ-последовательность из примера, построенного П. Мартин-Лефом.

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

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

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

Апробация работы. 1. Седьмая всесоюзная конференция по математической логике. Новосибирск, 1984, секционный доклад.

2. Восьмая всесоюзная конференция по математической логике. Москва, 1986, секционный доклад.

3. Семинар "Временные поля" кафедры математической статистики и случайных процессов м/м факультета МГУ, 1988, 1989.

4. Межвузовская научная конференция, Математические чтения, Иваново, 1991. Доклад и демонстрация программы.

5. Семинар "Дискретные системы", Институт математики Сибирского отделения РАН, 1992.

Публикации. Все результаты диссертации опубликованы. Ниже приведен список из 9 работ автора по теме диссертации. Из них 4 работы выполнена в соавторстве с И.Г. Журбенко и И.А. Кожевниковой. Основные результаты с доказательствами содержатся в работах [5] и [7-9].

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

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

КРАТКОЕ СОДЕРЖАНИЕ ДИССЕРТАЦИИ

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

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

Следующая концепция алгоритмической случайности принадлежит П. Мартин-Лефу. Она является основным аппаратом, применяемым в данной работе, однако использовались и другие (сложностный и частотный) подходы, иногда на содержательном уровне, что позволило получить некоторые полезные результаты.

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

Ь{и\Г(и) > га} < 2~т, где Т(и>) = вир (и>п)).

хСш

Каждый тест случайности соответствует некоторому конструктивно формулируемому свойству с вероятностью единица — конструктивному закону теории вероятностей. Говорят, что последовательность выдерживает тест Тт.е. удовлетворяет соответствующему вероятностному закону, если !Р{и) конечно.

Определение. Последовательность называется случайной по Мартин-Лефу относительно меры Ь, если она выдерживает. любой Ь-тест случайности.

Т^еорема (Мартин-Леф). Существует универсальный тест Т, такой, что для любого теста 0 выполнено неравенство РУО, где символ "У" обозначает неравенство с точностью до аддитивной константы.

Следствие. Последовательность случайна (по мере Ъ) в смысле Мартин-Лефа тогда и только тогда, когда она выдерживает универсальный тест.

Простейший пример случайной последовательности и1, характеристической для двухкванторного предиката .Р(п)=(\/£)(3г)(5(£, г, п), принадлежит также П. Мартин-Лефу [5]. Известно, что более простых характеристических для вычислимых и перечислимых множеств, случайных последовательностей не существует [5, 6].

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

Исторически наиболее старой попыткой определить случайную последовательность как индивидуальный объект является частотный подход, основанный на идее фон Мизеса считать двоичную последовательность случайной, если существует предел частоты вхождения единиц в ее начальный п-фрагмент и такой же предел существует для каждой ее подпоследовательности. Оно настолько естественно, что было сделано много попыток формализовать его, определив корректно класс допустимых правил. Успех был достигнут А. Ше-нем, который определил такой класс допустимых преобразований пространства двоичных последовательностей, что множество последовательностей, выдерживающих все допустимые правила преобразования с сохранением частоты вхождения единицы, совпадает с классами последовательностей, случайных по Мартин-Лефу и наиболее

сложных. В этом смысле все три варианта определения случайной последовательности эквивалентны [6, 7].

Следующие два параграфа первой главы посвящены доказательству основных теоретических результатов работы (теоремы 1 и 2).

Первая из этих теорем утверждает, что существует формальный алгоритм, который генерирует последовательность {ж'} двоичных слов, таких, что предел их длин есть бесконечность, сходящуюся в определенном смысле к последовательности, обладающей всеми свойствами последовательности независимых испытаний с вероятностью успеха 1/2, а именно к двухкванторной случайной последовательности из известного примера Мартин-Лефа, которая всюду далее будет обозначаться ш1.

Теорема 1 (о построении последовательности слов, монотонно приближающих и1). Существует такая последовательность двоичных слов {х"}, хп = Л(п), где А — общерекурсивная функция, что:

(1) Для каждого п слово х" лексикографически не превосходит начальный фрагмент ы1 той же длины.

(2) Начиная с некоторого номера по, каждое слово хп, п > по, содержит начальный фрагмент уп, являющийся также начальным фрагментом о*1, причем для бесконечно многих п выполнено равенство хп = у11.

(3) Функция А(п), равная длине уп, монотонно не убывая, стремится к бесконечности при п —► оо, причем не существует вычислимой нижней оценки скорости роста А(п).

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

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

Несмотря на то, что не все слова х* являются фрагментами предельной случайной последовательности, они могут использоваться как временные версии таблицы случайных чисел, тем лучшие, чем больше их длина и номер. Действительно, можно показать, что для всех достаточно длинных слов, или что то же, для таблиц с достаточно большими номерами, частота появления единицы мало отличается от 1/2, это верно и для выборок из таблиц, полученных с помощью достаточно простых правил выбора, при том тем большего их числа, чем длиннее таблица. Доказательство этого важного свойства последовательности таблиц основывается на теореме о примитивнорекур-сивном тесте случайности.

Теорема 2. Если тест случайности О

(1) примитивно рекурсивен,

(2) с(£(х),0) < 1(х), начиная с некоторого х,

где 1(х) обозначает длину слова х, а с(х,у) — канторовская нумерационная функция для пары, то 6(х) < х) + Сд для всех достаточно длинных слов х и для некоторой постоянной величины Сд, зависящей от теста

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

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

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

Определение Будем называть набор чисел б,-, г = 1,... , N согласованным набором значений тестов Т,, если существует случайная последовательность, на которой одновременно выполнены все N неравенств ^(и) < б,-, » = 1,... , N.

Очевидно, если С,- таковы, что Т + С,-, то для любого С набор С,- + С, г = 1,... , N согласован. Пусть теперь для всех Т{

выполнены условия теоремы 2. Определим ограниченный алгоритм Л', заменив в определении алгоритма А проверку ограниченности универсального теста на проверку ограниченности всех тестов семейства Ti согласованным набором констант.

Теорема 3. Последовательность слов zn = Л'(п) имеет предельную последовательность, на которой все тесты Т{ ограничены величинами Ci + 1.

Последовательность zn имеет предельные свойства, отчасти аналогичные свойствам последовательности {х1}, однако предельная последовательность уже не будет случайной, хотя и будет обладать заданным набором свойств настоящей случайной последовательности.

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

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

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

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

Теорема 4. Если набор тестов содержательно согласован, то модифицированный алгоритм вырабатывает бесконечную последовательность слов {х£}, содержащую бесконечную подпоследовательность у^ С у| С • ■ • С ■ ■ ■

Естественно определить бесконечную последовательность

ы = Л"(0 = «Ч> У?

п

как результат переработки стратегии £ алгоритмом А" ■

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

Список работ автора по теме диссертации. 1. Смирнова О. С. О монотонных приближениях для некоторой последовательности случайной по Мартин-Лефу. // Седьмая всесоюзная конференция по математической логике. Новосибирск, 1984. С. 170.

2. Журбенко И.Г., Кожевникова И.А., Смирнова О.С. О построении и исследовании псевдослучайных последовательностей различными методами. // Заводская лаборатория. N 5, 1985, С. 47-51.

3. Журбенко И.Г., Смирнова О. С. О некоторых свойствах датчиков случайных чисел. // Труды семинара Проблемы устойчивости стохастических моделей. Москва, 1987. С. 36-40. 4. Смирнова О.С. О некоторых свойствах последовательности асимптотически сложных двоичных слов. // Восьмая всесоюзная конференция по математической логике. Москва, 1986. С. 180.

5. Смирнова О.С. О построении последовательности асимптотически сложных двоичных слов. // Алгебраические и дискретные системы. Межвузовский сб. научных трудов. Иваново, 1988. С. 95102.

6. Журбенко И.Г., Смирнова О.С. Моделирование двоичной последовательности со слабой зависимостью. //IV Всес. научно-техническая конф. Применение многомерного статистического анализа в экономике и оценки качества продукции. Тезисы докладов. Тарту, 1989. Часть 1. С. 91-92.

7. Смирнова О.С. Теорема о примитивнорекурсивном тесте случайности. // В сборнике Алгебраические системы. Иваново, 1991. С. 89-96.

8. Журбенко И.Г., Смирнова О. С. Об алгоритме датчика случайных чисел со слабой корреляцией. // Статистические методы оценивания и проверки гипотез. Пермь, 1991. С. 107-120.

9. Смирнова О.С. Алгоритмы поиска с возвращением на двоичном дереве для построения псевдослучайных последовательностей // Итоговый сборник "Университеты России". Москва, 1994. С 142-144.

ЛИТЕРАТУРА

1. Колмогоров А.Н. О таблицах случайных чисел. // Семиотика и информатика. 1981. Вып.18. Перевод с англ.: Kolmogorov A.N. On the Tables of Random numbers. Sankhya. The Indian Jurnal of Statistics. Ser. A, 1963. 25. Part. 4. P. 369-376.

2. Колмогоров А.Н. Три подхода к определению понятия количества информации. // Проблемы передачи информации, I (1965). N 1, С. 3-5.

3. Kolmogorov A.N. On logical foundation of probability theory. Lecture notes in mathematics. // V. 1021. Probability theory and mathematical statistics. 4-th USSR-Japan Symposium. Springer-Verlag, 1982. P. 1-5.

4. Loweland D. The Kleene hierarchy classification of recursively random sequences. // Transaction of Amer. Math. Society. 1966. 125. N 3. P. 497-510.

5. Звонкин А.К., Левин JI.А. Сложность конечных объектов и обснование понятия информации и случайности с помощью теории алгоритмов. // УМН. Т. 25 (1970). N 6. С. 85-127.

6. Вьюгин В.В. Алгоритмическая энтропия (сложность) конечных объектов и ее применение к определению случайности и количества информации. // Семиотика и информатика. 1981. Вып. 16 С. 14-43.

7. Шень А. Частотный подход к определению случайной последва тельности. // Семиотика и информатика. 1982. Вып. 18. С. 14-42.

8. Кнут Д. Искусство программирования для ЭВМ, Т. 2. М Мир, 1977.

9. Невзоров В.Б. Распределение максимального значения в последовательностях выборочных средних. // Теория вероятностей и ее применения. Т. XXXII. Вып. 1. Москва, 1987.

10. Феллер В. Введение в теорию вероятностей и ее приложения. // Москва, Мир, 1967.

11. Ширяев А.И. Вероятность. // Москва, Наука, 1980.

12. Мальцев А.И. Алгоритмы и рекурсивные функции. // Москва, Наука, 1965.

13. Журбенко И.Г., Кожевникова И.А., Клиндухова О.В. Определение критической длины последоательности псевдослучайных чисел. // Вероятностно-статистические методы исследований (сборник статей). Москва, МГУ, 1983. С. 18-39.

МГУ, Москва« Лснаекк горы. 75 »к». 01.ОЗ.94