Как измерить количество информации? / forpes.ru

Главная
Как измерить количество информации?

Как измерить количество информации? +29

13.01.2022 19:49

avsmal 15 4000 Источник

Мы ежедневно работаем с информацией из разных источников. При этом каждый из нас имеет некоторые интуитивные представления о том, что означает, что один источник является для нас более информативным, чем другой. Однако далеко не всегда понятно, как это правильно определить формально. Не всегда большое количество текста означает большое количество информации. Например, среди СМИ распространена практика, когда короткое сообщение из ленты информационного агентства переписывают в большую новость, но при этом не добавляют никакой «новой информации». Или другой пример: рассмотрим текстовый файл с романом Л.Н. Толстого «Война и мир» в кодировке UTF-8. Его размер — 3.2 Мб. Сколько информации содержится в этом файле? Изменится ли это количество, если файл перекодировать в другую кодировку? А если заархивировать? Сколько информации вы получите, если прочитаете этот файл? А если прочитаете его второй раз?

По мотивам открытой лекции для Computer Science центра рассказываю о том, как можно математически подойти к определению понятия "количество информации".

В классической статье А.Н. Колмогорова "Три подхода к определению понятия количества информации" (1965) рассматривают три способа это сделать:

комбинаторный (информация по Хартли),
вероятностный (энтропия Шеннона),
алгоритмический (колмогоровская сложность).

Мы будем следовать этому плану.

Комбинаторный подход: информация по Хартли

Мы начнём самого простого и естественного подхода, предложенного Хартли в 1928 году.

Пусть задано некоторое конечное множество . Количеством информации в будем называть $\chi(A) = \log_2|A|$ .

Можно интерпретировать это определение следующим образом: нам нужно $\chi(A)$ битов для описания элемента из .

Почему мы используем биты? Можно использовать и другие единицы измерения, например, триты или байты, но тогда нужно изменить основание логарифма на 3 или 256, соответственно. В дальшейшем все логарифмы будут по основанию 2.

Этого определения уже достаточно для того, чтобы измерить количество информации в некотором сообщении. Пусть про $x\in A$ стало известно, что $x\in B$ . Теперь нам достаточно $\chi(A\cap B) = \log_2 |A\cap B|$ битов для описания , таким образом нам сообщили $\chi(A) - \chi(A\cap B)$ битов информации.

Пример

Загадано целое число от до . Нам сообщили, что делится на . Сколько информации нам сообщили?

Воспользуемся рассуждением выше.

$\log_2 1000 - \log_2 166 = \log_2 \frac{1000}{166} \approx 2.59\ \text{битов.}$

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

Можно ещё сказать, что сообщение, уменшающее пространство поиска в $\alpha$ раз приносит $\log_2 \alpha$ битов информации. В данном примере пространство поиска уменьшилось в 1000/166 раз.

Интересно, что одного этого определения уже достаточно для того, чтобы решать довольно нетривиальные задачи.

Применение: цена информации

Загадано целое число от до . Разрешается задавать любые вопросы на ДА/НЕТ. Если ответ на вопрос "ДА", то мы должны заплатить рубль, если ответ "НЕТ" — два рубля. Сколько нужно заплатить для отгадывания числа ?

Любой вопрос можно сформулировать как вопрос о принадлежности некоторому множеству, поэтому мы будем считать, что все вопросы имеют вид " $x\in T$ ?" для некоторого множества .

Каким образом нужно задавать вопросы? Нам бы хотелось, чтобы вне зависимости от ответа цена за бит информации была постоянной. Другими словами, в случае ответа "НЕТ" и заплатив два рубля мы должны узнать в два больше информации, чем при ответе "ДА". Давайте запишем это формально.

Потребуем, чтобы

$2\cdot(\log |X| - \log|X \cap T|) = \log |X| - \log|X\cap\overline T|.$

$2\log (1/\alpha) = \log (1/(1-\alpha)).$

Это эквивалентно квадратному уравнению $\alpha^2 = 1 - \alpha.$ Положительный корень этого уравнения $\alpha=(\sqrt 5 - 1) / 2$ . Таким образом, при любом ответе мы заплатим $c = 1/\log(1/\alpha)\approx 1.44$ рублей за бит информации, а в сумме мы заплатим примерно $c\log n$ рублей (с точностью до округления).

Осталось понять, как выбирать такие множества . Будем выбирать в качестве непрерывные отрезки прямой. Пусть нам известно, что принадлежит отрезку [a,b] (изначально это отрезок [1,n] ). В следующего множества возмём отрезок $[a, a+ \alpha\cdot(b-a)]$ , где $\alpha=(\sqrt 5 - 1) / 2$ . Тогда за каждый заплаченный рубль текущий отрезок будет уменьшаться в $1/\alpha^2 = 1/(1-\alpha)$ раз. Когда длина отрезка станет меньше единицы, мы однозначно определим . Поэтому цена отгадывания не будет превосходить

$c\log((n-1)/\alpha^2) = c\log(n-1) - 2c\log \alpha = c\log(n-1) + 2.$

Приведённое рассуждение доказывает только верхнюю оценку. Можно доказать и нижнюю оценку: для любого способа задавать вопросы будет такое число , для отгадывания которого придётся заплатить не менее $c\log (n-1)$ рублей.

Вероятностный подход: энтропия Шеннона

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

Пусть задана случайная величина , принимающая различных значений с вероятностями $p_1,p_2,\dotsc,p_k$ . Энтропия Шеннона случайной величины определяется как

$H(X) = \sum_{i=1}^k p_i\cdot\log\frac1p_i.$

(По непрерывности тут нужно доопределить $0\cdot \log\frac10 = 0$ .)

Энтропия Шеннона оценивает среднее количество информации (математическое ожидание), которое содержится в значениях случайной величины.

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

Я попробую объяснить происхождение этой формулы как обобщение информации по Хартли. Нам бы хотелось, чтобы это определение согласовывалось с определением Хартли, т.е. должны выполняться следующие "граничные условия":

если все исходы равновероятны ( $p_1=\dotsb=p_k$ ), то $H(X) = \log k$ ,
если распределение вырождено (и для всех $i\neq j$ ), то .

Будем искать $H(\alpha)$ в виде математического ожидания количества информации, которую мы получаем от каждого возможного значения .

