Две стороны случайности: энтропия Шеннона и сложность Колмогорова
Статья разбирает математическую загадку: у вас есть два файла по миллиону цифр. Первый, чистый шум (результат миллиона бросаний десятигранного кубика). Второй, первый миллион цифр числа π. При подсчёте частоты каждой цифры 0, 9 в обоих файлах получается одинаково: примерно по 10% на каждую. Любой статистический тест случайности пройдёт одинаково для обоих. И всё же один файл можно отправить в трёх строках кода («вычисли π, выведи миллион цифр»), а другой нельзя сжать вообще, приходится отправлять его целиком.
Эта загадка разрешается разделением на две совершенно разные идеи компрессии. Первая, статистическая: если одни символы встречаются чаще, им дают короткие коды (как в zip или кодировании Хаффмана), другим, длинные, и в среднем получается экономия. Вторая, процессная: объект может происходить из простого правила (короткой программы), даже если его символы выглядят совершенно равномерно распределёнными. Это и есть сложность Колмогорова, длина кратчайшей программы, которая выводит данную последовательность.
Статья подробно разбирает энтропию Шеннона: это средняя «неожиданность» источника символов. Если источник всегда выдаёт один символ, энтропия нулевая. Если десять разных символов с равной вероятностью, энтропия максимальна. Автор выводит формулу энтропии через концепцию «бюджета»: короткие кодовые слова в системе код-дерева занимают много места, поэтому их нельзя раздавать щедро. Оптимальное распределение, давать каждому символу кодовое слово длины, пропорциональной логарифму его вероятности. Для равномерного распределения (как в обоих файлах) энтропия максимальна, статистически оба файла «несжимаемы».
Сложность Колмогорова, совершенно другой подход. Она определяется не частотами, а длиной кратчайшей программы. Миллион нулей, сложность крошечная (программа в одну строку). Случайная строка длины n, сложность примерно n (нельзя короче самой строки). Число π, сложность всего несколько сотен битов, потому что известен алгоритм для его вычисления.
База оба подхода правильны: они просто отвечают на разные вопросы. Энтропия Шеннона смотрит на ансамбли и долгосрочные распределения, видит только частоты. Сложность Колмогорова смотрит на конкретный объект и его внутреннюю структуру. На практике для большинства объектов (случайных и скучных) оба измерения совпадают, но для особых объектов вроде π они расходятся максимально.
В конце статья доказывает фундаментальный результат: почти всё не сжимается. Если рассмотреть все строки длины n, их существует 2^n штук. Всех возможных программ (описаний) короче n, всего 2^n - 1. Значит, даже если каждое короткое описание указывает на уникальную строку, покрыть получится максимум 2^n - 1 строк. По крайней мере одна строка длины n не имеет описания короче себя самой. На самом деле, огромное большинство строк, собственное кратчайшее описание.
Ключевые факты
- π и чистый шум статистически неотличимы (одинаковые частоты цифр), но первый сжимается алгоритмически (несколько строк кода), второй, нет. Это указывает на наличие двух разных типов случайности
- Энтропия Шеннона видит только частоты символов и слепа к структуре; для равномерного распределения (как в обоих файлах) энтропия максимальна, и оба файла статистически «несжимаемы»
- Сложность Колмогорова определяется длиной кратчайшей программы, которая генерирует объект, мера, зависящая от алгоритмической структуры, а не от символьных частот
- Энтропия выводится из принципа «бюджета кодовых слов»: короткие коды дорогие в системе с префиксным кодированием, поэтому оптимально давать их частым символам пропорционально их вероятности
- Почти все строки не сжимаются: для длины n существует 2^n строк, но лишь 2^n - 1 описаний короче n, так что подавляющее большинство строк неуменьшаемо ниже собственной длины
Почему это важно
Различие между статистической (энтропия) и алгоритмической (сложность Колмогорова) компрессией, это фундаментальное разделение в теории информации и информатике. Оно объясняет, почему визуально случайные объекты (вроде цифр π) могут быть внутренне структурированы. Это имеет глубокие последствия для криптографии (отличие истинной случайности от псевдослучайности), генерации случайных чисел, понимания границ вычислимости и того, почему некоторые данные принципиально несжимаемы.
Кому это важно
Математикам и информатикам, работающим с теорией информации и вычислимостью. Специалистам по сжатию данных и кодированию. Криптографам, которые должны понимать разницу между статистической и практической случайностью. Разработчикам, сталкивающимся с лимитами на сжатие данных. Исследователям ИИ и машинного обучения, где понимание структуры и компрессии данных критично.
Как это применить
При тестировании генератора случайных чисел помни, что статистические тесты (проверка частот) недостаточны, нужно проверять невычислимую сложность Колмогорова через более сложные тесты. При выборе алгоритма сжатия помни, что статистическое сжатие (вроде Huffman) достигает энтропии Шеннона, но если данные содержат скрытую структуру, нужны алгоритмические методы (контекстная модель, арифметическое кодирование). При анализе больших данных: частоты нужны, но неполны, ищи скрытые паттерны и правила, которые генерируют данные.
Можно ли доверять
Статья написана с математической строгостью и опирается на хорошо известные определения энтропии Шеннона и сложности Колмогорова. Вывод формулы энтропии через бюджет кодовых слов верен и используется в теории информации. Пример с π верен, число π действительно генерируется простым алгоритмом. Доказательство о несжимаемости почти всех строк, это стандартный результат теории вычислимости. Автор честно разделяет два подхода и показывает, где каждый применим.
Риски и подводные камни
Сложность Колмогорова невычислима в общем случае, можно привести конкретную короткую программу и проверить её, но никогда не доказать, что это кратчайшая программа для данной последовательности. Легко спутать статистическую неотличимость с теоретической несжимаемостью, нужно помнить, что это разные оси. Практические алгоритмы сжатия (gzip, bzip2) работают с конечными и конкретными стратегиями, поэтому они могут отличаться от теоретических пределов. Для реальных данных энтропия Шеннона часто даёт хорошее приближение, но скрытая структура может дать намного лучшее сжатие.
«Энтропия Шеннона статистична. Она об ансамбле, источнике, распределении, долгосрочности, и видит только частоты.»
— "Connections in Math: the two kinds of random"