<table><caption>Рис. 6.1. Происхождение трёх видов сложности.</caption><thead><tr><th rowspan="2" style="text-align: center;">описания</th><th colspan="2" style="text-align: center;">объекты</th></tr><tr><th style="text-align: center;">N<sub>⊥</sub></th><th style="text-align: center;">Σ</th></tr></thead><tbody><tr><th style="text-align: center;">N<sub>⊥</sub></th><td style="text-align: center;">KS</td><td style="text-align: center;">?</td></tr><tr><th style="text-align: center;">Σ</th><td style="text-align: center;">KP</td><td style="text-align: center;">KM</td></tr></tbody></table>

время это обозначение стало применяться в ином смысле, для так называемой distinguishing complexity, так что мы будем его избегать). Такой вид сложности был определён Д. Лавлэндом в [90].

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

Таким образом, машине такого типа соответствует отображение множества всех двоичных слов (которые можно отождествить с натуральными числами, входящими в $N_⊥$) в множество $\Sigma$ конечных и бесконечных последовательностей. Если $M$ — такая машина, то сложностью $KR_M(x)$ слова $x$ относительно способа описания $M$ называется длина кратчайшего слова $y$, для которого $M(y)$ (выходная последовательность машины, получившей $y$ на входе) начинается на $x$.

**192** Проверьте, что среди всех машин указанного вида имеется оптимальная машина $M$, для которой $KR_M$ минимально с точностью до $O(1)$.

**193** Дайте определение вычислимых непрерывных отображений $N_⊥ \to \Sigma$. Чем они отличаются от рассмотренных нами машин? Почему это различие несущественно для определения сложности? [Указание: значение на $⊥$ может быть непустым.]

Таким образом, пустая клеточка в нашей таблице заполняется (см. рис. 6.2).

<table><caption>Рис. 6.2. Четыре вида сложности.</caption><thead><tr><th rowspan="2" style="text-align: center;">описания</th><th colspan="2" style="text-align: center;">объекты</th></tr><tr><th style="text-align: center;">N<sub>⊥</sub></th><th style="text-align: center;">Σ</th></tr></thead><tbody><tr><th style="text-align: center;">N<sub>⊥</sub></th><td style="text-align: center;">KS</td><td style="text-align: center;">KR</td></tr><tr><th style="text-align: center;">Σ</th><td style="text-align: center;">KP</td><td style="text-align: center;">KM</td></tr></tbody></table>

В следующей теореме перечислены основные свойства сложности разрешения.

**Теорема 127.** (а) Если слово $x$ является началом слова $y$, то $KR(x) \le KR(y)$.
(б) Сложность начальных отрезков последовательности $ω \in \Omega$ (неубывающая с ростом длины отрезка) ограничена тогда и только тогда, когда последовательность $ω$ вычислима. (Назвав предел сложности начальных отрезков сложностью разрешения последовательности $ω$, можно сказать, что сложность разрешения бесконечной последовательности конечна тогда и только тогда, когда последовательность вычислима.)

(в) $KR(x) \le KS(x) + O(1)$ для любого слова х.

(г) $KR(x) \le KM(x) + O(1)$ для любого слова х.

(д) $KM(x) \le KR(x) + O(\log KR(x))$ для любого слова х.

(е) $KS(x) | I(x)) \le KR(x) + O(1)$ для любого слова х.

(ë) Если $f: \Sigma \to \Sigma$ — вычислимое непрерывное отображение, то
$KR(f(x)) \le KR(x) + O(1)$ (константа зависит от $f$, но не от $x$).

(ж) Если $f: \Sigma \to \mathbb{N}_-$ — вычислимое непрерывное отображение, то
$KS(f(x)) \le KR(x) + O(1)$ (константа зависит от $f$, но не от $x$).

(з) Если $f: \mathbb{N}_- \to \Sigma$ — вычислимое непрерывное отображение, то
$KR(f(x)) \le KS(x) + O(1)$ (константа зависит от $f$, но не от $x$).

(и) Любой набор попарно несравнимых слов (ни одно не является началом другого), все из которых имеют сложность разрешения меньше $n$, содержит менее $2^n$ слов.

(й) Функция $KR$ перечислима сверху.

(к) Функция $KR$ является минимальной (с точностью до константы) функцией, обладающей двумя предыдущими свойствами: если (i) функция $K$ перечислима сверху и (ii) любое множество несравнимых слов, у которого $K(x) < n$ для всех элементов, содержит $O(2^n)$ слов, то $KR(x) \le K(x) + O(1)$.

(л) $KR(x) \le KA(x) + O(1)$ для всех слов х.

◀ (а) Непосредственно следует из определения (описание слова есть описание любого его начала).

(б) Пусть последовательность $ω$ вычислима. Возьмём в качестве способа описания машину, которая независимо от входа печатает $ω$ на выходе бит за битом. Сложность начальных отрезков последовательности $ω$ при таком способе равна нулю (пустой вход является их описанием), и потому при оптимальном способе описания ограничена. Обратно, если сложность начальных отрезков ограничена, то некоторое описание годится для бесконечного числа начальных отрезков, и потому последовательность вычислима.

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

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

(д) Пусть $R: \mathbb{N} \to \Sigma$ — оптимальный способ описания при определении сложности разрешения. Рассмотрим вычислимое отображение $\tilde{R}: \Sigma \to \Sigma$, для которого
$\hat{R}(\hat{x}u) = R(x)$, где $\hat{x}$ — самоограниченный код слова $x$ (скажем, само $x$, предварённое двоичной записью его длины с удвоенными битами и разделителем 01), а $u$ — любое слово (последнее необходимо для монотонности).

(е) Пусть снова $R: \mathbb{N} \to \Sigma$ — оптимальный способ описания для сложности разрешения. Определим способ условного описания $S$, положив $S(y, n)$ равным $n$ первым битам последовательности $R(y)$ (если $n$ больше длины последовательности, то $S(y, n)$ не определено).

(ё) Рассмотрим новый способ описания, являющийся композицией оптимального способа описания и отображения $f$, и сравним его с оптимальным.

(ж) Рассмотрим композицию оптимального способа описания для сложности разрешения и отображения $f$ как способ описания для простой колмогоровской сложности.

(з) Рассмотрим композицию оптимального способа описания для простой колмогоровской сложности и отображения $f$ как способ описания для сложности разрешения.

(и) Попарно несравнимые слова не могут иметь общего описания (в этом случае они были бы началами описываемой им последовательности). Если сложности попарно несравнимых слов меньше $n$, то их описания — различные слова длины меньше $n$, а таких слов меньше $2^n$.

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

(к) Это — первое содержательное утверждение теоремы (до сих пор были лишь простые вариации на знакомые темы).

Пусть дана функция $K$, обладающая двумя указанными свойствами. Увеличивая её на константу, можно считать без ограничения общности, что существует не более $2^n$ несравнимых слов $x$, для которых $K(x) < n$.

Мы построим способ описания, при котором всякое слово $x$ с $K(x) < n$ будет иметь описание длины ровно $n$. Это делается параллельно и независимо для каждого $n$. А именно, наблюдая за уменьшающимися верхними оценками для $K$, мы пополняем список слов $x$, для которых $K(x) < n$. Можно считать, что в каждый момент этот список конечен и с течением времени растёт. Рассмотрим поддерево двоичного дерева, состоящее из слов этого списка и всех их начал. Со временем это поддерево растёт. В каждый момент у него не более $2^n$ листьев, поскольку листья являются несравнимыми словами $x$, для которых $K(x) < n$. Каждому листу мы присвоим метку, которая является словом длины $n$. При добавлении нового слова к дереву это новое слово либо продолжает какой-то из листьев (который перестаёт быть листом), либо ответвляется от дерева во внутренней вершине. В первом случае новое слово становится листом, который наследует метку прежнего листа. Во втором случае для нового листа мы выделяем новое слово в качестве метки (что всегда возможно, так как листьев меньше $2^n$).

Фиксируем метку и посмотрим, что происходит с листьями с этой меткой. Вначале таких листьев нет (метка не использована). Возможно, так и останется навсегда (до этой метки дело не дойдёт), но если дойдёт, то метка будет сдвигаться по дереву вверх (каждое следующее её положение будет продолжением предыдущего.
го), и потому ей соответствует некоторая конечная или бесконечная ветвь в дереве (последовательность нулей и единиц). Возникает отображение слов длины $n$ в $\Sigma$ (при этом меткам, до которых дело не дойдёт, соответствуют последовательности нулевой длины).

Объединив эти отображения при всех $n$, получим способ описания, при котором (для любого $n$) сложность всех слов $x$ с $K(x) < n$ не превосходит $n$, что и требовалось.

(л) Если $x_i$ — несравнимые двоичные слова, то $\sum 2^{-KA(x_i)} \le 1$ (поскольку $2^{-KA(x_i)}$ есть априорная вероятность множества $\Sigma_{x_i}$, а эти множества не пересекаются). Поэтому несравнимых слов, у которых $KA(x_i) < n$, не может быть больше $2^n$, и осталось воспользоваться предыдущим утверждением теоремы. ►

**194** Показайте, что сложность разрешения можно определять так: для каждой вычислимой функции $S$ двух аргументов (первый — слово, второй — натуральное число; значения — нули и единицы) определим $KR_S(x)$ для любого слова $x = x_0 \dots x_{n-1}$ как наименьшую длину слова $y$, при котором $S(y, i) = x_i$ при всех $i = 0, 1, \dots, n-1$, после чего среди всех функций $S$ выберем оптимальную.

**195** Показайте, что сложность разрешения слова $x$ равна (с точностью до $O(1)$) минимуму $KS(p)$ по всем программам $p$ (данного языка программирования, скажем, паскаля), которые не имеют входа и печатают на выходе слово $x$ или его продолжение.

**196** Показайте, что если в предыдущей задаче вместо $KS$ взять $KR$, то получится верхняя оценка для монотонной сложности. Показайте, что она не является $O(1)$-точной. [Указание. Монотонная сложность всех слов длины $n$ не превосходит $n$. Печатающие их (или их продолжения) программы должны быть все различны, и слов префиксной сложности не более $n$ не хватит.]

### 6.2. Сравнение сложностей

Сложности, входящие в рассмотренную нами таблицу (с двумя вариантами для пространств описаний и двумя вариантами для описываемых объектов), можно изобразить в виде ромба, стороны которого соответствуют неравенствам между сложностями (с точностью до $O(1)$), как показано на рис. 6.3.

<figure><img src="image_18.png" /><figcaption>Рис. 6.3. Неравенства между сложностями.</figcaption></figure>
Если мы хотим избежать упоминания топологических понятий и определения вычислимых непрерывных отображений для разных пространств (хотя они здесь по существу, как учит теория абстрактных типов данных в смысле Скотта и близкая к ней теория $f_0$-пространств Ершова, см. [152]), то для построения указанных четырёх сложностей по единой схеме можно обойтись следующей упрощённой конструкцией [168].

На множестве $Ξ = \mathbb{B}^*$ всех двоичных слов рассмотрим два бинарных отношения: равенство слов (=) и сравнимость слов (наличие общего продолжения, обозначение $\asymp$). Пусть $\alpha$ и $\beta$ — любые из этих двух отношений (так что всего есть четыре варианта).

Будем говорить, что множество $S \subset \Xi \times \Xi$ является $\alpha$-$\beta$-корректным, если следующее условие выполнено для всех слов $x_1, x_2, y_1, y_2$:

$$ (x_1, y_1) \in S, (x_2, y_2) \in S, x_1 \alpha x_2 \Rightarrow y_1 \beta y_2. $$

Например, $\text{=}-\text{=}$-корректные отношения — это униформные множества, то есть графики функций.

**[197]** (а) Покажите, как по $\asymp$-корректному отношению построить непрерывное отображение $\Sigma \to \mathbb{N}_\perp$.

(б) Покажите, как по $\asymp$-$\asymp$-корректному отношению построить непрерывное отображение $\Sigma \to \Sigma$.

(в) Покажите, как по $\text{=}$-$\text{=}$-корректному отношению построить непрерывное отображение $\mathbb{N}_\perp \to \Sigma$.

Будем называть $\alpha$-$\beta$-способом описания перечислимое $\alpha$-$\beta$-корректное отношение на $\Xi \times \Xi$. Для всякого способа описания $S$ определим сложность как функцию, сопоставляющую с каждым словом $x$ длину его кратчайшего описания, то есть длину кратчайшего слова $y$, для которого $\langle y, x \rangle$ принадлежит $S$.

**Теорема 128.** Для каждой из четырёх комбинаций $\alpha, \beta \in \{=, \asymp\}$ существует оптимальный $\alpha$-$\beta$-способ описания, и соответствующая сложность совпадает (с точностью до $O(1)$) с одной из четырёх сложностей $KS, KP, KM, KR$.

◀ В каждом из случаев по $\alpha$-$\beta$-корректному способу описания легко строится вычислимое отображение соответствующих пространств (см. задачу 197), задающее ту же самую сложность, и наоборот. ▶

Таким образом, в таблице сложностей можно поменять названия строк и столбцов (см. рис. 6.4).

**[198]** Покажите, как определить для пары слов:

(а) монотонную сложность, рассматривая в качестве декомпозессоров вычислимые непрерывные отображения $\Sigma \to \Sigma \times \Sigma$. (Такие отображения можно отождествить с парами вычислимых отображений $\Sigma \to \Sigma$.)

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

(в) сложность разрешения, рассматривая вычислимые непрерывные отображения $\mathbb{N}_\perp \to \Sigma \times \Sigma$.
<table><caption>Рис. 6.4. α-β-сложности.</caption><thead><tr><th rowspan="2" scope="col">описания</th><th colspan="2" scope="colgroup">объекты</th></tr><tr><th scope="col">=</th><th scope="col">~</th></tr></thead><tbody><tr><th scope="row">=</th><td>KS</td><td>KR</td></tr><tr><th scope="row">~</th><td>KP</td><td>KM</td></tr></tbody></table>

Аналогичные определения возможны и для троек, четвёрок и т. д.

**199** Показите, что сложность разрешения пары $\langle x, y \rangle$ не превышает $l(x) + l(y)$. [Указание. Слово z можно считать описанием пары $\langle z, z^R \rangle$, где $z^R$ — слово z, прочитанное с конца.]

Удивительным образом такое же свойство верно для троек слов [57] и даже для кортежей большей длины (это следует из результатов Нидеррайтера [126]). А для монотонной сложности пар аналогичное свойство неверно, как показал Павел Карпович [57]: значение $KM(x, y)$ может превосходить $l(x) + l(y)$ на величину порядка $\log n$ для слов длины $n$. Отсюда следует, в частности, что для пар априорная сложность отличается от монотонной на величину того же порядка.

Другая схема (восходящая к Левину, см. [77]) классификации сложностей состоит в описании их как наименьших перечислимых сверху функций, удовлетворяющих некоторым ограничениям. Соберём соответствующие ограничения (на перечисливую сверху функцию K):

* число различных слов $x$, при которых $K(x) < n$, есть $O(2^n)$ (простая сложность $KS$, теорема 8, с. 29);

* ряд $\sum_x 2^{-K(x)}$ сходится (префиксная сложность $KP$, теорема 62, с. 116);

* число различных несравнимых слов $x$, при которых $K(x) < n$, есть $O(2^n)$ (сложность разрешения $KR$, теорема 127, с. 219);

* $\sum_x 2^{-K(x_i)} \le 1$ для любого множества попарно несравнимых слов $x_i$ (априорная сложность $KA$, теорема 80, с. 145).

В этой схеме фигурируют те же четыре сложности, за одним исключением: вместо монотонной сложности фигурирует априорная. (Для случая префиксной сложности такого расхождения нет, поскольку она совпадает с логарифмом максимальной перечислимой снизу полумеры на $\mathbb{N}$.)

Поэтому при объединении этих двух схем у нас получается уже не ромб, а пятиугольник (рис. 6.5).

Напомним основные результаты о сравнении сложностей в этом пятиугольнике. Прежде всего, все сложности отличаются не более чем на $O(\log n)$ для слов длины $n$. В самом деле, $KP(x) \le KS(x) + O(\log KS(x))$ (теорема 65, с. 118). С другой стороны, $KS(x) \le KS(x|l(x)) + KS(l(x)) + O(\log n) \le KR(x) + O(\log n)$. По-
<figure><img src="image_19.png" /><figcaption>Рис. 6.5. Пять сложностей.</figcaption></figure>

этому две наиболее различающиеся сложности в этом пятиугольнике (верхняя и нижняя) отличаются не более чем на $O(\log n)$ для слов длины $n$.

Более сложная ситуация возникает, если мы хотим ограничить разность между двумя сложностями константой, умноженной на логарифм одной из них. Это можно сделать для неравенств вдоль линий, идущих в «северо-восточном» направлении:

$$KP(x) \leq KS(x) + O(\log KS(x))$$

(см. теорему 65) и

$$KM(x) \leq KR(x) + O(\log KR(x))$$

(теорема 127). Тем более это верно, если заменить $KM$ на $KA$ (как мы уже упоминали в задаче 140, с, 165). Для «северо-западных» неравенств это сделать нельзя: $KM$ и $KR$ ограничены для начальных отрезков вычислимых последовательностей (в частности, для слов из одних нулей), а $KS$ и $KP$ — нет (для слова из $n$ нулей сложность равна сложности $n$, и достигает $\log n$ при некоторых $n$). Мы уже обсуждали это в теореме 86, где отмечали, что разница между $KP$ и $KM$ может быть обоих знаков порядка $\log n$ для некоторых слов длины $n$ (при бесконечно многоих $n$). Теорема Гача-Дея показывает, что разница между $KM$ и $KA$ не ограничена и для некоторых слов достигает примерно $\log \log n$ или больше (теорема 87).

Отметим также, что из теоремы 73 (с. 130) следует, что разность между $KP(x)$ и $KS(x)$ не только не ограничена, но и стремится к бесконечности. Некоторые другие оценки разности между сложностями $KS(x)$ и $KP(x)$ (а также другими парами сложностей) приведены в работе [168].

### 6.3. Условные сложности

Мы уже упоминали несколько видов условной сложности (когда определяется сложность одного слова относительно другого). В разделе 2.2 мы определяли условную сложность $KS(x|y)$ как длину кратчайшего описания $p$ слова $x$ при известном $y$, то есть минимальную длину слова $p$, для которого $S(p,y) = x$. Здесь $S$ — способ описания; способами описания были произвольные частичные вычислимые функции двух аргументов.
В разделе 4.7 определялась условная префиксная сложность $KP(x|y)$. При этом требовалось, чтобы способ описания был префиксно корректным относительно $p$: это значит, что если слово $p$ является описанием данного $x$ при данном $y$, то любое продолжение слова $p$ также является таким описанием.

Наконец, при доказательстве теоремы 93 мы упоминали условную монотонную сложность $KM(x|y)$. При её определении в качестве способа описания берётся вычислимое семейство вычислимых непрерывных отображений $D_y: \Sigma \to \Sigma$, индексированное словами $y$. Вычислимость семейства понимается в том смысле, что множество троек $(y, u, v)$, для которых $v \preceq D_y(u)$, перечислимо.

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

Во всех этих определениях условия рассматриваются как законченные слова, никак не связанные друг с другом: если $p$ является описанием $x$ при известном $y$, для другого слова $y$ то же самое $p$ может быть описанием совершенно другого $x$ (даже если новое $y$ отличается от старого добавлением одного бита).

Другими словами, способ описания (скажем, для условной префиксной сложности) мы считаем вычислимым отображением $D: \Sigma \times \mathbb{N} \to \mathbb{N}_+$, при этом первый член пары $(p, y) \in \Sigma \times \mathbb{N}$ считается описанием (требуется монотонность по $p$), а второй условием (монотонность по $y$ не требуется).

Если рассматривать условия как вершины дерева и требовать монотонности по этому аргументу, получатся четыре других вида условной сложности, которые, однако, практически не рассматривались (работа [29] — одно из редких исключений).

Таким образом, всего возникает 8 видов условных сложностей (каждый из трёх компонентов — условия, описания и объекты — можно понимать двумя способами). Технически проще всего определить эти условные сложности так. Пусть $\alpha, \beta, \gamma \in \{=, \asymp\}$ (см. раздел 6.2). Определим $(\alpha, \beta)|\gamma$-способ описания как перечислимое множество $S$ троек слов $(p, x, y)$, удовлетворяющее следующему требованию:

$$ (p_1, x_1, y_1) \in S, (p_2, x_2, y_2) \in S, p_1 \alpha p_2, y_1 \gamma y_2 \Rightarrow x_1 \beta x_2. $$

Далее сложность $KS(x|y)$ определяется как наименьшая длина слова $p$, при котором $(p, x, y) \in S$.

**Теорема 129.** В каждом из восьми случаев среди способов описания существует оптимальный (для которого сложность минимальна в этом классе способов описания с точностью до $O(1)$).

**200** Проведите аккуратное доказательство этой теоремы (по существу ничем не отличающееся от случая обычной или префиксной условной сложности).

Соответствующую оптимальному $(\alpha, \beta)|\gamma$-способу описания сложность можно обозначить $K_{(\alpha,\beta)|\gamma}$. При таком обозначении $KP(x|y)$ есть $K_{(\asymp,=)|=}$, а $KS(x|y)$ есть $K_{(=,=)|=}$.

**201** Покажите, что от замены $= \to \asymp$ в качестве $\gamma$ условная сложность может только возрасти. [Указание: на способ описания накладываются дополнительные ограничения, поэтому их становится меньше. По этой же причине обычная сложность не превосходит префиксной.]
Было бы интересно исследовать эти сложности подробнее; видимо, этим никто не занимался. Насколько, скажем, велико возрастание, отмеченное в этой задаче?

Вот пример утверждения, включающего в себя рассмотренные только что модификации условных сложностей:

**202** Докажите, что $KS(x) \leqslant K_{(=,=)}(x|y) + KR(y) + O(\log KR(y))$.

Опишем ещё один подход к определению условной сложности, восходящий к колмогоровской интерпретации логических связок как операций над задачами [61]. Условную сложность $x$ при известном $y$ можно интерпретировать как сложность задачи «указать $x$ по данному у»; в свою очередь, эту задачу можно считать множеством всех функций, переводящих $y$ в $x$ (любая такая функция считается «решением» этой задачи).

Это можно уточнить, например, так. Рассмотрим пространство $\mathcal{F}$, элементами которого являются все частичные функции с натуральными аргументами и значениями. На этом множестве определим порядок: $f_1 \leqslant f_2$, если функция $f_2$ продолжает функцию $f_1$. Конечными элементами этого множества будем считать функции с конечной областью определения. Для каждого конечного элемента $f$ рассмотрим конус над ним, то есть множество всех его продолжений (конечных и бесконечных). Непрерывное отображение $T: \mathbb{N}_{\perp} \to \mathcal{F}$ будем называть вычислимым, если перечислимо множество пар $(a, f)$, где $a \in \mathbb{N}_{\perp}$, $f$ — конечный элемент $\mathcal{F}$ и $f \leqslant T(a)$. Такие вычислимые отображения будем считать способами описания (функций). Для каждой функции $f$ определим сложность (относительно данного способа описания $T$) как минимальную длину слова (точнее, логарифм числа, ведь мы отождествляем числа и двоичные слова) $a$, для которого $f \leqslant T(a)$.

**203** Докажите, что при таком определении существует оптимальный способ описания и что сложность функции $y \mapsto x$ (область определения состоит из единственного слова $y$, значение на котором равно $x$) равна $KS(x|y) + O(1)$.