$H(X) = \sum_i p_i\cdot \text{(информация в событии $X=a_i$)}.$

Как оценить, сколько информации содержится в событии X = a_i ? Пусть — всё пространство элементарных исходов. Тогда событие X = a_i соответствует множеству элементарных исходов меры p_i . Если произошло событие X = a_i , то размер множества согласованных с этим событием элементарных исходов уменьшается с |U| до $p_i\cdot|U|$ , т.е. событие X = a_i сообщает нам $\log|U| - \log(p_i\cdot|U|) = \log(1/p_i)$ битов информации. Тут мы пользуемся тем, что количество информации в сообщении, которое уменьшает размер пространство поиска в 1/p_i раз приносит $\log(1/p_i)$ битов информации.

Примеры

Подбрасывание честной монетки. Рассмотрим случайную величину, соответствующую подбрасыванию честной монетки. Выпадение орла и выпадение решки равновероятны, следовательно . Тогда $H(X) = 2\cdot \frac{1}{2}\cdot \log_2 2 = 1.$ Это соответствует информации по Хартли в двухэлементном множестве.
Подбрасывание нечестной монетки. Пусть $p_1 = p\neq 1/2$ . Тогда
$H(X) = p\cdot \log_2 \frac{1}{p} + (1-p)\cdot \log_2 \frac{1}{1-p} < 1.$
Если проанализировать это выражение, то можно заключить, что чем дальше монетка от честной, тем меньше энтропия соответствующей случайной величины.
Бросок игрального кубика. Аналогично честной монетке. Все грани выпадают равновероятно, т.е. $p_i=\frac{1}{6}$ . Следовательно, $H(X) = 6\cdot \frac{1}{6}\cdot \log_2 6 = \log_2 6.$ Снова получаем совпадение с информацией по Хартли.
Выбор автомобиля на сайте. Рассмотрим выбор автомобиля на сайте. Как определить, сколько информации в среднем содержит параметр "цвет"? Пусть всего доступны цветов. Обозначим через долю автомобилей с цветом . Пусть белый соответствует у 1/10 доле всех автомобилей. Тогда выбор белого цвета приносит $\log_2 10$ битов информации (по Хартли). В среднем выбор цвета приносит $\sum_k p_k\cdot \log_2\frac{1}{p_k}$ . Это соответствует энтропии Шеннона случайной величины, равномерно распределённой на множестве всех автомобилей.

Свойства энтропии Шеннона

Для случайной величины , принимающей значений с вероятностями $p_1,p_2,\dotsc,p_k$ , выполняются следующие соотношения.

$H(X) \ge 0$ .
$\iff$ распределение вырождено.
$H(X) \le \log k$ .
$H(X) = \log k$ $\iff$ распределение равномерно.

Чем распределение ближе к равномерному, тем больше энтропия Шеннона.

Энтропия пары

Понятие энтропии Шеннона можно обобщить для пары случайных величин. Аналогично это обощается для тройки, четвёрки и т.д.

Пусть совместно распределённые случайные величины и принимают значения $a_1,a_2,\dotsc,a_k$ и $b_1,b_2,\dotsc,b_m$ , соответственно. Энтропия пары случайных величин и определяется следующим соотношением:

$H(X,Y) = \sum_{i=1}^k\sum_{j=1}^m\Pr[X = a_i, Y=b_j]\cdot \log\frac{1}{\Pr[X = a_i, Y = b_j]}.$

Примеры

Рассмотрим эксперимент с выбрасыванием двух игральных кубиков — синего и красного.

Пусть соответствует числу на синем кубике, а — числу на красном кубике. Легко проверить, что $H(X,Y) = H(X)+H(Y) = 2\log 6.$ Это можно объяснить так: есть 36 различных вариантов значений и , и все они равновероятны. Поэтому и получаем $\log 36 = \log 6^2 = 2\log 6$ .
Пусть теперь соответствует сумме чисел на кубиках, а — произведению. Легко понять, что $H(X,Y) < 2\log 6,$ т.к. теперь некоторые пары значений и соответствуют нескольким парам чисел на кубиках, т.е. вариантов значений и меньше 36. Например, соответствует значениям (1,3) и (3,1).

Свойства энтропии Шеннона пары случайных величин

Для энтропии пары выполняются следующие свойства.

$H(X, Y) \le H(X) + H(Y)$ .
$\iff$ и независимы.
$H(X) \le H(X,Y)$ .
$\iff$ однозначно определяет .

Условная энтропия Шеннона

Теперь давайте научимся вычислять условную энтропию одной случайной величины относительно другой.

Условная энтропия относительно определяется следующим соотношением:

$H(X\mid Y) = H(X,Y) - H(Y).$

Примеры

Рассмотрим снова примеры про два игральных кубика.

Пусть соответствует числу на синем кубике, а — числу на красном кубике. Легко проверить, что $H(X\mid Y) = H(X)$ , т.к. знание никак не позволяет получить какую-либо информацию про значение .
Пусть теперь соответствует сумме чисел на кубиках, а — произведению. В этом случае зная произведение чисел на кубиках вы уже что-то знаете про возможные суммы (например, если произведение равно 1, то сумма определяется однозначно), поэтому $H(X\mid Y) < H(X)$ . Условная энтропия позволяет ответить на вопрос, сколько информации приносит величина , если вы уже знаете величину .

Свойства условной энтропии

Условная энтропия обладает следующими свойствами

$H(X\mid Y)\ge 0$ .
$H(X\mid Y) = 0$ $\iff$ однозначно определяется по .

Взаимная информация

Ещё одна информационная величина, которую мы введём в этом разделе — это взаимная информация двух случайных величин.

Информация в о величине (взаимная информация случайных величин и ) определяется следующим соотношением

$I(X:Y) = H(Y) - H(Y\mid X).$

Примеры

И снова обратимся к примерам с двумя игральными кубиками.

Пусть соответствует числу на синем кубике, а — числу на красном кубике. Легко проверить, что , т.к. знание никак не позволяет определить .
Пусть теперь соответствует сумме чисел на кубиках, а — произведению. Взаимная информация позволяет оценить количество общей информации, между двумя случайными величинами (в этом случае ).

Свойства взаимной информации

Выполняются следующие соотношения.

