Применение колмогоровской теории алгоритмической сложности к логическим основам теории вероятностей тема автореферата и диссертации по математике, 01.01.06 ВАК РФ

Введение

Используемые обозначения

1. Случайность конечных объектов

2. Некоторые понятия алгоритмической теории случайности

2.1. Вычислимые функции.

2.2. Рекурсивно перечислимые полумеры.

2.3. Алгоритмическая случайность.

3. Прогнозирование конечных последовательностей

3.1. Виды прогнозирования конечных последовательностей

3.2. Предсказательная сложность.

3.3. Трудно предсказуемые последовательности.

3.4. Доказательство предложения 3.4.

3.5. Доказательство предложения 3.5.

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

5. Вероятностное прогнозирование конечных последовательностей

5.1. Перечислимые снизу супермартингалы.

5.2. Равномерные тесты случайности.

5.3. (о;,/3)-нестохастические последовательности.

6. Алгоритмический анализ эргодической теоремы Бирк

6.1. Сходимость по вероятности.

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

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

7.1. Лемма о росте супермартингала.

7.2. Метод разрезания и складывания.

7.3. Теоремы о неустойчивости.

8. Алгоритмически-инвариантные свойства последовательностей

8.1. Алгебра инвариантных свойств.

8.2. Сети и потоки.

8.3. Доказательство теоремы 5.2.

8.4. Доказательство теоремы 8.2.

8.5. Доказательство теоремы 8.3.

8.6. Сводимость атомов.

Актуальность темы. Теория вероятностей в классической формулировке А.Н.Колмогорова [18] представляет собой аксиоматическую теорию, являющуюся частью теории меры. Математическая статистика и теория информации используют аппарат теории вероятностей и имеют те же основания. Одновременно с развитием математической теории постоянно обсуждались вопросы применимости теории вероятностей к явлениям реального мира. В настоявшее время в практических приложениях общепринятой является частотная интерпретация вероятности (см. например, учебники [2, 10, 41]). А.Н.Колмогоров, предложивший глубокие уточнения частотной интерпретации в своей знаменитой книге [18], продолжал исследования в области обоснования приложений теории вероятностей. Первая попытка построить теорию алгоритмической случайности для конечньпс последовательностей была предпринята им в работе [60 .

В результате своих исследований А.Н.Колмогоров предложил в начале 60-тых годов программу построения математической теории, обосновывающей приложения теории вероятностей на основе теории алгоритмов [15,16]. Согласно этой программе практические выводы теории вероятностей могут быть обоснованы в качестве следствий гипотез о предельной (при данных ограничениях) сложности изучаемых явлений. При таком подходе основным является понятие алгоритмической сложности конечного объекта.

Идеи А.Н.Колмогорова были частично реализованы его учениками и последователями. В частности, Левиным [24, 27, 26] и Шнорром 77, 78] были определены различные варианты колмогоровской сложности - префиксная и монотонная сложности, сложность разрешения, была развита колмогоровская теория алгоритмической случайности. Отметим также аналогичные публикации Чейтина [47, 48 .

Классическая теория вероятностей не в состоянии даже поставить задачу определения понятия индивидуальной случайной последовательности. Одним из первых достижений колмогоровской теории сложности было математическое определение, на основе теории алгоритмов, понятия индивидуальной случайной (по Мартин-Лёфу) последовательности [68]. Оказалось, что возможны различные варианты алгоритмического определения бесконечной случайной последовательности, приводящие однако, к одному и тому же классу последовательностей [19].

Следует отметить, что сам Колмогоров неоднократно подчеркивал также важность изучения понятия случайности конечных объектов [15, 17]. Он ввел понятие дефекта случайности d{x\A) конечного слова X, принадлежащего конечному множеству Л, относительно этого множества и сформулировал в 1973 г. проблему изучения зависимости дефекта случайности от алгоритмической сложности множества А. Формы кривых зависимостей дефекта случайности от сложности множества А изучаются в диссертации.

Доклад Колмогорова в 1982 г. на семинаре в Московском университете породил исследования алгоритмического понятия (а, ¡3)-стохастического объекта. Колмогоров также сформулировал задачу изучения асимптотики меры множества нестохастических последовательностей длины п. Оценки доли (равномерной меры) таких последовательностей были получены Шенем [39]. Обобщение этой задачи Колмогорова возможно в рамках вычислительной теории самообучающихся алгоритмов (Computational Learning Theory), в которой рассматриваются произвольные способы оценки потерь при использовании различных предсказательных алгоритмов. В диссертации проводится анализ предельных возможностей различных алгоритмических методов предсказания (прогнозирования) и классификации на основе понятия предсказательной сложности [90, 92].

Независимо, Р.Дж.Соломонов [80] (см. также [79, 81]) пытался построить универсальный метод для предсказания будущих исходов на основе уже известных исходов. При этом такой метод должен использовать как можно более широкие предположения о механизме порождения данных. Общим в обоих подходах явилось использование универсальной машины Тьюринга, что привело Колмогорова к определению понятия алгоритмической сложности конечного слова как длины самого короткого описания этого слова с помощью этой машины. Соломонов использовал универсальную машину Тьюринга для построения своего универсального предсказателя. Позже эта идея Соломонова нашла точное математическое выражение в 1970 г. в виде понятия универсальной или априорной полумеры, введенного Л.А.Левиным [12 .

Совокупность результатов, связанных с исследованием свойств колмогоровской сложности и ее применений к основаниям теории вероятностей и теории информации, объединяется под общим названием - алгоритмическая теория случайности. Ряд обзоров суммируют результаты исследований: Звонкий и Левин (1970) [12], Вьюгин (1981) [97], Колмогоров и Успенский (1987) [19], Ли и Ви-таньи (1988) [28], Успенский, Семенов, Шень (1990) [36], Мучник, Семенов, Успенский (1998) [71], Вьюгин (1999) [108]. Основополагающая монография в этой области опубликована Ли и Витаньи [65].

Последние годы получено много результатов о колмогоровской сложности и определенном на ее основе понятии количества информации между словами. В частности, в [58] изучались линейные неравенства для колмогоровской сложности, в [84] изучалось информационное расстояние между словами, в работах [70, 33] изучалась возможность материализации общей информации.

Более подробно остановимся на результатах, связанных с применением колмогоровских идей алгоритмической случайности к вопросам обоснования теории вероятностей и математической статистики. Значительный прогресс в развитии алгоритмического подхода и его приложений к теории вероятностей был достигнут в работах В.Г.Вовка. В [3] была установлена связь между колмогоровским определением бернуллиевской последовательности и определением бернуллиевости на основе дефекта случайности. В [4, 6] получены чисто алгоритмические доказательства закона больших чисел и закона повторного логарифма для индивидуальных последовательностей случайных относительно бернуллиевских мер. Были также найдены точные условия выполнимости каждого из этих законов на индивидуальных последовательностях. Условие выполнимости задается в виде специфической для данного закона асимптотики дефекта алгоритмической случайности (1(х) начальных фрагментов этой последовательности: для выполнения закона больших чисел на индивидуальной последовательности и1и)2 • • • достаточно потребовать (¿{л1. .Шп) = о{п), ДЛЯ выполнения закона повторного логарифма достаточно . .CJJn) = o{loglogn).

Вопросы асимптотической эффективности оценок (множества точек сверхэффективности) изучались в [8] с применением алгоритмической случайности. Анализ и построение оптимальных алгоритмов вероятностного прогнозирования проводились в работах 5, 7, 87].

До последнего времени открытой оставалась проблема применимости эргодической теоремы Биркгофа [42] к индивидуальным случайным последовательностям. Вопрос об этом был поставлен в монографии ван Ламбальгена [62]. Вопросы алгоритмического анализа различных аспектов эргодической теоремы является предметом изучения в диссертации. Часть результатов диссертации связана с исследованием применимости эргодической теоремы к индивидуальным последовательности с малыми отклонениями случайности. Заметим, что данные результаты могут быть переформулированы и в рамках традиционной эргодической теории (см. например, 109]). Однако постановки этих результатов и их мотивировка выглядят более естественными на языке алгоритмической теории случайности.