В этом же духе можно интерпретировать и все восемь указанных выше условных сложностей (для пространств $Y, X \in \{\mathbb{N}_{\perp}, \Sigma\}$ определив пространство функций ($Y \to X$), а затем в качестве способов описания рассматривая вычислимые отображения пространства описаний $P \in \{\mathbb{N}_{\perp}, \Sigma\}$ в пространство ($Y \to X$). При этом удобно использовать домены Скотта или $f_0$-пространства в смысле Ершова (подробности см. в [152]).

Несколько другая интерпретация условной сложности как сложности задачи «получить $x$ из $y$», не использующая вычислимость в пространствах функций, рассмотрена в главе 13.

Родственное (хотя и несколько другое) понятие сложности функции было рассмотрено Шнорром [145, 147]. Напомним, что в теории рекурсии нумерацией называется некоторое отображение $\nu$, сопоставляющее с каждым натуральным числом $n$ некоторую функцию $\nu_n$ (частичную) из $\mathbb{N}$ в $\mathbb{N}$. Нумерация $\nu$ называется вычислимой, если частичная функция двух аргументов $(n, x) \mapsto \nu_n(x)$ является вычислимой, и гёделевой, или (в русскоязычной литературе) главной, если для любой другой вычислимой нумерации $\mu$ существует вычислимая всюду определённая функция $h$, сводящая $\mu$ к $\nu$ в том смысле, что $\mu_n = \nu_h(n)$ при всех $n$. (В частности, среди $\nu_n$ должны встречаться все вычислимые функции.)
Следуя Шнорру, усилим это условие и дополнительно потребуем, чтобы $h(n) = O(n)$ (длина слова $h(n)$ превосходила бы длину $n$ не более чем на константу, если отождествить натуральные числа с двоичными словами). Если для всякой вычислимой нумерации $\mu$ существует функция $h$ с таким свойством, то нумерацию $\nu$ будем называть оптимальной.

**Теорема 130.** *Оптимальные нумерации существуют.*

◀ Выберем какой-нибудь естественный язык программирования двухместных функций и будем считать слово $ûv$ номером функции, которая получится, если в функции с программой *u* фиксировать первый аргумент равным *v*. (Здесь $û$ — самоограниченное описание слова *u*, получаемое, например, удвоением каждого бита и приписыванием 01 в конец.) ▶

Шнорр (см. [145, 147]) предложил определить сложность вычислимой функции как логарифм её номера в оптимальной нумерации. (При этом минимальная сложность функции, отображающей $x$ в $y$, также оказывается равной $KS(y|x)$.) Он показал также, что любые две оптимальные нумерации $\nu_1$ и $\nu_2$ отличаются вычислимой перестановкой номеров $\pi$, увеличивающей объём в ту и другую сторону не более чем на $O(1)$. (Это значит, что $\nu_1(n) = \nu_2(\pi(n))$ при всех $n$, причём $\pi(n) = O(n)$ и $\pi^{-1}(n) = O(n)$.)

### 6.4. Сложности и оракулы

#### 6.4.1. Сложность с оракулом

В теории вычислимых функций хорошо известен следующий метод, называющий релятивизацией: берётся какое-то определение или утверждение, касающееся класса вычислимых функций, и всюду в нём вычислимые функции заменяются на функции, вычислимые относительно некоторого оракула. В качестве такого оракула берётся некоторая всюду определённая функция $\alpha$, аргументами и значениями которой являются натуральные числа или двоичные слова (обычно характеристическая функция некоторого множества $A$). Алгоритмам разрешается в качестве элементарного действия обращаться к «внешней процедуре», возвращающей значение $\alpha(n)$ для переданного ей значения параметра $n$. (Для характеристической функции множества $A$ это означает, что про любое натуральное число можно узнать, принадлежит ли оно множеству $A$ или нет.) Если сама функция $\alpha$ не вычислима (множество $A$ неразрешимо), то класс вычислимых функций расширяется; вычисляемые такими алгоритмами функции называются $\alpha$-вычислимыми.

После этого практически все понятия и теоремы теории вычислимых функций переносятся на $\alpha$-вычислимые функции. Скажем, можно говорить об $\alpha$-перечислимых множествах, или об $\alpha$-вычислимых действительных числах, или (подходя ближе к колмогоровской сложности) об $\alpha$-перечислимых снизу полумерах. При этом (практически все) теоремы остаются верными и в таком «релятивизованном» варианте.

В частности, для любого множества $A$ можно определить понятие колмогоровской сложности, релятивизованной относительно множества $A$, рассматривая
способы описания (декомпрессоры) с оракулом А. Это можно сделать и для обычной, и для префиксной, и для всех других видов рассмотренных нами сложностей (условных и безусловных). Обычно использование оракула отмечают верхним индексом, так что, скажем, $KP^A(x)$ есть префиксная сложность слова $x$ с оракулом А.

На самом деле мы делаем даже несколько большее: мы не просто для фиксированного оракула А определяем релятивизованную сложность (с точностью до $O(1)$), а определяем (с этой точностью) некоторую функцию двух аргументов: $\langle x, A \rangle \mapsto K^A(x)$ (где $K$ — один из четырёх видов сложности).

**204** Проверьте, что это действительно можно сделать, и что получающиеся сложности являются пределами условных сложностей, описанных в разделе 6.3:

$$KP^A(x) = K_{\le,=}(x) = \lim_{n \to \infty} K_{(\le,=|\le)}(x|A_n),$$

где $A_n$ — начальный отрезок длины $n$ характеристикической функции множества А. (Аналогично и для других видов сложностей.)

Заметим, что релятивизованные сложности (с точностью $O(1)$) не больше обычных (алгоритм может не обращаться к оракулу, потому среди А-способов описания есть и обычные способы описания).

При некоторых А функция сложности с оракулом А может существенно уменьшаться (по сравнению со сложностью без оракула). Например, рассмотрим в качестве оракула А универсальное перечислимое неразрешимое множество. (Такой оракул обычно обозначают $0'$.) Другими словами, $0'$-оракул есть внешний оракул для проблемы остановки: ему можно послать для анализа программу (без оракула), и он скажет, завершится её работа или нет. Имея такой оракул, можно для каждого слова $x$ найти его кратчайшее описание (поскольку мы можем с помощью оракула проверять, закончит декомпрессор работу на данном слове или нет). Поэтому функция KS является $0'$-вычислимой (это же относится к функции KP, условным сложностям и т.п.), а список всех слов сложности меньше $n$, который без оракула имел сложность $n + O(1)$, а также числа $B(n)$ и $BB(n)$ (см. раздел 1.2) теперь имеют $0'$-сложность $O(\log n)$.

С другой стороны, большинство слов длины $n$ имеют $0'$-сложность $n - O(1)$, и потому для них $0'$-сложность близка к обычной (нерелятивизованной).

**205** Покажите, что если для некоторого множества А его использование в качестве оракула не меняет функции KS, то есть если $KS(x) = KS^A(x)$, то А разрешимо. Аналогичное утверждение верно для KM, KR, KA. [Указание. Вычислимость последовательности можно характеризовать в терминах скорости роста сложности начальных отрезков, см. задачу 49, с. 53.]

Как мы уже отмечали, для префиксной сложности аналогичное утверждение неверно: существуют KP-низкие множества (в английских текстах их назвывают K-low, поскольку префиксная сложность обычно обозначается буквой K), добавление которых в качестве оракула не меняет KP. Этот важный и сложный результат был получен сравнительно недавно (см. [127, 37]).
### 6.4.2. Сложность при условии большей чисел

Определим новый вид условной сложности: сложность числа (слова $x$) относительно множества $A$. Эта сложность, говоря неформально, есть сложность такой задачи: «получить $x$, если задан некоторый элемент множества $A$» (неизвестно какой). Такую сложность можно определить несколькими эквивалентными способами.

Пусть фиксирован некоторый разумный язык программирования. (Формально говоря, нужно, чтобы соответствующая ему нумерация была главной, то есть чтобы была возможна эффективная трансляция программ с других языков [175].) Определим условную сложность объекта (слова, натурального числа) $x$ относительно множества объектов $A$ как минимальную (простую колмогоровскую) сложность программы, переводящей любой из элементов множества $A$ в $x$. (В более общем виде это определение рассматривается в главе 13.)

Возможность трансляции гарантирует, что это определение корректно, то есть что сложность (с точностью до $O(1)$) не зависит от выбора главной нумерации.

Важно отличать эту сложность от сложности $x$ относительно конечного множества $A$, заданного списком своих элементов (известен не список элементов $A$, а некоторый его элемент — неважно какой). Мы будем обозначать только что определённую сложность $KS(x \parallel A)$, сохраняя обозначение $KS(x|A)$ для сложности $x$ относительно конечного множества $A$, заданного списком своих элементов.

Другой (эквивалентный) способ определения $KS(x \parallel A)$ состоит в следующем. Пусть $D$ — вычислимая частичная функция двух аргументов (декомпрессор), $x$ — двоичное слово, а $A$ — множество двоичных слов. Определим $KS_D(x \parallel A)$ как наименьшую длину такого слова $p$, что $D(p,y) = x$ для всех $y \in A$.

**206** Докажите, что среди всех вычислимых частичных функций имеется оптимальная функция (для которой функция $KS_D$ минимальна с точностью до $O(1)$). Докажите, что для оптимальной функции $D$ величина $KS_D(x \parallel A)$ совпадает с ранее определённой сложностью $KS(x \parallel A)$ с точностью до $O(1)$.

Для случая одноэлементного множества $A = \{a\}$ обе величины $KS(x|A)$ и $KS(x \parallel A)$ совпадают (с точностью до $O(1)$) с обычной условной сложностью $KS(x|a)$; см. задачу 28.

Рассмотрим в качестве $A$ множество всех чисел, больших некоторого числа $n$. (Как всегда, числа мы отождествляем со словами.) Сложность $x$ относительно этого множества будем обозначать $KS(x \parallel \ge n)$. Очевидно, эта сложность не превосходит $KS(x)$ и убывает с возрастанием $n$ (вообще $KS(x \parallel A)$ очевидным образом убывает при уменьшении множества $A$, превращаясь в $O(1)$ для пустого $A$). Поэтому у неё есть некоторый предел при $n \to \infty$.

**Теорема 131.**

$$ \lim_{n \to \infty} KS(x \parallel \ge n) = KS^{0'}(x) + O(1). $$

◀ Пусть указанный предел равен $k$. Тогда существует программа $p$ сложности $k$, переводящая все достаточно большие числа в $x$. Имея дополнительно оракул $0'$, можно использовать эту программу как описание объекта $x$. Именно, надо путём перебора найти такие $N$ и $y$, что программа $p$ не переводит никакое $n \ge N$ ни
в какой объект, отличный от у. Это можно сделать с помощью оракула, поскольку выделенное свойство пары $N$, у имеет перечислимое дополнение. При этом из нашего предположения следует, что $y = x$. Поэтому

$$KS^{0'}(x) \le \lim_{n \to \infty} KS(x \parallel \ge n) + O(1).$$

Напротив, пусть имеется описание у объекта $x$ относительно $0'$-оптимального способа описания, имеющее длину $k$. Рассмотрим следующую программу: получив некоторое $N$, сделать $N$ шагов порождения универсального перечислимого множества $0'$ и затем использовать полученное множество в качестве оракула, применяя оптимальный способ описания к у. Эта программа эффективно строится по у и потому её сложность не превосходит $KS(y) + O(1) \le l(y) + O(1) = k + O(1)$. С другой стороны, для достаточно больших $N$ эта программа порождает $x$ (поскольку при вычислении значения оптимального способа описания на у используется лишь конечное число запросов к оракулу, при достаточно большом $N$ все эти запросы получат правильные ответы даже и при замене настоящего оракула на его $N$-шаговое приближение). ▶

Оказывается, что аналогичное утверждение верно, если заменить $KS(x \parallel \ge n)$ на величину $\sup_{m \ge n} KS(x|m)$. Сразу же ясно, что

$$\sup_{m \ge n} KS(x|m) \le KS(x \parallel \ge n),$$

поскольку оптимальная программа в правой части годится и для любого $m$ из левой. Удивительным образом оказывается, что это уменьшение не меняет предела при $n \to \infty$:

**Теорема 132.**

$$\limsup_{n \to \infty} KS(x|n) = KS^{0'}(x) + O(1).$$

◀ Нужно доказать, что если для данного слова $x$ выполнено свойство

сложность $KS(x|n)$ меньше $k$ при всех достаточно больших $n$,

то $0'$-сложность $x$ не превосходит $k + O(1)$. Сложность здесь — в отличие от предыдущей теоремы — в том, что существующие по предположению программы (длины меньше $k$) для разных $n$ могут быть разными.

Заметим, что слов $x$ с указанным свойством (для данного $k$) меньше $2^k$: если бы их было больше, то при достаточно больших $n$ на них не хватило бы программ длины меньше $k$.

Поэтому было бы достаточно доказать, что множество таких слов является $0'$-перечислимым и соответствующий алгоритм перечисления эффективно строится по $k$ (другими словами, что функция $x \mapsto \limsup KS(x|n)$ является $0'$-перечисли-мой сверху). Однако естественное описание этого множества,

$$\exists N (\forall n \ge N) [KS(x|n) < k],$$
доказывает лишь его принадлежность к $\Sigma_3$ (условие в квадратных скобках перечислимо, и есть два дополнительных квантора), так что мы поступим иным образом.

Заметим, что нам не нужна $0'$-перечислимость этого множества, нам достаточно включить его в некоторое $0'$-перечислимое множество, содержащее менее $2^k$ элементов с данным $k$. Это делается следующим образом.

Рассмотрим двумерное перечислимое множество пар $(n, x)$, для которых выполнено неравенство $KS(x|n) < k$. Это множество «тонкое» в том смысле, что все вертикальные сечения этого множества содержат менее $2^k$ элементов.

Пусть выбрана некоторая точка $(n, x)$. Попробуем добавить горизонтальный луч, выходящий из этой точки, к нашему множеству (добавить в него все пары $(m, x)$ при $m \ge n$). При этом множество может перестать быть тонким, а может и не перестать, и эти два случая можно различить с помощью $0'$-оракула: нарушение тонкости есть перечислимое свойство (найдётся сечение, в котором обнаружатся $2^k$ различных элементов — вместе с добавленным).

Будем выполнять эту операцию по очереди для всех лучей (для всех пар $(n, x)$) в некотором порядке. (При этом, если какой-то луч удалось добавить без нарушения тонкости, то в дальнейшем его элементы учитываются наравне с элементами исходного множества при добавлении следующих лучей.) Этот процесс является $0'$-вычислимым, и потому $x$-координаты всех добавленных лучей образуют $0'$-перечислимое множество.

Оно содержит менее $2^k$ элементов (поскольку добавление лучей не нарушает тонкости), а также содержит все $x$, у которых $\limsup K(x|n) < k$. В самом деле, для такого $x$ найдётся луч, изначально лежавший в множестве, и потому его добавление заведомо возможно. ►

(Это доказательство является упрощённым вариантом рассуждения из [169]. См. также аналогичные рассуждения в [9].)

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

### Теорема 133.

$$ \limsup_{n \to \infty} KP(x|n) = KP^{0'}(x) + O(1). $$

◀ Переходя к априорным вероятностям (условным и безусловным), эту теорему можно переписать так:

$$ \liminf_{n \to \infty} m(x|n) = m^{0'}(x) $$

(с точностью до ограниченного и отделённого от нуля множителя).

Покажем сначала, что левая часть не меньше правой (точнее, меньше не более чем в $O(1)$ раз). В самом деле, рассмотрим машину с оракулом $0'$, выход которой имеет распределение $m^{0'}$. Теперь будем для каждого $n$ запускать эту машину с конечной частью оракула, соответствующей $n$ шагам его перечисления. При этом вероятность получить $x$ на выходе может и увеличиться и уменьшиться, но нижний предел этих вероятностей не меньше соответствующей вероятности для настоящего оракула. В самом деле, вероятность получить $x$ для настоящего оракула есть мера
открытого множества (объединения конусов), и каждый из этих конусов использует
лишь конечное число вопросов к оракулу и на некотором шаге появится.

Докажем теперь обратное неравенство. Тут ситуация очень похожа на доказательство теоремы 132. Имеется перечислимое снизу семейство полумер; при каком $n$ функция $x \mapsto m(x|n)$ является полумерой (сумма ряда по $x$ не больше 1). Отсюда легко следует, что для нижнего предела

$$m'(x) = \liminf_{n \to \infty} m(x|n)$$

сумма ряда $\sum_x m'(x)$ также не превышает единицы. Если бы функция $m'$ оказалась $0'$-перечислимой снизу, то всё было бы доказано — но запись этого свойства в виде

$$r < \liminf_{n \to \infty} m(x|n) \Leftrightarrow (\exists q > r) \exists N (\forall n > N) [q < m(x|n)]$$

содержит лишний квантор (свойство в квадратных скобках перечислимо, а не решимо). Но, как и в предыдущем доказательстве, нам достаточно построить $0'$-перечислимую мажоранту.

Для этого будем рассматривать тройки $\langle N, x, \varepsilon \rangle$ (где $\varepsilon$ — положительное рациональное число) и будем пытаться увеличивать функцию $m(\cdot|\cdot)$ до $\varepsilon$ на луче, состоящем из пар $\langle n, x \rangle$ при данном $x$ и при всех $n \ge N$, если это не нарушит свойство полумеры (для каждого $n$ сумма по всем $x$ не превышает 1).

Как и раньше, возможность такого добавления можно проверить с помощью $0'$-оракула (поскольку невозможность есть перечислимое свойство). Будем производить такие добавления для всех троек (учитывая уже сделанные увеличения при определении возможности следующих). Оставляя от каждой добавленной тройки $x$ и $\varepsilon$ (то есть рассматривая для каждого $x$ точную верхнюю грань всех $\varepsilon$, с которыми это $x$ добавлено), получим $0'$-перечислимую снизу полумеру, мажорирующую $m'$ (ведь если $m'$ где-то больше $\varepsilon$, то на некотором луче функция уже больше $\varepsilon$ и тем самым добавление заведомо возможно). ►

Чтобы сформулировать аналогичное утверждение для $KP(x \parallel \ge n)$, надо прежде всего определить эту сложность (префиксную сложность с условием, являющимся множеством). Тут есть несколько возможностей, и не вполне ясно, какую из них следует считать «правильной».

Можно пытаться определить $KP(x \parallel A)$ как минимальную префиксную сложность программы, которая даёт $x$ на любом входе из множества $A$. Однако, как показывает задача 109 (с. 121) тогда для одноэлементных множеств $A = \{a\}$ не получится $KP(x|a)$ и потому, видимо, такое определение надо считать неудачным.

Можно действовать по аналогии с задачей 206. Рассмотрим произвольную вычислимую функцию $\langle p, x \rangle \mapsto D(p, x)$ префиксно корректную по первому аргументу (при фиксированном втором). Для любого $x$ и любого множества $A$ определим $KP_D(k \parallel A)$ как наименьшую длину такого $p$, что $f(p, n) = k$ для всех $n \in A$. Разница с определением для обычной сложности состоит в том, что мы требуем от декомпрессора префиксной корректности по первому аргументу. Среди таких декомпрессоров есть оптимальный (в этом классе), и соответствующую функцию $KP_D$ можно принять за определение префиксной сложности с множеством в качестве условия.
**207** Показите, что та же самая сложность (с точностью до $O(1)$) получится, если в качестве декомпозиторов рассматривать вычислимые непрерывные отображения $\Sigma \to \mathbb{F}$ (пространства конечных и бесконечных последовательностей нулей и единиц в пространство частичных функций из $\mathbb{N}$ в $\mathbb{N}$) и рассматривать кратчайшее слово $p$, образ которого есть некоторая частичная функция, равная $x$ на всех элементах $A$.

Можно определять префиксную сложность относительно множества, используя беспрефиксные функции вместо префиксно корректных. В классе вычислимых беспрефиксных по первому аргументу функций существует функция, для которой относительная сложность $KP_f(x \parallel A)$ минимальна. Таким образом мы получаем определение $KP'(x \parallel A)$, аналогичное условной сложности $KP'(k \parallel n)$ и совпадающее с ней при $A = \{n\}$ (с точностью до аддитивной константы).

Наконец, можно определить априорную вероятность $m(x \parallel A)$, взяв вероятностную машину с входом $u$ и изучая меру множества всех последовательностей $\omega$, которые (будучи использованы в качестве случайных битов) заставляют машину напечатать $x$ при любом входе $y \in A$. Здесь также существует оптимальная машина (при которой эта вероятность наибольшая) и для одноэлементных множеств $A$ это определение сводится к ранее известному.

Как и раньше, для всех $k$, $A$ выполнены неравенства

$$-\log m(k \parallel A) \le KP(k \parallel A) + O(1) \le KP'(k \parallel A) + O(1).$$

Однако неравенств здесь уже не получается, по крайней мере во втором неравенстве; это установила Елена Калинина [56]; про первое неравенство авторы не знают. Тем не менее можно отметить, что все эти величины превышают

$$-\log \inf_{x \in A} m(k|x) = \sup_{x \in A} KP(k|x),$$

и потому любая из них может быть использована в теореме, аналогичной теореме 131. В частности, для (видимо, наиболее естественной) величины $KP(k \parallel A)$, определённой выше с помощью префиксно корректных функций, получаем такое утверждение:

**Теорема 134.**

$$\lim_{n \to \infty} KP(k \parallel \ge n) = KP^{0'}(k) + O(1).$$

**208** Докажите, что величины $KP(k \parallel A)$, $KP'(k \parallel A)$ и $KS(k \parallel A)$ отличаются друг от друга не более, чем на линейную функцию от логарифма наименьшей из них, то есть, $O(\log KS(k \parallel A))$.

Авторам неизвестно, ограничена ли сверху $KS(k \parallel A)$ линейной или хотя бы вычислимой функцией от $-\log m(k \parallel A)$ (хотя бы для конечных или даже двухэлементных множеств).

Здесь уместно заметить, что существует и другой тип задач, для которого логарифм априорной вероятности может сильно отличаться от сложности. Речь идет о задачах перечисления множеств, рассмотренных в работе Соловея [162]. Будем рассматривать не останавливаемые алгоритмы со входом, являющимся конечным
двоичным словом, и печатающие на выходе через запятую конечный или бесконечный список слов (между печатью двух соседних слов списка может быть сколь большой временной интервал, и для любого слова списка следующее за ним слово может быть вообще не напечатано никогда, однако, начав печатать какое-то слово, алгоритм обязательно должен его закончить, поставив запятую в конце). Для каждого такого алгоритма А и всякого множества слов S можно определить сложность S относительно А, как наименьшую длину входа, на котором А печатает список элементов S в произвольном порядке:

$$ KE_A(S) = \min\{l(p) \mid M(p) \text{ печатает список } S\}. $$

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

С другой стороны можно рассмотреть вероятностные алгоритмы перечисления множеств. Так называется любой вероятностный неостанавливающийся алгоритм без входа, который на своей выходной ленте печатает через запятую некоторый конечный или бесконечный список слов. Для любого такого алгоритма А можно рассмотреть вероятность того, что алгоритм напечатает данное множество S. Эту вероятность мы будем обозначать через $m_A(S)$. Обычными рассуждениями нетрудно показать, что среди всех алгоритмов А существует такой, для которого функция $m_A(S)$ максимальна с точностью до мультиликативной константы. Для этого алгоритма величина $m_A(S)$ называется априорной вероятностью перечисления множества S и обозначается через $m(S)$. Априорная вероятность положительна только для перечислимых множеств (это утверждение называется теоремой Де Леу – Мура – Шеннона – Шапиро [74]).

**209** Докажите теорему Де Леу – Мура – Шеннона – Шапиро. [Указание. Если подмножество $\Omega$ имеет положительную меру, то в некотором интервале доля этого множества больше половины.]

Из определений следует, что $KE(S) \le \log m(S) + O(1)$. Однако неизвестно, верно ли обратное неравенство, хотя бы с логарифмической точностью: $-\log m(S) \le KE(S) + O(\log KE(S))$? Известно всего лишь [162], что обратное неравенство верно с мультиликативной константой 3 перед сложностью:

$$ - \log m(S) \le 3 \cdot KE(S) + O(\log KE(S)), $$

и для конечных множеств S константу 3 можно заменить на 2 (см. [170]).

### 6.4.3. Пределы частот и априорная вероятность, релятивизованная $0'$

В заключение приведём результат из статьи [114], связывающий частоты показания в вычислимых последовательностях с релятивизованной относительно $0'$ префиксной сложностью. (См. также упрощённое изложение в [9].)

Пусть $f(0), f(1), \dots$ — вычислимая последовательность натуральных чисел. Для данных натуральных $n$ и $k$ подсчитаем, сколько раз встречается $k$ среди
$f(0), \dots, f(n-1)$, и поделим результат на $n$. Полученное частное можно назвать частотой $k$ среди первых $n$ членов последовательности.

Теперь при фиксированном $k$ рассмотрим нижний предел частоты $k$ среди первых $n$ членов при $n \to \infty$, который будем называть нижней частотой числа $k$ в последовательности $f$.

Пусть $p_k$ — нижняя частота числа $k$ в данной последовательности. Легко выдеть, что $\sum_k p_k \le 1$. В самом деле, если какая-то конечная частичная сумма этого ряда была бы больше 1, то сумма соответствующих нижних пределов была бы больше 1, и потому сумма достаточно далёких допредельных значений превзошла бы 1, что невозможно (сумма частот в любом начальном отрезке не больше 1).

Кроме того, выполнено следующее утверждение (для любой вычислимой последовательности $f$ и нижних частот $p_k$ появления в ней различных чисел $k$):

**Теорема 135.** Функция $k \mapsto p_k$ 0'-перечислима снизу.

Определение перечислимой снизу функции мы давали в разделе 4.1; сейчас мы рассматриваем релятивизированный относительно 0' вариант этого понятия.

◀ В самом деле, утверждение $r < p_k$ (где $r$ — рациональное число) можно записать так:

> существует такое рациональное $p > r$ и такое $N$, что частота появления $k$ в любом начальном отрезке последовательности длины больше $N$ превосходит $p$.

Набранное курсивом свойство является коперечислимым (имеет перечислимое дополнение): если оно неверно, то это можно обнаружить, предъявив соответствующий начальный отрезок. Поэтому это свойство 0'-разрешимо (применим оракул к алгоритму поиска этого отрезка). А потому свойство $r < p_k$ в целом 0'-перечислимо. ▶

По существу мы тут используем такой общий факт:

**210** Пусть $r_n$ — вычислимая последовательность рациональных чисел. Положите, что число $\lim_{n \to \infty} r_n$ является 0'-перечислимым снизу и соответствующий 0'-алгоритм можно построить, зная алгоритм для $r_n$.

Отметим кстати, что верно и обратное утверждение:

**211** Всякое 0'-перечислимое снизу действительное число является нижним пределом вычислимой последовательности рациональных чисел. [Указание. Это число является точной верхней гранью 0'-вычислимой последовательности рациональных чисел $r_n$, каждое из которых является предельным значением стабилизирующейся последовательности $r_{n,k}$. Положим $s_k$ равным максимуму из чисел $r_{0,k}, \dots, r_{t-1,k}$, где $t$ — минимальное число, для которого $r_{t,k} \ne r_{t,k-1}$.]

Оказывается, что для подходящей последовательности $f$ функция $k \mapsto p_k$ является максимальной 0'-перечислимой снизу полумерой. Это вытекает из следующего утверждения:

**Теорема 136.** Для всякой 0'-перечислимой снизу последовательности неотрицательных действительных чисел $q_0, q_1, \dots$ с $\sum_i q_i \le 1$ найдётся вычислимая
последовательность $f(0), f(1), \dots$, нижняя частота появления любого нату-
рального $k$ в которой не меньше $q_k$.

Это позволяет дать эквивалентное определение $0'$-релятивизованной префикс-
ной сложности числа $k$ как минус логарифма нижней частоты числа $k$ в опти-
мальной последовательности $f$ (той, в которой нижние частоты максимальны с
точностью до $O(1)$-множителя).

◀ Перечислимость снизу означает, что множество пар $\langle r, k \rangle$, где $r$ — рациональное число, меньше $q_k$, перечислимо (с оракулом $O'$). Как известно из теории вычислимых функций (см., например, [175]), $O'$-перечислимые множества составляют класс $\Sigma_2$, и потому можно найти разрешимое свойство $R$, для которого

$$r < q_k \Leftrightarrow \exists u \forall v R(r, k, u, v).$$

Нам будет удобно иметь дело с несколько другим представлением, а именно, мы выберем вычислимую всюду определённую функцию $\langle r, k, n \rangle \mapsto S(r, k, n)$ со значениями $0$ и $1$, для которой $r < q_k$ тогда и только тогда, когда в последовательности $S(r, k, 0)$, $S(r, k, 1)$... конечное число нулей. Последовательность $S(r, k, 0)$, $S(r, k, 1)$... можно построить так: ищем последовательно для каждого из $u = 0, 1, 2, \dots$ значение $v$, при котором $R(r, k, u, v)$ ложно, одновременно дописывая в последовательность единицы; как только такое значение обнаруживается, перемежаем единицы нулём. Конечность числа нулей означает, что для некоторого $u$ такого $v$ не найдётся, то есть что $r < q_k$.

Удобна такая метафора: время от времени для некоторых пар $\langle r, k \rangle$ появляется запрос «хочу, чтобы $q_k$ было больше $r$», которые время от времени могут «сбрасываться», одновременно возобновляясь. При этом для пар $\langle r, k \rangle$, у которых $r < q_k$, число сбросов конечно (и возобновлённый в какой-то момент запрос уже не будет сброшен), а для остальных пар ($r \ge q_k$) запросы сбрасываются бесконечно много раз. (Моменты сбросов запросов соответствуют нулям в последовательности $S$.) Весь этот процесс вычислим и в каждый момент имеется лишь конечное число запросов (так нам удобно считать, а роли это не играет, поскольку конечность числа нулей в последовательности не зависит от её начального отрезка).

Напомним, что нам нужна вычислимая последовательность $f(0), f(1), \dots$, в которой нижняя частота появления числа $k$ не меньше $q_k$.

Для этого достаточно представить исходную $O'$-перечислимую снизу полумеру как нижний предел вычислимой последовательности мер с рациональными значениями, то есть построить вычислимую двумерную таблицу из рациональных чисел

$$ \begin{array}{ccccc} p_0^0 & p_1^0 & p_2^0 & \dots \\ p_0^1 & p_1^1 & p_2^1 & \dots \\ p_0^2 & p_1^2 & p_2^2 & \dots \\ \multicolumn{5}{c}{\text{...................}} \end{array} $$

с такими свойствами: в каждой строке лишь конечное число ненулевых элементов, в сумме равных единице, а нижний предел в $k$- столбце не меньше $q_k$. В самом деле, пусть дана такая таблица. Можно считать, что все числа в $i$-й строке кратны $1/i$
(заменив их на приближения, что не повлияет на предел). Теперь строим последовательность $f$ так: вначале некоторое время руководствуемся первой строкой как таблицей частот, затем переходим ко второй строке и пользуемся ей гораздо большее время (так, чтобы вклад первой строки в частоты стал мал), затем переходим к третьей строке и следуем ей ещё дольше (чтобы забить вклад первой и второй строки) и так далее.

Итак, осталось построить таблицу с таким свойством: если запрос «сделать $q_k$ больше $r$» с некоторого момента не сбрасывается, то в $k$-м столбце нижний предел не меньше $q_k$. Это делается так: строя $n$-ю строку таблицы в момент времени $n$, мы удовлетворяем все имеющиеся к данному моменту запросы (для всех $k$) в порядке их «стажа» (сколько времени этот запрос уже не сброшен), увеличивая соответствующие $p_k$ до соответствующего $r$ пока это возможно (пока сумма не превошла единицу; можно считать, что запросов достаточно много и это рано или поздно служится, в этот момент мы обрезаем последний запрос, делая сумму равной единице, и завершаем построение $n$-й строки).

Почему это гарантирует выполнение условия на нижний предел? Предположим, что $r < q_k$ на самом деле. Тогда запрос «сделать $q_k$ больше $r$» в некоторый момент появится и уже более никогда не будет сброшен. Посмотрим на запросы, которые появились до него. Некоторые из них будут сброшены, а некоторые — так и не будут. Дождёмся такого момента, когда все эти сбросы произойдут. Тогда среди запросов с большим стажем останутся лишь такие пары $r', k'$, которые никогда не будут сброшены, и потому для них $r' < q_k'$ и потому сумма всех таких $r'$ вместе с нашим $r$ меньше единицы. Поэтому запросы с большим стажем не помешают удовлетворить наш запрос, что и требовалось доказать. ►

**212** Покажите, что можно построить вычислимую последовательность, в которой нижние пределы частот в точности равны $q_k$. [Указание. Надо скомбинировать приведённую конструкцию с решением задачи 211.]

Ещё один результат из упомянутой статьи Мучника [114]:

**213** Докажите, что теорема 136 останется верной, если разрешить рассматривать частичные вычислимые функции $f$ из $N$ в $N$ как «последовательности с пробелами»: для любой вычислимой частичной функции $f$ из $N$ в $N$ существует вычислимая последовательность $g(0), g(1), ...$ (без пробелов) с теми же или большими нижними частотами: нижняя частота любого числа $k$ в $g$ не меньше его нижней частоты в $f(0), f(1), ...$ (определяемой как нижний предел количества появлений числа $k$ среди $f(0), ..., f(N-1)$, делённого на $N$). [Указание [9]. Для каждого $N$ частоты появления в начальном отрезке длины $N$ образуют перечислимую снизу полумеру (вместо вычислимой меры для всюду определённых последовательностей); конструкция из доказательства теоремы 133 позволяет мажорировать нижний предел $0'$-перечислимой снизу полумерой, от которой уже можно перейти ко всюду определённой функции. ]
# 7. Шенноновская энтропия и колмогоровская сложность

## 7.1. Шенноновская энтропия

Пусть нам нужно закодировать буквы некоторого алфавита А, состоящего из $k$ букв $a_1, \dots, a_k$, двоичными словами (наподобие азбуки Морзе, только вместо точки и тире используются нуль и единица). Пусть буква $a_i$ кодируется некоторым словом $c_i$. Естественно требовать, чтобы все слова $c_i$ были различны. Но этого мало, если записывать коды подряд. Скажем, если алфавит состоит из букв А, Б и В, имеющих коды 0, 1 и 01, то мы не сможем отличить слово АБАБ от слова АБВ: в обоих случаях будет последовательность 0101. (В азбуке Морзе, кстати, такой проблемы нет, поскольку между отдельными буквами делается перерыв — больший, чем между точками и тире внутри буквы.) Поэтому надо отдельно позаботиться об однозначности декодирования.

Другой предмет заботы при построении кода — его экономность. Полезно выбирать кодовые слова $c_i$ по возможности более короткими (насколько это возможно при сохранении однозначности декодирования). Более того, если не удаётся сделать короткими все кодовые слова, разумно в первую очередь позаботиться о наиболее часто встречающихся буквах. (Это обстоятельство учитывалось и при составлении азбуки Морзе.)

### 7.1.1. Коды

Перейдём к формальным определениям. Кодом для алфавита А, состоящего из $k$ букв $a_1, \dots, a_k$, называется набор из $k$ двоичных слов $c_1, \dots, c_k$. Они называют-ся кодовыми словами данного кода; слово $c_i$ называется кодом буквы $a_i$; всякое слово в алфавите А кодируется двоичным словом, получаемым соединением кодов соответствующих букв.

Будем называть код *инъективным*, если коды различных букв различны, и *однозначно* декодируемым, если коды любых двух различных слов различны. Код называется *префиксным*, если ни одно из кодовых слов (соответствующих буквам алфавита А) не является началом (префиксом) другого. (Это название стало традиционным, хотя более логичное — беспрефиксный код — также используется.)

**Теорема 137.** Всякий префиксный код является однозначно декодируемым.

◀ Первое кодовое слово (код первой буквы) отщепляется однозначно (в силу префиксности), затем отщепляется код второй буквы и т. п. ▶
**214** Покажите, что не всякий однозначно декодируемый код является префиксным. [Указание. Он может быть, например, «суффиксным».]

**215** Укажите явно взаимно однозначное соответствие между множеством бесконечных последовательностей цифр 0, 1, 2 и множеством бесконечных последовательностей нулей и единиц. [Указание. Используйте префиксный код $0 \mapsto 00$, $1 \mapsto 01$, $2 \mapsto 1$.]

**216** Пусть слова $c_1, \dots, c_k$ и $d_1, \dots, d_l$ образуют префиксный код (по отдельности). Покажите, что kl слова $c_i d_j$ (приписываем одно слово к другому без разделителя) также образуют префиксный код.

Чтобы сравнивать коды по их экономности, нужно фиксировать частоты букв. Пусть даны неотрицательные числа $p_1, \dots, p_k$, в сумме равные единице; число $p_i$ будем называть частотой (или вероятностью) буквы $a_i$. Для каждого кода $c_1, \dots, c_k$ (для букв $a_1, \dots, a_k$) определим среднюю длину кода как сумму

$$ \sum_i p_i l(c_i). $$

Возникает задача: для данных $p_1, \dots, p_k$ найти код по возможности меньшей средней длины (в том или ином классе кодов).

**217** Как найти минимальный (с точки зрения средней длины) инъективный код для данного набора $p_1, \dots, p_k$? [Указание: все буквы надо упорядочить по убыванию частот, а все двоичные слова — в порядке возрастания длин, начиная с пустого.]

### 7.1.2. Определение шенкононовской энтропии

Что можно сказать о минимально возможной длине префиксного кода для данных частот $p_1, \dots, p_k$? Для ответа на этот вопрос полезна шенкононовская энтропия. Она определяется для данных $p_1, \dots, p_k$ (неотрицательных и в сумме равных единице) как величина

$$ H = p_1(-\log p_1) + p_2(-\log p_2) + \dots + p_k(-\log p_k) $$

(при $p = 0$ мы полагаем $p \log p = 0$, доопределяя тем самым функцию $p \mapsto p \log p$ по непрерывности).

Мотивировка этой формулы такова: буква $a_i$ появляется с частотой $p_i$, а каждое её появление несёт $-\log p_i$ битов информации; в среднем получается $H$ битов на букву. Нужно только объяснить, почему мы считаем, что появление буквы с вероятностью $p$ несёт $-\log p$ битов информации. Это можно сделать так. Пусть задумано одно из $2^n$ равновозможных чисел. Чтобы его отгадать, надо задать $n$ вопросов (тепа да/нет), каждый из которых даёт 1 бит информации. Значит, вероятность $1/2^n$ соответствует $n$ битам информации в событии.

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

Пусть фиксированы неотрицательные числа $p_1, \dots, p_k$, в сумме равные единице.
**Теорема 138.** (а) Для любого префиксного кода с кодовыми словами $c_1, \dots, c_k$ выполняется неравенство

$$ \sum_i p_i l(c_i) \ge H $$

(средняя длина любого кода не меньше энтропии).

(б) Существует префиксный код, для которого

$$ \sum_i p_i l(c_i) < H + 1. $$

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

**Лемма** (неравенство Крафта). Пусть фиксированы целые неотрицательные числа $n_1, \dots, n_k$ и требуется найти двоичные слова $c_1, \dots, c_k$ указанных длин ($l(c_i) = n_i$), причём так, чтобы ни одно из этих слов не было началом другого. Это возможно тогда и только тогда, когда $\sum_i 2^{-n_i} \le 1$.

Это утверждение нам уже встречалось, см. леммы в доказательстве теорем 56 (с. 107) и 58 (с. 108). В одну сторону: если ни одно из слов $c_i$ не является началом другого, то соответствующие интервалы длин $2^{-n_i}$ не пересекаются, и потому сумма их длин не превосходит единицы. (В других терминах: случайная последовательность нулей и единиц начинается на $c_i$ с вероятностью $2^{-n_i}$; эти события несовместны, так как слова несравнимы, и потому сумма вероятностей не превосходит единицы.)

В обратную сторону можно воспользоваться даже более простым способом, чем при доказательстве теоремы 58, поскольку число слов конечно их длины заранее известны. Нужно просто выкладывать соответствующие интервалы длин $2^{-n_i}$ слева направо на отрезке $[0, 1]$, причём делать это в порядке убывания длин. Тогда каждый интервал будет правильно «выровнен» и ему будет соответствовать двоичное слово длины $n_i$.

Вернёмся к доказательству теоремы. Можно считать, что все $p_i$ положительны, поскольку нулевые $p_i$ не дают вклада ни в среднюю длину кода, ни в энтропию. В пункте (а) нам надо доказать, что если $n_i$ — неотрицательные целые числа и $\sum_i 2^{-n_i} \le 1$, то сумма $\sum_i p_i n_i$ не меньше шенкононовской энтропии $H$. Это удобнее доказывать сразу для произвольных $n_i$ (не обязательно целых) и перейдя к другим координатам. Обозначим через $q_i$ величину $2^{-n_i}$. В этих координатах утверждение таково: если $q_i > 0$ и $\sum q_i \le 1$, то

$$ \sum_i p_i (-\log q_i) \ge \sum_i p_i (-\log p_i). $$

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

$$ \sum_i p_i \log \frac{q_i}{p_i} $$
и в силу выпуклости логарифма (взвешенная сумма логарифмов не превосходит логарифма взвешенной суммы: $\sum p_i \log u_i \le \log(\sum_i p_i u_i)$; это верно для любых положительных $u_i$) не превосходит

$$ \log\left(\sum_i p_i \frac{q_i}{p_i}\right) = \log\left(\sum q_i\right) \le \log 1 = 0. $$

Утверждение (а) доказано.

Отметим кстати, что неотрицательную величину

$$ \sum_i p_i \log \frac{p_i}{q_i} $$

называют **расстоянием Кульбака – Лейблера** (Kullback – Leibler distance) между распределениями вероятностей $p_i$ и $q_i$ (при этом предполагается, что $\sum q_i = 1$), хотя это «расстояние» и не симметрично. Выпускность логарифма (отрицательность второй производной) гарантирует, что расстояние Кульбака – Лейблера неотрицательно и обращается в нуль, лишь если $p_i = q_i$ при всех $i$.

Чтобы доказать утверждение (б), рассмотрим числа $n_i = \lceil -\log_2 p_i \rceil$ (где $\lceil u \rceil$ обозначает наименьшее целое число, большее или равное $u$). Тогда

$$ \frac{p_i}{2} < 2^{-n_i} \le p_i. $$

Неравенство $2^{-n_i} \le p_i$ гарантирует, что выполнены условия леммы (и потому можно найти кодовые слова соответствующих длин). Неравенство $p_i/2 < 2^{-n_i}$ означает, что $n_i$ превосходит $(-\log p_i)$ менее чем на 1, что сохраняется и после усреднения: средняя длина кода $(\sum p_i n_i)$ превосходит $H = \sum p_i (-\log p_i)$ менее чем на 1. ►

Кратко доказательство теоремы можно резюмировать так: если забыть, что длины кодовых слов должны быть целыми, и разрешать любые числа $n_i$, только бы сумма $2^{-n_i}$ не превышала единицы, то выгоднее всего взять $n_i = -\log p_i$ (следует из выпускности логарифма). Требование же целочисленности приводит к увеличению $n_i$, но не более чем на единицу.

**Теорема 139.** Энтропия распределения $p_1, \dots, p_n$ с п значениями не превосходит $\log n$ и равна $\log n$ в единственном случае, когда все $p_i$ равны.

◀ Если $n$ есть степень двойки, то неравенство $H \le \log n$ прямо следует из теоремы 138, поскольку можно рассмотреть префиксный код, в котором $n$ кодовых слов имеют длину $\log n$. В общем случае надо применить неравенство Гиббса с $q_i = 1/n$ при всех $i$ и вспомнить, что это неравенство обращается в равенство при $p_i = q_i$. ►

### 7.1.3. Код Хаффмана

Мы доказали, что средняя длина оптимального префиксного кода (для данных $p_1, \dots, p_k$) заключена между $H$ и $H+1$. Попробуем разобраться, как найти этот код.
Пусть $n_1, \dots, n_k$ — длины кодовых слов оптимального кода для данных $p_1, \dots, p_k$. Будем предполагать (переставив буквы), что

$$p_1 \le p_2 \le \dots \le p_k.$$

Можно считать также, что

$$n_1 \ge n_2 \ge \dots \ge n_k$$

(если бы более частая буква кодировалась длиннее, чем более редкая, то обмен кодов уменьшил бы среднюю длину; буквы с одинаковой частотой можно переставлять, не меняя средней длины кода).

Заметим, что для оптимального кода $n_1 = n_2$ (две наиболее редкие буквы всегда имеют одну и ту же длину кода). В самом деле, если $n_1 > n_2$, то $n_1$ больше всех остальных $n_i$. Поэтому в сумме $\sum_i 2^{-n_i}$ первое слагаемое меньше всех других, неравенство $\sum_i 2^{-n_i} \le 1$ не может обратиться в равенство по соображениям чётности, и левая часть его меньше правой по крайней мере на $2^{-n_1}$. А значит, $n_1$ можно уменьшить на единицу, не нарушив неравенства $\sum_i 2^{-n_i} \le 1$, и код не является оптимальным.

Поэтому при выборе оптимального кода достаточно ограничиться кодами с $n_1 = n_2$, и оптимальный среди них соответствует минимуму выражения

$$p_1 n_1 + p_2 n_2 + p_3 n_3 + \dots + p_k n_k = (p_1 + p_2)n + p_3 n_3 + \dots + p_k n_k$$

(если через $n$ обозначить общее значение $n_1$ и $n_2$) по всем $n, n_3, \dots, n_k$, для которых

$$2^{-n} + 2^{-n} + 2^{-n_3} + \dots + 2^{-n_k} \le 1.$$

Перепишем это неравенство как

$$2^{-(n-1)} + 2^{-n_3} + \dots + 2^{-n_k} \le 1,$$

а выражение, подлежащее минимизации, как

$$(p_1 + p_2) + (p_1 + p_2)(n-1) + p_3 n_3 + \dots + p_k n_k.$$

Член $(p_1 + p_2)$ постоянен и не влияет на поиск минимума, а остаток выражения в точности соответствует задаче поиска оптимального префиксного кода для $k-1$ букв с вероятностями $p_1 + p_2, p_3, \dots, p_k$.

Получаем рекурсивный алгоритм: соединить две наиболее редкие буквы в одну (сложив вероятности), найти оптимальный префиксный код для этого случая (рекурсивный вызов), а потом вместо одного кодового слова х для соединённой буквы взять два кодовых слова на единицу длиннее ($x_0$ и $x_1$); ясно, что префиксность кода при этом не нарушится.

Построенный с помощью такого алгоритма оптимальный префиксный код называется кодом *Хаффмана* для данного набора вероятностей $p_i$.
### 7.1.4. Неравенство Крафта – Макмиллана

До сих пор мы изучали в основном префиксные коды. Оказывается, что переход
к произвольным однозначно декодируемым кодам ничего не даёт (с точки зрения
сокращения кода):

**Теорема 140** (неравенство Макмиллана). Пусть $c_1, \dots, c_k$ — кодовые слова однозначно декодируемого кода, а $n_i = l(c_i)$ — их длины. Тогда

$$ \sum_{i} 2^{-n_i} \le 1. $$

Тем самым (лемма Крафта) можно построить и префиксный код с теми же длинами слов.

Будем считать, что в кодовых словах вместо цифр 0 и 1 используются буквы $u$ и $v$. (Скажем, кодовые слова 0, 01 и 11 мы запишем как $u$, $uv$ и $vv$.) Напишем формальную сумму $(c_1 + \dots + c_k)$ всех кодовых слов, возведём её в $N$-ю степень (число $N$ мы потом выберем) и раскроем скобки, не переставляя $u$ и $v$ (как если бы они не коммутировали). Например, для $N=2$ и для приведённого выше примера получится

$$ (u + uv + vv)(u + uv + vv) = \\ = uu + uuv + uvv + uvu + uvuv + uvvv + vvu + vvuv + vvvv. $$

Каждое слагаемое в правой части есть соединение некоторых кодовых слов, причём все слагаемые различны (свойство однозначности декодирования). Теперь подставим вместо $u$ и $v$ число $1/2$. В левой части $(c_1 + \dots + c_k)^N$ превратится при этом в $(2^{-n_i} + \dots + 2^{-n_k})^N$. Правую часть оценим сверху: если бы в неё входили все возможные слова данной длины $t$, то получилось бы $2^t$ членов, каждый из которых равен $2^{-t}$, и сумма равнялась бы 1 (для каждой длины). Поэтому сумма в правой части не превосходит максимальной длины слагаемых, то есть, не больше $N \max(n_i)$.

Теперь видно, что если $\sum 2^{-n_i} > 1$, то при больших $N$ левая часть (растущая экспоненциально) становится больше правой (растущей линейно). ►

Это доказательство производит впечатление искусственного (хотя и красивого) трюка. Более естественное доказательство (или, если угодно, более естественное изложение того же доказательства) будет приведено ниже (с. 249).

## 7.2. Энтропия пары и условная энтропия

### 7.2.1. Энтропия пары случайных величин

При обсуждении энтропии удобно использовать стандартную для теории веро-
ятностей терминологию. Пусть $\xi$ — случайная величина, принимающая конечное
число значений $\xi_1, \dots, \xi_k$ с вероятностями $p_1, \dots, p_k$. Тогда её шенноновская эн-
тропия определяется формулой

$$ H(\xi) = p_1(-\log p_1) + \dots + p_k(-\log p_k). $$
Это определение позволяет говорить об энтропии пары случайных величин $\xi$ и $\eta$ (опредёлённых на одном и том же вероятностном пространстве), поскольку та- кая пара сама образует случайную величину. Следующая теорема утверждает, что энтропия пары не превосходит суммы энтропий:

**Теорема 141.**

$$H(\langle\xi, \eta\rangle) \le H(\xi) + H(\eta).$$

Мы предполагаем, что величины $\xi$ и $\eta$ принимают конечное число значений, поэтому эта теорема представляет собой некоторое неравенство с суммами ло- гарифмов. Пусть $\xi$ принимает $k$ значений $\xi_1, \dots, \xi_k$, а $\eta$ принимает $l$ значений $\eta_1, \dots, \eta_l$. Тогда величина $\langle\xi, \eta\rangle$ может принимать, вообще говоря, $kl$ значений $\langle\xi_i, \eta_j\rangle$ (некоторые из значений могут не встречаться или встречаться с вероятно- стью нуль). Распределение вероятностей для пары $\langle\xi, \eta\rangle$, таким образом, задаётся таблицей из $k$ строк и $l$ столбцов: число $p_{ij}$, стоящее в $i$-й строке и $j$-м столбце, представляет собой вероятность события «$(\xi = \xi_i)$ и $(\eta = \eta_j)$» (здесь $i = 1, \dots, k$ и $j = 1, \dots, l$). Все числа $p_{ij}$ неотрицательны и в сумме равны единице (некоторые из них могут равняться нулю).

Сложив числа в строках, мы получим распределение вероятностей для вели- чины $\xi$: она принимает значение $\xi_i$ с вероятностью $\sum_j p_{ij}$; эту сумму удобно обо- значить $p_{i*}$; аналогичным образом $\eta$ принимает значение $\eta_j$ с вероятностью $p_{j*}$, которая есть сумма чисел в $j$-м столбце.

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

$$\sum_{i,j} p_{ij} (-\log p_{ij}) \le \sum_{i} p_{i*} (-\log p_{i*}) + \sum_{j} p_{*j} (-\log p_{*j})$$

(где $p_{i*}$ и $p_{*j}$ определяются как суммы по строкам и столбцам).

Это неравенство в конечном счёте сводится к выпуклости логарифма, но по- лезно понимать его интуитивный смысл. Если отождествить (забыв про разницу порядка единицы) энтропию с длиной кратчайшего префиксного кода, то теоре- му можно доказать так: пусть имеются короткие префиксные коды для $\xi$ и $\eta$ (с кодовыми словами $c_1, \dots, c_k$ и $d_1, \dots, d_l$). Тогда можно рассмотреть код для па- ры $\langle\xi, \eta\rangle$, кодируя значения $\langle\xi_i, \eta_j\rangle$ словом $c_i d_j$ (приписываем $d_j$ справа к $c_i$ без разделителя). Это будет, как легко проверить, префиксный код (чтобы отщепить кодовое слово от бесконечной последовательности, надо сначала отщепить $c_i$, а по- том $d_j$; в обоих случаях это делается однозначно). Средняя длина этого кода будет равна сумме средних длин кодов для $\xi$ и $\eta$. Он не обязан быть оптимальным (ведь и неравенство может быть строгим), но даёт оценку сверху для оптимального кода.

◀ Это рассуждение можно превратить в строгое доказательство, если вспо- мнить, что при доказательстве теоремы 138 (с. 241) мы установили, что энтропия равна минимуму величины $\sum_i p_i (-\log_2 q_i)$ по всем наборам неотрицательных чи- сел $q_i$ с единичной суммой. В частности, энтропия пары (левая часть неравенства) есть минимум сумм

$$\sum_{i,j} p_{ij} (-\log q_{ij})$$
по всем наборам $q_{ij}$ неотрицательных чисел с суммой единица. Будем рассматривать не все наборы, а лишь наборы «ранга 1», которые получаются как произведения

$$q_{ij} = q_{i*} \cdot q_{j*}$$

для некоторых наборов неотрицательных чисел $q_{i*}$ и $q_{j*}$, каждый из которых имеет сумму 1. Тогда $(-\log q_{ij})$ распадётся в сумму $(-\log q_{i*}) + (-\log q_{j*})$, а вся сумма — в две суммы, которые (после суммирования по одному из индексов) окажутся равными

$$\sum_{i} p_{i*}(-\log q_{i*})$$

и

$$\sum_{j} p_{j*}(-\log q_{j*})$$

соответственно. Минимумы этих сумм равны $H(\xi)$ и $H(\eta)$.

Таким образом, левая часть неравенства есть минимум некоторой величины по всем наборам, а правая — по наборам ранга 1, откуда и вытекает требуемое неравенство. ►

### 7.2.2. Условная энтропия

**Условной вероятностью** некоторого события В при условии события А называют отношение вероятности события «А и В» к вероятности события А. Это определение имеет смысл, если вероятность события А отлична от нуля. Мотивировка понятна: мы рассматриваем долю исходов, где произошло В, не среди всех исходов, а только среди тех, где произошло А.

Если А — событие, а $\xi$ — случайная величина с конечным числом значений $\xi_1, \dots, \xi_k$, то можно рассмотреть (помимо вероятностей $\text{Pr}[\xi = \xi_i]$) и условные вероятности $\text{Pr}[(\xi = \xi_i) | A]$. Их сумма тоже равна единице, и получается некоторое новое распределение вероятностей. Его энтропия называется **условной энтропией величины $\xi$** при условии А и обозначается $H(\xi | A)$, а само это распределение вероятностей можно обозначить $(\xi | A)$.

**218** Покажите, что величина $H(\xi | A)$ может быть и больше, и меньше величины $H(\xi)$. [Указание: распределение $(\xi | A)$ (особенно при малой вероятности события А) мало связано с распределением для $\xi$.]

Неформально говоря, $H(\xi | A)$ — это минимально возможная средняя длина кода, если нас интересуют лишь случаи, когда произошло событие А.

Пусть теперь (как и в прошлом разделе) даны две случайные величины $\xi$ и $\eta$. Будем предполагать, что для каждой из них все значения имеют ненулевую вероятность (нулевые можно выбросить). Для каждого значения $\eta_j$ величины $\eta$ рассмотрим событие $\eta = \eta_j$ (его вероятность мы обозначали $p_{*j}$). Рассмотрим условную энтропию величины $\xi$ при условии этого события. Она соответствует распределению вероятностей $i \mapsto p_{ij}/p_{*j}$. Далее усредним эти энтропии с весами, равными
вероятностям событий $\eta = \eta_j$. Полученное среднее называют условной энтропией $\xi$ при известном $\eta$ и обозначают $H(\xi|\eta)$. Формально говоря,

$$H(\xi|\eta) = \sum_j \Pr[\eta = \eta_j] H(\xi|\eta = \eta_j)$$

или, в наших обозначениях,

$$H(\xi|\eta) = \sum_j p_{*j} \sum_i \frac{p_{ij}}{p_{*j}} (-\log \frac{p_{ij}}{p_{*j}})$$

Основные свойства условной энтропии перечислены в следующей теореме, спра-
ведливой для любых случайных величин $\xi, \eta$:

**Теорема 142.** (а) $H(\xi|\eta) \ge 0$;

(б) $H(\xi|\eta) = 0$ тогда и только тогда, когда $\xi = f(\eta)$ с вероятностью 1 для некоторой функции $f$ (оговорка про «вероятность 1» означает, что мы пренебрегаем значениями, которые имеют нулевую вероятность);

(в) $H(\xi|\eta) \le H(\xi)$;

(г) $H(\langle\xi, \eta\rangle) = H(\eta) + H(\xi|\eta)$.

◀ Первое из этих утверждений очевидно: все $H(\xi|\eta = \eta_j)$ неотрицательны, потому неотрицательна и их взвешенная сумма.

(б) Если взвешенная сумма равна нулю, то все слагаемые с ненулевыми коэффициентами равны нулю, то есть при каждом значении $\eta_j$ величина $(\xi|\eta = \eta_j)$ имеет нулевую энтропию (и потому принимает лишь одно значение с точностью до событий нулевой вероятности).

Утверждение (в) можно объяснить так: $H(\xi|\eta)$ будет средней длиной оптималь-
ного кода для $\xi$, если разрешить кодировать значения $\xi$ по-разному, в зависимости
от значения величины $\eta$ (в каждом случае свой код, который оптимизируется с
учётом условных вероятностей). Ясно, что это облегчает построение оптимально-
го кода, поэтому средняя длина получается меньше $H(\xi)$.

Более формально: при каждом $j$ величина $H(\xi|\eta = \eta_j)$ равна минимуму суммы

$$\sum_i \frac{p_{ij}}{p_{*j}} (-\log q_{ij})$$

по всем неотрицательным $q_{ij} + q_{2j} + \dots + q_{kj} = 1$ (мы используем свой набор
переменных для каждого $j$) и потому $H(\xi|\eta)$ равна минимуму суммы

$$\sum_j p_{*j} \sum_i \frac{p_{ij}}{p_{*j}} (-\log q_{ij})$$

по всем таблицам, составленным из неотрицательных чисел $q_{ij}$, у которых сумма
каждого столбца равна единице. Если мы теперь ограничимся таблицами, у которых
все столбцы одинаковы, $q_{ij} = q_i$, то сумма превратится в

$$\sum_j p_{*j} \sum_i \frac{p_{ij}}{p_{*j}} (-\log q_i) = \sum_j p_{ij} (-\log q_i) = \sum_i p_{i*} (-\log q_i)$$

и её минимум станет равным $H(\xi)$. Поэтому $H(\xi|\eta) \le H(\xi)$.
Наконец, пункт (г) представляет собой равенство, которое непосредственно следует из определений:

$$
\begin{align*}
\sum_{i,j} p_{ij} (-\log p_{ij}) &= \sum_{j} p_{*j} \sum_{i} \frac{p_{ij}}{p_{*j}} \left( -\log \frac{p_{ij}}{p_{*j}} - \log p_{*j} \right) = \\
&= \sum_{j} p_{*j} \sum_{i} \frac{p_{ij}}{p_{*j}} \left( -\log \frac{p_{ij}}{p_{*j}} \right) + \sum_{j} p_{*j} \sum_{i} \frac{p_{ij}}{p_{*j}} \left( -\log p_{*j} \right) = \\
&= \sum_{j} p_{*j} H(\xi | \eta = \eta_j) + \sum_{j} p_{*j} (-\log p_{*j}) = H(\xi | \eta) + H(\eta).
\end{align*}
$$

Теорема доказана. ►

Из этой теоремы немедленно вытекает теорема 141 (с. 245). Кроме того, из неё видно, что энтропия пары не меньше энтропии любого из её членов (поскольку условная энтропия неотрицательна). Отсюда легко вытекает такое утверждение:

**Теорема 143.** Пусть $\xi$ — случайная величина с конечным числом значений, а $f$ — функция, определённая на множестве значений величины $\xi$. Тогда

$H(f(\xi)) \le H(\xi),$

где $f(\xi)$ — случайная величина, получающаяся применением $f$ к $\xi$ (формально говоря, композиция $f$ и $\xi$).

С точки зрения наборов чисел переход от $\xi$ к $f(\xi)$ означает, что мы объединяем некоторые значения (складывая соответствующие вероятности).

◀ В самом деле, величина $\langle \xi, f(\xi) \rangle$ имеет в точности то же распределение, что и $\xi$, поэтому её энтропия не меньше энтропии второго члена пары. ►

**219** Укажите прямое доказательство в терминах кодирования и поиска минимума.

**220** В каких случаях неравенство теоремы 143 обращается в равенство?

### 7.2.3. Независимость и энтропия

Понятие независимости случайных величин легко выражается в терминах энтропии. Напомним, что величины $\xi$ и $\eta$ независимы, если вероятность события «$\xi = \xi_i$ и $\eta = \eta_j$» равна произведению вероятностей событий $\xi = \xi_i$ и $\eta = \eta_j$ по отдельности. (Переформулировка: если распределение вероятностей $\xi$ относительно любого из условий $\eta = \eta_j$ совпадает с исходным; аналогично и для $\eta$ относительно $\xi = \xi_i$.) В наших обозначениях независимость означает, что $p_{ij} = p_{i*}p_{*j}$ (матрица вероятностей имеет ранг 1).

**Теорема 144.** Величины $\xi$ и $\eta$ независимы тогда и только тогда, когда

$H(\langle \xi, \eta \rangle) = H(\xi) + H(\eta).$

Другими словами, критерий независимости состоит в том, что неравенство теоремы 141 обращается в равенство. Используя теорему 142, можно переписать это равенство в виде $H(\xi) = H(\xi | \eta)$ или $H(\eta) = H(\eta | \xi)$.
### Логарифм является строго выпуклой функцией: неравенство

$$ \log(\sum p_i x_i) \geq \sum p_i \log x_i, $$

справедливое для неотрицательных $p_i$ с единичной суммой и произвольных положительных $x_i$, обращается в равенство, лишь если все $x_i$ равны (за исключением тех, которые входят с нулевыми коэффициентами $p_i$).

Отсюда следует, что для любых неотрицательных $p_i$, в сумме равных единице, минимум выражения

$$ \sum p_i (-\log q_i), $$

который берётся по всем неотрицательным $q_i$, в сумме равным 1, достигается в единственной точке, когда $q_i = p_i$. (Надо уточнить, что при $p_i = 0$ мы полагаем $p_i(-\log q_i) = 0$ и разрешаем $q_i$ быть нулевым.)

Теперь вспомним, что делалось при доказательстве теоремы 141. Минимум по матрицам ранга 1 (при котором правая часть равна сумме энтропий) достигался при

$$ q_{ij} = p_{i*} \cdot p_{j*}. $$

Если он совпадает с минимумом по всем наборам $q_{ij}$, который достигается при $q_{ij} = p_{ij}$, то это значит, что имеет место равенство

$$ p_{ij} = p_{i*} \cdot p_{j*} $$

и величины $\xi$ и $\eta$ независимы. ►

**221** Проведите аналогичное рассуждение, основываясь на теореме 142.

**222** Докажите, что величины $\alpha, \beta, \gamma$ независимы в совокупности (это значит, что вероятность события ($\alpha = \alpha_i, \beta = \beta_j, \gamma = \gamma_k$) равна произведению трёх отдельных вероятностей) тогда и только тогда, когда

$$ H(\langle\alpha, \beta, \gamma\rangle) = H(\alpha) + H(\beta) + H(\gamma). $$

Теоремы 141 и 144 показывают, что разность $H(\xi) + H(\eta) - H(\langle\xi, \eta\rangle)$ всегда неотрицательна и обращается в нуль тогда и только тогда, когда величины $\xi$ и $\eta$ независимы. Тем самым логично считать её числовой мерой «степени зависимости» между $\xi$ и $\eta$. Эту разность обозначают $I(\xi:\eta)$ и называют взаимной информацией случайных величин $\xi$ и $\eta$. Теорема 142 позволяет переписать выражение для $I(\xi:\eta)$ так:

$$ I(\xi:\eta) = H(\eta) - H(\eta|\xi) = H(\xi) - H(\xi|\eta) $$

(взаимная информация показывает, «насколько знание одной величины уменьшает энтропию другой»).

В качестве применения рассмотренных понятий снова докажем неравенство Максимлана. Мы будем действовать немного в другом порядке и сначала докажем, что для однозначно декодируемого кода случайной величины $\xi$ средняя длина кодового слова не меньше $H(\xi)$.
Чтобы сделать это, заметим, что для инъективного (не обязательно однозначно декодируемого) кода, у которого все кодовые слова имеют длину меньше $c$, средняя длина не меньше $H(\xi) - \log c$. В самом деле, если $n_i$ — длины кодовых слов такого кода, то сумма величин $2^{-n_i}$ не превосходит $c$ (для каждой длины сумма по словам этой длины не превосходит единицы), и потому неравенство теоремы 138 ухудшается не более чем на $\log c$.

Теперь рассмотрим $N$ независимых одинаково распределённых копий случайной величины $\xi$. Возникающая случайная величина, которую мы обозначим $\xi^N$, имеет энтропию в $N$ раз больше. Если использовать для кодирования каждой из копий наш однозначно декодируемый код, а потом все слова соединить, то получится код для $\xi^N$, средняя длина которого в $N$ раз больше средней длины исходного кода для $\xi$. Этот код будет инъективным (по определению однозначного декодирования), и максимальная длина его не превосходит $cN$, где $c$ — максимальная длина кодовых слов рассматриваемого нами однозначно декодируемого кода. Применяя утверждение предыдущего абзаца, получаем, что

$$N \cdot (\text{средняя длина однозначно декодируемого кода}) \geq NH(\xi) - \log(cN).$$

Теперь, поделив на $N$ и устремив $N$ к бесконечности, получаем искомое утверждение (поскольку $\log(cN)/N$ стремится к 0).

Теперь уже легко доказать собственно неравенство Макмиллана. Пусть однозначно декодируемый код состоит из слов длиной $n_1, \dots, n_k$, и при этом $\sum 2^{-n_i} > 1$. Положим сначала $p_i = 2^{-n_i}$, а затем пропорционально уменьшим все $p_i$, сделав их сумму равной единице. Рассмотрим случайную величину с распределением вероятностей $p_i$ и её кодирование с помощью нашего кода. Средняя длина кода будет $\sum p_i n_i$ и будет меньше $H = \sum p_i (-\log p_i)$, поскольку $n_i < -\log p_i$ за счёт уменьшения величин $p_i$.

**223** Проведите подробно это доказательство неравенства Макмиллана и установите его соответствие с ранее приведённым.

### 7.2.4. «Релятивизация» и базисные неравенства

Доказанные нами утверждения имеют свои «условные» варианты. Например, неравенство

$$H(\langle\xi, \eta\rangle) \leq H(\xi) + H(\eta)$$

при добавлении случайной величины $\alpha$ в качестве условия превращается в

$$H(\langle\xi, \eta\rangle|\alpha) \leq H(\xi|\alpha) + H(\eta|\alpha).$$

Нового доказательства по существу не требуется, так как при каждом значении $\alpha_i$ случайной величины $\alpha$ выполнено неравенство

$$H(\langle\xi, \eta\rangle|\alpha = \alpha_i) \leq H(\xi|\alpha = \alpha_i) + H(\eta|\alpha = \alpha_i)$$

(применяем теорему 141 к условным распределениям вероятностей случайных величин $\xi$ и $\eta$), и остаётся сложить эти неравенства с весами $\text{Pr}[\alpha = \alpha_i]$.
Теперь можно выразить условные энтропии через безусловные, используя формулу $H(\beta|\gamma) = H(\langle\beta, \gamma\rangle) - H(\gamma)$, и привести подобные члены. Получится такое утверждение:

**Теорема 145** (базисное неравенство).

$$H(\xi, \eta, \alpha) + H(\alpha) \le H(\xi, \alpha) + H(\eta, \alpha).$$

Для краткости мы здесь опускаем угловые скобки и пишем $H(\xi, \eta, \alpha)$ вместо $H(\langle\xi, \eta, \alpha\rangle)$ или ещё более подробного $H(\langle\langle\xi, \eta\rangle, \alpha\rangle)$.

Аналогичную «релятивизацию» (Добавление случайных величин как условий) можно применить и к понятию взаимной информации. Например, $I(\alpha: \beta|\gamma)$ определяется как

$$H(\alpha|\gamma) + H(\beta|\gamma) - H(\langle\alpha, \beta\rangle|\gamma).$$

Базисное неравенство (теорема 145) утверждает, что $I(\alpha: \beta|\gamma) \ge 0$ для любых случайных величин $\alpha, \beta, \gamma$.

**224** Докажите, что $I(\langle\alpha, \beta\rangle: \gamma) \ge I(\alpha: \gamma)$.

**225** Докажите, что

$$I(\langle\alpha, \beta\rangle: \gamma) = I(\alpha: \gamma) + I(\beta: \gamma|\alpha).$$

Если $I(\alpha: \gamma|\beta) = 0$, говорят, что $\alpha$ и $\gamma$ независимы при известном $\beta$, а также что $\alpha, \beta, \gamma$ образуют марковскую цепь («прошлое» $\alpha$ связано с «будущим» $\gamma$ лишь через «настоящее» $\beta$).

**226** Докажите, что в этом случае $I(\alpha: \gamma) \le I(\alpha: \beta)$, и потому выполняется неравенство $I(\alpha: \gamma) \le H(\beta)$.

При решении этих задач полезно использовать диаграммы, аналогичные диаграммам для колмогоровской сложности в главе 2. Диаграмма для двух величин состоит из трёх областей, каждой из которых соответствует неотрицательное значение; суммы значений в двух областях слева равна $H(\alpha)$, а в двух областях справа — $H(\beta)$ (рис. 7.1).

<figure><img src="image_20.png" /><figcaption>Рис. 7.1. Энтропии двух случайных величин.</figcaption></figure>

Диаграмма для трёх величин $\alpha, \beta, \gamma$ показана на рис. 7.2. Центральной области соответствует значение, которое мы обозначили через $I(\alpha: \beta: \gamma)$; его можно определить как $I(\alpha: \beta) - I(\alpha: \beta|\gamma)$, а также как $I(\alpha: \gamma) - I(\alpha: \gamma|\beta)$ и т.п. — при переходе к безусловным энтропиям получается одно и то же выражение

$$I(\alpha: \beta: \gamma) = H(\alpha) + H(\beta) + H(\gamma) - H(\alpha, \beta) - H(\alpha, \gamma) - H(\beta, \gamma) + H(\alpha, \beta, \gamma).$$
<figure><img src="image_21.png" /><figcaption>Рис. 7.2. Энтропии трёх случайных величин.</figcaption></figure>

В отличие от шести других величин на рисунке, величина $I(\alpha:\beta:\gamma)$ может быть отрицательной. Так будет, например, если величины $\alpha$ и $\beta$ независимы, но зависимы при известном $\gamma$.

[227] Приведите пример таких величин $\alpha, \beta, \gamma$. [Указание. По аналогии с примером на с. 61 можно рассмотреть независимые величины $\alpha$ и $\beta$, равномерно распределённые на $\{0, 1\}$, и положить $\gamma = (\alpha + \beta) \mod 2$.]

[228] Докажите, что если величины $\alpha$ и $\beta$ различаются с вероятностью $\varepsilon < 1/2$, и число различных значений величины $\alpha$ равно $a$, то выполняется неравенство Фано:

$$H(\alpha | \beta) \le \varepsilon \log a + h(\varepsilon),$$

где $h(\varepsilon)$ — энтропия случайной величины с двумя значениями, имеющими вероятности $\varepsilon$ и $1 - \varepsilon$. [Указание. Введём величину $\gamma$, которая принимает два значения 0 и 1 при $\alpha \ne \beta$ и $\alpha = \beta$ соответственно. Тогда $H(\alpha | \beta) \le H(\alpha, \gamma | \beta) = H(\gamma | \beta) + H(\alpha | \beta, \gamma) \le H(\gamma) + H(\alpha | \beta, \gamma)$. Первое слагаемое равно $h(\varepsilon)$, а второе надо записать как

$$\mathrm{Pr}[\gamma = 0]H((\alpha | \beta) | \gamma = 0) + \mathrm{Pr}[\gamma = 1]H((\alpha | \beta) | \gamma = 1),$$

то есть

$$\mathrm{Pr}[\alpha \neq \beta]H((\alpha | \beta) | \alpha \neq \beta) + \mathrm{Pr}[\alpha = \beta]H((\alpha | \beta) | \alpha = \beta),$$

что не превосходит $\varepsilon \log a + 0.$]

[229] Пусть $H(\alpha | \beta, \gamma) = 0$ и $I(\beta:\alpha) = 0$. Докажите, что $H(\gamma) \ge H(\alpha)$. (Если агент хочет передать в Центр секретное сообщение $\alpha$ в виде открытого текста $\beta$
с помощью заранее согласованного с Центром ключа $\gamma$, причём так, чтобы враги, не знающие $\gamma$, не получили никакой информации об $\alpha$, то энтропия ключа должна быть не меньше энтропии сообщения. Это утверждение называют иногда теоремой Шеннона об идеальном шифре.)

**230** Докажите, что для любых трёх случайных величин $\alpha, \beta, \gamma$ выполнено неравенство

$$2H(\alpha, \beta, \gamma) \le H(\alpha, \beta) + H(\beta, \gamma) + H(\alpha, \gamma).$$

[Указание: см. доказательство аналогичного утверждения для колмогоровской сложности в теореме 26 (с. 59).]

**231** Докажите аналогичное неравенство для любого числа случайных величин:

$$(n-1)H(\alpha_1, \dots, \alpha_n) \le H(\alpha_2, \dots, \alpha_n) + \dots + H(\alpha_1, \dots, \alpha_{n-1}).$$

(В правой части неравенства складываются энтропии кортежей, состоящих из всех случайных величин, кроме одной.)

**232** (неравенство Ширера [31]) Докажите следующее обобщение предыдущего неравенства. Пусть $T_1, \dots, T_k$ — произвольные кортежи, составленные из случайных величин $\alpha_1, \dots, \alpha_n$, причем каждая случайная величина входит ровно в r кортежей из числа $T_1, \dots, T_k$. Тогда

$$rH(\alpha_1, \alpha_2, \dots, \alpha_n) \le H(T_1) + \dots + H(T_k).$$

**233** Покажите, что из неравенства задачи 231 следует оценка для объёма n-мерного тела через объемы его n-1-мерных проекций (обобщение неравенства, упомянутого на с. 22): объем тела, возведенный в (n-1)-ю степень, не превышает произведения n-1-мерных объемов его n проекций на координатные гиперплоскости. [Указание. Сначала докажите неравенство для тел, составленных из единичных кубиков. Для этого рассмотрите случайную величину, равномерно распределенную среди кубиков, составляющих тело. Для общего случая надо перейти к пределу, разбивая тело на кубики.]

Это неравенство является частным случаем более общего геометрического неравенства Лумиса – Уитни [87].

## 7.3. Сложность и энтропия

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

Вопрос этот можно понимать двояко. Во-первых, можно доказывать, что колмогоровская сложности и шенноновская энтропия похожи по своим свойствам (скажем, для них верны одни и те же неравенства, см. раздел 10.6, с. 364). С другой стороны, можно сравнивать численные значения колмогоровской сложности и шенноновской энтропии, и этим мы сейчас займёмся. Правда, тут сразу же возникает
проблема: шенноновская энтропия определена для случайных величин, а колмогоровская сложность — для двоичных слов, как же их сравнивать? Тем не менее иногда такое сравнение возможно, и мы сейчас разберём несколько утверждений такого вида. Общее и весьма расплывчатое описание соответствующих результатов звучит так: шенноновская энтропия учитывает лишь частотные закономерности, а колмогоровская сложность — все алгоритмические закономерности, поэтому в общем случае колмогоровская сложность меньше. Однако в тех случаях, если объект порождается случайно по вероятностной мере, с большой вероятностью других (не частотных) закономерностей нет, и сложность близка к энтропии.

Перейдём к конкретным уточнениям этого общего тезиса.

### 7.3.1. Колмогоровская сложность и энтропия частот

Будем рассматривать произвольный (не обязательно двухбуквенный) конечный алфавит А и слова в этом алфавите. Колмогоровская сложность для них определяется естественным образом, и мы будем говорить о ней без особых оговорок. (Мы нигде не использовали, что объекты, сложность которых определяется, являются именно двоичными словами. Но важно, что мы рассматриваем двоичные слова в качестве описаний: измеренная в байтах сложность будет в восемь раз меньше битовой!)

Пусть фиксирован алфавит А, содержащий k букв. Рассмотрим произвольное слово х некоторой длины N в этом алфавите. Пусть $p_1, \dots, p_k$ — частоты появления букв в слове х. Все они являются дробями со знаменателем N; сумма частот равна единице. Пусть $h(p_1, \dots, p_k)$ — шенноновская энтропия соответствующего распределения.

**Теорема 146.**

$$ \frac{KS(x)}{N} \le h(p_1, \dots, p_k) + \frac{O(\log N)}{N}. $$

Неравенство обращается в равенство для большинства слов х (среди всех слов длины N с заданными частотами букв).

Имеется в виду, что $O(\log N)$ не больше $c \log N$, причём константа c не зависит ни от N, ни от слова х, ни от частот $p_1, \dots, p_k$, но может зависеть от k, так что в этой теореме размер алфавита считается фиксированным.

По существу это чисто комбинаторное утверждение. В самом деле, условия сложность $KS(x|N, p_1, \dots, p_k)$ не превосходит $\log C(N, p_1, \dots, p_k) + O(1)$, где

$$ C(N, p_1, \dots, p_k) = \frac{N!}{(p_1 N)! (p_2 N)! \dots (p_k N)!} $$

есть количество слов длины N в алфавите А, имеющих данные частоты $p_1, \dots, p_k$. Это следует из того, что каждое слово с такими частотами может быть (при известных параметрах) задано своим порядковым номером в (скажем, алфавитном) списке таких слов, для чего достаточно $\log C(N, p_1, \dots, p_k)$ битов.

Оценка числа $C(N, p_1, \dots, p_k)$ выполняется по формуле Стирлинга. Если отбросить полиномиальные по N множители (возникающие из-за $\sqrt{2\pi k}$ в формуле для $k!$), то останется как раз $2^{Nh(p_1, \dots, p_k)}$. Подробно это вычисление для случая
$k = 2$ проводилось при доказательстве усиленного закона больших чисел (теорема 27, с. 66); общий случай аналогичен.

Остаётся заметить, что для задания $N, p_1, \dots, p_k$ достаточно примерно $k \log N$ битов (нужно указать $k$ целых чисел $p_1 N, \dots, p_k N$, в сумме дающих $N$), поэтому при удалении условия в выражении $KS(x|N, p_1, \dots, p_k)$ сложность возрастёт не более чем на $O(\log N)$ (с константой, примерно равной $k$).

Отметим, что верхняя оценка $\log C(N, p_1, \dots, p_k)$ должна достигаться (с точностью $O(\log N)$) для большинства слов из рассматриваемого списка, поскольку слов с более короткими описаниями меньше, чем $C(N, p_1, \dots, p_k)$). В частности, верхняя оценка достигается для слова $x$ с максимальной (среди слов в данном списке) колмогоровской сложностью. ►

Другой способ доказательства того же утверждения использует верхнюю оценку для монотонной сложности (теорема 89, с. 165). Рассмотрим распределение вероятностей на последовательностях букв алфавита $A$, соответствующее независимым испытаниям с частотами $p_1, \dots, p_k$. Вероятность появления последовательности, начинающейся на слово $z$ длины $N$, в котором частоты букв равны $q_1, \dots, q_k$, равна

$$p_1^{q_1 N} \dots p_k^{q_k N}$$

(буква $a_i$ имеет вероятность $p_i$ и появляется $q_i N$ раз), а её двоичный логарифм равен

$$-N \cdot (q_1(-\log p_1) + \dots + q_k(-\log p_k)).$$

В частности, если $q_i = p_i$, то логарифм вероятности равен $-Nh(p_1, \dots, p_k)$ и поэтому монотонная сложность оценивается сверху числом $Nh(p_1, \dots, p_k)$. Остаётся заметить, что монотонная сложность отличается от обычной на величину порядка $O(\log N)$ для слов длины $N$.

Это рассуждение, однако, не вполне корректно. Дело в том, что в оценке для монотонной сложности предполагалось, что мера фиксирована и оцениваются сложности различных слов. Здесь же, интересуясь оценкой для сложности слова $x$, мы рассматриваем меру, которая соответствует частотам появления букв в самом слове $x$, поэтому формально утверждение теоремы 89 применить нельзя. Если вспомнить её доказательство, то видно, что получается оценка для «условной» монотонной сложности при известных $p_1, \dots, p_k$; переход от неё к безусловной сложности может привести к увеличению оценки на $O(\log N)$, так что таким способом мы получаем другое доказательство теоремы 146.

**234** Оцените зависимость константы в $O(\log N)$ от $k$. [Указание: оба доказательства дают $k(1 + o(1)) \log N$.]

**235** Показайте, что при отделённых от нуля частотах $p_1, \dots, p_k$ оценку предыдущей задачи можно улучшить до $(k/2 + O(1)) \log N$. Точнее, для любых $\varepsilon > 0$ и $k$ найдется константа $C$ такая, что для всех слов $x$ длины $N$ в $k$-буквенном алфавите истинно неравенство $KS(x) \le h(p_1, \dots, p_k)N + (k/2 + 1) \log N + C$, при условии, что частоты $p_1, \dots, p_k$ вхождений всех букв в $x$ не меньше $\varepsilon$. [Указание. В первом доказательстве надо вспомнить об опущенных квадратных корнях в формуле Стирлинга, которые в основном попадают в знаменатель. Второе доказательство также
можно модифицировать, рассмотрев меру, в которой вместо точных значений $p_k$ берутся их приближения с точностью до $1/\sqrt{N}$. При этом оценка ухудшится, но поскольку в окрестности минимума приращение гладкой функции пропорционально квадрату аргумента, то это ухудшение будет не более чем на $O(1)$; на этом мы сэкономим половину битов при задании чисел $p_1, \dots, p_k$.

Заметим, что неравенство теоремы 146 может быть как угодно далеко от равенства: если, скажем, алфавит состоит из двух букв, и в слове $x$ они чередуются, то правая часть равна 1, а левая имеет порядок $(\log N)/N$. Что и не удивительно — правая часть учитывает только частоты, а не другие (не-частотные) закономерности. В следующем разделе мы покажем, что при случайном порождении слова сложность близка к энтропии.

### 7.3.2. Математическое ожидание сложности

Пусть фиксирован $k$-буквенный алфавит $A$ и $k$ чисел $p_1, \dots, p_k \ge 0$ с суммой 1 (которые мы для простоты считаем рациональными).

Рассмотрим случайную величину $\xi$, значениями которой являются буквы алфавита $A$, принимаемые с вероятностями $p_1, \dots, p_k$. Для каждого $N$ рассмотрим случайную величину $\xi^N$, соответствующую $N$ независимым копиям случайной величины $\xi$. Её значениями являются слова длины $N$ в алфавите $A$ (каждая буква порождается независимо, причём вероятность появления $i$-й буквы равна $p_i$). Нас будет интересовать математическое ожидание сложности значений случайной величины $\xi^N$ (взвешенное среднее с весами, равными вероятностям).

**Теорема 147.** Математическое ожидание $\text{KP}(\xi^N | N)$ равно $\text{NH}(\xi) + O(1)$ (константа в $O(1)$ может зависеть от $\xi$, но не зависит от $N$).

Заметим, что (при положительных $p_i$) среди значений величины $\xi^N$ будут встречаться все слова длины $N$ в алфавите $A$; некоторые из них имеют сложность много больше $NH$ (если только распределение вероятностей не равномерное, поскольку в этом случае таких слов нет), а другие имеют сложность много меньше $NH$.

◀ Для каждого слова длины $N$ (то есть для каждого значения случайной величины $\xi^N$) рассмотрим его кратчайшее описание при известном $N$ (относительно оптимального префиксно корректного способа описания). Полученные слова образуют префиксный код в смысле раздела 7.1.1. Средняя длина этого кода как раз равна математическому ожиданию сложности значений величины $\xi^N$. Поэтому теорема 138 (с. 241) гарантирует, что это математическое ожидание не меньше $H(\xi^N) = NH(\xi)$. Нижняя оценка (и даже без константы $O(1)$) доказана.

Та же самая теорема позволяет получить и верхнюю оценку. В самом деле, она утверждает существование префиксного кода, имеющего среднюю длину кодового слова не выше $H(\xi^N) + 1$. Такой код можно алгоритмически построить, зная число $N$ (и числа $p_i$, предполагаемые фиксированными). Например, можно использовать конструкцию из доказательства теоремы 138, или применить код Хаффмана, или даже просто перебирать все коды, пока не найдётся подходящий.

Так или иначе построенный код можно рассматривать как некоторый способ условного префиксного описания (при известном $N$), для которого средняя пре-
фиксная сложность значения величины $\xi^N$ не превосходит $H(\xi^N) + 1 = NH(\xi) + 1$. Переход к оптимальному префиксно корректному способу описания увеличит среднюю сложность не более чем на константу. ►

**236** Покажите, что можно немного усилить верхнюю оценку и показать, что среднее значение монотонной сложности $KM(\xi^N)$ не превосходит $NH(\xi) + O(1)$. [Указание. Примените теорему 89 к распределению вероятностей, соответствующему независимым испытаниями величины с распределением $\xi$.]

Мы предполагали, что величины $p_1, \dots, p_k$ рациональны и фиксированы зарайнее. Если стремиться получить «равномерную» оценку, имеющую место для всех наборов $p_1, \dots, p_n$, то следует добавить их в условие и оценивать среднее значение величины $KP(\xi^N | N, p_1, \dots, p_k)$. На нижнюю оценку это вообще не повлияет, поскольку она верна для любого префиксного кода, а для получения верхней оценки (построения кода) этой информации достаточно. (Сказанное относится к случаю рациональных значений $p_i$; для произвольных действительных значений $p_i$ можно взять их достаточно точные приближения.)

**237** Сформулируйте и докажите соответствующие точные утверждения.

Доказанная теорема показывает, что в среднем сложность равна энтропии, хотя она бывает и больше, и меньше её. На самом деле верно и более сильное утверждение: почти что с единичной вероятностью сложность близка к энтропии, и вероятность того, что случайно выбранное значение величины $\xi^N$ будет иметь сложность, сильно отличающуюся от энтропии, мала. Это утверждение является алгоритмическим аналогом теоремы Шеннона о пропускной способности канала без шума, и мы вернёмся к этому вопросу в разделе 7.3.4.

### 7.3.3. Сложность начальных отрезков случайных последовательностей

Покажем, как связана сложность с энтропией для начальных отрезков случайных (в смысле Мартин-Лёфа) последовательностей. Пусть по-прежнему фиксирован некоторый алфавит $A$ из $k$ букв и распределение вероятностей $p_1, \dots, p_k$ на буквах этого алфавита. Будем считать, что $p_1, \dots, p_k$ являются вычислимыми действительными числами.

Рассмотрим пространство $A^\infty$ бесконечных последовательностей букв алфавита $A$ и распределение вероятностей на нём, соответствующее независимым появлением каждой буквы с распределением $p_1, \dots, p_k$. Получается вычислимое распределение вероятностей на $A^\infty$, и можно говорить о случайных по Мартин-Лёфу элементах $A^\infty$. (Соответствующая теория, которая была у нас для двухбуквенного алфавита, переносится безо всяких изменений.)

**Теорема 148.** Пусть $\omega$ — случайная по Мартин-Лёфу последовательность (относительно указанного распределения), $(\omega)_N$ — её начальный отрезок длины $N$. Тогда

$$ \lim \frac{KS((\omega)_N)}{N} = H, $$

где $H$ — шенноновская энтропия, то есть $H = \sum p_i (-\log p_i)$.
**238** Покажите, что для равномерного распределения это утверждение являет-ся непосредственным следствием критерия случайности (теорема 90, с. 167).

(Редкий случай, когда равномерность распределения действительно существен-на.)

В формулировке теоремы мы использовали простую колмогоровскую слож-ность $KS$, но это не имеет значения, поскольку разные варианты отличаются на $O(\log N) = o(N)$. В доказательстве будет удобнее использовать монотонную слож-ность.

◀ По критерию случайности Левина – Шнорра (теорема 90, с. 167) сложность близка к минус логарифму вероятности появления начального отрезка $(\omega)_N$. Веро-ятность берётся относительно рассматриваемого распределения вероятностей на $A^\infty$, и упомянутый минус логарифм равен $N \sum q_i (-\log p_i)$, где $q_i$ — частота появления $i$-й буквы в слове $(\omega)_N$. Остаётся воспользоваться тем, что для случайных после-довательностей справедлив усиленный закон больших чисел, который гарантирует, что $q_i$ стремится к $p_i$ при $N \to \infty$. ▶

Из доказательства видно, что отклонение удельной сложности (в расчёте на бу-кву) от энтропии складывается из трёх частей: дефект случайности (который имеет порядок $O(1)/N$), различие между простой сложностью и монотонной (порядок $O(\log N)/N$) и отклонение частот от вероятностей (оно даёт наибольший вклад; закон повторного логарифма в теории вероятностей говорит, что это отклонение чуть больше $O(\sqrt{N})/N$.

Мы предполагали, что числа $p_i$ вычислимы, поскольку в противном случае нельзя говорить о случайности по Мартин-Лёфу. Тем не менее и в этом случае можно утверждать, что множество тех последовательностей, у которых удельная сложность начальных отрезков не стремится к шенноновской энтропии соответству-ющего распределения, имеет меру $O$ (относительно данного распределении вероят-ностей).

**239** Докажите это. [Указание. При получении верхней оценки для сложности можно использовать не сами числа $p_i$, а приближения к ним (с некоторым запасом точности, скажем, с точностью до $1/N^2$ для слов длины $N$); при этом для зада-ния этих приближений потребуется дополнительная информация объёма $O(\log N)$. Нижняя же оценка вообще не использует алгоритмической природы $p_i$ (скажем, можно получить оценку для сложности с оракулом, при котором $p_i$ вычислимы).]

### 7.3.4. Вероятность отклонения сложности от энтропии

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

Пусть фиксировано некоторое распределение вероятностей $p_1, \dots, p_k$ на буквах алфавита А. Будем снова для простоты предполагать, что числа $p_i$ рациональны (или хотя бы вычислимы). Рассмотрим распределение вероятностей на $A^N$, считая
буквы во всех позициях независимыми. Для каждого слова, порождаемого таким
процессом, рассмотрим его сложность. Мы уже знаем (теорема 147), что среднее
значение этой сложности равно энтропии NH, где $H = \sum p_i (-\log p_i)$. Но интересно
знать также, как именно колеблется сложность вокруг этого среднего значения.

В самом простом (но, как мы увидим, совсем не типичном) случае, когда имеются две равновероятные буквы, распределение вероятностей равномерно на всех словах длины N. Мы знаем, что в этом случае все слова имеют сложность не больше $N + O(1)$, а подавляющее большинство слов (за вычетом доли $2^{-c}$) имеют сложность не меньше $N - c$, то есть сколько-нибудь большие отклонения сложности от энтропии весьма маловероятны.

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

Ключевое наблюдение здесь состоит в следующем. Для каждого слова х, помимо фиксированных вероятностей $p_i$, рассмотрим также фактические частоты $q_i(x)$ появления соответствующих букв в х. Оказывается, что с большой вероятностью сложность случайно выбранного (в соответствии с рассматриваемым распределением $p_i$) слова близка к $k(x) = N \sum_i q_i(x) (-\log p_i)$.
В самом деле, монотонная сложность по теореме 89 (с. 165) превосходит $k(x)$ не более чем на константу. С другой стороны, рассуждение при доказательстве теоремы Левина-Шнорра (с. 167, лемма 1) показывает, что вероятность события $KM(x) < k(x) - c$ (в соответствии с рассматриваемым нами распределением вероятности на словах длины $N$) не превосходит $2^{-c}$ для любого с.

Таким образом, вопрос о распределении сложностей сводится к хорошо известному в теории вероятностей вопросу о распределении частот. Известно (теорема Муавра-Лапласа), что оно близко к нормальному (гауссовскому); математическое ожидание частоты есть вероятность, а среднеквадратическое отклонение убывает пропорционально $1/\sqrt{N}$. По сравнению с таким отклонением разницей порядка $O(\log N)$ (различные виды сложности, использование $N$ в качестве условия и т.д.) можно пренебречь. Сказанное при некотором уточнении превращается в доказательство следующей теоремы:

**Теорема 149.** Пусть фиксирована случайная величина $\xi$ с к значениями. Для любого положительного $\epsilon > 0$ существует такое число $c$, что при всех $N$ вероятность события $NH(\xi) - c\sqrt{N} < KS(x) < NH(\xi) + c\sqrt{N}$, если все буквы слова х независимы и распределены как $\xi$, не меньше $1 - \epsilon$.

Строго говоря, наши рассуждения использовали вычисливость чисел $p_i$. Но от этого предположения можно избавиться, если заменить числа $p_i$ достаточно точными приближениями (скажем, с точностью до $1/N^2$, что требует $O(\log N)$ дополнительных битов).

7.3.5. Теорема Шеннона о кодировании

Доказанное нами утверждение об отклонении сложности от энтропии является естественным переводом на язык теории сложности известных результатов Шеннона о длине кода, который позволяет передавать блоки из $N$ независимых случайных символов с данным распределением с малой вероятностью ошибки.
Пусть вновь $\xi$ — случайная величина с k значениями (буквами алфавита А) и некоторым распределением. Пусть N — некоторое число, а $\xi^N$ — случайная величина со значениями в $A^N$, у которой буквы в каждой позиции распределены как $\xi$ и независимы. Мы хотим кодировать значения случайной величины m-битовыми словами по схеме рис. 7.3.

<figure><img src="image_22.png" /><figcaption>Рис. 7.3. Кодирование величины $\xi^N$ с помощью m битов.</figcaption></figure>

Здесь в качестве кодера рассматривается произвольное отображение множества $A^N$ в множество $\mathbb{B}^m$ двоичных слов длины m, а в качестве декодера — произвольное отображение $\mathbb{B}^m$ в $A^N$. Говорят, что происходит ошибка, если выходное слово в алфавите А не равно входному (значению величины $\xi^N$). Вероятность ошибки измеряется относительно описанного распределения случайной величины $\xi^N$. Нас интересует, при каких m и $\varepsilon$ существует код длины m с вероятностью ошибки не более $\varepsilon$. Начнём со следующего очевидного замечания:

**Теорема 150.** Такой код существует тогда и только тогда, когда $2^m$ наиболее вероятных значений случайной величины $\xi^N$ имеют суммарную вероятность не меньше $1 - \varepsilon$.

◀ В самом деле, при кодировании m битами weka-код сопровождается произвольным отображением $2^m$ значений, но не больше двух битов. Ясно, что вероятность ошибки будет минимальной, если в качестве этих $2^m$ значений выбрать $2^m$ наиболее вероятных значений. ▶

В следующей теореме алфавит А и величина $\xi$ фиксированы.

**Теорема 151.** Для всякого $\varepsilon > 0$ существует такое число c, что:

(а) для $\xi^N$ существует код длины не больше $NH(\xi) + c\sqrt{N}$ с вероятностью ошибки не больше $\varepsilon$;

(б) любой код длины не больше $NH(\xi) - c\sqrt{N}$ для $\xi^N$ имеет вероятность ошибки не меньше $1 - \varepsilon$ (вероятность правильной передачи не больше $\varepsilon$).

◀ (а) Мы знаем, что при подходящем с значение случайной величины $\xi^N$ имеет сложность менее $m = NH(\xi) + c\sqrt{N}$ с вероятностью $1 - \varepsilon$. Поэтому для таких значений можно использовать кратчайшие описания (в смысле колмогоровской сложности) в качестве кодов. (Заметим, что в теореме ничего не говорится про алгоритм кодирования, нам важно лишь существование кода. Формально говоря, в качестве закодированных сообщений у нас выступают слова длины меньше m, но их менее $2^m$ штук и можно их заменить на слова длины m.)

(б) Здесь нам понадобится небольшая хитрость. Если существует код указанной длины с указанной вероятностью ошибки, то можно построить такой код эффективно (воспользовавшись предыдущей теоремой, или просто полным перебором) и рассматривать декодирующую функцию этого кода как способ условного описания (при известных параметрах $p_i$ и $N$). Поэтому все значения величины $\xi^N$, которые расколдируются правильно, имеют (условную — относительно указанных
параметров) сложность не более $NH(\xi) - c\sqrt{N} + O(\log N)$ (последний член соот-ветствует сложности параметров и поглощается при увеличении константы $c$). По предыдущей теореме (при подходящем $c$) вероятность этого не превосходит $\varepsilon$. ►

**240** Как и раньше, в этом рассуждении предполагается, что мы знаем числа $p_i$ точно, и если они невычислимы, возникают дополнительные трудности. Пока-жите, как можно исправить это рассуждение, заменив $p_i$ на их достаточно точные приближения.

**241** Сформулируйте и докажите аналогичным способом теорему об условном кодировании и условной энтропии. [Указание. Пусть имеются две зависимые служащие величины $\xi$ и $\eta$, проводится $N$ независимых испытаний, значение величины $\eta^N$ известно и отправителю, и получателю, и отправитель хочет передать $m$ битов так, чтобы получатель смог восстановить значение величины $\xi^N$. При каких $m$ это возможно, а при каких нет?]
# 8. Некоторые приложения

## 8.1. Бесконечность множества простых чисел

Начнём с совсем «игрушечного» применения: докажем, что множество простых чисел бесконечно.

Пусть это не так и существует всего $m$ различных простых чисел $p_1, \dots, p_m$. Тогда любое целое число $x$, разлагаясь на простые множители, представляется в виде

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

и тем самым может быть задано набором степеней $k_1, \dots, k_m$. Каждое из чисел $k_i$ не превосходит $\log x$ (основания степеней не меньше 2) и потому имеет сложность не более $O(\log \log x)$ (двоочная запись содержит $O(\log \log x)$ битов). Поскольку $m$ фиксировано, то сложность набора $\langle k_1, k_2, \dots, k_m \rangle$ есть $O(\log \log x)$ и потому сложность любого числа $x$ (которое алгоритмически получается из этого набора) есть $O(\log \log x)$. А для «случайного» $n$-битового числа $x$ сложность примерно равна $n$, а не $O(\log n)$, как получается по этой формуле (логарифм $n$-битового числа не превосходит $n$).

Можно ли считать это «честным» применением колмогоровской сложности? Скептик скажет, что здесь всего лишь производится обычный подсчёт числа возможностей (counting argument, как говорят): если существует лишь $m$ различных простых чисел, то различных чисел от 1 до $x$ существует не более $(\log x)^m$, поскольку каждое такое число задаётся показателями степеней при простых множителях, и каждый показатель меньше $\log x$. После чего мы приходим к противоречию, поскольку $x > (\log x)^m$ при больших $x$.

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

К этому обсуждению мы ещё вернёмся, разобрав другие примеры.

## 8.2. Перенос информации по ленте

Следующий пример тоже модельный — мы докажем, что копирование слова длины $n$ на одноленточной машине Тьюринга требует (в худшем случае) не менее $\varepsilon n^2$ шагов. Этот классический результат был получен в 1960-е годы с помощью так
называемого «метода следов»; наше доказательство является переводом классического на язык колмогоровской сложности. (Мы предполагаем известными основные понятия, связанные с машинами Тьюринга; см, например, [175]).

Пусть на ленте машины Тьюринга выделена «буферная зона» некоторого размера $b$; нас интересует скорость переноса информации через эту буферную зону, скажем, слева направо, из области $L$ в область $R$ (рис. 8.1).

<figure><img src="image_23.png" /><figcaption>Рис. 8.1. Буферная зона размера $b$.</figcaption></figure>

Предположим, что в некоторый момент ленты буферная область и $R$ пусты, а область $L$ содержит произвольную информацию. Нас интересует, какова может быть сложность слова $R$ через $t$ шагов после этого. Мы докажем, что она не больше $(t \log m)/b + O(\log t)$, где $m$ — число состояний машины Тьюринга, а $b$ — ширина буферной зоны. В самом деле, каждое из $m$ состояний машины несёт $\log m$ битов информации, и за шаг информация переносится на одну клетку, а перенос её на $b$ клеток требует в $b$ раз больше времени.

Осталось лишь уточнить формулировку и доказательство.

**Теорема 152.** Пусть фиксирована машина Тьюринга с состояниями. Тогда существует такая константа $c$, что для любого $b$ и для любого вычисления с буферной зоной $b$ (вначале эта зона и лента справа от неё пусты, головка машины слева от зоны) сложность правой части ленты $R(t)$ после $t$ шагов вычисления не превосходит

$$ \frac{t \log m}{b} + 4 \log t + c. $$

◀ Проведём границу где-нибудь посередине буферной зоны, и при каждом пересечении границы головкой машины Тьюринга слева направо (при «выезде за границу») будем записывать, в каком состоянии она её пересекла (мечта ЧК-ГБ). Записанная последовательность состояний называется следом машины. Зная след, можно восстановить работу машины справа от границы (без использования информации о ленте слева от границы). В самом деле, надо искусственно поместить машину в первое состояние, указанное в следе, и выпустить её за границу; по возвращении перевести её во второе состояние следа и снова выпустить и так далее. При этом за границей машина будет вести себя так же, как и раньше (ведь ничего, кроме состояния, при пересечении границы у неё нет). В частности, в некоторый момент $t'$ правая часть ленты будет содержать $R(t)$. При этом $t'$ не превосходит $t$, хотя может быть и меньше (поскольку время, проведённое машиной слева от границы, теперь не учитывается). Таким образом, можно алгоритмически восстановить $R(t)$, зная след, $t'$, а также расстояние $b'$ от границы до начала зоны $R$. Поэтому найдётся такая константа $c$ (зависящая от машины, но не от $b$ и $t$), что для любого
следа S

$$KS(R(t)) \le l(S) \log m + 4 \log t + c$$

(мы умножили длину $l(S)$ следа $S$ на $\log m$, поскольку след является словом в $m$-буквенном алфавите и на каждую букву приходится $\log m$ битов; приписывание к нему чисел $b'$ и $t'$ (в самоограниченной записи) требует не более $2 \log b + 2 \log t$ битов, причём можно считать, что $t > b$ (иначе $R$ пуста, головка туда не дошла); константа $c$ возникает при переходе к оптимальному способу описания).

Это неравенство верно для любого начального содержимого части $L$ и для любого положения границы: если теперь для данного $L$ взять самый короткий из следов, то его длина меньше $t/b$ (всего разных положений границы $b+1$, и в каждый момент пересечение происходит лишь в одном месте, так что сумма длин следов не больше $t$). Получаем требуемое неравенство. ►

**242** Покажите, что оценку теоремы можно улучшить, заменив $b$ в знаменателе на $2b$. [Указание. Въезд суммарно требует почти столько же шагов, сколько и выезд.]

Теперь сразу же получается квадратичная оценка для задачи копирования.

Пусть одноленточная машина $M$ копирует любое входное слово: если вначале на ленте написано слово $x$ из нулей и единиц, а дальше лента пуста, то в конце работы справа от $x$ появляется его копия, и на ленте написано $xx$.

**Теорема 153.** Существует такая константа $\varepsilon > 0$, что для любого $n$ существует слово длины $n$, копирование которого с помощью $M$ занимает не менее $\varepsilon n^2$ шагов.

◀ Будем для простоты считать, что $n$ чётно, и возьмём в качестве $x$ слово, у которого вторая половина $u$ имеет сложность не меньше длины (то есть $n/2$). При меним теорему о скорости переноса информации, считая буферной зоной участок длины $n/2$ справа от $x$ (рис. 8.2).

<figure><img src="image_24.png" /><figcaption>Рис. 8.2. Буферная зона при копировании.</figcaption></figure>

Пусть копирование заняло $t$ шагов, тогда сложность зоны $R$ после этого не меньше $n/2$; с другой стороны, она не превосходит $t \log m/b + 4 \log t + c$ по доказанной теореме, где $b$ — ширина буферной зоны, то есть $n/2$. Получаем, что

$$\frac{n}{2} \le \frac{t \log m}{n/2} + 4 \log t + c.$$
Без ограничения общности считаем, что $t < n^2$ (иначе всё и так хорошо) и заменяем $4 \log t$ на $8 \log n$. Получаем, что

$$t \ge \frac{n^2}{4 \log m} - O(n \log n).$$

Второй член мал по сравнению с первым при больших $n$ (и формально можно распространить неравенство на все $n$ за счёт уменьшения коэффициента при $n^2$). ►

Насколько существенна в этом доказательстве колмогоровская сложность? Скептик может вновь сказать, что по существу мы просто оценивали число слов, которые можно скопировать за данное время, используя тот факт, что разные слова должны давать разные следы (иначе справа от границы поведение машины было бы одно и то же). Действительно, именно так и выглядело первоначальное доказательство этой оценки (уточним, что в первоначальных работах рассматривалось не копирование, а распознавание симметрии, но вся техника та же самая). Насколько идея этого доказательства становится понятнее при переводе его на язык колмогоровской сложности — вопрос вкуса.

Многие оценки в теории сложности вычислений могут быть доказаны аналогичным образом, когда в качестве «трудного случая» рассматривается слово максимальной сложности в некотором классе и затем показывается, что если бы оценка не соблюдалась, то это слово имело бы меньшую сложность. Много таких приложений (со ссылками на оригинальные работы) приведено в книге Ли и Витаньи [85], которые сами сыграли большую роль в развитии этого метода (называемого *In-compressibility method*). Отметим, что во многих случаях оценка впервые была доказана как раз с использованием колмогоровской сложности.

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

### 8.3. Конечные автоматы с несколькими головками

Конечный автомат с $k$ головками отличается от обычного (с которым, как мы предполагаем в этом разделе, читатель знаком) тем, что вместо одной читающей головки он имеет $k$ односторонних (движущихся слева направо) читающих головок. В начальный момент $k$ читающих головок видят первый (крайний слева) символ входного слова. На каждом шаге, в зависимости от состояния автомата и от $k$ символов, читаемых $k$ головками, автомат меняет своё состояние и продвигает некоторые из $k$ головок (не менее одной) вправо, после чего процесс повторяется. Вслед за словом на ленте записан специальный символ конца слова; работа автомата заканчивается, когда все головки попадают на этот символ. Автомат допускает слово, если по окончании работы он находится в заключительном состоянии. Множество всех слов, допускаемых автоматом, называется языком, распознаваемым этим автоматом.
Будем говорить, что пара головок автомата *М* проверила слово *w*<sub>i</sub>, если при работе автомата *М* на данном слове был момент, когда эти головки находились внутри левой и правой колпии слова *w*<sub>i</sub>. (Говоря о парах, мы имеем в виду неупорядоченные пары с различными элементами.) Ключевое наблюдение: никакая пара головок не может проверить два разных слова. В самом деле, если она проверила слово *w*<sub>i</sub>, то до этого левая головка читала слова с номерами, меньшими *i*, а правая — с большими, а после этого наоборот.

По предположению $m > C_k^2$; поэтому существует некоторое слово $w_i$, не проверенное ни одной парой головок. Покажем, что либо это слово проще, чем нужно, либо одну из его колий можно изменить незаметно для автомата *М* (тем самым дискредитировав этот автомат).

Будем наблюдать за работой автомата *М* на слове *W*, обращая особое внимание на те моменты, когда одна из головок автомата входит в слово *w*<sub>i</sub> (в любую из колий) или выходит из него, и записывать состояние автомата в эти моменты, а также передвижение головок (откуда и куда они переместились). Полученный протокол *P* имеет сложность *O*(log *N*) (константа зависит от *k*, *m* и от числа состояний автомата, но не от *N*), поскольку моментов входа и выхода не более 4к (по четыре для каждой головки), и в каждый момент надо записать состояние автомата и положение всех головок, что требует *O*(log *N*) битов.

Покажем, что (если автомат *М* распознаёт *L*<sub>m</sub>) слово *w*<sub>i</sub> восстанавливается однозначно по всем остальным словам *w*<sub>j</sub> с *j*≠*i* и протоколу *P*. В этом случае сложность слова *w*<sub>1</sub>...*w*<sub>m</sub> не превосходит (*m* − 1)*N* (число битов в остальных словах) плюс *O*(log *N*) (число битов в протоколе) плюс *O*(1), что меньше *mN* при больших *N*, и полученное противоречие завершает доказательство.

Восстанавливать будем так: подставляя по очереди всевозможные слова *w* einer der Dliны на место *w*<sub>i</sub> (при тех же *w*<sub>j</sub> с *j*≠ *i*), мы запускаем автомат *М* и смотрим, не получился ли протокол *P*. При этом возможны разные случаи.

(1) Если хотя бы при одном *w* автомат *М* не допустит соответствующего слова, он заведомо неправильный.

(2) Автомат *М* допускает все такие слова, при этом протокол *P* встречается только однажды, при *w* = *w*<sub>i</sub>. (В этом случае *w*<sub>i</sub> восстанавливается по *P* и остальным словам.)

(3) Автомат *М* допускает все такие слова, при этом протокол *P* встречается и при некотором *w* ≠ *w*<sub>i</sub>. Покажем, что в этом случае автомат *М* допускает неправильное слово (не из *L*<sub>m</sub>), а именно слово *W*', в котором в левой половине записано *w*<sub>i</sub>, а в правой на месте *w*<sub>i</sub> стоит слово *w*.

В самом деле, у нас есть два допускающих поведения автомата *М*: когда с обеих сторон *w*<sub>i</sub> и когда с обеих сторон *w*. Разрежем каждое из них на отрезки по тем моментам, когда одна из головок входит или выходит из *w*<sub>i</sub> (или *w*). Положения всех головок в эти моменты, а также состояния автомата, зафиксированы в протоколе *P*, и потому одни и те же в обоих случаях. (Сами моменты времени могут быть различны, поскольку их мы — хотя могли бы — не включили в протокол.) Поэтому можно склеивать отрезки поведения автомата для двух разных случаев; покажем, что это можно сделать так, чтобы в левой половине было *w*<sub>i</sub>, а в правой *w*.
По предположению в ходе обработки слова W никакая пара головок одновременно не попадает в левую и правую копии слова $w_i$; поскольку прохождение границы фиксируется в протоколе, это же верно и после замены $w_i$ на w. Поэтому для каждого отрезка протокола есть три возможности: (а) в левой копии есть головка; (б) в правой копии есть головка; (в) ни то, ни другое. Если теперь для случая (а) брать кусок поведения автомата M на слове W, для случая (б) брать кусок поведения на изменённом слове (когда $w_i$ заменено на w), а для случая (в) брать любой из двух вариантов (они совпадают), то получится работа автомата M на смешанном слове $W'$, и потому автомат допускает $W'$ в противоречии с предположением. ►

## 8.4. Усиленный закон больших чисел

Усиленный закон больших чисел был доказан нами в разделе 3.2 (теорема 27, с. 66) без использования колмогоровской сложности (прямым подсчётом). Подробно был разобран случай равномерной меры: в этом случае закон утверждает, что множество тех последовательностей $\omega = \omega_0\omega_1\dots$, у которых предел частот

$$p_n = \frac{\omega_0 + \omega_1 + \dots + \omega_{n-1}}{n}$$

при $n \to \infty$ существует и равен 1/2, имеет меру 1 относительно равномерной меры на пространстве $\Omega$. Другими словами, дополнение этого множества (те последовательности, где предел не существует или не равен 1/2), является нулевым. Впоследствии, в теореме 32 (с. 78), мы установили, что это нулевое множество является и эффективно нулевым, откуда заключили, что для всех случайных по Мартин-Лёфу последовательностей предел частот равен 1/2 (теорема 33, с. 78).

Однако можно действовать и в другом направлении. А именно, можно сначала доказать, что для всех случайных по Мартин-Лёфу последовательностей предел частот равен 1/2, используя критерий случайности в терминах сложности (теорема 90, с. 167). Этот критерий говорит, что для случайной по равномерной мере последовательности $\omega$ монотонная сложность её начального отрезка $(\omega)_n$ длины $n$ равна $n + O(1)$. Из этого можно заключить, что частота единиц $p_n$ единиц в $(\omega)_n$ стремится к 1/2. В самом деле, по теореме 146, сложность (обычная или монотонная, разница между ними логарифмическая) слова $(\omega)_n$ не превосходит $nh(p_n, 1-p_n) + O(\log n)$, и потому величина $h(p_n, 1-p_n)$ стремится к 1 при $n \to \infty$ (разница между ними не превосходит $O(\log n)/n$). Отсюда и из графика рис. 3.1 (с. 67) можно заключить, что $p_n \to 1/2$ при $n \to \infty$ для любой случайной последовательности, а такие последовательности образуют множество меры 1.

Возникает вопрос, является ли это рассуждение действительно новым или просто мы повторили по существу те же аргументы на несколько другом языке? Скорее второе: если вспомнить, как доказывалась теорема 146, то видно, что там использовалась та же оценка с формулой Стирлинга, что и в прямом доказательстве закона больших чисел. (Другое рассуждение, с оценкой через логарифм меры по теореме 89, также имеет прямой перевод в терминах оценок вероятностей, который приводился нами в разделе 3.2, после доказательства теоремы 27.)
Что же мы выигрываем от перехода к колмогоровской сложности? Можно указать несколько преимуществ. Во-первых, можно расширить класс последовательностей, для которых справедлив усиленный закон больших чисел:

**Теорема 155.** Пусть последовательность $\omega$ такова, что $KS((\omega)_n) = n + o(n)$. Тогда последовательность частот единиц в её начальных отрезках стремится к $1/2$.

### Доказательство аналогично: $h(p_n, 1 - p_n)$ по прежнему есть $1 + o(1)$.

Во-вторых, мы можем не ограничиваться утверждением $p_n \to 1/2$, а оценивать скорость этой сходимости. В теории вероятностей одна из таких оценок даётся законом повторного логарифма; этот закон выполняется для последовательностей, случайных по Мартин-Лёфу (как доказал Вовк [182]). Следуя Вовку, приведёмическое доказательство верхней оценки в этом законе, использующее колмогоровскую сложность.

**Теорема 156.** Пусть $\omega$ — последовательность, случайная по Мартин-Лёфу относительно равномерной меры, $p_n$ — частота единиц в её начальном отрезке длины $n$. Тогда, каково бы ни было $\varepsilon > 0$, неравенство

$$|p_n - 1/2| \le (1 + \varepsilon) \sqrt{\frac{\ln \ln n}{2n}}$$

выполнено для всех достаточно больших $n$.

### Посмотрим, какую оценку даёт нам (описанное выше) использование колмогоровской сложности. Мы знаем, что

$$n - O(1) \le KM((\omega)_n) \le nh(p_n, 1 - p_n) + O(\log n),$$

откуда

$$h(p_n, 1 - p_n) \ge 1 - O(\log n/n).$$

Функция

$$p \mapsto h(p, 1-p) = p(-\log p) + (1-p)(-\log(1-p))$$

имеет максимум в точке $p = 1/2$, при этом вторая производная в точке максимума отлична от нуля (и равна $-4/\ln 2$). Поэтому по формуле Тейлора получаем, что

$$h(1/2 + \delta, 1/2 - \delta) = 1 - \frac{2}{\ln 2} \delta^2 + o(\delta^2)$$

при $\delta \to 0$. Следовательно, для $\delta_n = p_n - 1/2$ имеем

$$\delta_n^2 = O(\log n/n),$$

то есть

$$|p_n - 1/2| = O\left(\sqrt{\frac{\log n}{n}}\right).$$

Это уже кое-что, хотя до нужной нам оценки ещё далеко. (Заметим в скобках, что и в теории вероятностей оценка с повторным логарифмом была получена не
сразу: сначала Хаусдорф (1913) доказал оценку $O(n^\varepsilon/\sqrt{n})$, затем Харди и Литлвуд (1914) её улучшили, заменив $n^\varepsilon$ на $\sqrt{\log n}$, затем Штейнгауз (1922) доказал оценку $(1+\varepsilon)\sqrt{(2\ln n)/n}$, и лишь потом Хинчин (1924) получил более сильную оценку доказываемой нами теоремы 156, заменив логарифм на повторный логарифм. Так что пока что мы находимся на уровне Харди и Литлвуда.)

Посмотрим, как можно улучшить верхнюю оценку для $KM((\omega)_n)$. (Нижнюю оценку улучшать особенно некуда.) Она получалась сравнением $KM((\omega)_n)$ с логарифмом вероятности последовательности $(\omega)_n$ относительно бернуллиевой меры с параметром $p_n$. Этот логарифм был в точности равен $nh(p_n, 1-p_n)$, но сама бернуллиева мера зависела от $n$, и потому конструкция из доказательства теоремы 89 давала оценку с дополнительным членом, равным $KP(p_n)$ (мы должны начать с самоограниченного кода для $p_n$). При этом $KP(p_n)$ можно оценить как $(2+\varepsilon)\log n$, поскольку числитель и знаменатель дроби $p_n$ не превосходят $n$. Всё это вместе даст оценку

$$ \frac{2}{\ln 2} (p_n - 1/2)^2 \approx 1 - h(p_n, 1 - p_n) \le (2 + \varepsilon) \log n/n, $$

что по-прежнему недостаточно.

Что же ещё можно сэкономить? Заметим, что мы уже знаем, что $p_n$ достаточно близко к $1/2$: если знаменателем считать $n$, то числитель отклоняется от $n/2$ на величину чуть больше $\sqrt{n}$. Поэтому (при известном знаменателе) количество битов для описания числителя можно сократить примерно вдвое, и тогда вместо 2 в правой части будет 1,5. Но мы хотим большего.

Решающая идея состоит в следующем. Пусть для определённости $p_n = 1/2 + \delta_n > 1/2$. Будем вместо $p_n$ использовать для оценки монотонной сложности величину $1/2 + \delta'_n$, где $\delta'_n$ — приближение к $\delta_n$ снизу с небольшой (фиксированной) относительной погрешностью. Пусть, например, $0,9\delta_n < \delta'_n \le \delta_n$. Такое число $\delta'_n$ можно найти среди членов геометрической прогрессии $(0,9)^k$, и его сложность равна примерно $\log k$, то есть $\log(-\log \delta_n / \log 0,9) = \log(-\log \delta_n) + c$. При этом, если $\delta_n < 1/\sqrt{n}$, то доказывать нечего, поэтому сложность $\delta_n$ можно оценить как $(1+\varepsilon)\log \log n$ (при сколь угодно малом $\varepsilon$ и достаточно больших $n$).

Это хорошо, но есть и ухудшение. А именно, вместо $h(p_n, 1-p_n)$ получается более сложное выражение

$$ p_n(-\log p'_n) + (1-p_n)(-\log(1-p'_n)), $$

где $p'_n = 1/2 + \delta'_n$; можно сказать, что фактические частоты нулей и единиц в $(\omega)_n$ равны $p_n$ и $1-p_n$, но при «кодировании» используются не они, а приближённые (и упрощённые) $p'_n$ и $1-p'_n$. Ясно, что это выражение лишь увеличится, если заменить в нём $p_n$ на $p'_n$ (поскольку $p_n > p'_n > 1/2$, вторая скобка с логарифмом больше первой, и увеличение её веса за счёт первой увеличивает всю сумму).

В итоге получаем оценку

$$ n - O(1) \le nh(p'_n, 1 - p'_n) + (1 + \varepsilon) \log \log n $$

для любого $\varepsilon > 0$ (при достаточно больших $n$) и отсюда, как и раньше, получаем

$$ \delta'_n \le (1 + \varepsilon) \sqrt{\ln 2 \cdot \log \log n / 2n}. $$
Оценка для «истинного» $\delta_n$ лишь ненамного больше (в $1/0,9$ раза в нашем примере); поскольку вместо $0,9$ можно было взять сколь угодно близкое к единице число, получаем искомое утверждение (множитель $\ln 2$ превращает первый логарифм в натуральный, а второй можно заменить на натуральный, поскольку это поглощается множителем $(1 + \varepsilon)$). ►

**243** Приведённое доказательство теоремы 156 не полностью использует случайность последовательности $\omega$: покажите, что оно проходит для последовательностей, у которых $n - KM((\omega)_n) = o(\log \log n)$.

### 8.5. Последовательности без запрещённых подслов

#### 8.5.1. Запрещённые и простые слова

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

**Теорема 157.** Пусть $\alpha < 1$ — некоторое положительное действительное число. Пусть для каждого $n$ некоторые двоичные слова, общим числом не более $2^{\alpha n}$, объявлены запрещёнными. Тогда существуют число $c$ и бесконечная последовательность нулей и единиц, не содержащая запрещённых подслов длиннее $c$.

Напимер, можно считать запрещёнными слова, у которых (простая) колмогоровская сложность меньше $\alpha n$, их как раз не больше $2^{\alpha n}$. Получаем такое следствие («лемма Левина», [39]):

**Теорема 158.** Пусть $\alpha < 1$ — некоторое положительное действительное число. Тогда существует бесконечная последовательность нулей и единиц, в которой все подслова достаточно большой длины $n$ имеют сложность не меньше $\alpha n$.

Поучительно сравнить это утверждение с критерием случайности для равномерной меры (теорема 94, с. 172). Там речь шла лишь о начальных отрезках, а не всех подсловах, зато монотонная сложность была не меньше $n - O(1)$ (для обычной сложности это даёт оценку $n - O(\log n)$). Как показывает следующая задача, для всех подслов (а не только для начал) такую более сильную оценку получить нельзя. (Это и не удивительно: в настоящей случайной последовательности должны появляться все подслова, в том числе и малой сложности.)

**244** Для всякой последовательности $\omega$ нулей и единиц найдётся $\alpha < 1$ и бесконечно много различных подслов, у которых отношение сложности к длине не больше $\alpha$. [Указание. Рассмотрим два случая. Если последовательность содержит в качестве подслов все двоичные слова, то доказывать нечего. Если же в неё не входит некоторое слово $i$ длины $k$, то разбивая длинные слова на блоки длины $k$ и кодируя их оптимальным образом (блок $i$ никогда не встречается и код ему не нужен), мы получаем отношение сложности к длине не больше $(\log(2^k - 1))/k$.]

Доказательство теоремы 157 происходит в два этапа. Сначала мы докажем её частный случай, теорему 158, а затем удивительным образом окажется, что из него следует и общий случай.
◀ Для доказательства теоремы 158 рассмотрим произвольное $\beta$, для которого $\alpha < \beta < 1$. Пользуясь теоремой 71 (с. 129), найдём число $N$ с таким свойством: ко всякому слову $x$ можно приписать $N$ битов так, чтобы префиксная сложность возросла от этого не менее чем на $\beta N$. Будем использовать это свойство много-кратно, начав с пустого слова: получится бесконечная последовательность блоков длины $N$, от добавления каждого блока префиксная сложность возрастает как мин-имум на $\beta N$. Отсюда следует, что сложность любой группы из подряд идущих $k$ блоков не меньше $\beta kN - O(1)$. В самом деле, от добавления этой группы слож-ность растёт не менее чем на $\beta kN$, а $KP(xy) \le KP(x) + KP(y) + O(1)$. Отсюда следует, что и для любого подслова $u$ (не обязательно начинающегося и кончаю-щегося на границе блока) сложность не меньше $\beta l(u) - O(1)$, поскольку измене-ние сложности и длины из-за граничных эффектов (обрезание по границе блока) есть $O(1)$. Остаётся вспомнить, что $\beta$ мы взяли (по сравнению с $\alpha$) с некоторым запасом, который покрывает и граничные эффекты, и разницу между обычной и префиксной сложностями. ▶

245 Проведите аналогичное рассуждение, используя обычную сложность вме-сто префиксной. [Указание. См. задачу 46 на с. 52.]

246 Докажите утверждение задачи 47 (с. 52), заменив в нём обычную слож-ность начальных отрезков на префиксную.

◀ Теперь докажем теорему 157; проще всего это сделать, если воспользоваться релятивизованным вариантом сложности. Будем считать, что множество $F$ запре-щённых слов дано нам в качестве оракула, то есть всем рассматриваемым алго-ритмам разрешается (в качестве внешней процедуры) узнавать про любое слово, запрещено оно или нет. Как обычно в теории алгоритмов, такая релятивизация ни-чему не мешает, и мы будем считать, что теорема 158 верна и для релятивизованной относительно $F$ сложности.

Заметим, что при таком оракуле все запрещённые слова длины $n$ имеют слож-ность (при известном $n$) не более $\alpha n + O(1)$, поскольку каждое слово может быть задано своим порядковым номером в списке запрещённых слов. Поэтому безуслов-ная сложность запрещённого слова длины $n$ не больше $\alpha n + O(\log n)$, и достаточно взять последовательность, у которой нет длинных подслов с удельной сложностью меньше $\beta$ для некоторого $\beta > \alpha$. ▶

Любопытно, что при желании можно вывести теорему 157 из теоремы 158, не используя релятивизации (см. [137]). А именно, справедливо следующее утвержде-ние:

**Теорема 159.** Если для некоторого рационального $\alpha$ и некоторого множества $F$ запрещённых слов утверждение теоремы 157 не выполняется, то оно не выполняется и для некоторого разрешимого множества $F$.

Ясно, что для разрешимого множества $F$ релятивизация ничего не меняет и не нужна; ограничение рациональными $\alpha$ тоже, очевидно, несущественно.

◀ Пусть для некоторого $\alpha < 1$ и некоторого множества $F$ утверждение тео-ремы 157 неверно. Тогда для всякого $c$ можно указать множество $F_c$ с такими
свойствами:

(а) $F_c$ содержит только слова длиннее $c$;

(б) $F_c$ содержит не более $2^{\alpha k}$ слов длины $k$ (при любом $k$);

(в) всякая бесконечная последовательность содержит хотя бы одно подслово из $F_c$.

(В самом деле, можно в качестве $F_c$ взять множество всех слов из $F$, имеющих длину больше $c$.)

Обычное рассуждение (лемма Кёнига, компактность) показывает, что тогда и всякая достаточно длинная последовательность содержит хотя бы одно слово из $F_c$, и потому множество $F_c$ без ограничения общности можно считать конечным. Более того, его (точнее, какое-либо множество с указанными свойствами) можно найти перебором, так что оно вычислимо строится по $c$. (Переход к конечному множеству нужен, чтобы воспользоваться перебором.)

Построим теперь последовательность $c_i$, беря $c_{i+1}$ больше длин всех слов в множестве $F_{c_i}$. Объединение соответствующих множеств $F_{c_i}$ и будет разрешимым множеством, для которого не выполнено утверждение теоремы 157. ►

Обратите внимание на схему рассуждения: мы предполагали, что объект с непросторовым свойством существует, а затем замечали, что тогда можно перебором построить (возможно, другой) объект с таким свойством. Эта схема в той или иной форме ещё не раз нам встретится.

**247** Докажите, что если существует бесконечная вправо последовательность, не содержащая подслов из некоторого множества $F$, то существует и бесконечная в обе стороны последовательность, не содержащая подслов из $F$. [Указание. В силу компактности оба эти свойства равносильны тому, что существуют сколь угодно длинные конечные последовательности, не содержащие подслов из $F$.]

Дж. Миллер [106] предложил прямое доказательство теоремы 157, в котором искомая последовательность строится слева направо, при этом мы следим за тем, чтобы некоторая явно определяемая величина («уровень тревоги») оставалась небольшой.

Фиксируем множество запрещённых слов $F$. Пусть дано некоторое слово $x$ (уже построенное начало последовательности). Определим величину $w_c(x)$; чем она больше, тем мы ближе к появлению запрещённого слова. Здесь $c$ — некоторый числовой параметр, который впоследствии мы выберем чуть больше $1/2$. Для каждого возможного вхождения запрещённого слова $z \in F$, которое пересекается с $x$ (и совпадает на пересечении), мы считаем число $k$ недостающих (в $x$) битов и добавляем к $w_c(x)$ число $c^k$. (Таким образом, $w_c(x)$ есть сумма по всем $z \in F$ и всем возможным местам их вхождения.)

При $c = 1/2$ величина $w_c(x)$ имеет простой вероятностный смысл: математическое ожидание числа вхождений запрещенных слов, пересекающих $x$, если к $x$ справа добавить последовательность случайных битов. Из этой интерпретации ясно соотношение

$$w_{1/2}(x) = \frac{1}{2}w_{1/2}(x0) + \frac{1}{2}w_{1/2}(x1) - \sum_{z \in F} (1/2)^{l(z)}.$$
<figure><img src="image_25.png" /><figcaption>Рис. 8.3. Вхождение запрещённого слова z, часть битов которого уже есть в х, но недостаёт k битов, дает вклад $c^k$ в $w_c(x)$.</figcaption></figure>

В самом деле, с вероятностью $1/2$ мы начинаем с добавления бита 0, и с вероятностью $1/2$ добавляем бит 1. Надо учесть еще, что в правой части мы захватим и вхождения, примыкающие к х, но не пересекающие х, и их надо вычесть. Это равенство — комбинаторный подсчёт, который можно выполнить и при произвольном с, если в х нет запрещённых подслов, и получится

$$w_c(x) = cw_c(x0) + cw_c(x1) - \sum_{z \in F} c^{l(z)}.$$

Изначально (на пустом слове) значение $w_c$ равно нулю, а если в х уже встретилось запрещённое слово, то значение равно как минимум 1. Поэтому достаточно доказать, что можно поддерживать неравенство $w_c(x) < 1$, добавляя очередной бит. Для этого достаточно, чтобы

$$w_c(x0) + w_c(x1) = \frac{1}{c} \left( w_c(x) + \sum_{z \in F} c^{l(z)} \right)$$

было меньше 2 при $w_c(x) < 1$, что будет гарантировано, если $1 + \sum_{z \in F} c^{l(z)} < 2c$.

Для доказательства теоремы 157 осталось заметить, что сумму можно сделать сначала конечной, выбрав подходящее с (тем ближе к $1/2$, чем ближе $\alpha$ к единице), а затем сколь угодно малой (выбросив из $F$ слова малых длин).

**248** Покажите, что это рассуждение позволяет доказать эффективный вариант теоремы 157: если множество $F$ (в дополнение к условию теоремы) разрешимо, то можно построить вычислимую последовательность, не содержащую коротких слов из $F$.

Предыдущую задачу можно обобщить (как сообщил авторам К. Макарычев) на двусторонние последовательности и найти вычислимую двустороннюю последовательность с тем же свойством. (Рассуждение следует идее Миллера, но надо ввести два параметра — левый и правый, и следить за их поведением, когда добавляется несколько букв: надо, чтобы один сильно уменьшался, а другой не сильно увеличивался.) Другой способ, описанный в [136], использует эффективный вариант леммы Ловаса и обобщается на многомерный случай.

### 8.5.2. Лемма Ловаса

Мы показали, как от сложностного утверждения перейти к комбинаторному аналогу. В этом разделе мы будем двигаться и в обратную сторону, начав с комбинаторного утверждения (локальной леммы Ловаса) и выведя из него следствия, касающиеся колмогоровской сложности. Но вначале несколько общих слов.
**Вероятностные доказательства существования.** Часто существование объекта, удовлетворяющего некоторому набору условий, доказывают так: на множестве всех объектов вводят распределение вероятностей, и для каждого условия подсчитывают вероятность того, что оно будет нарушено. Если эти вероятности малы — настолько малы, что их сумма меньше 1, — то случайный объект удовлетворяет всем условиям с положительной вероятностью и потому искомый объект существует.

Свойство вероятностей, используемое в этом рассуждении: если вероятность события $A_i$ не больше $\varepsilon_i$, то вероятность объединения событий $A_1, \dots, A_n$ не больше $\Sigma \varepsilon_i$, а вероятность того, что не произойдёт ни одного из них, не меньше

$$1 - \varepsilon_1 - \varepsilon_2 - \dots - \varepsilon_n.$$

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

Если попытаться доказать теорему 157 с помощью такого рода подсчётов, то ничего не получится: вероятность обнаружить плохую строку в данной позиции действительно мала $(2^{(\alpha-1)n})$, но если позиций достаточно много, то сумма этих вероятностей уже станет больше единицы — а нам надо доказать существование последовательностей любой длины без плохих подслов. Спасительное наблюдение: если два участка случайной последовательности не пересекаются, то появления в них запрещённых подслов — независимые события.

**Случай независимых событий.** Для начала рассмотрим случай полностью независимых событий. Если события $A_i$ независимы, и вероятность $A_i$ равна $\varepsilon_i$, то вероятность того, что ни одно из $A_i$ не произойдёт, равна

$$(1 - \varepsilon_1) \cdot (1 - \varepsilon_2) \cdot \dots \cdot (1 - \varepsilon_n).$$

Отсюда, кстати, можно заключить, что это произведение больше $1 - \varepsilon_1 - \varepsilon_2 - \dots$ (вариант неравенства Бернулли).

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

Лемма Ловаса относится к промежуточной ситуации, когда событий слишком много (и потому не годится первая оценка), и они не все независимы (и потому не годится вторая оценка).

Пусть имеется $n$ событий $A_1, \dots, A_n$ и для каждого $i$ от 1 до $n$ фиксировано некоторое множество $N(i) \subset \{1, \dots, n\}$, не содержащее $i$. Его элементы будем называть соседями $i$. (Никаких условий симметрии не предполагается: вершина может не быть соседом своего соседа.)

Предположим, что событие $A_i$ независимо со всеми событиями, кроме себя и своих соседей (мы допускаем вольность речи и отождествляем событие $A_i$ с
индексом $i$). Здесь имеется в виду именно независимость от набора всех несоседних событий, а не от каждого из них в отдельности. Тогда справедлива такая оценка:

**Теорема 160** (локальная лемма Ловаса). Если для каждого $i$ выбрано положительное число $\varepsilon_i < 1$ и

$$ \mathrm{Pr}[A_i] \le \varepsilon_i \prod_{j \in N(i)} (1 - \varepsilon_j), $$

то вероятность того, что не произойдёт ни одного из событий $A_i$, не меньше

$$ (1 - \varepsilon_1) \cdot (1 - \varepsilon_2) \cdot \dots \cdot (1 - \varepsilon_n). $$

Таким образом, мы получаем в точности ту же оценку, что и для независимых событий, но условие сильнее: за каждое событие-соседа $j$, с которым независимости нет, мы расплачиваемся множителем $(1 - \varepsilon_j)$ в правой части.

▲ Доказательство леммы Ловаса довольно странно — в нём вроде бы ни в какой момент ничего нетривиального не происходит, но придумать или даже запомнить его не так просто. Поэтому начнём для тренировки с простых замечаний.

(а) Если $A$ и $B$ — два события, то

$$ \mathrm{Pr}[A | B] \le \frac{\mathrm{Pr}[A]}{\mathrm{Pr}[B]}. $$

В самом деле, по определению условная вероятность $\mathrm{Pr}[A | B]$ есть $\mathrm{Pr}[A \wedge B] / \mathrm{Pr}[B]$, а $\mathrm{Pr}[A \wedge B] \le \mathrm{Pr}[A]$. (Как обычно в логике, $\wedge$ означает «и».)

(б) Добавим всюду в предыдущем утверждение условие $C$ («релятивизация»). Получим

$$ \mathrm{Pr}[A | B \wedge C] \le \frac{\mathrm{Pr}[A | C]}{\mathrm{Pr}[B | C]}. $$

В доказательстве леммы Ловаса это будет использоваться в ситуации, когда $A$ и $C$ независимы и потому числитель есть $\mathrm{Pr}[A]$, а знаменатель не слишком мал.

Теперь можно уже доказать лемму Ловаса по индукции. Как обычно, для индуктивного рассуждения полезно усилить утверждение. Будем доказывать такие факты ($\neg$ означает отрицание, то есть переход к дополнению):

(1) для любого $i$ и для любых $p, q, \dots$ (отличных от $i$ и различных между собой) выполняется неравенство

$$ \mathrm{Pr}[A_i \mid \neg A_p \wedge \neg A_q \wedge \dots] \le \varepsilon_i; $$

(2) для любых непересекающихся множеств индексов $i, j, \dots$ и $p, q, \dots$ выполняется неравенство

$$ \mathrm{Pr}[\neg A_i \wedge \neg A_j \wedge \dots \mid \neg A_p \wedge \neg A_q \wedge \dots] \ge (1 - \varepsilon_i) \cdot (1 - \varepsilon_j) \cdot \dots $$

Заметим, что из первого утверждения следует второе, если слева от черты (среди $i, j, \dots$) только одно утверждение: если вероятность события при некотором
условии не больше $\varepsilon_i$, то вероятность его отрицания при том же условии не меньше $(1 - \varepsilon_i)$.

Более того, это рассуждение можно продолжить и для большего числа событий в левой части:

$$ \mathrm{Pr}[\neg A_i \wedge \neg A_j | \neg A_p \wedge \neg A_q \wedge \dots] = \mathrm{Pr}[\neg A_i | \neg A_j \wedge \neg A_p \wedge \neg A_q \wedge \dots] \cdot \mathrm{Pr}[\neg A_j | \neg A_p \wedge \neg A_q \wedge \dots]; $$

остаётся оценить каждый из сомножителей по (1).

С другой стороны, из второго утверждения можно вывести первое. Для этого разделим условия в (1) на две группы: входящие в $N(i)$ и не входящие в $N(i)$. (Здесь $i$ — номер события, стоящего в левой части.) Пусть $N$ и $F$ — конъюнкции отрицаний соответствующих условий (соседних и остальных). Тогда, следуя ранее описанной схеме, можно оценить вероятность так:

$$ \mathrm{Pr}[A_i | N \wedge F] \le \frac{\mathrm{Pr}[A_i | F]}{\mathrm{Pr}[N | F]} = \frac{\mathrm{Pr}[A_i]}{\mathrm{Pr}[N | F]}. $$

Знаменатель в предположении (2) не меньше, чем произведение скобок $(1 - \varepsilon_t)$ по всем $t \in N$, и остаётся посмотреть на предположение леммы, где при $\varepsilon_i$ как раз стоит множитель, не больший этого произведения. (Если первая группа условий пуста, то под $N$ следует понимать тривиально инстинное условие: знаменатель в этом случае равен 1 и неравенство следует из условия леммы, а предположение (2) при этом не используется.)

Остаётся лишь объяснить, почему взаимное сведение (1) к (2) и обратно не приводит к порочному кругу. Когда мы сводим (1) к (2) с помощью только что рассмотренной оценки, общее количество событий в используемом неравенстве (2) по крайней мере на единицу меньше общего количества событий в доказываемом неравенстве (1) — исчезает событие $A_i$. Обратное сведение (2) к (1), с которого мы начали, не увеличивает общего количества событий: общее количество событий в каждом из используемых неравенств (1) не больше общего количества событий в доказываемом неравенстве (2). ►

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

**249** В каждой клетке конечной ленты мы хотим написать число от 1 до $N$. При этом для каждой границы между клетками некоторые пары чисел $(l, r)$ запрещены, то есть нельзя, чтобы слева от границы стояло $l$, а справа $r$. Докажите, что если (для каждой границы) доля запрещённых пар среди всех пар (которых $N^2$) не больше $4/27$, то заполнение возможно. [Указание. Сопоставим каждой границе событие (запрещение пары для случайного набора чисел). Соседей у каждого события два, при $\varepsilon_i = \frac{1}{3}$ условие леммы выполняется.]

**250** Докажите аналогичный результат (даже с лучшими параметрами) без ссылки на лемму Ловаса: если множество плохих пар имеет меру меньше $1/4$, то существует заполнение без плохих пар. [Указание. В каждой позиции имеются более половины чисел, для которых допустимы более половины правых соседей, и более
половины чисел, для которых допустимы более половины левых соседей. Значит,
для хотя бы одного числа допустимы большинство соседей слева и большинство
соседей справа. Взяв это число, можно дописывать к нему справа и слева числа из
того же большинства (поскольку два множества, больших половины, обязательно
пересекаются).]

8.5.3. Лемма Ловаса и запрещённые слова

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

Будем считать, что биты последовательности равновероятны и независимы. По-
явление запрещённой последовательности длины $n$ в данной позиции (на данном
интервале $I$) имеет вероятность $2^{(\alpha-1)n}$, где $n$ — длина интервала. В качестве оцен-
ки в лемме Ловаса для этого события возьмём $2^{(\beta-1)n}$ для некоторого $\beta \in (\alpha, 1)$.
Надо подобрать $\beta$ так, чтобы выполнялось условие леммы Ловаса.

Соседями события на интервале $I$ являются события на интервалах $J$, которые перекрываются с $I$. Поскольку вероятности событий зависят от длины, при подсчётах удобно групшировать интервалы по длинам. Имеется $n + k - 1$ интервалов $J$ длины $k$, перекрывающихся с данным интервалом $I$ длины $n$. Для каждого из них в правой части оценки леммы Ловаса появляется множитель $(1 - 2^{(\beta-1)k})$, и всего получается

$$ (1 - 2^{(\beta-1)k})^{n+k-1}. $$

Теперь надо это перемножить по всем $k$, начиная с некоторого $N$ (если мы доказываем существование последовательности без плохих подслов короче $N$). Таким образом, для применения леммы Ловаса нам нужно, чтобы

$$ 2^{(\alpha-1)n} \le 2^{(\beta-1)n} \cdot \prod_{k \ge N} (1 - 2^{(\beta-1)k})^{n+k-1}. $$

(На самом деле в нашем подсчёте есть погрешность — при $n = k$ мы учитываем сам интервал в качестве соседа, но это в нашу пользу.) Нам достаточно очень грубой оценки: заменим $n + k - 1$ на $nk$, извлечём корень $n$-степени и используем неравенство Бернулли в правой части. Останется доказать, что

$$ 2^{\alpha-\beta} \le 1 - \sum_{k \ge N} k 2^{(\beta-1)k}. $$

Бесконечный ряд $\sum_k k 2^{(\beta-1)k}$ сходится при $\beta < 1$, а левая часть меньше 1 при $\alpha < \beta$, так что при достаточно большом $N$ неравенство выполняется.

(Таким образом, порядок выбора параметров такой: берём любое $\beta \in (\alpha, 1)$, а затем подбираем $N$. Затем применяем лемму Ловаса к словам длины не меньше $N$ и получаем, что существуют сколь угодно длинные конечные последовательности без запрещённых слов длины $N$ и более (оценки выполнены при любой длине последовательности). Наконец, по компактности получаем бесконечную последовательность.)
**251** Докажите двумерный аналог теоремы 157: можно заполнить бесконечную клетчатую бумагу нулями и единицами так, чтобы любой прямоугольник достаточно большой площади не был запрещённым. (Предполагаем, что для каждого прямоугольника площади $k$ выбрано не более $2^{\alpha k}$ запрещённых заполнений, где $\alpha < 1$ — некоторая константа.) [Указание: несложно провести аналогичные оценки.]

### 8.5.4. Запрещённые подпоследовательности

До сих пор мы говорили о запрещённых подсловах, то есть комбинациях подряд идущих битов. Это ограничение выглядит несколько искусственно. Более общая постановка вопроса, согласно [135], может быть такой: есть счётное число битовых переменных и некоторые ограничения; каждое ограничение запрещает конечному числу переменных принимать (одновременно) некоторые значения. Нас интересуют результаты такого типа: если ограничений «не слишком много», то они заведомо совместны (независимо от того, что конкретно запрещается).

На другом языке можно сказать, что мы хотим доказать выполнимость некоторой конъюнктивной нормальной формы (КНФ), то есть конъюнкции нескольких дизъюнктов (клауз). Например, в формуле

$$ (\neg a \lor b \lor c) \land (a \lor c \lor \neg d) \land \dots $$

первый дизъюнкт $(\neg a \lor b \lor c)$ запрещает комбинацию значений $a = 1, b = 0, c = 0$. Найти выполняющий набор значений (при котором формула истинна) означает удовлетворить всем ограничениям.

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

Начнём с обозначений. Пусть $\omega = \omega_0\omega_1\omega_2\dots$ — некоторая последовательность. Для произвольного конечного множества $F \subset \mathbb{N}$ индексов через $\omega(F)$ обозначим двоичное слово, составленное из членов последовательности с индексами в $F$ (в порядке возрастания индексов). Рассмотрим пару $(F, X)$, где $F$ — конечное множество индексов, а $X$ — двоичное слово, длина которого равна числу элементов в $F$. Последовательность $\omega$ запрещается парой $(F, X)$, если $\omega(F) = X$. Пары такого вида будем называть запрещениями, а число элементов в $F$ (длину слова $X$) — размером запрещения. Запрещение покрывает индексы, входящие в $F$. Теперь мы можем сформулировать и доказать такое утверждение [135]:

**Теорема 161.** Пусть дано действительное число $\alpha \in (0, 1)$ и множество запрещений $(F, X)$, при этом для любого индекса $i$ и числа $n$ имеется не более $2^{\alpha n}$ запрещений размера $n$, которые покрывают $i$. Тогда существует число $N$ и последовательность, не запрещённая ни одним из запрещений размера больше $N$.

◀ По соображениям компактности достаточно доказать утверждение для конечных последовательностей (для некоторого $N$, не зависящего от длины последовательности).
Событием будет нарушение запрещения. Вероятность такого события для запрещения размера $n$ есть $2^{-n}$. Применяя лемму Ловаса, выберем в качестве соответствующего $\epsilon_i$ для события размера $n$ значение $2^{-\beta n}$, где $\beta$ — некоторая константа, большая $\alpha$ (как мы увидим, годится любая).

Соседями запрещения будут запрещения, пересекающиеся с ним (покрывающие общее число). Для применения леммы Ловаса надо взять запрещение размера $n$ и проверить, что $2^{-n}$ не больше $2^{-\beta n}$, умноженного на произведение множителей $(1 - 2^{-\beta m})$ по всем запрещениям, пересекающимся с данным.

Произведение разделим на части, соответствующие возможным точкам пересечения. Всего таких возможных точек $n$. (Если в пересечении несколько точек, произвольно выберем одну из них.) Кроме того, в каждой части расклассифицируем сомножители по размерам. Тогда для данной точки и для данного размера $m$ получим не более $2^{\alpha m}$ сомнителей, каждый из которых есть $(1 - 2^{-\beta m})$. Дальше надо перемножить по всем $m$ и возвести в степень $n$ (поскольку частей $n$). Таким образом, нам надо проверить неравенство

$$2^{-n} \le 2^{-\beta n} \prod_{m>N} (1 - 2^{-\beta m})^{2^{\alpha m} n},$$

или (если убрать возведение в степень $n$)

$$2^{\beta-1} \le \prod_{m>N} (1 - 2^{-\beta m})^{2^{\alpha m}}.$$

По неравенству Бернулли это заведомо выполнено, если

$$2^{\beta-1} \le 1 - \sum_{m>N} 2^{\alpha m} 2^{-\beta m}.$$

Поскольку левая часть меньше 1, а убывающая геометрическая прогрессия

$$\sum_m 2^{(\alpha - \beta)m}$$

сходится, то при подходящем $N$ нужное неравенство выполнено. (Порядок выбора: сначала берём $\beta \in (\alpha, 1)$, затем выбираем $N$, глядя на сходящийся ряд, затем для любой длины последовательности применяем лемму Ловаса, и, наконец, ссылаемся на компактность.) ►

Другое доказательство теоремы 161, не ссылющееся на лемму Ловаса (а проводящее аналогичное ей рассуждение непосредственно), предложили Ан. А. Мучник и А. Л. Семёнов. Пусть фиксировано множество запрещений, удовлетворяющее предположениям теоремы; пусть $N$ — минимальный размер запрещений, входящих в это множество.

Для каждого конечного множества индексов $I \subset \mathbb{N}$ через $c(I)$ обозначим количество разрешённых расрасок $I$, то есть отображений $I$ в $\{0, 1\}$, которые не нарушают запрещений. (При этом рассматриваются только запрещения $(F, X)$ с $F \subset I$, поскольку вне $I$ отображение не определено и сравнивать его с запрещением нельзя.) Для пустого $I$ естественно положить $c(I) = 1$.
Выберем $\beta \in (\alpha, 1)$ и будем доказывать, что при добавлении одной новой точки к множеству $I$ величина $c(I)$ увеличивается в $2^\beta$ раз (в предположении, что $N$ достаточно велико). Отсюда будет следовать, что число разрешённых раскрасок на множестве размера $k$ не меньше $2^{\beta k}$ и уж заведомо положительно — нам нужно только это, но по индукции приходится доказывать более сильное утверждение.

Итак, пусть мы добавили к $I$ новую точку $i$, получив $I' = I \cup \{i\}$. Каждая разрешённая раскраска $I$ порождает две раскраски на $I'$ (для двух возможных знаковений в новой точке). Получаем $2c(I)$ раскрасок, но часть из них может быть запрещёнными и их надо вычесть. Кто может их запрещать? Поскольку раскраска на $I$ разрешена, то запрещение должно содержать $i$ в дополнение к некоторым точкам в $I$; пусть $K$ — множество этих точек, а $k$ — их количество. Сколько раскрасок нужно вычесть из $2c(I)$ из-за одного такого запрещения? Их не больше, чем разрешённых раскрасок $I \setminus K$, а по предположению индукции таковых не больше $c(I)/2^{\beta k}$. (В самом деле, если добавление точки увеличивает число разрешённых раскрасок по крайней мере в $2^\beta$ раз, то удаление одной точки уменьшает это число в то же число раз, а удаление $k$ точек уменьшает это число по крайней мере в $2^{\beta k}$ раз.) Теперь вычитаемое надо просуммировать по всем $k$ от $N-1$ до $I$, а для каждого $k$ по не более чем $2^{\alpha(k+1)}$ запрещениям, содержащим $i$ и $k$ элементов в $I$.

В итоге получаем оценку

$$c(I') \ge 2c(I) - \sum_{k=N-1}^{|I|} 2^{\alpha(k+1)} \frac{c(I)}{2^{\beta k}},$$

которую можно ослабить (заменяя $2^\alpha$ на 2 и продолжая суммирование до бесконечности) до

$$c(I') \ge 2c(I) \left( 1 - \sum_{k \ge N-1} \frac{2^{\alpha k}}{2^{\beta k}} \right).$$

Поскольку ряд в правой части сходится, то при достаточно большом $N$ множитель в скобках не меньше $2^{\beta-1}$, и индуктивное рассуждение завершается. (Заметим, что мы применяли предположение индукции лишь к множествам размера меньше $|I|$, так что порочного круга не получается.)

### 8.5.5. Сложные подпоследовательности

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

Можно ли надеяться, что сложность любой подпоследовательности достаточно большой длины $m$ не меньше $\alpha m$ для некоторого $\alpha < 1$ (как это было для подслов)? Очевидно, нет: ведь можно включить в подпоследовательности те индексы, где стоят ни у (или единицы). Но при этом сложность перейдёт в сложность набора индексов.

И действительно, мы уже встречали подобное утверждение в задаче 145 (для равномерной меры — пункт (д) теоремы 94, с. 172): если последовательность $\omega$
случайна в смысле Мартин-Лёфа по равномерной мере, то

$$KP(F, \omega(F)) \ge |F| - c$$

для некоторого с и для всех конечных множеств F.

Но это не то, к чему мы стремимся (это скорее аналог теоремы о том, что у случайной последовательности сложные начальные отрезки, а не существования последовательности со сложными подсловами). Нас будет интересовать другое утверждение [135]:

**Теорема 162.** Пусть $\alpha \in (0, 1)$ — действительное число. Существует последовательность $\omega$ и константа $N$, для которых

$$\max_{t \in F} KS(F, \omega(F) | t) \ge \alpha |F|$$

при всех F, содержащих не менее N элементов.

Заметим, что отсюда вытекает такое свойство последовательности $\omega$: всякое конечное множество F размера не менее N имеет элемент $t$, для которого

$$KS(\omega(F) | F, t) \ge \alpha |F| - 2 KS(F | t)$$

(константа 2 написана для простоты, её можно уменьшить). Опуская $t$ в левой части, получаем, что для любого конечного $F$ выполнено неравенство

$$KS(\omega(F) | F) \ge \alpha |F| - 2 \max_{t \in F} KS(F | t).$$

В частности, если индексы представить себе расположенными в плоскости, а в качестве $F$ брать прямоугольники, то вычитаемое в правой части будет логарифмическим и потому его можно скомпенсировать изменением параметра $\alpha$. Получаем утверждение задачи 251 (с. 279).

◀ Теорема 162 является сложностной переформулировкой теоремы 161. В самом деле, в ней рассматривается множество запрещений $(F, Z)$, для которых неравенство $KS(F, Z | t) < \alpha |F|$ выполнено для всех $t \in F$. Значит, для любого индекса $t$ количество таких запрещений размера $k$, у которых $F$ содержит $t$, не превосходит $2^{\alpha k}$, что и составляет предположение теоремы 161. ▶

### 8.5.6. «Эффективное» доказательство леммы Ловаса

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

В этом смысле лемма Ловаса ещё менее «эффективна» — поскольку вероятность в ней экспоненциально мала (хотя и положительна), то непосредственное использование датчика случайных битов (с распределением, фигурирующим в лемме) ничего хорошего не даёт. Однако случайные биты можно использовать и более
хитрым способом. Пусть нам надо, скажем, построить двоичное слово, имея не-
который набор запрещений (другими словами, выполнить КНФ, см. раздел 8.5.4).
Сначала выберем биты случайно. Небольшая доля запрещений при этом (скорее
всего) нарушится. Возьмём какое-то из них и попробуем его исправить, выбрав
значения входящих в него переменных заново (снова бросив монету для каждой
из переменных). Скорее всего, это поможет (вряд ли второй раз получится тот
же запрещённый набор значений). Правда, могут появиться новые нарушения. Что
ж, повторим процесс: выберем нарушенное запрещение и заново выберем значения
входящий в него переменных. И так далее.

Формально говоря, мы сначала случайно назначаем значения всем переменным,
а потом повторяем такое действие: выбираем одно из нарушенных запрещений (ска-
жем, первое в каком-то порядке, или по какому-то другому правилу), и присваиваем
входящим в него переменным новые случайные значения. Так мы делаем до тех пор,
пока нарушенных запрещений не останется. Удивительно, но этот простой способ
приводит к цели, как недавно доказали Мозер и Тардош [111, 112]. (Удивительно
и то, что раньше до этого простого способа не додумались, и доказывали более
слабые варианты более сложными способами.)

Мы разберём упрощённое рассуждение, которое предполагает, что все запре-
щения одинакового размера, и что они исправляются в некотором определённом
порядке (с помощью рекурсивных вызовов соседей) — тем более что его удобно
изложить на языке колмогоровской сложности, следуя Фортноу.

Итак, пусть наша формула (КНФ) содержит $n$ переменных и $N$ дизъюнктов,
каждый из которых имеет длину $t$, то есть включает ровно $t$ переменных. Будем
считать соседями дизъюнкты, имеющие общую переменную (и потому являющие-
ся зависимыми событиями). Пусть у каждого дизъюнкта не более $t$ соседей. Мы
утверждаем, что если $t$ не слишком велико, то по лемме Ловаса формула выпол-
нима.

Какие нужны ограничения? Поскольку все дизъюнкты одного размера, есте-
ственно выбрать в лемме Ловаса одно и то же значение $\varepsilon$. Оно должно удовлетво-
рять неравенству

$$
2^{-m} \le \varepsilon(1 - \varepsilon)^t
$$

(слева стоит вероятность нарушения в данном дизъюнкте). Правая часть макси-
мальна при $\varepsilon = 1/(t+1)$, но для упрощения формул положим $\varepsilon = 1/t$, получится
$(1 - 1/t)^t/t$, то есть (с большой точностью) $1/et$. Другими словами, выполнимость
гарантируется условием $t \le 2^m/e$. В конструктивном доказательстве нам понадо-
бится более сильное условие $t \le 2^m/8$.

Теорема 163. Существует вероятностный алгоритм, который ищет выпол-
няющий набор для любой КНФ с $n$ переменными и $N$ дизъюнктами размера $t$,
у каждого из которых менее $2^m/8$ соседей, за полиномиальное от $n + N$ время
с вероятностью не менее $1/2$.

(Как обычно, вероятность успеха можно приблизить к 1, если повторить алго-
ритм несколько раз.)
◀ Алгоритм использует рекурсивную процедуру $Fix(d)$ (где $d$ — дизьюнкт):

для всех дизьюнктов $d$ формулы:

если $d$ не выполнен, то $Fix(d)$

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

Текст процедуры $Fix(d)$ тоже совсем прост:

выбрать новые случайные значения для всех переменных в $d$;

для всех соседей $d'$ дизьюнкта $d$:

если $d'$ не выполнен, то $Fix(d')$

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

Остаётся убедиться, что с большой вероятностью процесс закончится за полиномиальное время. Для этого посмотрим, как в нём используются случайные биты (представляя себе, что они заранее заготовлены). Сначала $n$ битов используются в качестве начальных значений переменных, а затем при каждом вызове $Fix(d)$ очередные $m$ битов используются для переменных, входящих в $d$. (Именно здесь удобно, что мы не повторяем выборку в том же вызове $Fix$, если новые значения совпали со старыми.)

**Наблюдение:** полный комплект случайных битов, использованных к данному моменту работы алгоритма, можно восстановить по текущим значениям переменных и по списку дизьюнктов, для которых вызывалась процедура $Fix$.

В самом деле, из текста алгоритма видно, что $Fix(d)$ вызывается только в случае, когда $d$ не выполнен, что однозначно определяет значения переменных $d$ до вызова. А значения их после вызова — те самые случайные биты. Значит, можно восстанавливать события с конца, и дойти до начала, получив начальные $n$ случайных битов.

Таким образом, список дизьюнктов плюс текущие значения позволяет восстановить случайные биты. Что противоречит их несжимаемости, если список и текущие значения можно задать короче. Чтобы получить такое противоречие (при долго работающем алгоритме), надо оценить сложность списка дизьюнктов. Ключевую роль здесь играет то, что при рекурсивном вызове мы от дизьюнкта переходим к соседу, которого можно задать порядковым номером в списке соседей.<fnref n="1" />

<footnote n="1">¹Удивительно, что утверждение, как доказали Мозер и Тардош, верно и при другом порядке обработки ложных дизьюнктов, но доказывать его надо иначе.</footnote>
Итак, подсчитаем, сколько используется случайных битов и сколько нужно битов, чтобы задать их (описанным способом). Рассмотрим ситуацию после $k$ вызовов процедуры $Fix$. К этому моменту использован $n + km$ случайных битов. Чтобы восстановить их, нужно знать:

* текущие значений переменных;

* для каких дизьюнктов вызывалась процедура $Fix$ из основной программы;

* какие вызовы процедуры $Fix$ были сделаны рекурсивно для каждого из этих дизьюнктов.

Первое требует $n$ битов. Второе требует не более $N$ битов (для каждого дизьюнкта мы указываем, вызывался он или нет; порядок просмотра дизьюнктов в основной программе мы считаем фиксированным, так что его указывать не надо). Чтобы оценить третье, нарисуем деревья рекурсивных вызовов. Например, на рисунке показано дерево, начинающееся с вызова для дизьюнкта $a$. Этот вызов рекурсивно порождает три других, для дизьюнктов $b, c, d$; первый из трёх порождает вызовы для $e, f, g$, второй ничего не порождает, третий порождает вызов для $h$. Хронологический порядок вызовов такой: $a, b, e, f, g, c, d, h$ (мы располагаем сыновей вершины слева направо в порядке их вызовов). В самом деле, мы переходим к вызову $c$, только вернувшись из вызова $b$, который рекурсивно включает в себя вызовы $e, f, g$.

<figure><img src="image_26.png" /></figure>

Нам будет удобно представлять себе, что мы обходим граф, начав в точке $a$ и держась за него правой рукой (как если бы это был вид сверху на стенку): $a-b-e-b-f-b-g-b-a-c-a-d-h-d-a$ (что соответствует передаче управления между копиями программ при рекурсивных вызовах). При этом новые случайные биты требуются, когда мы в первый раз (снизу) приходим в какую-то вершину.

Теперь видно, что для указания последовательности дизьюнктов достаточно закодировать обход дерева в указанном порядке. Он состоит из шагов вверх и вниз. Идя вверх, мы должны сообщить не только тот факт, что мы идём вверх, но и по какому ребру (к какому соседу) мы идём, что требует $\log t$ битов (плюс к одному биту, указывающему направление «вверх»). Здесь $t$ обозначает $2^m/8$ — верхнюю оценку количества соседей. Идя вниз, мы можем не указывать соседа, поскольку он однозначно определяется предыдущей информацией. (При рекурсивном вызове мы помещаем параметр в стек, и надо указать, какой, а при выходе из процедуры мы удаляем вершину стека, и ничего указывать не надо).

В итоге на каждую вершину (кроме корня) уходит $\log t + 2$ бита (было бы $\log t + 1$, если были бы только шаги вверх, плюс по одному на шаги вниз, которых
не больше, чем шагов вверх). Таким образом, всего получается $N + n + k(\log t + 2)$. Если случайные биты действительно имеют максимальную сложность, то $N + n + k(\log t + 2) \ge n + km$, что даёт ограничение сверху на $k$, поскольку $\log t + 2 = m - 1$, а именно $k \le N$. То есть не более $N$ вызовов процедуры *Fix*, что гарантирует полиномиальность алгоритма.

Правда, ещё нужно сделать некоторые уточнения и комментарии.

1. Если формально говорить о колмогоровской сложности, то появятся константы. Как обычно, проще с ними не связываться и перейти к подсчёту вероятностей: если $k = N + c$, то разница между левой и правой частью (числом случайных битов и числом битов в описании) есть $c$. Это означает, что количество исходов бросаний, при которых процедура *Fix* вызывается $N + c$ раз (или более), в $2^c$ раз меньше общего количества исходов, поэтому вероятность такого события не больше $2^{-c}$.

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

3. Наконец, есть ещё одна проблема: вполне может оказаться, что мы прервали работу алгоритма в середине обхода одного из деревьев, так что мы должны уметь описывать незаконченный обход дерева. Но наш способ описания позволяет описать и незаконченный обход вокруг дерева с теми же оценками (число ходов вниз не превышает число ходов вверх, которое и есть число рекурсивных вызовов процедуры *Fix*). ►

## 8.6. Доказательство одного неравенства

Мы уже говорили (с. 22), что неравенства для колмогоровской сложности имеют разные любопытные следствия. Подробно этот вопрос разбирается в главе 10, но одно следствие подобного рода (вариант неравенства Лумиса – Уитни) мы приведём уже сейчас.

**Теорема 164.** Пусть $X, Y$ и $Z$ — конечные множества, а $f: X \times Y \to \mathbb{R}$, $g: Y \times Z \to \mathbb{R}$ и $h: X \times Z \to \mathbb{R}$ — функции с неотрицательными значениями. Тогда

$$ \left( \sum_{x,y,z} f(x,y)g(y,z)h(x,z) \right)^2 \le \left( \sum_{x,y} f^2(x,y) \right) \cdot \left( \sum_{y,z} g^2(y,z) \right) \cdot \left( \sum_{x,z} h^2(x,z) \right). $$

◀ Как ни странно, это неравенство можно доказать с использованием неравенства

$$ 2KP(x, y, z) \le KP(x, y) + KP(y, z) + KP(x, z) + O(\log n) $$

(теорема 26, с. 59). Нам удобно записать последнее неравенство для префиксной сложности, а не для обычной, как раньше, но это несущественно, так как разница есть $O(\log n)$. (На самом деле для префиксной сложности это неравенство верно и с точностью $O(1)$ (задача 114, с. 129), но для нас большая точность не нужна.)
Будем для удобства считать, что множества X, Y и Z, о которых идёт речь в теореме, состоят из двоичных слов. Достаточно доказать, что если суммы в правой части неравенства равны единице, то сумма в левой части не превосходит 1. (В самом деле, от умножения функции $f$ на число и левая, и правая части возрастают в одинаковое число раз, так что можно «нормировать» $f$; аналогично для $g$ и $h$.)

Итак, пусть $\sum_{x,y} f^2(x, y) = 1$ и аналогично для двух других сумм. Нам надо доказать, что $\sum_{x,y,z} f(x, y)g(y, z)h(x, z) \le 1$.

Идея проста: функция $f^2$ задаёт распределение вероятностей на парах $(x, y)$, поэтому $KP(x, y) \le -\log f^2(x, y) = -2 \log f(x, y)$ (если временно считать, что это распределение вероятностей меньше априорного не с точностью до константы, а прямо так). Аналогично $KP(y, z) \le -2 \log g(y, z)$ и $KP(x, z) \le -2 \log h(x, z)$. Поэтому (вспоминаем неравенство для $KP(x, y, z)$ и временно забываем о логарифмической добавке)

$$2 KP(x, y, z) \le -2 \log f(x, y) - 2 \log g(y, z) - 2 \log h(x, z),$$

то есть

$$f(x, y)g(y, z)h(x, z) \le 2^{-KP(x,y,z)}.$$

Поскольку сумма $2^{-KP(x,y,z)}$ по всем тройкам $x, y, z$ не превосходит единицы (теорема 57, с. 108), получаем искомое неравенство.

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

Для начала заметим, что нам (по непрерывности) достаточно доказать неравенство для функций $f, g$ и $h$ с рациональными значениями.

Пусть $N$ — произвольное натуральное число (которое потом будет стремиться к бесконечности). Рассмотрим множества $X^N$, $Y^N$ и $Z^N$, элементы которых являются кортежами из $N$ слов. Рассмотрим распределение вероятностей на $X^N \times Y^N = (X \times Y)^N$, соответствующее $N$ независимым копиям распределения $f^2$ на $X \times Y$. (Формально говоря, вероятность точки $\langle\langle x_1, \dots, x_N \rangle\rangle$, $\langle\langle y_1, \dots, y_N \rangle\rangle$) равна произведению $f^2(x_1, y_1) \dots f^2(x_N, y_N)$.) Мы получаем семейство распределений, вычислимо зависящее от $N$, и потому найдётся такая константа $c$, что

$$KP(\langle x_1, \dots, x_N \rangle, \langle y_1, \dots, y_N \rangle | N) \le 2 \sum_i (-\log f(x_i, y_i)) + c$$

при всех $N$ и при всех $x_1, \dots, x_N, y_1, \dots, y_N$ (сравниваем построенное распределение с априорной вероятностью). Можно убрать условие $N$ в левой части неравенства, написав справа $c \log N$ вместо $c$. Далее, как и раньше, сложим три таких неравенства и оценим сложность тройки через сложность пар. При этом получится

$$KP(\langle x_1, \dots, x_N \rangle, \langle y_1, \dots, y_N \rangle, \langle z_1, \dots, z_N \rangle) \le \sum_i (-\log f(x_i, y_i)) + \sum_i (-\log g(y_i, z_i)) + \sum_i (-\log h(x_i, z_i)) + c \log N$$

для некоторой константы $c$ и для всех $N$, $x_1, \dots, x_N, y_1, \dots, y_N, z_1, \dots, z_N$ (заметим, что суммарная длина всех слов $x_i, y_i, z_i$ при $i = 1, \dots, N$ есть $O(N)$, поэтому
все логарифмические добавки поглощаются с log N). Подставляя эту оценку в неравенство $\sum_u 2^{-KP(u)} \le 1$, получаем, что при любом N сумма

$$ \sum_i \prod_{j \ne i} f(x_i, y_i) g(y_i, z_i) h(x_i, z_i) $$

по всем наборам $x_1, \dots, x_N, y_1, \dots, y_N, z_1, \dots, z_N$ не превосходит $2^{O(\log N)}$, то есть некоторого полинома от N. Но эта сумма есть N-я степень суммы

$$ \sum_{(x,y,z) \in X \times Y \times Z} f(x,y)g(y,z)h(x,z), $$

поэтому если бы эта последняя сумма была больше 1, то получилось бы противоречие. Неравенство доказано. ►

**252** Покажите, что из доказанного неравенства следует оценка для объёма трёхмерного тела через площади его плоских проекций, упомянутая на с. 22. [Указание: в качестве f, g, h можно взять характеристикические функции проекций тела; это даёт необходимую оценку в дискретном случае, а для непрерывного надо перейти к пределу либо разбивая тело на кубики, либо устремляя сумму к интегралу.]

Для сравнения приведём два других доказательства того же неравенства. Вот (простое) доказательство того же неравенства с помощью неравенства Коши (которое гласит, что $(u, v)^2 \le \|u\|^2 \cdot \|v\|^2$, то есть $(\sum u_i v_i)^2 \le (\sum u_i^2)(\sum v_i^2)$). В самом деле,

$$ \begin{aligned} \left(\sum_{x,y,z} f(x,y)g(y,z)h(x,z)\right)^2 &\le \left(\sum_{x,y} f^2(x,y)\right) \left(\sum_{z} \left(\sum_{y,z} g(y,z)h(x,z)\right)^2\right) \le \\ &\le \left(\sum_{x,y} f^2(x,y)\right) \sum_{x,y} \left(\left(\sum_z g^2(y,z)\right) \left(\sum_z h^2(x,z)\right)\right) = \\ &\quad \left(\sum_{x,y} f^2(x,y)\right) \left(\sum_{y,z} g^2(y,z)\right) \left(\sum_{x,z} h^2(x,z)\right). \end{aligned} $$

Ещё одно доказательство может быть получено с использованием шенноновской энтропии (и в каком-то смысле представляет собой «перевод» доказательства с колмогоровской сложностью). Итак, пусть $\sum f^2 = \sum g^2 = \sum h^2 = 1$. Мы хотим доказать, что $\sum_{x,y,z} p'(x,y,z) \le 1$, где $p'(x,y,z) = f(x,y)g(y,z)h(x,z)$. Рассуждая от противного, предположим, что эта сумма равна $c > 1$. Тогда пропорционально уменьшим её члены, получив некоторое распределение вероятностей $p'$ на $X \times Y \times Z$:

$$ p'(x,y,z) = \frac{1}{c} f(x,y)g(y,z)h(x,z). $$

Соответствующую случайную величину со значениями в $X \times Y \times Z$ обозначим через $\xi$. Её можно рассматривать как тройку (вообще говоря, зависимых) следующих величин $\xi_x, \xi_y$ и $\xi_z$; можно также рассматривать двумерные проекции $\xi_{xy} = \langle \xi_x, \xi_y \rangle$ и т. п. Например, величина $\xi_{xy}$ принимает значение $\langle x, y \rangle$ с вероятностью $\sum_z p'(x,y,z)$. Напомним, что по определению шенноновская энтропия распределения $(p_1, \dots, p_k)$ равна сумме $\sum_i p_i(-\log p_i)$ и не превосходит $\sum_i p_i(-\log q_i)$.
для любого другого распределения $q_1 + \dots + q_k = 1$. Поэтому энтропию $H(\xi_{xy})$ можно оценить сверху, взяв в качестве другого распределения значения $f^2(x, y)$:

$$H(\xi_{xy}) \le \sum_{x,y} \left( \sum_z p'(x, y, z) \right) (-2 \log f(x, y)).$$

Записав аналогичные оценки для двух других направлений проекции и применив неравенство

$$H(\xi) = H(\xi_x, \xi_y, \xi_z) \le \frac{1}{2} (H(\xi_{xy}) + H(\xi_{yz}) + H(\xi_{xz}))$$

(задача 230, с. 253), получим, что

$$\begin{aligned} H(\xi) \le \sum_{x,y,z} p'(x,y,z) (-\log f(x,y) - \log g(y,z) - \log h(x,z)) = \\ = \sum_{x,y,z} p'(x,y,z) (-\log p(x,y,z)). \end{aligned}$$

Но по определению $H(\xi) = \sum_{x,y,z} p'(x,y,z) (-\log p'(x,y,z))$, и получается противоречие, так как $p'$ меньше $p$ в с раз (и потому $-\log p'$ больше $-\log p$ на $\log c$).

## 8.7. Нетранзитивность липшицевых преобразований

В этом разделе мы рассмотрим приложение колмогоровской сложности к анализу свойств бесконечных последовательностей. Начнём с такого определения, связанного с канторовским пространством $\Omega$ бесконечных двоичных последовательностей.

Отображение $f: \Omega \to \Omega$ называется липшицевым, если

$$d(f(\omega_1), f(\omega_2)) \le cd(\omega_1, \omega_2)$$

для некоторой константы $c$ и для всех $\omega_1, \omega_2 \in \Omega$. Здесь $d$ — расстояние между последовательностями в канторовском пространстве, определяемое как $2^{-k}$, где $k$ — номер первого места, где последовательности различаются.

Неформально говоря, это свойство означает, что первые $n$ знаков последовательности $f(\omega)$ определяются первыми $n + O(1)$ знаками последовательности $\omega$. Поэтому, в частности, все отображения, задаваемые локальными правилами (каждый бит в $f(\omega)$ определяется некоторой окрестностью этого бита в $\omega$), являются липшицевыми.

Нас будет интересовать такое свойство отображения $f$: для любых последовательностей $\omega_1$ и $\omega_2$ и любого $\varepsilon > 0$ существует число $N$ и последовательности $\omega'_1$ и $\omega'_2$, для которых

$$\omega'_2 = f(f(f(\dots f(\omega'_1)\dots))) \quad (N \text{ раз})$$

