< а. Для любого х функция /?а-(а) определена для всех о: > с, где с — некоторая положительная константа, и не возрастает по а.Позже в [52] было отмечено, что А. Н. Колмогоров предложил еще в 1973 г. на Таллинской конференции по теории информации вариант функции (0.1) и поставил проблему изучения возможных форм кривых (0.1).
В работе получено описание возможных форм кривых в следующей форме. Пусть Loo = Loo ([0,1]) — пространство всех непрерывных на отрезке [0,1] функций с нормой ||/|| — sup |/(а-)|.
Пусть г/(п) и //(п) — неотрицательные, неубывающие вычислимые функции, причем Л (п) не ограничена, О < //(п) < п для всех п и 7Л (п) = o{fi{n)) при п 00. Для изучения асимптотики кривых (0.1) м II рассмотрим семейство нормализованных кривых.
Л’Л’Л.
Мп) где п = 1(х), с — константа и О < -i < 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. а-&bdquo-) = Л {шг, !{ил1и2. илг-х)) — (0.4) 1.
Мы предполагаем, что значения функции / вычислимы некоторым алгоритмом.
Сумма (0.4) представляет собой некоторую меру сложности последовательного предсказания элементов последовательности и — 00×002.ШпОсновная задача предсказания заключается в нахождении такой прогнозируюндей стратегии /, которая минимизирует общие потери (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. а-&bdquo-. порождается в соответствии с некоторым вероятностным распределением Р на П. Если 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, если либо подпоследовательность индексов, выбранная из а- = ыхоЛг. а-&bdquo-. посредством Л, конечна, либо для нее выполняется вариант усиленного закона больших чисел.
— А Л п г — - л Л 1{ш1и)2. .. Шп,-1) —> О г=1? = 1 при Г -> СО.
Вероятностная прогнозирующая стратегия / или соответствующее ей распределение вероятностей Р вычислимо калибруема на бесконечной последовательности о?, если она вычислимо калибруема на и) относительно любого вычислимого правила выбора. Данное определение обобщает частотное определение случайности по Ми-зесу — Черчу [50, 38] (предложенное для распределений Бернулли) на произвольные распределения вероятностей.
В главе выясняется следующее соотношение между данным определением случайности и определением алгоритмической случайности. Пусть / - произвольная вычислимая прогнозирующая стратегия и Р — соответствующее распределение вероятностей. Тогда.
— прогнозирующая стратегия / вычислимо калибруема на любой алгоритмически случайной относительно Р бесконечной последовательности ш.
— существует бесконечная последовательность на которой прогнозирующая стратегия /{%) = ½, для всех х еЕ, вычислимо калибруема и которая не является случайной относительно равномерной меры.
Последовательность аназывается стохастической по Дейвиду, если на ней вычислимо калибруема хотя бы одна вычислимая прогнозирующая стратегия. В противном случае, последовательность и называется нестохастической, говорим также, что ш не допускает корректного вероятностного прогнозирования. Основной результат этой части заключается в том, что используя вероятностные алгоритмы (алгоритмические операторы), можно с вероятностью, как угодно близкой к 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{Tuj) = f{ijj). Если к тому же преобразование Т эргодично, то f (u) = E{f) для этой же последовательности ш.
В главе 7 изучаются вопросы устойчивости эргодической теоремы при малых нарушениях случайности индивидуальной последовательности. Бесконечная последовательность о? является случайной по мере Р тогда и только тогда, когда величина дефекта случайности dpiuu’A) ограничена с ростом п. Вовк [4] заметил, что основные законы теории вероятностей при их применении к индивидуаль.
II II ным последовательностям имеют свойство устойчивости относительно небольшого роста дефекта случайности. Более точно, они имеют место не только для случайных последовательностей, но и для последовательностей из более широкого класса. Например, закон больших чисел для равномерной бернуллиевской меры имеет место для любой последовательности w, для которой дефект случайности может ограниченно расти с ростом длины фрагмента как dp{iju" ') = о{п). Для выполнения закона повторного логарифма достаточно потребовать dp{uj'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. Существует вычислимая стационарная мера Р такая, что для любой вычислимой, неограниченной, неотрицательной, неубывающей функции р (п) существует бесконечная последовательность UJ. такаяАчто ар (ш'А) < р (п) для всехп, начиная с некоторого, и предел л п-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 — пространство функций, суммируемых в квадрате на U;
П/П2) — норма в пространстве Li (L2) — р{и) — универсальная мера невозможности бесконечной последовательности и (подразумевается, что задана мера Р на U);
К{ху) — колмогоровская сложность конечного объекта х при заданном конечном объекте у;
Л ((7,р) — функция потерь, где, а равно О или 1, р — действительное число из интервала [0,1];
Ьо888(а-1. Шп) суммарные потери предсказания на конечной двоичной последовательности. а-&bdquoпри использовании предсказательной стратегии Б;
КО (х) — предсказате. льная сложность конечной двоичной последовательности 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, с .105 162.
36. Хинчин А. Я. О стационарных рядах случайных величин // Математический сборник, 1933, т.40, N2, с. 124−128.
37. Шень А. Х. Частотный подход к определению понятия случайной последовательности // Семиотика и информатика. М.: ВИНИТИ, 1982, Вып. 18. — (Второй выпуск за 1981 г.) с. 14−42.
38. Шень А. Х. Понятие (а,/3)-стохастичности по Колмогорову и его свойства // Доклады АН СССР, 1983, т.271, N6, с. 13 371 340.
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 inequalitiesinformation 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-Lof 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.
.