Следует отметить работы представителей классической статистической школы, которые также в 1980-ых годах развивали частотный подход на основе теории алгоритмов. Дейвид [53, 54, 55 рассматривал задачу вероятностного прогнозирования индивидуальных последовательностей, он ввел понятие калибруемости про-гнозируюп];ей стратегии на бесконечной последовательности исходов, что соответствует некоторому варианту частотного определения случайности относительно произвольного вычислимого распределения вероятностей. Проблема существования последовательностей, на которых не калибруема никакая вычислимая прогнозирующая стратегия, т.е. последовательностей, не допускающих вычислимого вероятностного прогнозирования, была поставлена Дейвидом 54] в 1985 г. и послужила предметом дискуссии в Королевском статистическом обществе [73]. Вопрос о существовании механизмов, генерирующих такие последовательности изучается в диссертации.

В конце 1990-ьос годов обнаружилась тесная связь между понятиями алгоритмической теории случайности и сформировавшейся в 1980-ых годах теорией самообучающихся алгоритмов В этой области строятся алгоритмы предсказания и классификации, минимизирующие заданные функции потерь [51, 59, 66, 86, 94, 83]. Как выяснилось, сложности колмогоровского типа можно интерпретировать как универсальные способы оценки минимально возможных потерь при предсказании [90, 92].

Идеи алгоритмической теории случайности также послужили основой для теоретико-игрового или чисто мартингального подхода к теории вероятностей и финансовой математике, развиваемого Вовком, Дейвидом и Шейфером [56, 74].

Проблема изучения классов стохастических и нестохастических последовательностей может быть рассмотрена в информационном аспекте. В диссертации рассматриваются вопросы классификации бесконечных последовательностей нулей и единиц, как носителей информации. Л.А.Левин [27, 64] заметил, что множество всех алгоритмически случайных последовательностей (относительно различных вычислимых мер) может быть разделено только на два нетривиальных алгоритмически инвариантных подмножества положительной априорной меры. Первое из них порождается всеми невычислимыми случайными последовательностями, второе - это все вычислимые последовательности. Таким образом, единственной инварианти и м и и II ной характеристикой случайной информации является ее количество, конечное или бесконечное. Л.А.Левин [27] поставил вопрос о том можно ли алгоритмической трансформацией случайных последовательностей получить последовательности, обладающие другими нетривиальными алгоритмически инвариантными свойствами. Существование и свойства таких последовательностей являются предметом изучения в диссертации.

В диссертации получены следующие основные результаты:

1) Решена проблема А.Н.Колмогорова об описании кривых зависимости дефекта алгоритмической случайности конечной последовательности от сложности объемлющего множества.

2) Получены верхние и нижние оценки меры множества всех алгоритмически (а, /?)-нестохастических объектов. Задача получения таких оценок была поставлена А.Н.Колмогоровым.

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

4) Проведен алгоритмический анализ степени конструктивности эргодической теоремы Биркгофа. Показано, что сходимость по вероятности и сходимость в среднем (квазиэргодическая теорема Дж.фон Неймана) в этой теореме не являются алгоритмически эффективными. Получен вариант этой теоремы для индивидуальных случайных последовательностей (ответ на вопрос ван Ламбальге-на).

5) Доказана неустойчивость основного утверждения эргодиче-ской теоремы при наличии в исходных данных отклонений от алгоритмических условий случайности. Доказано, что утверждение эр-годической теоремы для индивидуальной последовательности становится неверным, если допустить даже малый рост дефекта алгоритмической случайности конечных фрагментов последовательности.

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

Содержание работы. В главе 1 решается проблема А.Н.Колмогорова об описании кривых зависимости дефекта случайности элемента конечного множества слов в зависимости от алгоритмической сложности этого множества.

Конечные объекты естественным образом отождествляются со своими конструктивными представлениями. Поэтому в дальнейшем мы будем говорить о конструктивных объектах. Конструктивные объекты естественно объединяются в так называемые ансамбли [35]. Типичные примеры таких ансамблей: все слова в конечном алфавите, все конечные множества слов (в заданном алфавите) т.д. В дальнейшем мы будем предполагать, что для каждого такого ансамбля установлено эффективное взаимно-однозначное соответствие между его элементами и конечными двоичными последовательностями.

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

Кв(х\у) = тш{1{р) I В{р,у) = х}, где 1(р) - длина двоичного слова р (полагаем штО = со). Важную роль играет выбор функции 5(р, у) - способа декодирования конструктивных объектов, при этом р трактуется как код объекта х при условии у. В основе определения Колмогорова лежит утверждение о том, что среди способов декодирования существует оптимальный. Колмогоров называет оптимальным такой способ декодирования В(р, у), что для любого другого способа декодирования В'{р, у) существует такая константа с, что Кв(х\у) < Кв{х\у) + с имеет место для всех х л у. Любые два оптимальных способа декодирования определяют меры сложности, отличающиеся на константу. Один из таких оптимальных способов декодирования фиксируется, соответствующая мера сложности обозначается К(х\у) и называется (условной) колмогоровской сложностью X относительно у. Безусловная сложность конструктивного объекта х определяется как К(х) •= К(х\К), где Л - пустая последовательность.

Конструктивное задание конечного множества А определяет некоторый порядок перечисления всех его элементов. Поэтому для задания произвольного элемента х Е А, при известном А, достаточно знать порядковый номер х при этом перечислении. Следовательно, выполнено

К{х\А) < log(#A) + с для некоторой константы с (здесь #Л - число элементов множества А; в дальнейшем все логарифмы будут по основанию 2). Более того, для произвольного с > о число всех х Е А, для которых

К{х\А) < log(#A) - с, не превосходит 2~''+А(#Л), т.е. большинство элементов множества А имеют условную колмогоровскую сложность, близкую к максимальной. А.Н.Колмогоров [17] называет элемент х конечного множества конструктивных объектов А случайным, если К(х\А) А log(#A). Для точного определения он рассматривает разность

ФИ) = log(#A) - К(х\А), которая называется дефектом случайности х относительно множества А. Пусть а и Р - произвольные натуральные числа. Согласно Колмогорову элемент х некоторого ансамбля конструктивных объектов называется (а, /?)-стохастическим, если существует конечное множество D элементов этого ансамбля такое, что х Е D, K(D) < а и d(x\D) < /5.

В 1987 г. автором в [101] была введена и изучалась функция

РхМ = niin d(x D), (0.1) xeD,K{D\n)<a л где X - двоичная последовательность длины п. Функция Kxip) характеризует возможность описания конечной последовательности х с помощью множеств сложности < а. Для любого х функция /?а;(а) определена для всех о: > с, где с - некоторая положительная константа, и не возрастает по а.

Позже в [52] было отмечено, что А.Н.Колмогоров предложил еще в 1973 г. на Таллинской конференции по теории информации вариант функции (0.1) и поставил проблему изучения возможных форм кривых (0.1).

В работе получено описание возможных форм кривых в следующей форме. Пусть Loo = Loo ([0,1]) - пространство всех непрерывных на отрезке [0,1] функций с нормой ||/|| — sup |/(а;)|.

Пусть г/(п) и //(п) - неотрицательные, неубывающие вычислимые функции, причем Л(п) не ограничена, О < //(п) < п для всех п и 7Л(п) = o{fi{n)) при п 00. Для изучения асимптотики кривых (0.1) м II рассмотрим семейство нормализованных кривых

Л'Л'Л

Мп) где п = 1(х), с - константа и О < ;í < 1. Получен основной результат, формулируемый в следующей теореме.

