Применение колмогоровской теории алгоритмической сложности к логическим основам теории вероятностей

• Автор: Вьюгин, Владимир Вячеславович
• Шифр специальности: 01.01.06
• Научная степень: Докторская
• Год защиты: 2001
• Место защиты: Москва
• Количество страниц: 164 с.

Оглавление
Введение

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

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. (а, /?)-нестохастические последовательности

6. Алгоритмический анализ эргодической теоремы Бирк-гофа
6.1. Сходимость по вероятности
6.2. Эргодическая теорема для алгоритмически случайных последовательностей
7. Неустойчивость эргодической теоремы при нарушениях случайности
7.1. Лемма о росте супермартингала
7.2. Метод разрезания и складывания
7.3. Теоремы о неустойчивости
8. Алгоритмически-инвариантные свойства последовательностей
8.1. Алгебра инвариантных свойств
8.2. Сети и потоки
8.3. Доказательство теоремы 5.
8.4. Доказательство теоремы 8.
8.5. Доказательство теоремы 8.
8.6. Сводимость атомов
Литература

Введение
Актуальность темы. Теория вероятностей в классической формулировке А.Н.Колмогорова [18] представляет собой аксиоматическую теорию, являющуюся частью теории меры. Математическая статистика и теория информации используют аппарат теории вероятностей и имеют те же основания. Одновременно с развитием математической теории постоянно обсуждались вопросы применимости теории вероятностей к явлениям реального мира. В настоящее время в практических приложениях общепринятой является частотная интерпретация вероятности (см. например, учебники [2, 10, 41]). А.Н.Колмогоров, предложивший глубокие уточнения частотной интерпретации в своей знаменитой книге [18], продолжал исследования в области обоснования приложений теории вероятностей, Первая попытка построить теорию алгоритмической случайности для конечных последовательностей была предпринята им в работе [60].
В результате своих исследований А.Н.Колмогоров предложил в начале 60-тых годов программу построения математической теории, обосновывающей приложения теории вероятностей на основе теории алгоритмов [15, 16]. Согласно этой программе практические выводы теории вероятностей могут быть обоснованы в качестве следствий гипотез о предельной (при данных ограничениях) сложности изучаемых явлений. При таком подходе основным является понятие алгоритмической сложности конечного объекта.
Идеи А.Н.Колмогорова были частично реализованы его учениками и последователями. В частности, Левиным [24, 27, 26] и Шнорром [77, 78] были определены различные варианты колмогоровской сложности - префиксная и монотонная сложности, сложность разреше-

Лемма 1.2. Если V С D и х е V, тогда d(xJ,D) > log Щ — 2K(VJ) — с для некоторой неотрицательной константы с.
Доказательство. Как замечено ранее, К(хJ, У) < log(#y) + с для всех х € У, где с - константа. Отсюда получаем для всех таких х
K(xJ) < K(xJ, У) + 2K{VJ) + с' < log(#y) + 2K(VJ) + с,
где с, с' константы. Из определения следует K(xJ, D) < K(xJ)+c для всех х, где с - константа. Из всех этих неравенств следует
d(xJ, D) = log(#.D) - K(xJ, D) > log #D - log #У - 2K(VJ) - c,
для всех x € У, где с - константа. □
По лемме 1.2 для произвольных 1 < j < k, K(DJ) < а,- и I е Uk ("] D выполнено
d(xD,J)>oSwffiu:-2K(Dr)UkJ)> (1.4)
lj — Uj — 2 — 6а*, — c = lj — 7ak — с = (1.5)
0j — 7atk — felogfc — fc — сз, (1.6)
где с, сз - положительные константы. Здесь мы использовали неравенство K(Df] UkJ) < «j + 2сц, + с < За*, + с., где cud- положительные константы.
По свойству дефекта случайности
ф{х | х G A,d(xA, J) > т} < 2П"8#^1-
для любого конечного множества А. Так как #U* = суще-
ствует множество 1Ух С Uk такое, что
#Wi > г”-*-

d(x|J,3„) < 0i +
для всех I £ И).
Так как число х е Wi, для которых
ада, j) = iog(#0i) - к(хии j)> + 2,