Неравенства для колмогоровской сложности и общая информация

• Автор: Ромащенко, Андрей Евгеньевич
• Шифр специальности: 01.01.06
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Москва
• Количество страниц: 88 с.

Оглавление
Введение
Используемые обозначения
1. Р-типичность и Р-случайность
2. Неравенства для колмогоровской сложности и шенноновской энтропии
3. Полурешетки с отношением условной простоты
4. Пары с нематериализуемой взаимной информацией
4.1. Стохастические пары
4.2. Пары ортогональных подпространств
Введение
Актуальность темы. Одна из первых работ А. Н. Колмогорова по теории алгоритмической сложности называлась «Три подхода к определению понятия “количество информации”». Двумя из трех рассмотренных подходов были энтропия Шеннона и алгоритмическая (или колмо-горовская) сложность. В этой, а также в нескольких последующих работах ([3, 4]) Колмогоров указывал на связь данных понятий и параллелизм их свойств. Один из простейших примеров параллелизма свойств шенноновской энтропии и колмогоровской сложности - симметричность шенноновской взаимной информации и симметричность взаимной информации по Колмогорову. Другим, нетривиальным примером является аналогичность свойств двух родственных понятий - введенных П. Гачем и Я. Кернером общей информации пары случайных величин и общей информации пары слов [9]. Гач и Кернер исследовали свойства общей информации пар случайных величин и пар слов методами теории вероятностей. В ряде других работ [5, 13, 15] свойства общей информации пар слов изучались алгоритмическими методами.
Многие естественные свойства колмогоровской сложности и шенноновской энтропии формулируются с помощью линейных неравенств. Ряд нетривиальных неравенств для колмогоровской сложности, а также их приложения изучались в [10,11]. В [16] рассматривалась связь между выразимыми с помощью линейных неравенств свойствами колмогоровской сложности и шенноновской энтропии.
Таким образом, к различным вопросам теории информации разработаны вероятностный и алгоритмический подходы. Многие параллельные понятия из классической и алгоритмической теории информации имеют аналогичные свойства. Изучение данного параллелизма является важной задачей, находящейся на границе двух дисциплин - теории вероятностей и математической логики.
Целью дайной работы является изучение классов линейных нера-
венств, выполняющихся для колмогоровских сложностей произвольных наборов слов и для шенноновских энтропий произвольных случайных величин, а также усиление результатов Гача и Кернера [9] и Ан. А. Мучника [5,13], касающихся алгоритмического варианта понятия общей информации.
Методы исследования. В работе применяются методы теории алгоритмов и теории вероятностей.
Научная новизна. Все основные результаты работы являются новыми и состоят в следующем:
1) Доказано совпадение классов линейных неравенств, выполняющихся для колмогоровской сложности слов и шенноновской энтропии дискретных случайных величин.
2) Показано, что неравенство Инглетона не выполняется для колмогоровской сложности и шенноновской энтропии.
3) Доказано, что определенные в [15] отношения условной простоты на последовательностях слов задают частичные порядки, являющиеся верхними полурешетками, но не являющиеся нижними полурешет-ками.
4) Построены два новых класса примеров пар слов, имеющих большую взаимную информацию и нулевую общую информацию. Получен положительный ответ на вопрос Ан. А. Мучника [13] о возможности дополнить любое слово до пары с большой взаимной и нулевой общей информацией.
Приложения. Работа носит теоретический характер. Полученные результаты относятся к теории колмогоровской сложности и могут применяться в классической и алгоритмической теории информации.
Апробация работы. Результаты диссертации докладывались на Научно-исследовательском семинаре по математической логике в МГУ (руководители академик РАН проф. С. И. Адян и проф. В. А. Успенский), а также на Колмогоровской семинаре кафедры математической логики и теории алгоритмов мех.-мат. факультета МГУ (руководители проф. Н. К. Верещагин, д. ф.-м. н. А. Л. Семенов и к. ф,-м. н. А. X. Шень).
Публикации. Основные результаты диссертации опубликованы в работая [15, 16, 17, 18].
Далее, последовательность w типична относительно распределения /3. Это значит, что для каждого ; - 1 г слово wn содержит
m.j = Prob[/3 = bj] ■ п + 0(1) (1.6)
букв bj. Заметим, что
т. = 2^ niij.

Предположим, что слово wn известно и требуется найти vn. Сложность нахождения всех чисел ту есть O(logrj) (константа перед логарифмом зависит от размеров алфавитов Л и В, но не зависит от в). Пусть величины ту уже найдены. Тогда для получения слова vn достаточно для каждого j = 1,2 ..., г указать разбиение тех rrij позиций, в которых в слове и>„ стоит буква bj, на s классов (содержащих ти,msj ПОЗИЦИЙ), В которых В слове Vn СТОЯТ буквы «1, ... ,as соответственно. Для каждого j имеется
rrtj!
тцЦ,-!... msj!
способов разбить rrtj позиций на непересекающиеся подмножества размера rrtij,..., maj. Следовательно,
кыК) < £iog (L7)
Оценивая факториалы с помощью формулы Стирлинга, нетрудно преобразовать правую часть (1.7) в выражение
-nY,r^lo^+0^n)-

Из (1.5) и (1.6) следует, что ^ = Probfa = а*,/? = bj] + 0(1/п) и ^ = Prob[a — 0^1/? = bj] + 0(1/п). Значит правая часть неравенства (1.7) равна
—п РгоЬ[а = аг-, /3 = bj] log Prob[a = сч(3 = bj] -f <9(iog п) =

= п • Н(а |/3) --0 (log п).