Теорема 1.1. Любая невозрастаюгцая функция F G Loo, расположенная в единичном квадрате, является предельной точкой (в указанной выше метрике) семейства нормализованных функций {fx}, зависящих от параметра х - произвольной конечной двоичной последовательности.

Глава 2 носит технический характер. В ней вводятся основные понятия конструктивной математики, такие как понятия веще-ственнозначной функции перечислимой снизу (сверху), вычислимой функции с вещественными значениями. Вводятся понятия перечислимой снизу полумеры, понятие алгоритмически случайной последовательности, рассматриваются различные способы количествени U T-v ной оценки степени случайности. В качестве основного рассматривается вероятностное пространство (П,Р, Р), где О - множество всех бесконечных последовательностей, состоящих из О и 1. Боре-левское поле F порождается шарами вида = {о; G О : ж С о;}, где X = xiX2. .Хп - конечная последовательность, состоящая из О и 1 (в дальнейшем множество таких последовательностей будет обозначаться как S), а ж С о; означает то, что последовательность (j продолжает конечную последовательность х. Длина последовательности X обозначается как 1{х). Вероятностная мера Р на пространстве Q задается следующим образом. Задаются согласованные значения Р(Тх) = Р(х). Согласованность означает, что Р(х) — Р{хО) + Р{х1) для всех X, где ха обозначает последовательность х, продолженную на а. Кроме этого, дополнительно требуется -Р(Л) = 1, где Л -пустая последовательность. Далее Р стандартным образом продолжается на все элементы борелевского поля F. Мера Р называется вычислимой, если значениями функции Р(х) служат вычислимые действительные числа и сама эта функция вычислима. В дальнейшем рассматриваются только вычислимые меры.

Аналогичным образом, множество S = Q U Н всех конечных и бесконечных двоичных последовательностей также рассматривается как вероятностное пространство, в котором борелевское поле порождается шарами где X - конечная двоичная последовательность (см. [12]). Вычислимые функции на множестве Е называются вычислимыми операторами. Для произвольной вероятностной меры Q яа. U вычислимый оператор F порождает меру Р на S следуюш,им образом

P{h) = Р{х) = Q{ujen:xC F{uj)}, (0.2) где X е В. (далее она распространяется стандартным образом). Функция Р{х) перечислима снизу, т.е. множество {(г, х) : г < Р{х)}А где г - рационально, рекурсивно перечислимо. Более того, любая перечислимая снизу вероятностная мера на Е может быть представлена в виде (0.2) для некоторого вычислимого оператора F, где в качестве меры Q можно взять равномерную меру на О.

Класс перечислимых снизу мер подобного типа содержит максимальный, с точностью до мультипликативной константы, элемент М, т.е. такой, что для любой перечислимой снизу меры Р существует такая константа с, что сМ(А) > P(A) для всех измеримых vi С S. Мера М называется также априорной (полувычислимой) мерой. Известно, что величина — log М{х) совпадает с алгоритмической сложностью К{х) конечной последовательности х с точностью до O(log/(a:)). Вероятностным алгоритмом называется пара (F, Q), где F - вычислимый оператор, Q - вычислимая вероятностная мера на П. Тогда формула (0.2) может интерпретироваться как вероятность того, что вероятностная машина (F, Q) напечатает на вьБсодной ленте качестве начального фрагмента конечную последовательность X.

В главе 3 рассматривается задача алгоритмического прогнозирования конечных последовательностей в случае произвольной функции потерь. Пусть некоторый процесс измерения последовательно порождает последовательность битов и = и:1Ш2 • • - АпМы будем рассматривать задачу предсказания какой-либо характеристики рп п-то исхода на основе уже известных исходов Ш1и)2. - Аи-ь При этом не делается никаких предположений о механизме порождения последовательности исходов и)1и)2 • • - (лп • • На каждом шаге п потери от предсказания измеряются некоторой функцией Л(а;„,р„). Мы будем предполагать, что эта функция вычислима некоторым алгоритмом. Наиболее часто используемые примеры таких функций - квадратичная функция потерь Х{и;п,Рп) = (Ап — Рп)^ и логарифмическая функция потерь \(и;п,Рп) = —Aogpn, если сАЛ = 1 и Х{шп,Рп) = — log(l —Рп), в противном случае (см. [91]).

Обш;ие потери в результате предсказания Р1,., при исходах и)\,.,и}п измеряются суммой п

L0SS(wi .Un) = УЛ Клг,Рг)- (0.3)

Основная задача широкого класса методов, относяш;ихся к теории самообучающихся алгоритмов (и математической статистике), заключается в минимизации общих потерь (0.3) (или каких либо производных от них функций). Например, в случае логарифмической функции потерь, сумма (О.З) имеет вид — logP(a;), где Р - распределение вероятностей на последовательностях исходов длины тг, порождаемое условными вероятностями

Pi = P{ui = l|a;i. .a;ii),« = l,.n.

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

С точки зрения удобства интерпретации мы будем рассматривать, введенное Дейвидом [54], понятие прогнозирующей стратегии, которая в бинарном случае представляет собой функцию f{uioj2. • • a;„i), определенную на последовательных начальных фрагментах последовательности си и принимающую неотрицательные действительные значения. В этом случае сумма (0.3) принимает вид п

ЬosSf{uJl. а;„) = Л \{шг, !{ил1и2 . илг-х))- (0.4) 1

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

Сумма (0.4) представляет собой некоторую меру сложности последовательного предсказания элементов последовательности и — 00x002.Шп- Основная задача предсказания заключается в нахождении такой прогнозируюндей стратегии /, которая минимизирует общие потери (0.4) на всех о;, например, в том же смысле, как в случае колмогоровской сложности. Решение этой задачи возможно в рамках идеи построения колмогоровской сложности. Соответствующее понятие меры предсказательной сложности было введено в [90 .

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

КО{х) < КС'{х) + с для всех X ЕЕ. Пусть о: и 7 - натуральные числа. Любая вычислимая функция задается своей программой - конструктивным объектом, поэтому можно рассматривать сложность К{8) вычислимой прогнозирующей стратегии 5. По определению, некоторая последовательность X длины п называется (а, 7)-предсказуемой, если существует прогнозирующая стратегия 5 такая, что К(8) < а и

Ьо885(а;) - КО(х) < 7 для всех X Е Данное определение обобщает определение стоха-стичности по Колмогорову на произвольные функции потерь. Предсказательная сложность определяет асимптотически минимальные потери от предсказания. При этом учитываются и произвольно сложные вычислимые прогнозирующие стратегии. Мы рассмотрим ограничение на сложность прогнозирующей стратегии К(8) < а. В главе 4 доказано, что даже в том случае, когда а асимптотически мала по сравнению с длиной двоичной последовательности, например, а = О(1о§п), можно достичь минимально возможных потерь жество всех двоичных последовательностей длины гг, которые не являются (а, 7)-предсказуемыми. Для любого х 6 БААА выполнено для каждой прогнозируюп];ей стратегии S такой, что K{S) < а.

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

