Кафедра математической логики и теории алгоритмов

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


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

Последней областью интересов А. Н. Колмогорова была основанная им «алгоритмическая статистика». Сейчас многие исследования в этом направлении, также идут в научной школе Н. К. Верещагина. Классическая теория вероятностей не объясняет, почему, имея последовательность из тысячи нулей, полученную бросанием монетки, мы отвергаем гипотезу о том, что монетка была симметричной, а бросания независимыми. Теория алгоритмов позволяет объяснить этот факт — эта последовательность слишком проста (ее колмогоровская сложность ничтожна). Колмогоров предложил измерять правдоподобность статистической гипотезы о происхождении данной двоичной последовательности (здесь и далее в данном абзаце — конечной) разностью модуля двоичного логарифма ее вероятности (относительно распределения вероятностей, задаваемого гипотезой) и ее сложности. Эту разность он назвал «дефектом случайности x». Последовательность x называется стохастической, если существует простая статистическая гипотеза, дефект случайности x относительно которой мал. Колмогоров не знал, существуют ли нестохастические последовательности. На этот вопрос ответили выпускники кафедры, ученики В. А. Успенского Владимир Вячеславович Вьюгин и Александр Шень, которые доказали их существование и оценили количество. В алгоритмической статистике много открытых вопросов. Например, неясно, всегда ли метод наибольшего правдоподобия, выбирающий среди простых гипотез ту, которая максимизирует вероятность последовательности, дает оптимальную статистическую гипотезу, то есть, гипотезу с наименее возможным дефектом случайности (среди простых гипотез).

Дефект случайности можно определить и для бесконечных последовательностей (относительно вероятностной меры на пространстве бесконечных 0-1-последовательностей). В отличие от конечных, бесконечные последовательности можно разделить на случайные (их дефект случайности конечен) и неслучайные. Впервые это было сделано учеником Колмогорова шведским логиком Пером Мартин-Лёфом. П. Мартин-Лёф — академик Шведской королевской академии наук; он руководил объединенной кафедрой математики и философии Стокгольмского университета до 2009 г. Итоги исследований в этом направлении были подведены в статье «Математическая метафизика случайности» Ан.А. Мучника, А. Л. Семенова и В. А. Успенского и книге В.А. Успенского, Н.К Верещагина и А. Шеня «Колмогоровская сложность и алгоритмическая случайность». Тематику случайности продолжают ученики А. Шеня.