. Т.е. определение взаимной информации симметрично и его можно переписать так:

$I(X:Y) = H(X) - H(X\mid Y).$

Или так: .
$I(X:Y) \le H(X)$ и $I(X:Y) \le H(Y)$ .
.
$I(X:Y)\ge 0$ .

Все информационные величины, которые мы определили к этому моменту можно проиллюстрировать при помощи кругов Эйлера.

Мы пойдём дальше и рассмотрим информационную величину, зависящую от трёх случайных величин.

Пусть , и совместно распределены. Информация в о при условии определяется следующим соотношением:

$I(X:Y\mid Z) = H(Y\mid Z) - H(Y\mid X,Z).$

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

Всё, что мы успели определить можно удобно проиллюстрировать при помощи трёх кругов Эйлера.

Из этой иллюстрации можно вывести все определения и соотношения на информационные величины.

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

Рассмотрим треугольник в пересечении всех трёх кругов H(X) , H(Y) и H(Z) . Этот треугольник соответствуют взаимной информации трёх случайных величин I(X:Y:Z) . Проблема с этой информационной величиной заключается в том, что ей не удаётся придать какой-то "физический" смысл. Более того, в отличие от всех остальных величин на картинке I(X:Y:Z) может быть отрицательной!

Рассмотрим пример трёх случайных величин равномерно распределённых на $\{0,1\}$ . Пусть и будут независимы, а $Z=X\oplus Y$ . Легко проверить, что H(X)=H(Y)=H(Z)=1 . При этом I(X:Y) = I(Y:Z) = I(Z:X) = 0 . В то же время $H(X\mid Y,Z) = H(Y\mid X,Z) = H(Z\mid X,Y) = 0$ . Получается следующая картинка.

Мы знаем, что a+c+d=a+d+b=c+d+b=1 . При этом a+d=c+d=b+d=0 . Получается, что a=b=c=1 , а d=-1 , т.е. для таких случайных величин I(X:Y:Z) = -1 .

Применение энтропии Шеннона: кодирование

В этом разделе мы обсудим, как энтропия Шеннона возникает в теории кодирования. Будем рассматривать коды, которые кодируют каждый символ по отдельности.

Пусть задан алфавит $\Sigma$ . Код — это отображение из $\Sigma$ в $\{0,1\}^*$ . Код называется однозначно декодируемым, если любое сообщение, полученное применением к символам некоторого текста, декодируется однозначно.

Код называется префиксным (prefix-free), если нет двух символов $\alpha$ и $\beta$ таких, что $C(\alpha)$ является префиксом $C(\beta)$ .

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

Теорема [Шеннон]. Для любого однозначно декодируемого кода существует префиксный код с теми же длинами кодов символов.

Таким образом для изучения однозначно декодируемых кодов достаточно рассматривать только префиксные коды.

Задача об оптимальном кодировании.
Дан текст $T = \langle a_1,a_2,\dotsc,a_n\rangle$ . Нужно найти такой код , что

$\sum_{i=1}^n |C(a_i)| \to \min.$

Пусть $\Sigma = \{\alpha_1,\alpha_2,\dotsc,\alpha_k\}$ . Обозначим через f_i частоту, с которой символ $\alpha_i$ встречается в . Тогда выражение выше можно переписать как

$n\sum_{i=1}^k f_i\cdot |C(\alpha_i)| \to \min.$

Следующая теорема могла встречаться вам в курсе алгоритмов.

Теорема [Хаффман]. Код Хаффмана, построенный по $f_1,f_2,\dotsc,f_k$ , является оптимальным префиксным кодом.

Алгоритм Хаффмана по набору частот эффективно строит оптимальный код для задачи оптимального кодирования.

Связь с энтропией

Имеют место две следующие оценки.

Теорема [Шеннон]. Для любого однозначно декодируемого кода выполняется

$\sum_{i=1}^k f_i\cdot|C(\alpha_i)|\ge \sum_{i=1}^n f_i\cdot \log\frac1{f_i}.$

Теорема [Шеннон]. Для любых значений $\{f_1,f_2,\dotsc,f_k\}$ существует префиксный код , такой что

$\sum_{i=1}^n f_i\cdot|C(\alpha_i)|\le \sum_{i=1}^n f_i\cdot \log\frac1{f_i} + 1.$

Рассмотрим случайную величину , равномерно распределённую на символах текста . Получим, что $H(X) = f_i\cdot \log\frac1{f_i}$ . Таким образом, эти две теоремы задают оценку на среднюю длину кода символа при оптимальном кодировании, т.е. и для кодирования Хаффмана.

$H(X) \le \sum_{i=1}^n f_i\cdot|C(\alpha_i)|\le H(X) + 1.$

Следовательно, длину кода Хаффмана текста можно оценить, как

$nH(X) \le |C(T)|\le n(H(X) + 1).$

Применение энтропии Шеннона: шифрования с закрытым ключом

Рассмотрим простейшую схему шифрования с закрытым ключом. Шифрование сообщения с ключом шифрования выполняется при помощи алгоритма шифрования . В результате получается шифрограмма c = E(k, m) . Зная получатель шифрограммы восстанавливает исходное сообщение : m = D(k, c) .

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

Для совершенной схемы шифрования (perfect secrecy) выполняются следующие соотношения:

$H(c\mid k, m) = 0$ , т.е. шифрограмма однозначно определяется по ключу и сообщению.
$H(m\mid k, c) = 0$ , т.е. исходное сообщение однозначно восстанавливается по шифрограмме и ключу.
, т.е. в отсутствие ключа из шифрограммы нельзя получить никакой информации о пересылаемом сообщении.

Теорема [Шеннон]. $H(k)\ge H(m)$ , даже если условие $H(c\mid k,m) = 0$ нарушается (т.е. алгоритм использует случайные биты).

Эта теорема утверждает, что для совершенной схемы шифрования длина ключа должна быть не менее длины сообщения. Другими словами, если вы хотите зашифровать и передать своему знакомому файл размера 1Гб, то для этого вы заранее должны встретиться и обменяться закрытым ключом размера не менее 1Гб. И конечно, этот ключ можно использовать только однажды. Таким образом, самая оптимальная совершенная схема шифрования — это "одноразовый блокнот", в котором длина ключа совпадает с длиной сообщения.