Пусть М - априорная мера. Для произвольного множества конечных последовательностей D величина M{D) — М{1)хев'Ах) определяет асимптотически максимальную вероятность генерации последовательности из D на вероятностной машине. Основной результат имеет место для широкого класса функций потерь.

Теорема 3.1. Существуют константы cub такие, что

2-a-logn-21 oglogTi-c А M(J)'A ) < 2~"+21ogn+21oglogn-log7+c для всех о < 7 < 6n — 2с{а -Ь log те).

Неравенства (0.5) можно интерпретировать как верхнюю и нижнюю оценки вероятности порождения "трудно" предсказуемых последовательностей с помоп];ью вероятностной машины.

В главе 4 проводится алгоритмический анализ возможностей вероятностного прогнозирования бесконечных последовательностей. Предполагается, что последовательность исходов и = UiU2 . а;„. порождается в соответствии с некоторым вероятностным распределением Р на П. Если p{loiuj2 . .Шп) Ф О для всех п, то можно определить вероятностную прогнозируюшую стратегию на большинстве последовательностей длины п. Пусть мно f{b)iU)2 • • • Wn-l) = P{iAn = lklA2 • • • An-l) = P(a;ia;2 • • •uJn-il)/P{uJiU2 • • .tOn-i)

0.6) (0.7) с другой стороны, любая (вычислимая) прогнозируюп];ая стратегия / однозначно определяет (вычислимое) распределение вероятностей Р такое, что (0.6) выполнено для всех оЛх^ • • • таких, что Р(и)1Ш2-. .ооп-х) 7Л 0. В дальнейшем мы будем рассматривать только вычислимые прогнозируюш;ие стратегии, определенные на всех конечных последовательностях. т-ч и о

В математической статистике исходят из некоторой последовательности исходов и = 0)1Л2. .сОп - • • случайного эксперимента и проверяют "правильность или соответствие" прогнозируюп];ей стратегии / этой последовательности. Правилом выбора называется функция 5{х), определенная на конечных последовательностях и принимающая значения О или 1. Правило выбора д выбирает подпоследовательность индексов 5 = П1П2. из бесконечной последовательности и = Ш1Ш2. .и;п' •; если п € « тогда и только тогда, когда 6(и;1. .и)п-1) — 1. Прогнозирующая стратегия / вычислимо калибруема на о; = 001л2. . относительно (5, если либо подпоследовательность индексов, выбранная из а; = ыхоЛг . а;„. посредством Л, конечна, либо для нее выполняется вариант усиленного закона больших чисел

- А Л п г - - л Л 1{ш1и)2 . . . Шп,-1) —> О г=1 ¿ = 1 при Г -> СО.

Вероятностная прогнозирующая стратегия / или соответствующее ей распределение вероятностей Р вычислимо калибруема на бесконечной последовательности о?, если она вычислимо калибруема на и) относительно любого вычислимого правила выбора. Данное определение обобщает частотное определение случайности по Ми-зесу - Черчу [50, 38] (предложенное для распределений Бернулли) на произвольные распределения вероятностей.

В главе выясняется следующее соотношение между данным определением случайности и определением алгоритмической случайности. Пусть / - произвольная вычислимая прогнозирующая стратегия и Р - соответствующее распределение вероятностей. Тогда

- прогнозирующая стратегия / вычислимо калибруема на любой алгоритмически случайной относительно Р бесконечной последовательности ш\

- существует бесконечная последовательность на которой прогнозирующая стратегия /{%) = 1/2, для всех х еЕ, вычислимо калибруема и которая не является случайной относительно равномерной меры.

Последовательность а; называется стохастической по Дейвиду, если на ней вычислимо калибруема хотя бы одна вычислимая прогнозирующая стратегия. В противном случае, последовательность и называется нестохастической, говорим также, что ш не допускает корректного вероятностного прогнозирования. Основной результат этой части заключается в том, что используя вероятностные алгоритмы (алгоритмические операторы), можно с вероятностью, как угодно близкой к 1, генерировать бесконечные последовательности, не допускающие корректного вероятностного прогнозирования.

Теорема 4.2. Для любого е > О существует вероятностный алгоритм, который с вероятностью 1 — е выдает бесконечную, нестохастическую по Дейвиду последовательность.

В главе 5 проводится алгоритмический анализ возможностей вероятностного прогнозирования конечных двоичных последовательностей. В этой главе рассматривается логарифмическая функция потерь. В этом случае предсказательная сложность КС(х) конечной двоичной последовательности х равна — 1о§М(ж), где М - априорная мера, а разность Ьо88р(а;) — КО{х) между суммарными потерями на X (при использовании стратегии, соответствующей Р) и сложностью X равна д(х) = \оА{М{х)/Р(х)). Нетрудно проверяется, что величина ф{х) = 2ЛЛ*Л является неотрицательным перечислимым снизу Р-супермартингалом, т.е. удовлетворяет условиям

1) Л(Л) < 1;

2) А{х) > ф{хО)Р{0\х) 4- 'ф(х1)Р(1\х) для всех х.

Из определения априорной меры М легко следует, что Р-супермар-тингал а/а{х) = М{х)/Р{х) является максимальным с точностью до мультипликативной константы (зависящей от Р) перечислимым снизу Р-супермартингалом.

В работе также построен перечислимый снизу по р, х супермартингал А{р, х), для которого условия 1) - 2) выполнены для каждой меры, вычислимой посредством программы р, и который является максимальным с точностью до мультипликативной константы (не зависящей от меры), точнее, для любого перечислимого снизу равномерного супермартингала -ф существует константа с такая, что неравенство с'ф(р,х) >ф(р,х) выполнено для всех х и всех р, являющихся программами вычислимых прогнозирующих стратегий (вероятностных мер). Величина (1р{х) — 1о§^гЛ(р, а;) называется (равномерным) дефектом случайности. Мы будем оценивать степень случайности конечной последовательности X относительно вычислимой прогнозирующей стратегии (или соответствующей меры), значения которой могут быть вычислены посредством программы р, по значению д,р(х).

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