и

$$d(\omega_1, \omega'_1) < \varepsilon, \quad d(\omega_2, \omega'_2) < \varepsilon.$$
(Другими словами, для любых двух открытых окрестностей найдётся орбита, начинающаяся в одной окрестности и попадающая в другую.) Это свойство мы будем для краткости называть «транзитивностью».

Легко понять, что отображение сдвига влево (отбрасывание первого члена последовательности) транзитивно: если мы хотим, чтобы последовательность начиналась на некоторое слово $x_1$, а после нескольких сдвигов начиналась на другое слово $x_2$, достаточно начать её с $x_1x_2$.

Возникает вопрос, сохранит ли сдвиг свойство транзитивности, если заменить $d$ на так называемое расстояние Безиковича

$$ \rho(\omega_1, \omega_2) = \limsup_{n \to \infty} d_n(\omega_1, \omega_2)/n, $$

где $d_n$ — количество несовпадений среди первых $n$ членов последовательностей, то есть количество тех $i < n$, при которых $i$-е члены $\omega_1$ и $\omega_2$ различны? Очевидно, что нет, поскольку расстояние Безиковича не изменяется при сдвиге последовательностей: $\rho(f(\alpha), f(\beta)) = \rho(\alpha, \beta)$. Поэтому любая окрестность последовательности из одних нулей (которая устойчива относительно сдвига) отображается сдвигом в себя. Значит с помощью сдвигов невозможно попасть из любой ее точки в достаточно малую окрестность любой далёкой от неё точки (например, последовательности из одних единиц).