Если же вы используете ключ, который короче пересылаемого сообщения, то шифрограмма раскрывает некоторую информацию о зашифрованном сообщении. Причём количество этой информации можно оценить, как разницу между энтропией сообщения и энтропией ключа. Если вы используете пароль из 10 символов при пересылке файла размера 1Гб, то вы разглашаете примерно 1Гб – 10 байт.

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

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

Доказательство. Нарисуем картинку для трёх случайных величин и отметим то, что нам известно.

$H(m\mid k, c) = 0$ .
, следовательно , а значит .
$I(c:k)\ge 0$ (по свойству взаимной информации), следовательно $w + y\ge 0$ , а значит $y \ge -w = x$ .
$u\ge 0$ . Таким образом,

$H(k) = u + z + w + y \ge u + z + w + x = u + H(m)\ge H(m).$

В доказательстве мы действительно не воспользовались тем, что $H(c\mid k,m) = 0$ .

Алгоритмический подход: колмогоровская сложность

Подход Шеннона хорош для случайных величин, но если мы попробуем применить его к текстам, то выходит, что количество информации в тексте зависит только от частот символов, но не зависит от их порядка. При таком подходе получается, что в "Войне и мире" и в тексте, который получается сортировкой всех знаков в "Войне и мире", содержится одинаковое количество информации. Колмогоров предложил подход, позволяющий измерять количество информации в конкретных объектах (строках), а не в случайных величинах.

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

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

Сложностью K_F(x) строки относительно языка программирования называется длина кратчайшей программы, которая выводит .

Таким образом сложность "Войны и мира" относительноя языка Python — это длина кратчайшей программы на Python, которая печатает текст "Войны и мира". Естественным образом сложность отсортированной версии "Войны и мира" относительно языка Python получится значительно меньше, т.к. её можно предварительно закодировать при помощи RLE.

Сравнение языков программирования

Дальше нам потребуется научиться любимой забаве всех программистов — сравнению языков программирования.

Будем говорить, что язык не хуже языка программирования и обозначать $F\prec G$ , если существует константа c_G такая, что для для всех $x\in\{0,1\}^*$ выполняется $K_F(x) \le K_G(x) + c_G.$

Исходя из этого определения получается, что язык Python не хуже (!) этого вашего Haskell! И я это докажу. В качестве константы $c_\text{Haskell}$ мы возьмём длину реализации интепретатора Haskell на Python. Таким образом, любая программа на Haskell переделывается в программу на Python просто дописыванием к ней интерпретатора Haskell на Python.

Соломонов и Колмогоров пошли дальше и доказали существования оптимального языка программирования.

Теорема [Соломонова-Колмогорова]. Существует способ описания (язык программирования) такой, что для любого другого способа описания выполняется $U\prec F$ .

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

Это приводит нас к следующему определению, предложенному Колмогоровым в 1965 году.

Колмогоровской сложностью строки будем называть её сложность относительно оптимального способа описания и будем обозначать K(x) = K_U(x) .

Важно понимать, что при разных выборах оптимального языка программирования колмогоровская сложность будет отличаться, но только на константу. Для любых двух оптимальных языков программирования F_1 и F_2 выполняется $F_1\prec F_2$ и $F_2\prec F_1$ , т.е. существует такая константа , что $|K_{F_1} - K_{F_2}| \le c.$ Это объясняет, почему в этой науке аддитивные константы принято игнорировать.

При этом для конкретной строки и конкретного выбора колмогоровская сложность определена однозначно.

Свойства колмогоровской сложности

Начнём с простых свойств. Колмогоровская сложность обладает следующими свойствами.

Существует такая, что для всех $K(x)\le |x| + c$ .
Существует такая, что для всех $K(xx)\le K(x) + c$ .

Первое свойство выполняется потому, что мы всегда можем зашить строку в саму программу. Второе свойство верно, т.к. из программы, выводящей строку , легко сделать программу, которая выводит эту строку дважды.

Примеры

Какова колмогоровская сложность "Войны и мира"? Это некоторая константа, зависящая от нашего выбора .
Какова колмогоровская сложность первых знаков числа $\pi$ ? Про число $\pi$ любят расказывать, что там вероятно встречается любая подстрока. Это могло бы свидетельствовать, что в числе $\pi$ заключено очень много информации (все возможные строко). Однако с точки зрения колмогоровской сложности число $\pi$ — это простая последовательность. Ведь для её построения можно написать программу фиксированного размера, в которую достаточно вписать числчтобы она вывела первые цифр числа $\pi$ . Таким образом, колмогоровская сложность не превосходит $\log n + c$ для некоторой константы .

Несжимаемые строки

Важнейшее свойство колмогоровской сложности заключается в существовании сложных (несжимаемых строк). Проверьте себя и попробуйте объяснить, почему не бывает идеальных архиваторов, которые умели бы сжимать любые файлы хотя бы на 1 байт, и при этом позволяли бы однозначно разархивировать результат.

В терминах колмогоровской сложности это можно сформулировать так.

Вопрос. Существует ли такая длина строки , что для любой строки $x\in\{0,1\}^n$ колмогоровская сложность меньше ?

Следующая теорема даёт отрицательный ответ на этот вопрос.

Теорема. Для любого существует $x\in\{0,1\}^n$ такой, что $K(x)\ge n$ .

Доказательство. Битовых строк длины всего 2^n . Число строк сложности меньше не превосходит число программ длины меньше , т.е. таких программ не больше чем

$1+2+\dotsb +2^{n-1} = 2^n - 1 < 2^n.$

Таким образом, для какой-то строки гарантированно не хватит программы.

Верна и более сильная теорема.

Теорема. Существует c > 0 такое, что для $99\%$ слов длины верно

$n - c \le K(x) \le n + c .$

Другими словами, почти все строки длины имеют почти максимальную сложность.

Колмогоровская сложность: вычислимость

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

Теорема. Не существует программы, которая по двоичной записи числа выводит строку , такую что $K(x)\ge n$ .

Эта теорема говорит о том, что не существует программы-генератора, которая умела бы генерировать сложные строки по запросу.

Доказательство. Проведём доказетельство от противного. Пусть такая программа существует и P(n) = x . Тогда с одной стороны сложность не меньше , а с другой стороны мы можем описать при помощи $\log n$ битов и кода программы.

