Астурия

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

Иссак Альбенис. "Астурия" (ликбез: область в Испании) из цикла "Испанская сюита для фортепиано". Великолепное исполнение Бориса Березовского, не того самого, а его тезки, талантливого музыканта.

Случайность случайности

Все, кто изучал теорию вероятности, наверное, помнят, что такое случайная величина. Однако, вряд ли они сходу могут ответить, что такое случайное значение (более строго -- случайный элемент вероятностного пространства). Чтобы понять в чем разница, приведу пару простых примеров. Последовательность выпадений "орла" и "решки" 0001011101 случайна или нет? А 000000? Другой пример. Все программисты знают генераторы случайных (на самом деле -- псевдо-случайных) чисел. Обычно, эти генераторы дают значения, распределенные равномерно или нормально. Однако, они не случайно называются "псевдо-случайными". Несмотря на сходство основных параметров с "модельными" распределениями, последовательности значений не случайны, так как генерируются вполне детерминированными алгоритмами. Их можно "запускать" с одного и того же места и т.д. Обычно они все имеют цикл, большего или меньшего размера.

Меня этот вопрос интересовал довольно давно чисто с практической стороны, так как в свое время я намучался с "плохими" генераторами случайных чисел, и мне было интересно, есть ли надежный критерий "хорошести". Однако, интерес был не настолько глубоким, чтобы этот вопрос как-то изучить. И вот на днях совершенно случайно наткнулся на большую статью-обзор "Может ли (индивидуальная) последовательность нулей и единиц быть случайной?", одним из авторов которой выступает уважаемый и бывающий здесь a_shen (второго автора -- его научного руководителя В.А. Успенского я тоже, конечно, знаю, читал его воспоминания о Колмогорове и какие-то книжки по теории вероятности). Эта статья все расставляет на свои места. Оказывается, что вопрос о случайности конкретной последовательности отнюдь не тривиален, существует три подхода к этой проблеме, один из которых был предложен Колмогоровым в 1965г. Он основан на понятии колмогоровской сложности. Причем, я бы мог и раньше догадаться об этой идее, так как колмогоровской сложностью интересовался.

Я назову только сами подходы и основные идеи. В статье все очень подробно написано, рассмотрено с разных сторон и доказано.

1. Стохастический или частотный. Он основан на свойстве устойчивости частот. Идея я том, у случайных последовательностей "неслучайные" подпоследовательности (например, только четные элементы) "ведут себя" так же, как и сама последовательность. Исторически, это первая попытка предпринятая Рихардом фон Мизесом.

2. Сложностный (Колмогоровский) подход. Отождествляет случайность с хаотичностью или сложностью. Т.е. длина программы, генерирующей случайную последовательность, растет максимально быстро (по отношению ко всем последовательностям) в зависимости от длины самой последовательности.

3. Подход типичности. Типичность в интуитивном смысле "типичный представитель". Оказывается, можно дать строгое вероятностное построение такого объекта, что было сделано шведским математиком Мартин-Лёфом. Учеником Колмогорова, кстати.

Примечательно, что построения Колмогорова и Мартина-Лёфа очень разные, но эквивалентные. То есть хаотичные (по Колмогорову) последовательности типичны по (Мартину-Лёфу) и наоборот. Это утверждает теорема Левина-Шнорра.

P.S. Печально, что хотя я все еще в состоянии понять и проследить логику математических статей и построений, в голове ничего не задерживается. Я неплохо, как мне кажется, разобрался с Колмогоровской сложностью и вычислимостью несколько лет назад, но практически все забыл :(