Более того, имеет место следующий результат (мы воспроизводим доказательство из [10]):

**Теорема 165.** Никакое липшицево отображение не является В-транзитивным.

(Говоря о липшицевом отображении, мы имеем в виду исходное определение, с канторовским расстоянием.)

Причина этого проста: липшицево отображение почти не увеличивает сложности начальных отрезков последовательности, так как $n$ битов выходной последовательности определяются $n + O(1)$ битами входной (и соответствующее правило можно считать вычислимым, выбрав подходящий оракул). С другой стороны, близкие в смысле Безиковича последовательности имеют близкие сложности начальных отрезков (поскольку изменение небольшой доли среди первых $n$ битов кодируется малым количеством битов по сравнению с $n$).

◀ Удобно воспользоваться понятием эффективной хаусдорфовой размерности последовательности (которая равна $\liminf KS(\omega_0...\omega_{n-1})/n$ для одноэлементного множества $\{\omega\}$, см. теорему 120 на с. 198 в разделе 5.8).

**Лемма 1.** Вычислимое липшицево отображение не увеличивает эффективную хаусдорфову размерность последовательности.

(Говоря о вычислимости липшицева отображения $f: \Omega \to \Omega$, мы имеем в виду, что $n$ первых знаков $f(\omega)$ алгоритмически определяются по $n + c$ знакам $\omega$ для некоторого $c$.)