$n\le K(x)\le K_P(x) + c_P \le \lceil\log n\rceil + c_P.$

Это приводит нас к противоречию, т.к. при достаточно больших значениях неизбежно станет больше, чем $\lceil\log n\rceil +c_P$ .

Как следствие мы получаем невычислимость колмогоровской сложности.

Следствие. Отображение $x\to K(x)$ не является вычислимым.

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

Связь с энтропией Шеннона

Теорема. Пусть $x = \langle{011010010\dotso 10110}\rangle$ длины содержит $p\cdot n$ единиц и $(1-p)\cdot n$ нулей, тогда

$K(x)\le \left(p\cdot\log\frac1p + (1-p)\cdot\log\frac{1}{1-p}\right)\cdot n + O(\log n).$

Я надеюсь, что вы уже узнали энтропию Шеннона для случайной величины с двумя значениями с вероятностями и 1-p .

Для колмогоровской сложности можно проделать весь путь, который мы проделали для энтропии Шеннона: определить условную колмогоровскую сложность, сложность пары строк, взаимную информацию и условную взаимную информацию и т.д. При этом формулы будут повторять формулы для энтропии Шеннона с точностью до $O(\log n)$ . Однако это тема для отдельной статьи.

Применение колмогоровской сложности: бесконечность множества простых чисел

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

Теорема. Простых чисел бесконечно много.

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

Доказательство. Проведём доказательство от обратного. Пусть существует всего простых чисел: $p_1,p_2,\dotsc,p_m$ . Тогда любое натуральное раскладывается на степени простых:

$x = p_1^{k_1}\cdot p_2^{k_2}\cdot\dotsm\cdot p_m^{k_m},$

т.е. определяется набором степеней $k_1,k_2,\dotsc,k_m$ . Каждое $k_i\le\log x$ , т.е. задаётся $O(\log \log x)$ битами. Поэтому любое можно задать при помощи $O(\log\log x)$ битов (помним, что — это константа).

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

$n \le K(x) \le O(\log\log x) = O(\log n).$

Противоречие.

Применение колмогоровской сложности: алгоритмическая случайность

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

Пусть в лаборатории живёт обезьянка, которую научили печатать на печатной машинке так, что каждую кнопку она нажимает с одинаковой вероятность. Вам предлагается посмотреть на лист печатного текста и сказать, верите ли вы, что его напечатала эта обезьянка. Вы смотрите на лист и видите, что это первая страница "Гамлета" Шекспира. Поверите ли вы? Очевидно, что нет. Хорошо, а если это не Шекспир, а, скажем, текст детектива Дарьи Донцовой? Скорей всего тоже не поверите. А если просто какой-то набор русских слов? Опять же, очень сомневаюсь, что вы поверите.

Внимание, вопрос. А как объяснить, почему вы не верите? Давайте для простоты считать, что на странице помещается 2000 знаков и всего на машинке есть 80 знаков. Вы можете резонно заметить, что вероятность того, что обезьянка случайным образом породила текст "Гамлета" порядка $1/80^{2000}$ , что астрономически мало. Это верно.

Теперь предположим, что вам показали текст, который вас устроил (он с вашей точки зрения будет похож на "случайный"). Но ведь вероятность его появления тоже будет порядка $1/80^{2000}$ . Как же вы определяете, что один текст выглядит "случайным", а другой — не выглядит?

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

Это обобщается на случай бесконечных последовательностей. Пусть $\bar x = x_1x_2x_3\dotso x_n\dotso$ . Как определить понятие случайной последовательности?

(неформальное определение)
Последовательность случайна по Мартину–Лёфу, если каждый её префикс является несжимаемым.

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

Свойства случайных последовательностей

Почти все последовательности являются случайными по Мартину–Лёфу, а мера неслучайных равна .
Всякая случайная по Мартину-Лёфу последовательность невычислима.
Если $\bar x$ случайная по Мартин-Лёфу, то

$\lim_{n\to\infty} \frac{\text{число единиц в префиксе длины n}}{n} = \frac12.$

Заключение

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

Верещагин Н.К., Щепин Е.В. Информация, кодирование и предсказание. МЦНМО. (нет в свободном доступе, но pdf продаётся за копейки)
В.А. Успенский, А.Х. Шень, Н.К. Верещагин. Колмогоровская сложность и алгоритмическая случайность.
Курс "Введение в теорию информации" А.Е. Ромащенко в Computer Science клубе.

Если вам интересны подобные материалы, подписывайтесь в соцсетях на CS клуб и CS центр, а так же на наши каналы на youtube: CS клуб, CS центр.

Комментарии (15)

kt97679
14.01.2022 00:30
#23937103
-1
Верещагин и Щепин нашлись здесь.

Arvardan
14.01.2022 13:42
#23939295
Так сколько же информации в «Война и мир»?
1. avsmal Автор
  14.01.2022 14:02
  #23939421
  С математической точки зрения это просто константа, зависящая от выбора универсального способа описания.
  
  На практике её можно попытаться оценить сверху при помощи сжатия. Если сжали до 2Мб, то можно считать, что информации там не более 2Мб. Для текстов это неплохо работает, а вот для числа $\pi$ будет работать плохо.
  1. Arvardan
    14.01.2022 15:54
    #23940029
    А есть модели описывающие информативность отдельно взятых слов или фраз?
    Например, слово «стена» несет ведь информацию, как узнать сколько этой информации?
    
    avsmal Автор
    14.01.2022 18:39
    #23940859
    Информативность относительно языка? Слово "стена" не несёт информацию само по себе, а количество передаваемой им информации зависит от контекста. Сомневаюсь, что такие (математические) модели существуют.

Sergey_Kovalenko
14.01.2022 17:44
#23940617
Спасибо за статью. Позвольте сделать несколько замечаний.

Указание префиксного кодирования в объяснении понятия энтропии - без сомнения методологически правильный ход, но... . Спросите у своего читателя, появилось ли у него интуитивное понимание откуда все-таки берется сумма "пэ-логарифм-пэ". Это важно, это то что останется в голове читателя через неделю или месяц спустя. Мне кажется этот момент должен быть центральным в подобной статье.

Второе.

