§4. Случайность и сложность: насколько ты реально непредсказуем

Стоп. Мы тут гоняем «псевдослучайные» числа из детерминированных алгоритмов — коротких, предсказуемых станков. И тут напрашивается неудобный вопрос в лоб: в каком смысле они вообще случайны? Если я знаю формулу и старт, я выдам всю твою «случайную» цепочку наперёд, до последней цифры. Какая же это случайность?

Вопрос не праздный — над ним бились лучшие головы XX века. Разберёмся, что за зверь эта случайность на самом деле.

Первый заход: частоты (фон Мизес)

Рихард фон Мизес заходил так: последовательность случайна, если частоты символов в ней устаканиваются — и не только во всей цепочке, но и в разумных подпоследовательностях. Выдёргиваешь из потока любой честный «подпоток» (не подсматривая в сами значения) — а доля нулей и единиц в нём всё равно садится на свои $0{,}5$. Какие именно подпоследовательности считать «честными» — этот момент потом уточнял Чёрч.

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

Колмогоров: случайное — это то, что дорого описать

Андрей Николаевич Колмогоров зашёл с другого конца и провёл дерзкую параллель: случайным выглядит то, что очень сложно получить. Чем труднее коротко описать штуку — тем она случайнее.

Вникни в логику на пальцах. Возьми две строки из нулей и единиц, по тысяче знаков:

• 0101010101... — тысяча раз «ноль-один». Чтобы её описать, хватает пяти слов: «повтори 01 пятьсот раз». Описание коротенькое — значит, строка регулярная, предсказуемая, ни разу не случайная.
• 1100101110001... — без всякого порядка, как бог на душу положит. Чтобы её описать точно, короче самой строки ничего не придумаешь — приходится выписывать её целиком. Описание длинное, как сама строка — значит, она случайная.

Вот это и есть ядро колмогоровской сложности (её строго оформили Колмогоров и Мартин-Лёф в 1965–66):

Сложность последовательности — это длина самой короткой программы, которая её печатает (на стандартной машине — машине Тьюринга). Чем длиннее кратчайшая программа — тем последовательность сложнее, тем она случайнее.

Разбираем по кирпичикам:

• короткая программа есть $\Rightarrow$ в строке зашита закономерность, её можно сжать, описать кратко $\Rightarrow$ она не случайна;
• короче самой строки ничего не выходит (программа ≈ сама строка) $\Rightarrow$ сжимать нечего, закономерности нет $\Rightarrow$ строка случайна.

Формально: последовательность длины $N$ называют случайной, если её сложность близка к максимально возможной (примерно к $N$). И вот что красиво — таких большинство. Если накидать все строки длины $N$, почти все окажутся несжимаемыми, то есть случайными. Мартин-Лёф вдобавок доказал: такие строки проходят вообще все мыслимые статистические тесты на случайность. То есть сложность и случайность — это, по сути, одно и то же, просто с разных боков.

Проверим чуйку кодом. Возьмём регулярную строку 0101... и честно случайную, и попробуем их сжать архиватором (сжатие — это и есть поиск короткого описания). Жми Run:

Регулярную строку архиватор ужимает в десятки раз — потому что у неё короткое описание («01 тыщу раз»). А случайную почти не трогает — сжимать нечего, короче уже не опишешь. Вот тебе колмогоровская сложность вживую: случайное = несжимаемое.

Парадокс, с которым живут все

А теперь неудобный итог, который прямо бьёт по нашим датчикам из §3.

Если по-честному, по Колмогорову–Мартин-Лёфу, настоящие случайные числа может выдать только достаточно длинная программа (короткая по определению порождает сжимаемую, а значит, не случайную последовательность). А на практике генераторы случайных чисел — коротюсенькие: пара строк кода, формула (1) из прошлого параграфа. Как это вообще совмещается?

А вот так: на практике живут по «презумпции случайности». Датчик считают годным и пускают в дело, пока не доказано, что он гнилой. И почти любой станок выдаёт приличные числа, если их нужно немного — десятки, сотни штук. Беда приходит, когда симуляции требуют тысячи и миллионы чисел: на таких длинных сериях уже трудно найти датчик, который не спалится на проверках (а проверять мы научимся в части про критерии согласия).

По-дворовому: мелкую движуху короткий датчик провернёт чисто, никто не подкопается. Но размахнёшься по-крупному — и фальшивая случайность вылезет наружу, как палёный товар на серьёзной сделке. Знай меру и проверяй свой станок.

Проверь себя