Пусть а,(5 - натуральные числа. Конечная последовательность X длины п называется (а,л)-стохастической, если для некоторой и о / а некоторой прогнозирующей стратегии / выполнено (1р(хА) < Р для всех ] < п. Данное определение стоха-стичности является более сильным, чем определение предсказуемости для случая логарифмической функции потерь.

Пусть а,/3 - натуральные числа. Конечная последовательность X длины п называется (а,Р) - нестохастической, если для каждой а-простой программы р (длины < а) некоторой прогнозирующей стратегии / существует л < п такое, что д,р(хА) > р (говорим, что программа несостоятельна на последовательности х на уровне /?). Данное определение нестохастичности обобщает понятие (а,РУ нестохастичности по Колмогорову на произвольные вероятностные распределения.

Для любых натуральных чисел а ж Р пусть 1)ллл - множество всех (а,/3)-нестохастических последовательностей длины п. Вероятность генерации (а,/3)-нестохастической последовательности в а-простом вероятностном процессе мала: для любых натуральных чисел а, ß, п ш вычислимой меры Р сложности < а выполнено P[D'Aß) < 2~л. Вероятность генерации таких последовательностей стремится к О даже при использовании произвольных вероятност-ньЕХ алгоритмов.

Теорема 5.1. Пусть а(п) и ß{n) - неограниченные неубыва-юЮ/Не вычислимые функции, принимающие натуральные значения. Тогда lim AA(Um = n Aa(m),/3(m)) ~ л ~ универсальная мера.

Получена также конкретная оценка (в зависимости от п) универсальной меры этого множества в терминах функций а и ß.

Теорема 4.2 утверждает, что с вероятностью >! — £ можно генерировать последовательность, на которой любая прогнозирующая программа когда-либо в будущем окажется несостоятельной при любом заданном уровне доверия. Теорема 5.1 дополняет этот результат. Она показывает, что в том случае, когда границы а = а{п) и ß = ß{n) являются вычислимыми, априорная мера всех последовательностей длины те, на которых на уровне ß все прогнозирующие программы длины < а оказались несостоятельными, стремится к 0.

В главе б проводится алгоритмический анализ степени конструктивности эргодической теоремы Биркгофа.

Точное математическое понятие случайной последовательности, разработанное в рамках колмогоровского подхода, позволяет формулировать законы теории вероятностей (утверждения, имеющие место почти всюду) для индивидуальных последовательностей и находить новые "алгоритмические" формулировки и доказательства этих законов. Пример такого рода - найденное Вовком алгоритмическое доказательство закона повторного логарифма для хаотических (случайных по Колмогорову) последовательностей. Для эрго-дической теоремы не было известно, имеет ли она место для индивидуальных случайных последовательностей. Доказательства индивидуальной эргодической теоремы, принадлежащие Биркгофу [42], Хинчину [61, 37], Колмогорову [14], Гарсия [41] и др., "неконструктивны" и непосредственно не переносятся на случай индивидуальных случайных последовательностей. Ван Ламбальген [62] выражал сомнение в том, возможно ли перенесение эргодической теоремы на индивидуальные случайные последовательности.

Согласно эргодической теореме Биркгофа [42], если Р - мера, / -интегрируемая функция, а Т - сохраняющее меру преобразование, то для почти всех ш существует предел

Ия. /И + /(Тс.) + . + /(Т--М. (0.8) п-лоо п

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

Пусть /п(со) - некоторая последовательность случайных функций. Последовательность /«(о;) сходится по вероятности к некоторой функции /(а;), если для любого Л > О будет

Р{а;: |Л(а;)-/(а;)| >(л}->0 при п —> 00. Сходимость по вероятности является алгоритмически эффективной, если существует вычислимая функция т{Ь, е) от ра-циональньЕк: ежЬ, принимающая неотрицательные целые значения, такал, что

Р{^'\Ш-'{ио)\>Ь}<е при всех п > 7п{6, е).

Как правило, сходимость по вероятности для сумм случайных величин является алгоритмически эффективной. Например, если Х1(и}) - последовательность независимых случайных величин со средним //ИИ конечным вторым моментом сгЛ, то л • 1 при всех п > т(е,6) = аА/{€бА) (для простоты считаем, что а -рационально). Ясно, что здесь т{£,6) - вычислимая функция.

Из сходимости (0.8) почти всюду следует сходимость средних и по вероятности. Однако для эргодической теоремы имеет место следующий отрицательный результат.

Теорема 6.1. Существует вычислимая стационарная мера Р, для которой сходимость по вероятности средних

1 ¿ . , (0.9) г=1 не является алгоритмически эффективной.

Поскольку из сходимости сумм (0.9) в среднем следует сходимость по вероятности, квазиэргодическая теорема Дж.фон Неймана [72] также не является алгоритмически эффективной.

В главе 6 приводится формулировка эргодической теоремы для индивидуальных случайных последовательностей. Доказательство использует некоторую конструкцию Бишопа [43, 44]. Бишоп не использовал понятие случайности и алгоритмического теста, поэтому его формулировка эргодической теоремы отличалась от общепринятой и значение результата не было должным образом оценено. Понятие случайной последовательности позволяет использовать конструкцию Бишопа для формулировки следующего алгоритмического варианта эргодической теоремы.

Теорема 6.2. Пусть Р - вычислимая мера, Т - вычислимоеА сохраняющее меру Р преобразование, f - вычислимая функция на О. Тогда существует такая интегрируемая функция /, что E{f) = E{f) (Е - символ математического ожидания) и

• ¿=1 для любой индивидуальной последовательности и, являющейся алгоритмически случайной относительно меры Р, кроме этого, f{Tüj) = f{ijj). Если к тому же преобразование Т эргодично, то f(u) = E{f) для этой же последовательности ш.

В главе 7 изучаются вопросы устойчивости эргодической теоремы при малых нарушениях случайности индивидуальной последовательности. Бесконечная последовательность о? является случайной по мере Р тогда и только тогда, когда величина дефекта случайности dpiüü'A) ограничена с ростом п. Вовк [4] заметил, что основные законы теории вероятностей при их применении к индивидуаль

II II ным последовательностям имеют свойство устойчивости относительно небольшого роста дефекта случайности. Более точно, они имеют место не только для случайных последовательностей, но и для последовательностей из более широкого класса. Например, закон больших чисел для равномерной бернуллиевской меры имеет место для любой последовательности w, для которой дефект случайности может ограниченно расти с ростом длины фрагмента как dp{ijü"') = о{п). Для выполнения закона повторного логарифма достаточно потребовать dp{üj'A) = o(loglogn). Такая же асимптотика дефекта случайности является условием выполнения закона о длине серии "успехов" в индивидуальной случайной последовательности 105 .

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

Теорема 7.1. Для любой неограниченной, неотрицательной, неубывающей функции р{п) существует вычислимая относительно нее стационарная эргодическая мера Р и бесконечная последовательность UJ такая, что ар{шА) < р{п) для всех п, начиная с некоторого, и предел

Иш — yAoji i=l не существует.

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

Теорема 7.2. Для любой неотрицательной, неубывающей и неограниченной функции р{п) существуют вычислимое относительно нее, сохраняющее равномерную меру L эргодическое преобразование Т и бесконечная двоичная последовательность и) такие, что dii'-A'A) < р{п) для всех п, начиная с некоторого; п-1 предел lim J J2 существует, где f(u)) = uji.

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

Теорема 7.3. Существует вычислимая стационарная мера Р такая, что для любой вычислимой, неограниченной, неотрицательной, неубывающей функции р(п) существует бесконечная последовательность ÜJ. такаяАчто ар(ш'А) < р(п) для всехп, начиная с некоторого, и предел л п-1 lim — yAUi П-Лоо п А—А не существует.

В главе 8 проблема стохастических и нестохастических последовательностей рассматривается в информационном аспекте. В ней проводится классификации бесконечных последовательностей нулей и единиц как носителей информации. Множество всех алгоритмически случайных последовательностей (относительно различных вычислимых мер) может быть разделено только на два нетривиальных алгоритмически инвариантных подмножества положительной априорной меры [27]. Первое из них состоит из всех невычислимых случайных последовательностей, второе - это все вычислимые последовательности. Таким образом, единственной инвариантной характеристикой "случайной информации" является ее количество, конечное или бесконечное. В той же работе был поставлен вопрос р том можно ли алгоритмической трансформацией случайных последовательностей получить последовательности, обладающие другими нетривиальными свойствами. В диссертации получен положительный ответ на этот вопрос - последовательности, алгоритмически не эквивалентные случайным (по каким-либо вычислимым мерам), можно (с положительной вероятностью) получать из случайных посредством вероятностных алгоритмов. Такие последовательности обладают разнообразными инвариантными свойствами. Существование и свойства таких последовательностей являются предметом изучения этой главы.

В связи с этим возникает следующая математическая структура. Бесконечная последовательность а алгоритмически сводится к бесконечной последовательности /3, если а — Е(/3) для некоторого алгоритмического оператора Г. Две бесконечные последовательности а т (3 алгоритмически эквивалентны, обозначается это как а = если каждая из них сводится к другой. Множество (свойство) бесконечных последовательностей Л называется алгоритмически инвариантным, если оно вместе с каждой последовательностью содержит и все алгоритмически эквивалентные ей последовательности. Пусть / - булева алгебра всех алгоритмически инвариантньгх: борелевских подмножеств О. Мы не различаем два множества из /, которые различаются на множество априорной меры О, точнее, рассматривается отношение эквивалентности

АглВ<=л М{(А \В)и{В\ А)) = 0.

Пусть Т - фактор алгебра алгебры / по отношению эквивалентности В главе 8 изучается структура этой фактор-алгебры Т. Класс эквивалентности алгоритмически инвариантного множества А обозначается а = [Л]. Для любой меры Р ш О, можно корректным образом определить Р(а) = Р{А). Нулевой элемент О алгебры Т определяется как класс эквивалентности пустого множества. Он состоит из всех алгоритмически инвариантных подмножеств А априорной меры О, поэтому М(0) = 0. Единица алгебры Т определяется 1 = [О]. Известно [12], что любая последовательность и, случайная относительно некоторой вычислимой меры, либо вычислима, либо алгоритмически эквивалентна последовательности, случайной относительно равномерной меры. Поэтому естественным образом возникает элемент г = [К] алгебры Т, где К - множество всех невычислимых алгоритмически случайных (относительно вычислимых мер), а также алгоритмически эквивалентных им последовательностей. Другой естественно возникающий элемент с определяется классом всех вычислимых последовательностей (последовательность и = и;1и)2. вычислима, если функция д{г) = Ш{ вычислима). Из свойств априорной меры легко следует, что М(с) > 0.

Очевидным образом М(г) > 0. Как уже замечено, элемент г является атомом Т, т.е. он ненулевой и не существует разложения г = а и Ь, где аПЬ = 0, атЛЛОнЬтЛО. Тривиальным образом, элемент с также является атомом алгебры Т.

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

Теорема 8.2. Множество всех атомов алгебры Т счетно.

Пусть ах, а2, аз,. - все атомы алгебры Т, причем ах = с и аг = г.

Теорема 8.3. Имеет место 1 \ А Ф О

Заметим, что по определению элемент (1=1 \ является бесконечно делимым, т.е. для любого ненулевого элемента х С (1 существует разложение х = хх их2, где хх Пх2 = 0, хх О и Х2 0.

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

Используемые обозначения

•К - множество всех натуральных чисел;

• Q - множество всех рациона-пьных чисел;

•Я - множество всех действительных (вещественных) чисел;

• Я"л - множество всех действительных чисел, расширенное добавлением -Ьоо и —00 (со стандартным расширением линейного порядка действительных чисел);

Б - множество {0,1}* всех конечных двоичных последовательностей (бинарных слов);

Л - пустая последовательность (является элементом 8);

О - множество {0,1}°° всех бесконечных двоичных последовательностей;

Б - поле борелевских подмножеств А;

Е - множество 12 и Н всех конечных и бесконечных двоичных последовательностей.

X С у - иоследовательность у продолжает последовательность х;

X Су обозначает х Су их фу\

Гж - шар в пространстве А: = {а; 6 О : х С где ж € Н; Гж - шар в пространстве Е: ГЛ; = {а; О 8 : С а;}, где а? 6 Н; х-1- г-ый элемент (бит) последовательности ж = • •.; а:) = п- длина последовательности х = Х1.Хп\ Е (или Ер) - символ математического ожидания по мере Р;

- целая часть действительного числа г; Гг1 - наименьшее целое, большее или равное г; ж,у) - упорядоченная пара элементов некоторого ансамбля (кортеж); x,y,z) - упорядоченная тройка элементов некоторого ансамбля (кортеж);

А® В - декартово произведение множеств Л и Б; а) ~ сумма значений /(а) по всем элементам а из множества А\ loga; - логарифм х по основанию 2; In а: - натуральный логарифм х\ е - основание натурального логарифма;

7Г - число "пи" (отношение длины окружности к ее диаметру); п) = 0{д{п)) - существует константа С > О такая, что f{n)\ < С\д{п)\ для всех п; п) = о(д{п)) - для любого с > О выполнено |/(п)| < с\д{п) для всех гг, начиная с некоторого;