К сожалению понятие "колмогоровской сложности" является относительным по отношению к языку описания и поэтому не несет никакой смысловой нагрузки для оценки "случайности" или "алгоритмичности" (конечных) символьных последовательностей. Для любой сколь угодно случайно выглядещей последовательности сколь угодно большой длины есть язык, в котором ее "колмогоровская сложность" равна нулю. Поэтому у Вас нет никаких логических оснований для вот этого места в тексте.

"Теперь предположим, что вам показали текст, который вас устроил (он с вашей точки зрения будет похож на "случайный"). Но ведь вероятность его появления тоже будет порядка $1/80^{2000}$ . Как же вы определяете, что один текст выглядит "случайным", а другой — не выглядит?

Колмогоровская сложность позволяет дать формальный ответ на этот вопрос. Если у текста отстутствует короткое описание (т.е. в нём нет каких-то закономерностей, которые можно было бы использовать для сжатия), то такую строку можно назвать случайной. И как мы увидели выше почти все строки имеют большую колмогоровскую сложность. Поэтому, когда вы видите строку с закономерностями, т.е. маленькой колмогоровской сложности, то это соответствует очень редкому событию. В противоположность наблюдению строки без закономерностей. Вероятность увидеть строку без закономерностей близка к 1."

Колмогоровскоая сложность - сырое, не проработанное понятие, которое имеет мало пользы и чаще всего (Ваша статья еще один пример в подтверждение) применяется не коректно. Ее вред еще и втом, что своим сущесвование она ложно закрывает еще не решенный современной наукой вопрос об объективной сложности конечных последовательностей и языков описания. Да, как я уже упоминал, для любой сколь угодно с виду сложной запутанной и длинной последовательности можно конструктивно предъявить язык, в котором длинна ее описания равна нулю. Но во в чем тонкость: любое естественное текстовое описание подобного языка скорее всего будет больше длины той последовательности, по которой он построен. Кажется что существования не относительного, а абсолютного пянятие сложности отсюда на лицо, но вот строго логически оформить эти идеи так никому и не удалось.
1. avsmal Автор
  14.01.2022 18:29
  #23940811
  Спасибо за содержательный комментарий.
  
  Я не ставил перед собой задачу объяснить, откуда там в теоремах Шеннона для кодов возникает энтропия. Это почти нереально сделать в рамках такого обзора. При этом я постарался в меру своих возможностей объяснить, почему формула для энтропии именно такая. Не уверен, что это хорошо получилось, но это действильно важный момент, вы совершенно правы.
  
  Про объяснение случайности для конечных объектов вы правы, что нет возможности определить случайность для конечных объектов без фиксации способа описания. Но я здесь и не пытаюсь определить случайность для конечных объектов, а только объясняю человеческую интуцию, которая неплохо позволяет отличать "случайные" и "неслучайные" тексты. Всё, что я хотел сказать, это то, что текст, который для конкретного человека кажется "неслучайным", это обычно текст имеющий какие-то завимости и закономерности с точки зрения конкретного человека, т.е. не текст не максимальной сложности относительно способа описания конкретного человека. В этом случае мы по сути зафиксировали способ описания тем, зафиксировали человека. Так что никакой проблемы тут нет. При этом определение случайной последовательности я даю только для бесконечных последовательностей.
  
  На замечание про сырость и вредность позволю себе не отвечать. Отмечу только, что вопрос о существовании абсолютного понятия сложности не кажется мне таким очевидным.
  1. Sergey_Kovalenko
    14.01.2022 19:40
    #23941153
    Про формулу "пэ-логарифм-пэ" можно попробовать так.
    
    Пусть есть длинная случайная последовательность из нулей и единиц, в которой частота единиц мала (n раз поставлен опыт, который дает "1" с малой вероятностью p и "0" с вероятностью 1-p, близкой к 1). При стандартном написании такая последовательность займет n бит. С другой стороны вы можете ее однозначно задать указав расстояния между началом и первой единицей а затем меду остальными единицами. Всего единиц будет примерно np, а характерное расстояние между ними 1/p. Чтобы записать число величиной потребуется -log(p) бит, таким образо все сообщение закодируется шишровкой примерно в -(np)log(p) бит.
    
    Пусть теперь последовательность состоит из (очень) большого числа числа символов и каждый из них встречается редко. Будем кодирывать ее следующим образом: перечислим расстояния между пермым символом в алфавите, затем без каких либо разделительных знаков расстояние меду вторым ит так далее для всех символов. Поскольку длина исходной последовательности считается известной, мы ее легко можем восстановить по написанной последовательности чисел (когда сумма интервалов очередной раз превышает n, значит мы перешли к ледующему символу). Суммируя числа, выражающие интервальные расстояния между символами как раз и получаем сумму -(np)log(p) бит.
    
    И так, величиной энтропии сообщение (асимптотически!) закодировать можно. Можно ли короче?
    Нет! Доказательство не сложное - оно заключается в подсчете числа всех вохможных расстановок из примерно np_1 символов первого сорта, np_2 второго ... и взятие от этого всего логарифма. Таким образом смысл энтропии вероятностных сообщений - это (усредненная) длинна их эффективного закодированного аналога.
    
    Тонким местом "доказательства" является подмена среднего логарифма логарифмом среднего, но для групп (асимпотически) больших чисел так делать можно, потому что "нелинейность" логарифмической функции на больших аргументах сходит почти на нет. Как доказать формуму, если частоты появления символов не являются бесконечно малыми? - Для любой последовательности вы можете перейти от исходного асфавита к "многобуквенным" сочетаниям символов, и если это сделать правильно, то вероятность наиболее частовстречаемого сочетания окажется меньше любого напередзаданного числа.
    
    avsmal Автор
    15.01.2022 19:56
    #23944453
    Эти рассуждения в другом сеттинге. Речь в разделе про кодирование шла про коды, которые кодируют отдельно каждый символ. То, что вы доказываете в первом абзаце — это оценка колмогоровскую сложность строки длины n с np единицами (вы приводите некоторый способ кодирования, который к посимвольным кодам не имеют никакого отношения). То же самое можно получить, просто указав номер этой последовательности среди всех последовательностей длины n с np единицами. Таких последовательностей: $\binom{n}{np}$ . Для записи такого числа потребуется
    $\log_2 \binom{n}{np} = \log_2 \frac{n!}{(np)!(n(1-p))!}\approx \log_2 \frac{\mathrm{poly}(n)\cdot (n/e)^n}{(np/e)^{np}(n(1-p)/e)^{n(1-p)}}$
    Сокращает на и получаем
    $\log_2 \frac{\mathrm{poly}(n)}{p^{np}\cdot(1-p)^{n(1-p)}} = n\left(p\log_2\frac{1}{p} + (1-p)\log_2\frac{1}{1-p}\right) + O(\log n)$
    В этом случае не нужно ничего предполагать про "характерное расстояние". В вашем рассуждении с этим есть проблема. Если для записи расстояния не хватило $-\log_2p$ символов, то не понятно, что с этим делать. Добавлять разделители?
    
    Идею про отсутствие то, как определять, что начались числа для следующего числа я тоже не понял (когда сумма перевалила за ). Ведь при таком кодировании могут быть неоднозначности: прпоследовательность 2, 1, 1... может разбиваться как (2,1) (1,..., так и как (2) (1,1,.... Либо нужно как-то кодировать количество чисел в самом начале.
    
    Для символов это тоже обоющается (картинка из моего конспекта, переписывать лень)
    
    Ваша нижняя оценка предлагает именно такое рассуждение выше с подсчётом числа последовательностей такого вида. Но она тоже по сути про колмогоровскую сложность, т.к. вы никак не пользуетесь тем, что это именно код определенного вида. Её с соответствующими оговорками и пояснениями можно применить к любому кодированию, но мы потеряем ту точность, что есть в соответствующей теореме Шеннона.
    
    Sergey_Kovalenko
    16.01.2022 01:47
    #23945393
    "Речь в разделе про кодирование шла про коды, которые кодируют отдельно каждый символ. То, что вы доказываете в первом абзаце — это оценка колмогоровскую сложность строки длины n с np единицами (вы приводите некоторый способ кодирования, который к посимвольным кодам не имеют никакого отношения)"
    
    -Ваша статья вроде бы про количество информации, я привел рассуждения как кодировать длинное случайнонабранное сообщение целиком, причем асимптотически оптимально. Да, и нет тут никакой колмогоровской сложности, не вводите себя в заблуждение - у меня конечная, хоть и очень длинная последовательность сиволов. На конечном множестве конечных последовательностей средняя колмогоровская сложность может быть сколь угодно большой - для этого достаточно выбрать язык описания "нужной громодкости". Вы снова пытаетесь применять теоремы о колмогоровской сложности к конечным конструктивным объектам - она в них безсильна.
    
    По поводу неодинаковости длин чисел, выражающих расстояния между символами - да молчаливо предполагался разделитель. Это не портит рассуждений, поскольку
    
    1) частоты предполагаются чрезвычайно малыми, следовательно логарифм и логарифм плюс единица - в относительном мастабе по сути равны (устремляя частоты к нулю можно сделать (математическое ожидание) эти отношения сколь угодно близкими к единице)
    
    2) для достаточно длинных (случайных) последовательностей с не слишком редкими частотами указан способ, как перейти к сочетаниям символов (кстати словарь сочетаний тоже должен быть "беспрефиксным") так, чтобы сочетания уже имели чрезвычайно малую частоту.
    
    Теперь про посимвольное кодирование. Оно ведь тоже не дает идеального объема кодированного сообщения, если частоты символов не выражены особого вида числами. Тем не менее на последовательностях, все символы в которых имеют чрезвычайно малую частоту, посимвольные коды приближаются к энтропийному оптимуму. Опять же работает трюк с переходом от исходного алфавита к (беспрефиксному) словарю символьых сочетаний, но для неслучайных последовательностей нужно делать оговорки.
    
    Применять понятие энтропии к неслучайным последовательностям нужно с большой осторожностью. Одно дело, когда я кладу орех в правый и левый кулак с вероятностью 1/2, другое - у меня в одном из кулаков орех, но вы не знаете в каком именно. Комбинаторная энтропия приписывает всем исходам равные вероятности, но ведь это по сути худший сценарий для сжатия длины сообщения о появившейся последовательности и только поэтому комбинаторная энтропия имеет право быть.
    
    avsmal Автор
    16.01.2022 11:26
    #23946107
    Да, и нет тут никакой колмогоровской сложности, не вводите себя в
    заблуждение - у меня конечная, хоть и очень длинная последовательность сиволов.
    
    Любой алгоритм кодирования битовых последовательностей задаёт верхнюю оценку на колмогороскую сложность с точностью до константы. В тексте поста есть такая теорема о связи энтропии и колмогоровской сложности.
    
    Вы снова пытаетесь применять теоремы о колмогоровской сложности к конечным конструктивным объектам
    
    И какую теорему я применил? )
    
    она в них безсильна.
    
    Не понял этого утверждения. Мы тут рассматриваем не конкретную длину, а асимптотическую оценку. Какая бы не была константа вылезающая из "нужной громодкости" при асимптотических рассуждениях (а тут речь именно про них и вы сами об это пишете) её вкад будет ничтожен.
    
    1) частоты предполагаются чрезвычайно малыми, следовательно логарифм и логарифм плюс единица - в относительном мастабе по сути равны (устремляя частоты к нулю можно сделать (математическое ожидание) эти отношения сколь угодно близкими к единице)
    
    У вас не получится сделать разделитель однобитным: для кодировки пары чисел суммарной длины нужно порядка $\log m + O(\log\log m)$ битов. Соответственно, на каждый разделитель потребуется порядка $O(\log\log(1/p))$ .
    
    но для неслучайных последовательностей нужно делать оговорки. (...)
    Применять понятие энтропии к неслучайным последовательностям
    
    Не очень понимаю, что вы имеете в виду. Как вы сами правильно заметили для конечных последовательностей не получается формально определить понятие случайности. Это, кстати, и к вашему способу кодирования относится. Вы там пишете про "случайнонабранное сообщение", а по сути просто хотите сделать оценку в среднем.
    
    Применять понятие энтропии к неслучайным последовательностям
    
    Я его нигде и не применяю, т.к. энтропия определена не для последовательностей, а для случайных величин.
    
    Sergey_Kovalenko
    16.01.2022 13:08
    #23946465
    Докатились до разбирательства по пунктам, ну что ж, если надо.
    
    Колмогоровская сложность одного объекта - есть понятие зависящие от языка. Подходящим выбором языка она может быть сделана любой, как очень большой, так и равной нулю.
    
    Однако если как-то задана последовательнсть конструктивных объектов, такая что их колмогоровская сложность относительно хотя бы одного алгоритмически полного языка стремится к бесконечности, то их колмогоровская сложность и относительно любого другого алгоритмически полного языка тоже будет стремится к бесконечности, а отношение обоих сложностей будет стремится к 1. Мне кажется это единственный способ корретно приписать смысл вашего утвержения об "колмогоровской сложности (случайных?) последовательностей из np единиц и mp нулей". То есть, мне кажется, что вы должны были предполагать некоторую последовательность сообщений, длинна n которых стремится к бесконечности.
    
    Теперь о чем говорю я.
    
    Если вы мне назовете алфавит и зададите вероятности появления его символов в сообщении, а потом укажите любое "эпсилон" большее нуля, то я смогу назвать вам такое натуральное "эн" и такой способ записи натуральных чисел с разделителителем, что для сообщения любой длинны "эм" большей "эн" описанный мной способ кодирования даст математическое ожидание длины шифровки не более чем в (1+"эпсилон") раз превышающюю энтропию этого сообщения.
    
    Да "эн" в действительности будет непрактично большим, однако я задам способ равномерно по всем длинным сообщениям, а не для какой-то конкретной их последовательности. Например, вы можете генерировать только сообщения какой-то определенной большой длинны "эм" - мое утверждение останется верным, а вот о колмогоровской сложности (ее математическом ожидании) на сообщениях этой конкретной длинны говорить не приходится - все зависит от языка описания. Оно, хоть и не может быть (всреднем) меньше энтропии (это все-таки больше теорема об энтропии: никакое описание в среднем не может быть меньше энтропии), однако подходящим выбором достаточно грамоздкого языка может быть сделано сколь угодно большим.
    
    Да, насчет разделителя я был не точен, но ведь это не меняет сути дела: двойной логарифм (1/p) для достаточно малых p будет пренебрежимо мал по сравнению с "просто" логарифмом (1/p).
    
    0
    
    avsmal Автор
    16.01.2022 14:01
    #23946641
    Колмогоровская сложность одного объекта - есть понятие зависящие от языка. Подходящим выбором языка она может быть сделана любой, как очень большой, так и равной нулю.
    
    Выбор языка не является параметром. В классическом определении мы в качестве языка выбираем совершенно конкретную универсальную машину Тьюринга. Можно выбрать и другой способо, но как было сказано, результат изменится не более, чем на константу.
    
    Однако если как-то задана последовательнсть конструктивных объектов
    
    Что значит "конструктивных" объектов? Все конечные строки конструктивны. Но для конечных строк это утверждение
    
    отношение обоих сложностей будет стремится к 1.
    
    просто не верно. Возьмём произвольную последовательность строк сложности и последовательность нулей (сложность будет $\log n$ ). Отношение сложностей будет в пределе будет бесконечным.
    
    Мне кажется это единственный способ корретно приписать смысл вашего утвержения об "колмогоровской сложности (случайных?) последовательностей из np единиц и mp нулей". То есть, мне кажется, что вы должны были предполагать некоторую последовательность сообщений, длинна n которых стремится к бесконечности.
    
    Про какое утверждение идёт речь? Про теорему в секции "Связь с энтропией Шеннона"? Это теорема. Ничего про случайность там нет. Теорема говорит о том, что колмогоровская сложность любой строки такого вида длины ограничена $nh(p) + O(\log n)$ (константа в O общая для всех строк и не зависит ). Докательство я привёл двумя комментариями выше.
    
    Если вы мне назовете алфавит ... (1+"эпсилон") раз превышающюю энтропию этого сообщения.
    
    Эту часть я понял сразу. Повторюсь, что моё замечание было только по форму утверждения. Вы не ограничиваете способ кодирования, так что вполне достаточно было бы просто записать частоты и назвать номер последовательности в лексикографическом порядке всех последовательностей с такими частотами. Получилось бы такая же оценка.
    
    Да "эн" в действительности будет непрактично большим, однако я задам способ равномерно по всем длинным сообщениям, а не для какой-то конкретной их последовательности. Например, вы можете генерировать только сообщения какой-то определенной большой длинны "эм" - мое утверждение останется верным, а вот о колмогоровской сложности (ее математическом ожидании) на сообщениях этой конкретной длинны говорить не приходится - все зависит от языка описания.
    
    Вы как-то смешиваете ваш способ кодирования и колмогоровскую сложность, что я не могу понять, что вы мне хотите доказать. Вы говорите, что начиная с некоторого средняя длина кода будет $nH(1+\epsilon).$ Но ровно такое же утверждение верно и для колмогоровской сложности. Единственная разница, что , начиная с которого это будет выполняться, сложно задать контретно. Для вычисления придётся запрограммировать генератор такой последовательности на машине Тьюринга.
    
    это все-таки больше теорема об энтропии: никакое описание в среднем не может быть меньше энтропии
    
    В вашей формулировке два понятия: описание и энтропия. Как вы решили, что это формулировка больше об энтропии, чем об описаниях?)
    
    однако подходящим выбором достаточно грамоздкого языка может быть сделано сколь угодно большим.
    
    Ещё раз повторюсь, что способ описания не является параметром.
    
    avsmal Автор
    16.01.2022 14:44
    #23946793
    Да, насчет разделителя я был не точен, но ведь это не меняет сути дела: двойной логарифм (1/p) для достаточно малых p будет пренебрежимо мал по сравнению с "просто" логарифмом (1/p).
    
    И всё же тут нужно быть аккуратным. Если в вашем способе кодирования вы добавляете разделитель на каждый символ, то в сумме получится $O(n\log\log n)$ (то, что "характерная" длина промежутка равна 1/p, не исключает возможности, что будет много промежутков порядка ). А добавка такого размера уже может быть сравнима . Энтропия может быть очень маленькой и поэтому добавлять что-то на каждый символ — не самая хорошая идея. Вполне возможно, что если аккуратно всё посчитать и применить неравенство Йенсена, то всё сойдётся, но мне не кажется это совсем уж очевидным.