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

[kaipa]

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

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

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

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

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

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

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

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

Comments

[fat-crocodile.livejournal.com]

эээ, поправь если ошибаюсь, но вроде же Колмогоровская сложность это замечательный теоретический конструкт, но практически её определить невозможно?

[fat-crocodile.livejournal.com]

А так вроде бы отличить можно только по тому, каким процессом она порождена. Любой статистический критерий может намекнуть нам, что что-то не так, но вот последовательность знаков числа пи он скорее всего проглотит не моргнув.

[ushastyi.livejournal.com]

Ага. Вообще, со сложностью и вычислимостью завязано несколько, казалось бы, разных вещей. Например, проблема остановки или неполноты. С этого я начал несколько лет назад интересоваться этими вопросами: http://ushastyi.livejournal.com/28233.html

[ushastyi.livejournal.com]

Колмогоровская сложность невычислима. Но это не мешает сравнивать строки (последовательности) по сложности.

[fat-crocodile.livejournal.com]

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

[antilamer.livejournal.com]

Если есть программа, порождающая из строки А строку Б, то сложность Б не больше, чем сложность А плюс длина программы :) это уже достаточно полезное сравнение.

[fat-crocodile.livejournal.com]

ну если только это, то значит ничего не пропустил :)

не знаю, мне видимо не оценить полезность такого сравнения.
например вроде бы из него сразу следует, что криптография толком не работает... мне кажется утверждения с настолько сильными следствиями на практике применять не получается.

[ushastyi.livejournal.com]

Почему из этого следует, что криптография не работает? Из этого следует, что сжимаемость (архиваторами, например) прямо связано со сложностью. Несжимаемые последовательности -- они же и наиболее сложные (при заданной длине) и наиболее случайные.

[fat-crocodile.livejournal.com]

одно другому не мешает, следует и про архиваторы и про криптографию.

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

[ushastyi.livejournal.com]

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

[fat-crocodile.livejournal.com]

Не-не-не. Вот я когда-то писал про криптографию типа введения на пальцах, посмотри http://fat-crocodile.livejournal.com/166478.html

Если конкретно на твой вопрос, то идея в том, что любую обнаруженную закономерность противник сможет использовать против тебя.

А если уже совсем конкретно, то, если он может отличить зашифрованную строку от случайной, становится невозможным режим шифрования CTR, допустим, и поточное шифрование вообще.

[ushastyi.livejournal.com]

Ага, понял.

Насчет AES. Сложность возрастает на сложность ключа плюс константа. Так что все зависит от "хороших" ключей, и нет никакого противоречия.

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

Так что все хорошо с криптографией.

[fat-crocodile.livejournal.com]

Сложность ключа всего 128 бит, больше алгоритм всё равно не использует. Так что если мы не говорим про one-time pad, то вся остальная криптография...

Так в том и дело! Эта получается оценка, которую использовать невозможно. Такая, очень теоретическая, с точки зрения субъекта с бесконечными вычислительными возможностями. Но таких субъектов нету и что тогда с этой оценкой делать не понятно...

[fat-crocodile.livejournal.com]

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

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

[whitelynx.livejournal.com]

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

[fat-crocodile.livejournal.com]

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

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

[whitelynx.livejournal.com]

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

[vincentfischer.livejournal.com]

статью пока не читал, с подходом, реализованным в RUNLUX'e это как-то соотносится?

[ushastyi.livejournal.com]

Статья в основном о теории, а не о практике. А что такое RUNLUX?

[vincentfischer.livejournal.com]

это такой генератор, который, как я понимаю, делает как динамическая система с хаосом
http://www.gnu.org/software/gsl/manual/html_node/Random-number-generator-algorithms.html
и там ссылочки

[dm-kalashnikov.livejournal.com]

//Все программисты знают генераторы случайных (на самом деле -- псевдо-случайных) чисел.

Ну так-то есть и аппаратная поддержка чипсетов, который генерируют реально случайные числа. Но это редкость.

[ushastyi.livejournal.com]

"Реально случайные числа" -- это звучит :) Интересно, как? Кроме как посредством оцифровки термодинамического шума я не могу придумать.

[dm-kalashnikov.livejournal.com]

Ну дык известное дело