Loo ([О, Ц) - пространство непрерывных функций, определенных на [0,1] с нормой 11/11 = sup |/(а;)|;

0<а;<1

Li - пространство функций, суммируемых по Лебегу на О;

L2 - пространство функций, суммируемых в квадрате на Ü;

П/П2)- норма в пространстве Li (L2); р{и) - универсальная мера невозможности бесконечной последовательности и (подразумевается, что задана мера Р на Ü);

К{х\у) - колмогоровская сложность конечного объекта х при заданном конечном объекте у;

Л((7,р) - функция потерь, где а равно О или 1, р - действительное число из интервала [0,1];

Ьо888(а;1. Шп) суммарные потери предсказания на конечной двоичной последовательности . а;„ при использовании предсказательной стратегии Б;

КО(х) - предсказате.льная сложность конечной двоичной последовательности X (подразумевается, что задана функция потерь А(о-,р));

М - максимальная перечислимая снизу полумера (априорная полумера или полувычислимая мера на Е); фр(х) - Р-супермартингал (для произвольной меры Р на П); dp(x) = logipp(x) - тест случайности конечной последовательности X относительно меры Р; фр(х) - максимальный перечислимый снизу Р-супермартингал (для произвольной меры Р на О); dp(x) = \о%фр(х) - дефект случайности конечной последовательности X относительно меры Р; ф(р-) х) ~ максимальный перечислимый снизу равномерный супермартингал; с?(р, х) - равномерный дефект случайности конечной последовательности X относительно прогнозирующей системы (вероятностной меры), заданной программой р.

1. Биллингслей П. Эргодическал теория и информация. М.: Мир, 1969.

2. Боровков A.A. Теория вероятностей. М.: Наука, 1976.

3. Вовк В.Г. О понятии бернуллиевости // Успехи математических наук, 1986, Т.41, N1, с. 185-186.

4. Вовк В.Г. Закон повторного логарифма для случайных по Колмогорову, или хаотических последовательностей // Теория вероятностей и ее применения, 1987, т.32, N3, с.456-468.