В самом деле, если $f(\omega_1) = \omega_2$, то сложность начального отрезка длины $n$ последовательности $\omega_2$ не превосходит константы (зависящей от сложности алгоритма для $f$) плюс сложность начального отрезка длины $n + c$ последовательности $\omega_1$, и в пределе эти константы не играют роли.
**Лемма 2.** Если $\rho(\omega_1, \omega_2) < \varepsilon$, то эффективные хаусдорфовы размерности последовательностей $\omega_1$ и $\omega_2$ отличаются не более чем на $h(\varepsilon)$.

(Здесь $h(\varepsilon)$ — шенноновская энтропия случайной величины с двумя значениями, имеющими вероятности $\varepsilon$ и $1 - \varepsilon$.)

В самом деле, если первые $n$ членов последовательностей $\omega_1$ и $\omega_2$ отличаются в $k$ позициях, то сложности соответствующих начальных отрезков отличаются не более чем на сложность их разности (или суммы) по модулю 2, а последовательность длины $n$ с $k$ единицами имеет сложность не более $nh(k/n) + O(\log n)$ (см. раздел 7.3.1, теорема 146, с. 254); отсюда легко следует утверждение леммы.

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

Таким образом, для вычислимых липшицевых отображений теорема доказана. Остаётся заметить, что все эти рассуждения можно релятивизовать относительно любого оракула и что любое липшицево отображение вычислимо относительно некоторого оракула. ►
# 9. Частотный и игровой подходы к определению случайности

