Shannon и Колмогоров — два разных способа формализовать «количество информации». Кратко и по существу:
Определения и смысл
- Shannon (энтропия). Для дискретной случайной величины $X$ с распределением $p(x)$:
$$H(X)=-\sum _{x}p(x)\log p(x).$$ Это среднее количество битов неопределённости / минимальная средняя длина кода на символ при известном распределении (теорема кодирования источника).
- Колмогоров (алгоритмическая сложность). Для строки $x$ относительна к универсальной машине $U$:
$$K_U(x)=\min \{|p|:U(p)=x\},$$ т.е. длина кратчайшей программы, генерирующей $x$. Характеризует информацию в конкретном объекте/строке.
Ключевые различия
- Объект описания: Shannon — свойство распределения (ансамбля), Колмогоров — свойство конкретной строки.
- Среднее vs индивидуальное: $H(X)$ — средняя скорость (в бит/символ), $K(x)$ — абсолютная длина описания одного экземпляра.
- Вычислимость: $H$ вычислима при известном $p$; $K(x)$ не вычислима (но полуразрешима сверху — можно получить верхние оценки через конкретные программы/сжатие). Различие по константам: $K$ зависит от выбора $U$ лишь до аддитивной константы.
- Оперативность: Shannon даёт асимптотические гарантии (AEP, теорема о кодировании); Колмогоров даёт строгую границу для индивидуальных строк, но не даёт конструктивного алгоритма.
Связь между ними
- Для стационарного эргодического источника и типичных строк длины $n$ $$K(x_{\mathrm{1..}n})\approx nH(X)+o(n),$$ т.е. в среднем алгоритмическая сложность растёт как $n$ раз энтропия источника.
Практические ситуации — где что полезнее
- Shannon полезен:
- проектирование кодов и каналов (минимальная средняя длина, пропускная способность),
- оценка компрессии в среднем для больших объёмов данных при известной или хорошо моделируемой статистике (например, сжатие текста при обученной языковой модели),
- статистические задачи (информация между признаками, критерии отбора).
- Колмогоров полезен:
- анализ конкретной структуры в одной последовательности (есть ли «правило», которое кратко генерирует строку),
- теоретические рассуждения о случайности (например, доказательства об Непредсказуемости конкретных последовательностей — алгоритмическая/Мартиновская случайность),
- принцип минимального описания (MDL) как мотивация для выбора модели и оценки сложности модели + данных.
Ограничения при сжатии данных
- Shannon:
- даёт нижнюю границу на ожидаемую длину кода: для источника $X$ любая кодировка с ожидаемой длиной $\mathbb{E}[\ell ]$ удовлетворяет $\mathbb{E}[\ell ]\ge H(X)$, и асимптотически это достижимо при знании $p$;
- на практике требуется оценить/обучить $p$; при неверной модели реальные коды хуже.
- Колмогоров:
- даёт идеал для конкретной строки: нельзя сжать строку короче, чем $K(x)$ (с точностью до константы) без потери информации;
- неалгоритмически применим — нельзя вычислить $K(x)$ для произвольного $x$, потому прямой алгоритмической схемы «сжать до $K(x)$» нет;
- практические компрессоры дают только верхние оценки $K(x)$ и ориентированы на статистические модели, т.е. чаще опираются на Shannon-подход.
Ограничения при анализе случайности
- Shannon: можно показать, что последовательность типична для заданного распределения, но нельзя по одной конечной строке строго утверждать «это случайная строка» без априорной модели; статистические тесты дают отказ/принятие гипотезы на уровне вероятностей.
- Колмогоров: формализует «истинную» случайность для конкретной строки (например, строки с $K(x)\approx |x|$ считаются случайными), но это свойство неразрешимо алгоритмически — нельзя проверить для произвольной строки.
Короткие иллюстрации
- Строка из честных подбрасываний монеты длины $n$: $H=1$ бит/символ, и типично $K(x)\approx n$.
- Строка «0101010101...» длины $n$: $H$ источника = $0$ (если источник детерминирован), а $K(x)\ll n$ (короткая программа генерирует период).
Вывод (кратко)
- Для инженерных задач сжатия и средних/асимптотических оценок используйте понятия Шеннона (энтропия, AEP, кодирование).
- Для фундаментальных рассуждений о том, есть ли у конкретной строки «короткая закономерность» и для формальной теории случайности — понятие Колмогорова, но с учётом его невычислимости и ограниченной практической применимости.