5. Вовк В.Г. Об одном критерии случайности // Доклады АН СССР, 1987, Т.294, N6, с. 1298-1302.

6. Вовк В.Г. О законе повторного логарифма Колмогорова Стаута // Математические заметки, 1988, т.44, N1, с.27-37.

7. Вовк В.Г. Прогнозирование стохастических последовательностей // Проблемы передачи информации, 1989, т.25, N4, с.35-49.

8. Вовк В.Г. Асимптотическая эффективность оценок: алгоритмический подход // Теория вероятностей и ее применения, 1991, Т.36, N2, с.247-261.

9. Гач П. О симметрии алгоритмической информации // Доклады АН СССР, 1974, Т.218, N6, с. 1265-1267.

10. Гнеденко Б.В. Курс теории вероятностей. М.: Изд-во Наука, 1965.и. Данфорд Н., Шварц Дж.Т. Линейные операторы. Общая теория. М.: Изд-во иностр. лит., 1962.

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

12. Качуровский А.Г. Скорости сходимости в эргодической теореме // Успехи математических наук, 1996, т.51, N4, с.73-124.

13. Колмогоров А.Н. Упрощенное доказательство эргодической теоремы Биркгофа Хинчина // Успехи математических наук, 1938, Т.5, с.52-56.

14. Колмогоров А.Н. Три подхода к определению понятия "количество информации" // Проблемы передачи информации, 1965, Т.1, N1, с.3-11.

15. Колмогоров А.Н. К логическим основам теории информации и теории вероятностей // Проблемы передачи информации, 1969, т.5, N3, с.3-7.

16. Колмогоров А.Н. Комбинаторные основания теории информации и исчисления вероятностей // Успехи математических наук, 1983, Т.38, N4, с.27-36.

17. Колмогоров А.Н. Основные понятия теории вероятностей. М.: Наука, 1974.

18. Колмогоров А.Н., Успенский В.А. Алгоритмы и случайностьТеория вероятностей и ее применения, 1987, т. 32, N3, с.425-455.

19. Косовский Н.К. Интегрируемые Рл/?-конструкты над вероятностным пространством // Записки научных семинаров Ле-нингр. отд. Матем. ин-та АН СССР, 1969, т. 16, с.97-104.

20. Косовский Н.К. Законы больших чисел в конструктивной теории вероятностей // Записки научных семинаров Ленингр. отд. Матем. ин-та АН СССР, 1969, т. 16, с. 105-113.

21. Ламперти Дж. Вероятность. М.: Наука, 1973.

22. Левин Л.А. О понятии случайной последовательности // Доклады АН СССР, 1973, Т.212, N3, с.548-550.

23. Левин Л.А. Законы сохранения (невозрастания) информации и вопросы обоснования теории информации // Проблемы передачи информации, 1974, т. 10, N3, с.30-35.

24. Левин Л.А. О различных мерах сложности конечных объектов (аксиоматическое описание) // Доклады АН СССР, 1976, Т.227, N4, с.804-807.

25. Левин Л.А. Об одном конкретном способе задания сложност-ных мер // Доклады АН СССР, 1977, т.234, N3, с.536-539.

26. Левин Л.А. О принципе сохранения информации в интуиционистской математике // Доклады АН СССР, 1976, т.227, N6, с. 1293-1296.

27. Ли М., Витаньи П. Колмогоровская сложность двадцать лет спустя // Успехи математических науктЛЗ, N6, с. 129-166.

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

29. Мизес Р. Вероятность и статистика. М. Л.: Государственное издательство, 1930.

30. Орнстейн Д. Эргодическая теория, случайность и динамические системы. М.: Мир., 1978.

31. Роджерс X. Теория рекурсивных функций и эффективная вычислимость. М.: Мир., 1972.

32. Ромащенко А.Е. Пары слов с нематериализуемой общеж информацией // Проблемы передачи информации, 2000, т.36, N1, с.3-20.

33. Успенский В.А. Лекции о вычислимых функциях. М.; Физмат-гиз, 1960

34. Успенский В.А., Семенов А.Л. Теория алгоритмов: основные открытия и приложения. М.:Наука. Гл. ред. физ.-мат. лит., 1987. -(Б-чка программиста).

35. Успенский В.А., Семенов А.Л., Шень А.Х. Может ли (индивидуальная) последовательность нулей и единиц быть случайной? // Успехи математических наук, 1990, т.45, N1, с .105162.

36. Хинчин А.Я. О стационарных рядах случайных величин // Математический сборник, 1933, т.40, N2, с. 124-128.

37. Шень А.Х. Частотный подход к определению понятия случайной последовательности // Семиотика и информатика. М.: ВИНИТИ, 1982, Вып. 18. - (Второй выпуск за 1981 г.) с. 14-42.

38. Шень А.Х. Понятие (а,/3)-стохастичности по Колмогорову и его свойства // Доклады АН СССР, 1983, т.271, N6, с. 13371340.

39. Шенфилд Дж. Степени неразрешимости. М.: Наука, 1977.

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

41. Birkhoff G.D. Proof of the ergodic theorem // Proceedings of the National Academy of the USA, 1931, v.l7, p.656-660.

42. Bishop E. An upcrossing inequahty with apphcations // Michigan Mathematical Journal, 1966, v.l3, p.1-13.

43. Bishop E. Foundation of Constructive Analysis. New York: McGraw-Hill, 1967.

44. Chaitin G.J. On the length of programs for computing binary sequences // Journal of the Association for Computing Machinery, 1966, V.13, p.547-569.

45. Chaitin G.J. On the length of programs for computing binary sequences: Statistical considerations // Journal of the Association for Computing Machinery, 1969, v. 16, p. 145-159.

46. Chaitin G.J. A theory of program size formally identical to information theory // Journal of the Association for Computing Machinery, 1975, V.22, p.329-340.

47. Chaitin G.J. Algorithmic information theory // IBM Journal of Research and Development, 1977, v.21, p.350~359.

48. Chaitin G.J. Algorithmic information theory, Cambridge University Press, 1987.

49. Church A. On the concept of random sequence // Bulletin of the American Mathematical Society, 1940, v.46, N2, p. 130-135.

50. Cesa-Bianchi N., Preund Y., Helmbold D.P., Haussler D., Schapire R.E., Warmuth M.K. How to use expert advice // Journal of the ACM, 1997, V.44, p.427-485.

51. Cover T.M., Gacs P., Gray R.M. Kolmogorov's contributions to information theory and algorithmic complexity // Annals of Probability, 1989, V. 17, N1, p.840-865.

52. Dawid A. P. Statistical theory: The prequential approach (with discussion) // Journal of the Royal Statistical Society, A, 1984, v. 147, p.278-292.

53. Dawid A.P. Calibration-based empirical probability with discussion // The Annals of Statistics, 1985, v.l3, p.1251-1285.

54. Dawid A.P. Probability forecasting //in S.Kotz and N.L.Johnson, editors, Encyclopedia of Statistical Sciences, v.7, p.210—218, Wiley, New York, 1986.

55. Dawid A.P., Vovk V.G. Prequential probability: principles and properties // Bernoulli, 1997, v.3, p. 1-38.

56. Gacs P. Exact expressions for some randomness tests // Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik, 1980, V.26, p.385-394.

57. Hammer D, Romashchenko A, Shen A, and Vereshchagin N. Inequalities for Shannon entropy and Kolmogorov complexity // Journal of Computer and System Sciences, 2000, v.60, p.442-464.