## 9.1. Исходный замысел фон Мизеса

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

В природе бывают явления, которые легко предсказывать (после того как изучены управляющие ими законы), например, движение планет. Но бывают и другие явления: как бы мы ни старались предсказать результат бросания монеты, обычно около половины предсказаний оказываются неверными. Именно такие явления и составляют предмет теории вероятностей.

Тем самым основным понятием теории вероятностей становится (более или менее неопределяемое) понятие **коллектива** — трудно предсказуемой последовательности символов (букв некоторого алфавита, который мы для простоты будем считать состоящим из нуля и единицы). А основным свойством коллектива $\omega = \omega_0\omega_1...$ является следующее свойство **устойчивости частот**:

существует предел

$$p = \lim_{n \to \infty} \frac{\omega_0 + \omega_1 + \dots + \omega_{n-1}}{n}$$

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

Указанное $p$ и называют вероятностью появления единицы (в данном коллективе).

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

Так — или примерно так — говорил фон Мизес (см., например, его книгу "Wahrscheinlichkeit, Statistik und Wahrheit" [108]; эта книга была переведена на русский язык под названием «Вероятность и статистика» — видимо, слово Wahrheit (истина) в названии показалось чрезмерно смелым посягательством на прерогативы
единственно верного и подлинно научного учения). Но говорил он это не во времена Евклида или Спинозы, а в начале ХХ века, когда требования математической строгости были достаточно настойчивы. Допустим, существование последовательностей с некоторыми свойствами можно объявить аксиомой или экспериментальным фактом, это ещё куда ни шло (хотя, конечно, экспериментальный факт, говорящий нечто о пределах последовательностей, вызывает сомнения, если не насмешки). Но уже сформулировать математически точно свойство устойчивости частот следовало бы.

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

