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

[kaipa]

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

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

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

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

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

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

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

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

Comments

[fat-crocodile.livejournal.com]

Кстати, я был не совсем прав, это не проблема Колмогоровской теории сложности. Похожая теорема есть и в Шенноновской теории информации -- про то что перекодирование не увеличивает энтропию в строгом смысле, и криптография по большому счёту опять не задалась -- ну не везёт криптографии с теоретическим оформлением.

Но для энтропии есть простые способы оценки сверху, схватывающие некоторые типичные случаи избыточности обычных текстов и дающие результат "полностью случайная" для зашифрованной последовательности.

[whitelynx.livejournal.com]

Прошу прощения, что вмешиваюсь. Я ни хрена конечно не понимаю в теме по большому счету, но если бы как-то теоретически удалось доказать что криптография сильно увеличила сложность, из этого наверное можно было бы вывести что P != NP нет?

[fat-crocodile.livejournal.com]

я думаю что нет.

тут же вопрос в том, что такое "сложность" :)
ты, кажется, смешиваешь два разных словоупотребления, в одном случае речь идёт о сложности задачи (и к этому относится P, NP и т.п.), и это понятно что такое. А в другом случае речь идет о сложности строки символов. И это очень нетривиальное понятие, которое по можно разными способами искусственно вводить.

[whitelynx.livejournal.com]

Я конечно слабо понимаю что такое сложность строки, но если увеличение такой сложности - это хорошо для криптографии, то видимо большая сложность строки означает, что ее трудно расшифровать, то есть алгоритм расшифровки будет долго работать. Может я конечно не понимаю чего-то, но смысл-то криптографии в том, чтобы сложно было расшифровать исходное сообщение не зная ключа.