58. Khintchine А. Zu Birkhoffs Losing des Ergodenproblems // Mathematische Annalen, 1932, Bd. 107, S.485-488.62. van Lambalgen M. Random sequences. Amsterdam: Academish Proefshri't., 1987

59. Levin L.A., V'yugin V. V. Invariant properties of informational bulks // Springer Lecture Notes on Computer Science v.53, 1977, p.359-364.

60. Levin L. A. Randomness conservation inequalities; information and independence in mathematical theories // Information and Control, 1984, V.61, p.15-37.

61. Li M., Vitanyi P. An Introduction to Kolmogorov Complexity and Its Applications, 2nd ed. New York: Springer-Verlag, 1997.

62. Littlestone N., Warmuth M.K., The weighted majority algorithmInformation and Computation, 1994, v. 108, p.212-261.

63. Loveland D. A new interpretation of the von Mises' concept of random sequence // Zeitschrift fur Mathematische Logik und Grundlagen der Mathematik, 1966, v.l2, N3, p.279-294.

64. Martin-Löf P. The definition of random sequences // Information and Control, 1966, v.9, p.602-619.

65. Mises R. On the foundations of probabihty and statistics // Annals of Mathematical Statistics, 1941, v.l2, p.191-205.

66. Muchnic An.A. On common information // Theoretical Computer Science, 1998, v.207, p.319-328.

67. Oakes D. Self-calibrating priors do not exists with discussion] //Journal of the American Statistical Association, 1985, v.80, p.339-342.

68. Shafer G., Vovk V. Probability and Finance, New York: Wiley, 2001.

69. Shields P.O. Cutting and stacking: a method for constructing stationary processes // IEEE Transactions on Information Theory, 1991, V.37, N6, p.1605-1617.

70. Shields P.C. Two divergence-rate counterexamples // Journal of Theoretical Probability, 1993, v.6, N3, p.521-545.

71. Shnorr CP. Process complexity and effective random tests //Journal of Computer and System Sciences, 1973, v.3, N4, p.376-378.

72. Schnor CP. A survey of the theory of random sequences. Logic, foundations of mathematics and computability theory. Eds. R.E.Butts, J.Hintikka. Dordrecht: D.Reidel. - 1977, p.193-211.

73. Solomonoff R.J. A prehminary report on a general theory of inductive inference. Technical Report, ZTB-138, Zator Company, Cambridge, Mass. (November, 1960).

74. Solomonoff R.J. A formal theory of inductive inference I, II // Information and Control, 1964, v.7, p. 1-22, p.224-254.

75. Solomonoff R.J. Complexity-based induction systems: Comparisons and convergence theorems // IEEE Transactions on Information Theory, 1978, IT-24, p.422-432.

76. Uspensky V.A., Shen A. Relations between varieties of Kol-mogorov complexities // Mathematical Systems Theory, 1996, V.29, p.271-292.

77. Vapnik V. Structure of Statistical Learning Theory. Computational learning and probabilistic reasoning Ed. A.Gammerman, New York: Wiley, 1996, p. 193-211.

78. Vereshchagin N, Vyugin M. Independent minimum length programs to translate between given strings // Proceedings of 15th Annual IEEE Conference on Computational Complexity, Florence, July 2000, p. 138-144.

79. Ville J. Etude critique de la notion de coUectif. Gauthier-VUars, Paris, 1939.

80. Vovk V. G. Aggregating strategies. In M. Fulk and J. Case, editors, Proceedings of the 3rd Annual Workshop on Computational Learning Theory, p.371-383, San Mateo, CA, 1990. Morgan Kaufmann.

81. Vovk V.G. Universal forecasting algorithms // Information and Computation, 1992, v.96, p.242-277.

82. Vovk V.G. and Vyugin V.V. On the empirical vaUdity of the Bayesian method // Journal of the Royal Statistical Society, B, 1993, V.55, p.253-266.

83. Vovk V.G. and Vyugin V.V. Prequential Level of impossibility with some applications // Journal of the Royal Statistical Society, B, 1994, V.56, p. 115-123.

84. Vovk V.G., Watkins C. J.H.C., Universal portfolio selection // Proceedings of the nth Annual Conference on Computational Learning Theory, 1998, p. 12-23.

85. Vovk V.G. A game of prediction with expert advice // Journal of Computer and System Sciences, 1998, v.56, p. 153-173.

86. Vovk V.G., Gammerman A., Complexity estimation principle //The Computer Journal, 1999, v.42, N4, p.318-322.

87. Wallace C.S., Freeman P.R. Estimation and inference by compact coding // Journal of the Royal Statistical Society, 1987, v.49, p.240-265.

88. Yamanishi K. Randomized approximate aggregating strategies and their appHcations to prediction and discrimination, in Proceedings, 8th Annual ACM Conference on Computational Learning Theory, 1995, p.83-90, Association for Computing Machinery, New York.

89. Вьюгин В.В. Об инвариантных по Тьюрингу множествах // Доклады АН СССР, 1976, т.229, N4, с.790-793.

90. Вьюгин В.В. Об одной факторизации алгебры Т инвариантных множеств. Четвертая Всесоюзная конференция по математической логике, (тезисы докладов и сообщений), Изд. "Штиинца", Кишинев, 1976, с.24.

91. Вьюгин В.В. Алгебра инвариантных свойств двоичных последовательностей // Проблемы передачи информации, 1982, т. 18, N2, с.83-100.

92. Вьюгин В.В. О нестохастических объектах // Проблемы передачи информации, 1985, т.21, N2, с.3-9.

93. V'yugin V.V. Some estimates for nonstochastic sequences. Proceedings of the 1st World Congress of the Bernoulli Society, Tashkent USSR, 8-Ц September, Vol. 1, Probability theory and applications, ed. Yu.A.Prohorov, V.V.Sazonov, 1986, p. 173-176.

94. Вьюгин В.В. О дефекте случайности конечного объекта относительно мер с заданными границами их сложности // Теория вероятностей и ее применения, 1987, т.32, N3, с.558-563.

95. V'yugin V. V. Bayesianism: an algorithmic analysis // Information and Computation, 1996, v.l27, N1, p.1-10.

96. Вьюгин В.В. Эргодическая теорема для индивидуальной случайной последовательности // Успехи математических наук, 1996, Т.51, N1, с. 191-192.

97. Вьюгин В.В. Эффективная сходимость по вероятности и эргодическая теорема для индивидуальных случайных последовательностей // Теория вероятностей и ее применения, 1997, Т.42, N1, с.35-50.

98. Вьюгин В.В. О длине максимальной серии "успехов" в индиJ \J SJ II ггтвидуальной случайной последовательности // Теория вероятностей и ее применения, 1997, т.42, N3, с.608-615.

99. V'yugin V. V. Non-stochastic infinite and finite sequences // Theoretical Computer Science, 1998, v.207, N4, p.363-382.

100. V'yugin V. V. Ergodic theorems for individual random sequences // Theoretical Computer Science, 1998, v.207, N4, p.343-361.

101. V'yugin V. V. Algorithmic complexity and stochastic properties of finite binary sequences // The Computer Journal, 1999, v.42, N4, p.294-317.

102. Вьюгин В.В. О неустойчивости индивидуальной эргодической теоремы // Проблемы передачи информации, 2001, т.37, N2, с.27-39.