Поэтому возможны разные уточнения замысла Мизеса, и несколько таких уточнений мы рассмотрим. Для каждого из них прежде всего возникает вопрос о существовании коллективов (который после уточнения определения становится математическим); при этом вопрос о том, действительно ли бросание монеты даёт коллектив, позволительно считать естественно-научным или философским и остаться в стороне.

Для простоты мы в основном ограничиваемся случаем симметричной монеты ($p = 1/2$), если обратное не оговорено явно. Будем называть бесконечную последовательность нулей и единиц сбалансированной, если предел частоты единиц (или нулей) в ней существует и равен $1/2$.

## 9.2. Правила выбора как множества слов

Пожалуй, самое естественное толкование допустимого правила выбора состоит в следующем: мы принимаем решение о включении $\omega_n$ в подпоследовательность, глядя на все предыдущие члены, то есть в зависимости от $\omega_0\omega_1\dots\omega_{n-1}$. Таким образом, допустимое правило выбора есть функция, отображающая все двоичные слова $\omega_0\dots\omega_{n-1}$ в двухэлементное множество $\{\text{включать, не включать}\}$. Другими словами, допустимое правило представляет собой некоторое множество $R$ двоичных слов (соответствующих значению «включать»).

Формально говоря, для произвольного множества $R \subset \Xi$ мы определяем соответствующее ему правило выбора как отображение $S_R$, которое ставит в соответствие произвольной последовательности $\omega \in \Omega$ некоторую (конечную или бесконечную) подпоследовательность $S_R(\omega) \in \Sigma$. А именно, $S_R(\omega)$ состоит из тех $\omega_n$, для которых $\omega_0\dots\omega_{n-1} \in R$ (в том же порядке, в котором они шли в $\omega$).

Пример: если принадлежность слова $x$ к множеству $R$ зависит лишь от длины слова $x$, то последовательность $S_R(\omega)$ получается из $\omega$ выбором членов $\omega_n$, стоящих на заранее известных местах (при тех $n$, для которых слова длины $n$ принад-