ментов — больше оно содержать и не может, поскольку все его элементы по построению имеют сложность не больше $KS(x_1, ..., x_n)$.

В самом деле, зная сложностной вектор $\mathcal{H}(x_1, ..., x_n)$, мы можем перечислять множество $A(x_1, ..., x_n)$. Задание сложностного вектора требует $O(\log N)$ битов (заметим, что число компонент в этом векторе, хотя и экспоненциально большое, зависит лишь от $n$ и потому может считаться постоянным). Поэтому любой элемент $A(x_1, ..., x_n)$ можно задать, указав (помимо сложностного вектора) его порядковый номер в перечислении, и сложность любого элемента в $A(x_1, ..., x_n)$ не превосходит

$$ \log |A(x_1, ..., x_n)| + O(\log N). $$

В частности, это относится и к исходному набору $\langle x_1, ..., x_n \rangle$, откуда и следует требуемая оценка.

Покажем, что множество $A(x_1, ..., x_n)$ является с-однородным для некоторой константы $c$, полиномиально зависящей от $N$. Для этого надо сравнить обе части неравенства

$$ m(1, 2, ..., n) \le m(1) \cdot m(2|1) \cdot m(3|1, 2) \cdot ... \cdot m(n|1, 2, ..., n-1). $$

Логарифмы сомнителей в правой части можно оценить сверху соответствующими сложностями: $m(1) \le 2^{KS(x_1)}$, поскольку по построению $KS(y_1) \le KS(x_1)$ для любого набора $\langle y_1, ..., y_n \rangle \in A(x_1, ..., x_n)$ (формально говоря, следовало бы написать $2^{KS(x_1)+1}$ в оценке, но с нашей логарифмической точностью это не имеет значения). Аналогично $m(2|1) \le 2^{KS(x_2|x_1)}$ и так далее. В итоге получается, что логарифм правой части не превосходит

$$ KS(x_1) + KS(x_2|x_1) + KS(x_3|x_1, x_2) + ... + KS(x_n|x_1, ..., x_{n-1}) + O(1), $$

что равно $KS(x_1, ..., x_n) + O(\log N)$. Но и для левой части мы знаем, что её логарифм не меньше $KS(x_1, ..., x_n) - O(\log N)$, так что разница между логарифмами есть $O(\log N)$, а отношение самих значений ограничено многочленом от $N$, что и требовалось. Одновременно мы устанавливаем, что

$$ KS(x_i | x_1, ..., x_{i-1}) = \log m(i | 1, ..., i-1) + O(\log N), $$

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

$$ KS(x_j | x_i) = \log m(J | I) + O(\log N) $$

для любых непересекающихся $I$ и $J$. ►

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

Теперь уже легко завершить доказательство обещанной теоремы:

**Теорема 212** (Ромащенко). Всякое линейное неравенство

$$ \sum_{I} \lambda_{I} H(\xi_{I}) \le 0, $$
выполненное для произвольных случайных величин $\xi_1, \dots, \xi_n$, выполнено для кол-могоровских сложностей произвольных слов сложности не более $N$ с погрешностью $O(\log N)$:

$$ \sum_I \lambda_I K(\xi_I) \le O(\log N). $$

Заметим, что константа в $O(\log N)$ зависит от $n$ (и быстро растёт с ростом $n$), но не от слов $x_1, \dots, x_n$.

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

Для обратного перехода у нас тоже всё готово. Пусть неравенство верно для энтропий. Рассмотрим произвольные слова $x_1, \dots, x_n$ и множество $A = A(x_1, \dots, x_n)$ из только что доказанной теоремы. Рассмотрим случайную величину $\langle \xi_1, \dots, \xi_n \rangle$, равномерно распределённую в множестве $A$. Поскольку множество $A$ является $N^c$-однородным, то энтропии будут отличаться от логарифмов размеров сечений не более чем на $O(\log N)$ по теореме 210. С другой стороны, величины $\log m(I|J)$ совпадают с соответствующими сложностями с точностью до $O(\log N)$ по теореме 211, что и завершает доказательство. ▶

Неравенства рассмотренного нами вида можно являются простейшими универсальными формулами некоторого формального языка. Возникает естественный вопрос — сохранится ли теорема Ромащенко, если от универсальных формул перейти к $\forall \exists$-формулам того же языка? Оказывается, что нет, более подробно об этом можно прочитать в [122].

## 10.7. Комбинаторная интерпретация: примеры

Вернёмся теперь к комбинаторной интерпретации. Напомним основную идею: «слово $x$ имеет сложность меньше $n$» надо понимать как «слово $x$ принадлежит множеству из менее чем $2^n$ элементов». (Поскольку сложность определена с точностью до $O(1)$, мы не будем аккуратно различать строгие и нестрогие неравенства.)

Строго говоря, таким образом мы получаем комбинаторную интерпретацию не для функции $KS$, а для двухместного предиката $KS(x) < n$ с аргументами $x$ и $n$, и все утверждения о сложности (в частности, неравенства) надо предварительно записать в этих терминах.

Разберём несколько примеров.

* Неравенство $KS(x) \le KS(y)$ записывается так: для всех $n$ из $KS(y) < n$ следует $KS(x) < n$.

* Неравенство $KS(x) \le 2KS(y)$ записывается так: для всех $n$ из $KS(y) < n$ следует $KS(x) < 2n$.

* Неравенство $KS(z) \le KS(x) + KS(y)$ записывается так: для всех $u$ и $v$ из $KS(x) < u$ и $KS(y) < v$ следует $KS(z) < u + v$.

Используя последний пример в качестве образца, попытаемся перевести на комбинаторный язык неравенство для сложности пары: $KS(x,y) \le KS(x) + KS(y)$.
Первый шаг: если $KS(x) < u$ и $KS(y) < v$, то $KS(x,y) < u + v$. Далее естественно переводить так: если $x$ принадлежит заданному множеству из менее чем $2^u$ элементов, а $y$ принадлежит заданному множеству из менее чем $2^v$ элементов, то можно указать множество из менее чем $2^{u+v}$ элементов, которому принадлежит пара $(x,y)$ (а именно, произведение множеств). Так что ничего особенно нового не получается.

Аналогичный перевод утверждения $KS(y|x) < v$ выглядел бы так: пара $(x,y)$ принадлежит известному множеству, у которого все сечения (при фиксированном $x$) имеют размер менее $2^v$. Так что и неравенство $KS(x,y) \le KS(x) + KS(y|x)$ тоже ясно, как переводить.

Ситуация существенно меняется, если обратить знак неравенства. Неравенство $KS(z) \ge KS(x) + KS(y)$ можно переписать так: если $KS(x) \ge u$ и $KS(y) \ge v$, то $KS(z) \ge u + v$. Но в нашем предикате $KS$ меньше границы, а не больше (и эта асимметрия существенна: мы можем перечислять слова малой сложности, но не слова большой сложности!) Поэтому надо перейти к отрицаниям: если неверно, что $KS(x) < u$ и неверно, что $KS(y) < v$, то неверно, что $KS(z) < u + v$. Другими словами: если $KS(z) < u + v$, то $KS(x) < u$ или $KS(y) < v$.

Попробуем применить тот же метод перевода для неравенства

$$KS(x, y) \ge KS(x) + KS(y|x),$$

с которым у нас были трудности. Получаем вот что: если пара $(x,y)$ принадлежит заданному множеству из менее чем $2^{u+v}$ элементов, то либо $x$ принадлежит какому-то множеству из менее чем $2^u$ элементов, либо $(x,y)$ принадлежит какому-то множеству, у которого любое сечение содержит не более $2^v$ элементов.

Более точно: для любых $u, v$ и всякого множества пар $A$ из менее чем $2^{u+v}$ элементов можно указать

* множество $B$ из менее чем $2^u$ элементов;

* множество $C$ пар, которое содержит менее $2^v$ элементов с одним и тем же первым членом,

причём так, что для всякого $(x,y) \in A$ выполнено по крайней мере одно из двух: либо $x \in B$, либо $(x,y) \in C$.

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

**287** Повторите это рассуждение и формально докажите сформулированное комбинаторное утверждение.

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

$$KS(x_1) + KS(x_1, x_2, x_3) \le KS(x_1, x_2) + KS(x_2, x_3)$$
(базисное неравенство, выполненное с точностью до $O(\log N)$ для слов сложности не выше $N$).

Переходя к двухместному предикату $KS(x) < n$, это неравенство можно пере-
писать так:

если $KS(x_1, x_2) < a$, $KS(x_1, x_3) < b$ и $a + b = p + q$, то выполнено по
крайней мере одно из неравенств $KS(x_1) < p$ и $KS(x_1, x_2, x_3) < q$.

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

если $A \subset X_1 \times X_2 \times X_3$, $m_A(1, 2) \le 2^a$, $m_A(1, 3) \le 2^b$ и $a+b=p+q$, то существуют такие $B, C \subset X_1 \times X_2 \times X_3$, что $A \subset B \cup C$, $m_B(1) \le 2^p$ и $m_C(1, 2, 3) \le 2^q$.

Или, переходя к мультипликативной записи и исключая лишние переменные:

если $A \subset X_1 \times X_2 \times X_3$ и $m_A(1, 2) \cdot m_A(1, 3) = l \cdot V$ для некоторых
чисел $l, V > 0$, то множество $A$ можно покрыть множествами $B$ и $C$,
для которых $m_B(1) \le l$ и $m_C(1, 2, 3) \le V$.

Геометрически это можно прочесть так: если у множества А проекции на плос-
кости 1, 2 и 1, 3 малы, то это ещё не мешает его длине в направлении 1 (проекции
на первую координату) и объёму (общему числу точек в А) быть большими. Од-
нако А можно разбить на две части В и С, у первой из которых мала длина по
первой координате, а у второго мал объём.

(Вспоминая пример с двумя параллелепипедами, мы видим, что в том случае
толстый параллелепипед мог бы составить B, а тонкий — C.)

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

Рассмотрим проекцию множества А на плоскость 1, 2; она является некоторым
подмножеством $X_1 \times X_2$, которое мы обозначим $A_{12}$. Для каждого $x \in X_1$ рассмо-
трим сечение этой проекции; пусть это сечение содержит $n_2(x)$ элементов. Тогда

$$
m(1, 2) = |A_{12}| = \sum_{x} n_{2}(x)
$$

(размер множества равен сумме всех его сечений). Аналогичным образом

$$
m(1, 3) = |A_{13}| = \sum_{x} n_{3}(x).
$$

Длина $m_A(1)$ есть число ненулевых слагаемых в этих суммах, а $m(1, 2, 3)$ (общее число элементов в $A$) можно оценить сверху:

$$
m(1, 2, 3) = |A| \le \sum_{x} n_{2}(x) n_{3}(x).
$$

(Без ограничения общности можно считать, что это неравенство обращается в ра-
венство, добавив в А недостающие элементы без изменения его проекций.)
Нам надо разбить А на части В и С, при этом у нас есть ограничения на длину В (в направлении первой координаты) и объём С. Естественно, что при данной длине В нужно забрать в это множество как можно больше точек, поэтому мы включим в В самые большие сечения (у которых $n_2(x)n_3(x)$ максимально) в количестве $l$ штук, а остальное отправим в С. После этого надо доказать лишь, что число элементов в С не больше $|A_{12}| \cdot |A_{13}|/l$.

Как это сделать? Для множества С мы можем оценить размеры двух его плоских проекций; они не превосходят $|A_{12}|$ и $|A_{13}|$. Мы знаем также, что все сечения множества С (при любом $x \in X_1$) по площади не превосходят $S_l$, где $S_l = l-e$ по величине (в порядке убывания) сечения множества А. Рассмотрим неравенство

$$2 \mathrm{KS}(x_1, x_2, x_3) \le \mathrm{KS}(x_1, x_2) + \mathrm{KS}(x_1, x_3) + \mathrm{KS}(x_2, x_3 | x_1)$$

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

$$m(1, 2, 3)^2 \le m(1, 2) \cdot m(1, 3) \cdot m(2, 3|1)$$

и потому

$$|C|^2 \le |A_{12}| \cdot |A_{13}| \cdot S_l.$$

Осталось, таким образом, доказать, что

$$S_l \le \frac{|A_{12}| \cdot |A_{13}|}{l^2}.$$

Вспомним, что множество В состоит из $l$ прямоугольников, каждый из которых имеет площадь не меньше $S_l$. Сумма «оснований» $n_2(x)$ этих прямоугольников не превосходит $|A_{12}|$, а сумма их «высот» $n_3(x)$ не превосходит $|A_{13}|$, так что среднее (арифметическое) основание не больше $|A_{12}|/l$, а средняя (арифметическая) высота не больше $|A_{13}|/l$. Остаётся заметить, что если $S \le a_i b_i$ при всех $i = 1, 2, \dots, l$, то

$$S \le \frac{a_1 + \dots + a_l}{l} \cdot \frac{b_1 + \dots + b_l}{l}$$

(что легко следует из выпуклости логарифма или неравенства о среднем арифметическом и геометрическом).

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

## 10.8. Комбинаторная интерпретация: общий случай

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

$$\sum \lambda_i \mathrm{KS}(x_i) \le \sum \mu_j \mathrm{KS}(x_j)$$
(суммы в левой и правой части берутся по непересекающимся множествам индексов $I, J \subset \{1, 2, \dots, n\}$; никакое множество индексов не входит одновременно в обе части; коэффициенты $\lambda_I$ и $\mu_J$ положительны).

Как выглядит соответствующее комбинаторное утверждение? По аналогии с рассмотренными примерами его можно сформулировать так:

Пусть $A \subset X_1 \times \dots \times X_n$ и пусть $n_I$ — произвольный набор чисел, для которого

$$ \prod_I (n_I)^{\lambda_I} = \prod_J m_A(J)^{\mu_J}. $$

Тогда множество $A$ можно покрыть множествами $B_I$, для которых

$$ m_{B_I}(I) \le n_I. $$

К сожалению, про сформулированное таким образом утверждение не удаётся доказать, что оно выполнено одновременно с соответствующим неравенством для сложностей. Нам придётся несколько ослабить утверждение, включив в него множитель, соответствующий $O(\log N)$ в неравенстве. Вот этот ослабленный вариант:

Существует такая константа $d$, что для произвольных $X_1, \dots, X_n$, для произвольного $A \subset X_1 \times \dots \times X_n$ и для произвольного набора чисел $n_I$, для которого

$$ \prod_I (n_I)^{\lambda_I} = \prod_J m_A(J)^{\mu_J}, $$

существует покрытие множества $A$ множествами $B_I$, для которых

$$ m_{B_I}(I) \le n_I \cdot (\log |A|)^d. $$

**Теорема 213.** Сформулированное утверждение верно для данных наборов $\lambda_I$ и $\mu_J$ тогда и только тогда, когда

$$ \sum \lambda_I K_S(x_I) \le \sum \mu_J K_S(x_J) + O(\log N) $$

для любых слов $x_1, \dots, x_n$ сложности не больше $N$.

◀ Предположим, что неравенство верно и покажем, как можно покрыть произвольное множество $A$ частями требуемого размера. Прежде всего заметим, что без ограничения общности можно считать элементы множества $A$ наборами $\langle x_1, \dots, x_n \rangle$ слов длины не больше $N = \log |A|$ (слов хватит, а конкретная природа элементов роли не играет).

Предположим временно, что множество $A$ является простым (имеет сложность $O(\log N)$). В этом случае простыми являются и все его проекции, и потому сложности их элементов не превосходят логарифма размера (с точностью до $O(\log N)$). Поэтому для произвольного элемента $\langle x_1, \dots, x_n \rangle \in A$ выполнены неравенства

$$ K(x_J) \le \log m_A(J) + O(\log N) $$
для всех $J$; складывая их с коэффициентами $\mu_J$, получаем, что

$$ \sum_J \mu_J K(x_J) \le \log \left( \prod m_A(J)^{\mu_J} \right) + O(\log N). $$

Пользуясь неравенством (которое мы считаем верным) и вспоминая свойство чисел $n_I$, заключаем, что

$$ \sum_I \lambda_I K(x_I) \le \log \left( \prod_I n_I^{\lambda_I} \right) + O(\log N) = \sum_I \lambda_I \log n_I + O(\log N) $$

для любого элемента $\langle x_1, \dots, x_n \rangle \in A$. А отсюда следует, что (для каждого элемента множества $A$) хотя бы одно слагаемое в левой части меньше соответствующего слагаемого в правой: для всякого $\langle x_1, \dots, x_n \rangle$ найдётся $I$, при котором

$$ KS(x_I) \le n_I + O(\log N), $$

то есть $x_I$ принадлежит множеству всех объектов сложности меньше $n_I + O(\log N)$. Соответствующие элементы $A$ и образуют искомое множество $B_I$.

Это завершает рассуждение для случая простого множества $A$. Общий случай сводится к этому с помощью стандартного приёма: для каждого $N$ рассмотрим всевозможные множества $A \subset X_1 \times \dots \times X_n$, где все $X_i$ состоят из слов длины не больше $N$, и рассмотрим то из них, которое (при данных $\lambda_I$ и $\mu_J$) покрывается хуже всего (с наибольшим частным левой и правой частей для оптимального покрытия). Это множество является простым (сложности $O(\log N)$) поскольку его можно найти перебором, для которого достаточно знать $N$ и коэффициенты $\lambda_I, \mu_J$, и поэтому к нему применимо изложенное выше рассуждение. Поскольку это множество было самым трудным для покрытия, для остальных множеств утверждение тем более верно.

(Сказанное требует некоторого уточнения. Вообще говоря, мы не предполагаем, что коэффициенты $\lambda_I$ и $\mu_J$ являются рациональными или даже вычислимыми. Но их достаточно рассматривать с точностью до $1/N$, поскольку логарифмы всех мощностей не превосходят $N$ и общая ошибка не больше $O(1)$. А задание их с такой точностью требует $O(\log N)$ битов.)

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

Рассмотрим произвольный набор слов $x_1, \dots, x_n$, каждое из которых имеет сложность не более $N$. Пусть для него неравенство не выполняется и левая часть заметно (более чем на $O(\log N)$) больше правой. Включим наш набор в почти однородное множество $A = A(x_1, \dots, x_n)$. Рассмотрим в качестве $n_I$ величины $KS(x_I)$, уменьшенные поровну настолько, чтобы сравнять левую часть неравенства с правой; поскольку $\log m_A(J)$ не превосходит $KS(x_J)$, можно применить комбинаторное утверждение. В результате множества $A$ будет покрыто множествами $B_I$, у которых $I$-проекции содержат не более $2^{n_I+O(\log N)}$ элементов, что заметно меньше соответствующей проекции множества $A$, содержащей примерно $2^{KS(x_I)}$ элементов (вспомníм, что мы заметно уменьшали $n_I$). В силу почти однородности множества $A$
всякая его часть, составляющая небольшую долю в одной из проекций, составляет небольшую долю по отношению ко всему А, и потому фиксированное число множеств $B_I$ не может покрыть множества А. ►

**288** Проведите аккуратно все требуемые в этом доказательстве оценки (скрытые за словами «заметно», «небольшая доля» и т. п.)

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

## 10.9. Комбинаторная интерпретация: другой вариант

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

А именно, рассмотрим набор чисел $\lambda_I$ любого знака и следующее комбинаторное утверждение:

Существует такая константа $d$, что для произвольных конечных множеств $X_1, \dots, X_n$ и для произвольного $A \subseteq X_1 \times \dots \times X_n$ можно представить $A$ в виде объединения не более чем $(\log |A|)^d$ множеств, для каждого из которых выполнено неравенство

$$ \prod m(I)^{\lambda_I} \le (\log |A|)^d $$

для размеров его проекций. (Части могут пересекаться.)

**Теорема 214.** Сформулированное утверждение верно для некоторого набора коэффициентов $\lambda_I$ тогда и только тогда, когда для любого $N$

$$ \sum \lambda_I K_S(x_I) \le O(\log N) $$

для любых слов $x_1, \dots, x_n$ сложности не более $N$.

◀ Пусть верно комбинаторное утверждение, и мы хотим доказать неравенство для сложностей. Рассмотрим произвольные слова $x_i$ сложности не больше $N$. Приallenем метод типизации и получим множество $A = A(x_1, \dots, x_n)$. При этом $\log |A|$ будет ограничен многочленом от $N$.

По предположению, множество $A$ можно представить в виде объединения полиномиального (от $\log |A|$, а потому и от $N$) числа множеств. Рассмотрим то из них, которое содержит больше всего элементов. Обозначим его $B$. Множество $B$ включает в себя полиномиальную долю элементов множества $A$, которое является $c$-однородным с полиномиальным значением $c$, а потому и $B$ является таковым (с большим, но по-прежнему полиномиальным значением $c$), причём логарифмы размеров проекций у $A$ и $B$ отличаются на $O(\log N)$. Следовательно, из неравенства для $B$ можно вывести неравенство для $A$ (с точностью $O(\log N)$), а потому, как мы видели, и для сложностей.
В другую сторону доказываемая теорема вытекает из такой леммы:

**Лемма.** Любое множество $A \subset X_1 \times \dots \times X_n$ можно представить в виде объединения полиномиального от $N = \log |A|$ числа частей, каждая из которых является с-однородным множеством с полиномиальным (от $N$) значением $c$. (Частям разрешается пересекаться.)

Заметим, что в этой лемме ничего не говорится ни о колмогоровской сложности, ни о неравенствах. Но из неё следует требуемое нам утверждение. В самом деле, как мы доказали, исходное неравенство верно и для шенноновских энтропий проекций любой $n$-мерной случайной величины. В частности, оно верно и для случайной величины, равномерно распределённой в любой из частей множества $A$. Поскольку части однородны, для любой из них логарифмы размеров её проекций отличаются от шенноновской энтропии проекций случайной величины не более чем на $O(\log c) = O(\log N)$.

Доказываем теперь сформулированную лемму. Интересно, что (пожалуй, самое) простое доказательство этой леммы использует колмогоровскую сложность. Без ограничения общности можно предполагать, что элементы $\langle x_1, \dots, x_n \rangle \in A$ состоят из двоичных слов. Для каждого элемента $x \in A$ рассмотрим множество всех $\langle y_1, \dots, y_n \rangle \in A$, для которых сложностной вектор, составленный из условных (относительно $A$) сложностей, не превосходит такого же вектора для $x$.

Эта конструкция отличается от ранее рассмотренной «типизации» в двух отношениях: во-первых, мы рассматриваем лишь элементы $y \in A$ (а раньше никакого $A$ не было); во-вторых, мы используем сложности при условии $A$.

Заметим, что полученное множество определяется сложностями слов $x_1, \dots, x_n$ и их комбинаций, а не самими этими словами, и потому получится лишь полиномиальное число таких множеств. Осталось проверить, что каждое из них является с-однородным для полиномиального (от $N$) значения $c$.

Это делается так же, как и раньше: число элементов в таком множестве не сильно меньше $2^{KS(x_1, \dots, x_n | A)}$, а логарифмы сечений оцениваются условными сложностями, так что эти два изменения оставляют доказательство однородности в силе. ►

Интересно найти чисто комбинаторное доказательство только что рассмотренной леммы, не использующее колмогоровскую сложность. Это не вполне тривиально даже для двумерных множеств. Пусть мы имеем некоторое конечное множество $A \subset \mathbb{N}^2$. «Почти однородность» в этом случае означает, что

$$m(1,2) \approx m(1)m(2|1), \quad m(1,2) \approx m(2)m(1|2).$$

Другими словами, среднее (непустое) вертикальное сечение $m(1,2)/m(1)$ должно не слишком сильно отличаться от максимального сечения $m(2|1)$ — и то же самое для горизонтальных сечений.

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

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

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

Ещё немного усложнив рассуждение, можно достичь ещё одного улучшения: неоднородность каждой части ограничена константой (зависящей от размерности задачи *n*, но не от размера разбиваемого на части множества). Это сделано в работе [3] с помощью следующего приёма.

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

Вес разбиения будет суммой весов всех элементов в этом разбиении. А вес элемента х, попавшего в часть X, определяется формулой

$$
\sum_{A,B} \log m_X(B|A) - d \log |X|,
$$

где сумма берётся по парам непересекающихся множеств A, B ⊂ {1, 2, ..., n}, а
d — некоторый постоянный коэффициент (заметим, кстати, что в сумме также
есть член log |X| — при A = ∅, B = {1, 2, ..., n}). Подчеркнём, что веса всех
элементов внутри одной части одинаковы.

Покажем, что если выбрать *d* достаточно большим, то разбиение наименьшего
веса содержит немного частей. А именно, мы покажем, что выгодно соединить две
части, у которых все параметры log *m*<sub>*X*</sub>(*B* | *A*) достаточно близки (отличаются не
более чем на единицу). В самом деле, при соединении каждое *m*<sub>*X*</sub>(*B* | *A*) возрастёт
не более чем втрое (по сравнению с обеими частями), а |*X*| возрастёт не менее чем
в полтора раза (также по сравнению с обеими частями). При достаточно большом *d*
второе перевесит первое, и при слиянии частей веса всех элементов уменьшатся.
Заметим, что нужное значение *d* определяется лишь числом слагаемых (которое,
в свою очередь, зависит лишь от *n* и не зависит от размера множества).

Пусть *d* выбрано таким образом. Будем классифицировать части по целым ча-
стям значений log *m*<sub>*X*</sub>(*B* | *A*) при всех *А* и *В*. Как мы видели, никакие две части не
попадут в один класс, а число классов ограничено полиномом от максимального
значения $\log|X|$, которое не превосходит логарифма числа элементов в разбивающем множестве. Таким образом мы получаем желаемую оценку на число частей.

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

$$ \sum_{A,B} \log m_X(B|A) - d \log |X| $$

для веса точки все члены (и слагаемые, и вычитаемое) уменьшаются. Нам надо разбить неоднородную часть на две так, чтобы уменьшение слагаемых (для обеих частей) пересилило бы уменьшение вычитаемого. Последнее легко подсчитать: если часть из $m$ элементов разбивается на две части из $pm$ и $qm$ элементов (так что $p+q=1$), то вычитаемое уменьшится на $dmh(p, q)$, где

$$ h(p, q) = p(-\log p) + q(-\log q) $$

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

Если множество (рассматриваемая нами часть) сильно неоднородно, то найдутся такие множества индексов $A$ и $B$, что $m(A \cup B)$ много больше $m(A) \cdot m(B|A)$. Это означает, что если мы рассмотрим проекцию на $A \cup B$, то у этой проекции сечения, параллельные $B$, сильно различаются по размеру, и максимальное из них значительно (скажем, в $l$ раз) превосходит среднее.

Эту проекцию (и тем самым всё множество) можно разбить на две части, считая в качестве граничного размера сечения среднее геометрическое между максимальным и средним размером. У части с «малыми» сечениями тогда уменьшится максимальный размер сечения в $\sqrt{l}$ раз. С другой стороны, большие сечения по неравенству Чебышёва составляют не более доли $1/\sqrt{l}$ (наче бы среднее было больше), поэтому у части с большими сечениями уменьшится (также в $\sqrt{l}$ раз) размер $A$-проекции.

Таким образом, после разбиения для каждой из новых частей хотя бы одно слагаемое в формуле для весов уменьшится на $\log \sqrt{l}$ (а остальные, как мы уже говорили, не возрастут). Поэтому при достаточно большом $l$ (когда $\log \sqrt{l} > d$) общий вес заведомо уменьшится. Значит, в разбиении минимального веса все части с-однородны для некоторой константы $c$, которая (вслед за $d$ и $l$) определяется лишь числом $n$ (хотя и быстро растёт с ростом $n$), что и завершает доказательство леммы с использованием весов.

## 10.10. Неравенства для двух и трёх слов

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

Это удалось сделать лишь для простейших случаев (при $n \le 3$). Для $n = 1$ ситуация вообще тривиальна. При $n = 2$ имеются неравенства

$$0 \le H(\xi_1) \le H(\xi_1, \xi_2), \quad 0 \le H(\xi_2) \le H(\xi_1, \xi_2), \quad H(\xi_1, \xi_2) \le H(\xi_1) + H(\xi_2),$$

которые означают, что три величины

$$H(\xi_2 | \xi_1), H(\xi_1 | \xi_2), I(\xi_1 : \xi_2)$$

неотрицательны. С другой стороны, ясно, что значения этих трёх величин могут быть любыми неотрицательными числами: возьмём три независимые величины $\alpha, \beta, \gamma$ с такими энтропиями и положим

$$\xi_1 = \langle \alpha, \beta \rangle, \xi_2 = \langle \beta, \gamma \rangle,$$

тогда, как легко проверить, $H(\xi_1 | \xi_2) = H(\alpha), I(\xi_1 : \xi_2) = H(\beta), H(\xi_2 | \xi_1) = H(\gamma)$. Таким образом, в данном случае выясняется, что указанные неравенства необходимы и достаточны, чтобы набор из трёх чисел мог быть равен

$$H(\xi_1), H(\xi_2), H(\xi_1, \xi_2),$$

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

Прежде чем переходить к случаю $n = 3$, отметим, что для $n = 2$ мы сделали нечто большее, чем просто описали все верные линейные неравенства для энтропий: мы доказали также, что все тройки чисел, удовлетворяющие этим неравенствам, могут быть значениями энтропий.

Геометрически это можно описать так. Для всякого набора случайных величин есть точка в (трёхмерном при $n = 2$) линейном пространстве, состоящая из энтропий комбинаций этих величин. Рассматривая разные наборы случайных величин, мы получаем некоторое множество $\mathcal{E}$ в этом линейном пространстве.

Линейные неравенства для энтропий — это замкнутые полупространства, содержащие целиком множество $\mathcal{E}$. В данном случае (при $n = 2$) мы установили, что $\mathcal{E}$ есть в точности многогранный конус, заданный нашими неравенствами.

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

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

После этих комментариев перейдём к случаю $n=3$. В этом случае имеется семимерное пространство (соответствующее семи непустым подмножествам трёхэлементного множества). Удобнее перейти к новым координатам $a_1, \dots, a_7$ в этом векторном пространстве, описанным на с. 60 (рис. 2.4) для случая колмогоровских сложностей. В этих координатах известные нам базисные неравенства означают, что все $a_i$, кроме «центральной части» $a_5$, которую мы также обозначали $I(\xi_1:\xi_2:\xi_3)$, неотрицательны<fnref n="1" />, а эта центральная часть неотрицательна в сумме с любой из трёх частей $a_2, a_4, a_6$. Другими словами, можно сказать, что множество $\mathcal{E} \subset \mathbb{R}^7$ всех возможных наборов энтропий содержится в множестве $\mathcal{F}$ всех семёрок, удовлетворяющих этим неравенствам.

Множество $\mathcal{F}$, как легко понять, состоит из неотрицательных линейных комбинаций конечного числа векторов (образующих этого выпуклого конуса). А именно, образующими будут векторы, в которых одно из $a_i$ равно единице, а остальные нулю. Кроме того, есть ещё один особый вектор $e$: у него $a_5 = -1$, $a_2 = a_4 = a_6 = 1$, остальные $a_i$ равны нулю. Этого достаточно: хотя $a_5$ может быть отрицательно, но по модулю не может превосходить $a_2, a_4$ и $a_6$, поэтому надо взять особый вектор $e$ с коэффициентом $|a_5|$ и добавить остальные по мере необходимости.

Теперь ясно, что других неравенств нет. В самом деле, все образующие реализуются как наборы энтропий; особый вектор соответствует независимым величинам $\xi_1, \xi_2$ с двумя равновероятными значениями $0,1$ и $\xi_3 = \xi_1 + \xi_2 \pmod 2$. Любое верное неравенство верно для образующих, и потому для всего $\mathcal{F}$, то есть вытекает из базисных неравенств.

**290** Покажите, что множество $\mathcal{E}$ (напомним, что мы рассматриваем случай $n=3$) не выпукло. Например, для особого вектора $e$ вектор $\lambda e$ принадлежит $\mathcal{E}$ тогда и только тогда, когда $\lambda$ есть логарифм целого числа.

**291** Докажите, что множество $\mathcal{E}$ (для $n$ случайных величин) замкнуто относительно сложения: если два вектора $e, e' \in \mathbb{R}^{2^n-1}$ принадлежат $\mathcal{E}$, то и их сумма $e+e'$ принадлежит $\mathcal{E}$. [Указание. Рассмотрите два независимых набора случайных величин, задающих векторы $e$ и $e'$, и соедините их в один.]

**292** Докажите, что замыкание множества $\mathcal{E}$ (для любого числа случайных величин) выпукло. [Указание. Если $e$ и $e'$ принадлежат множеству $\mathcal{E}$, то при больших целых $k$ и $l$ вектор $ke+le'$ также принадлежит множеству $\mathcal{E}$, осталось лишь научиться умножать вектор на число. На целые числа мы его умножать умеем, а приближённо делить на большое число можно так: с малой вероятностью $\varepsilon$ берём данные случайные величины, в противном случае тривиальные (имеющие только одно значение).]

<footnote n="1">¹На самом деле мы определяли величину $I(x_1:x_2:x_3)$ для слов $x_1, x_2, x_3$, а не для случайных величин; определение для энтропий аналогично.</footnote>
## 10.11. Размерности и неравенство Инглетона

В случае двух и трёх случайных величин (или слов) мы описали все истинные линейные неравенства для энтропий (и тем самым для сложностей); при этом для случая $n = 2$ мы описали даже множество $\mathcal{E}$, а не только двойственное к нему множество всех неравенств, выполненных для всех элементов из $\mathcal{E}$.

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

Напомним, что мы рассматриваем набор случайных величин $\xi = \xi_1, \dots, \xi_n$ и через $\xi_I$ (для данного множества индексов $I \subset \{1, \dots, n\}$) обозначаем часть этого набора, состоящую из величин с индексами из $I$. Через $H(\xi_I)$ обозначается энтропия этой части. Условные энтропии $H(\xi_I | \xi_J)$ (которые можно рассматривать только для непересекающихся множеств $I$ и $J$, так как общие элементы можно удалить из $I$) выражаются через безусловные и потому их нет необходимости рассматривать отдельно.

Каждому набору случайных величин $\langle \xi_1, \dots, \xi_n \rangle$ соответствует точка в пространстве $\mathbb{R}^{2^n-1}$, составленная из чисел $H(\xi_I)$ при всех непустых $I$. Эти точки (для всех наборов) образуют множество, которое мы обозначали через $\mathcal{E}$. Как мы видели в задачах 290, 291 и 292, это множество не обязательно выпукло, но его замыкание является выпуклым конусом (вместе с любыми двумя точками содержит их положительные линейные комбинации).

От множества $\mathcal{E}$ можно перейти к двойственному множеству всех линейных неравенств, выполненных для энтропий случайных величин (то есть для элементов $\mathcal{E}$). Геометрически это означает, что мы рассматриваем все полупространства, содержащие $\mathcal{E}$. Обратный переход даёт множество всех точек, для которых выполнены все эти неравенства (пересечение всех упомянутых полупространств); линейное программирование учит, что это пересечение есть минимальный замкнутый выпуклый конус, содержащий $\mathcal{E}$.

Среди неравенств заведомо есть следующие:

$$ 
\begin{array}{lll}
H(\xi_I) \ge 0 & \text{для любого } I, \\
H(\xi_I) \le H(\xi_J) & \text{для любых } I \subset J, \\
H(\xi_I \cap J) + H(\xi_I \cup J) \le H(\xi_I) + H(\xi_J) & \text{для любых } I, J.
\end{array}
$$

Будем называть эти неравенства базисными. Этот термин раньше употреблялся по отношению к неравенству

$$ H(\xi_1) + H(\xi_1, \xi_2, \xi_3) \le H(\xi_1, \xi_2) + H(\xi_1, \xi_3), $$

которое соответствует случаю $I = \{1, 2\}$, $J = \{1, 3\}$, и к которому сводится неравенство для произвольных $I$ и $J$, если объединить случайные величины в группы. Для удобства мы включаем в базисные неравенства и неравенства первых двух типов.

Таким образом, множество $\mathcal{E}$ содержится в многогранном конусе, состоящем из всех наборов, удовлетворяющих базисным неравенствам. В случае $n = 2$ имеет
место совпадение; при $n = 3$, как мы говорили, совпадения нет, но $\mathcal{E}$ плотно в этом конусе. При $n = 4$ это, как мы увидим, уже не так.

Выяснение ситуации естественно начать с описания структуры конуса. Всякое множество, задаваемое системой однородных линейных неравенств, есть множество всех положительных линейных комбинаций своих крайних точек (рёбер конуса). Если бы (как это происходит при $n = 3$) все эти крайние точки попали в $\mathcal{E}$, то мы бы установили, что все неравенства для энтропий следуют из базисных (потому что всякое неравенство, верное для рёбер, верно и для их положительных линейных комбинаций).

Для случая $n = 4$ такие рёбра можно найти вручную или с помощью компьютерной программы; это было сделано (см. статью [51], где приведён список всех рёбер). Выяснилось, что большинство рёбер действительно принадлежит $\mathcal{E}$ (и соответствующие случаиные величины легко найти, см. [51]), но есть и несколько особых рёбер. Эти особые рёбра по существу все одинаковы (отличаются переставной переменных), и мы приведём одно из таких особых рёбер:

$$ 
\begin{aligned}
H(\xi_1) &= H(\xi_2) = H(\xi_3) = H(\xi_4) = 2n, \\
H(\xi_1, \xi_2) &= 4n, \\
H(\xi_1, \xi_3) &= H(\xi_1, \xi_4) = H(\xi_2, \xi_3) = H(\xi_2, \xi_4) = H(\xi_3, \xi_4) = 3n, \\
H(\xi_1, \xi_2, \xi_3) &= H(\xi_1, \xi_2, \xi_4) = H(\xi_1, \xi_3, \xi_4) = H(\xi_2, \xi_3, \xi_4) = 4n, \\
H(\xi_1, \xi_2, \xi_3, \xi_4) &= 4n.
\end{aligned}
$$

Другими словами, каждое слово имеет сложность $2n$, все слова вместе и все тройки слов имеют сложность $4n$, а все пары имеют сложность $3n$, за исключением одной, которая имеет сложность $4n$. (Множитель $n$ указан, поскольку ребро конуса есть луч, и его точки определены с точностью до пропорциональности.)

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

<figure><img src="image_33.png" /><figcaption>Рис. 10.4. Распределение сложностей для троек слов.</figcaption></figure>

ные величины (или двоичные слова) с такой энтропией (сложностью), мы сталкиваемся со следующей трудностью: правая картинка показывает, что $\xi_3$ и $\xi_4$ хорошо бы иметь $n$ битов общей информации, и вся эта информация входит как в $\xi_1$, так и
в $ξ_2$. С другой стороны, левая картинка показывает, что $ξ_1$ и $ξ_2$ не должны иметь общей информации (в пересечении стоят нули). Конечно, это всего лишь разгово- ры, поскольку слова «п битов общей информации» пока ничего определённого не означают. Однако, как мы увидим ниже, действительно таких величин $ξ_1, ξ_2, ξ_3, ξ_4$ не существует.

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

$$I(\xi_3:\xi_4) \le I(\xi_3:\xi_4|\xi_1) + I(\xi_3:\xi_4|\xi_2) + I(\xi_1:\xi_2)$$

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

$$12 + 3 + 4 + 134 + 234 \le 13 + 23 + 14 + 24 + 34$$

(для краткости мы пишем лишь индексы: скажем, 134 обозначает $H(\xi_1, \xi_3, \xi_4)$), но в таком виде его смысл ещё менее ясен. Оказывается, что это неравенство хорошо известно в теории матроидов и называется неравенством Инглетона:

**Теорема 215.** Для любых конечномерных подпространств $H_1, H_2, H_3, H_4$ про- извольного векторного пространства выполнено неравенство

$$\dim(H_1 + H_2) + \dim H_3 + \dim H_4 + \dim(H_1 + H_3 + H_4) + \dim(H_2 + H_3 + H_4) \le \dim(H_1 + H_3) + \dim(H_2 + H_3) + \dim(H_1 + H_4) + \dim(H_2 + H_4) + \dim(H_3 + H_4).$$

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

Рассмотрим конечномерное пространство $X$ над конечным полем $F$ и его под- пространства. Этим подпространствам соответствуют случайные величины следу- ющим образом. Вероятностным пространством будет множество всех линейных функционалов $X \to F$, и каждому подпространству $Y \subset X$ соответствует случайная величина $\xi_Y$, которая сопоставляет с каждым функционалом его ограничение на $Y$. (Менее формально: случайная величина, соответствующая $Y$, есть ограничение случайного линейного функционала на подпространство $Y$.) Значениями такой слу- чайной величины являются элементы пространства $Y^*$, собряженного к $Y$, и все они равновероятны, их число равно $\dim F$ в степени $\dim Y^* = \dim Y$, так что энтропия такой случайной величины равна $\dim Y \cdot \log |F|$.

Заметим, что у нас не просто для каждого подпространства есть случайная вели- чина, а есть некоторое их совместное распределение. Поэтому можно задать такой вопрос. Пусть $Y$ и $Z$ — два подпространства. Какова будет энтропия пары величин $\langle \xi_Y, \xi_Z \rangle$? Заметим, что ограничения случайного функционала на подпространства
Y и Z однозначно определяют его ограничение на $Y + Z = \{y + z | y \in Y, z \in Z\}$ и наоборот. Поэтому энтропия пары равна $dim(Y + Z) \cdot \log|F|$.

Из этого наблюдения сразу же следует такая

**Теорема 216.** Всякому неравенству, выполненному для энтропий случайных величин и их наборов, соответствует неравенство для размерностей конечномерных подпространств векторного пространства над конечным полем (в котором энтропии группы величин соответствует размерность суммы подпространств).

**293** Покажите, что аналогичное утверждение верно для размерностей конечномерных подпространств векторного пространства над $\mathbb{R}$ и над $\mathbb{C}$. [Указание. Вешественная размерность пространства вдвое больше его комплексной размерности, так что достаточно рассмотреть вещественный случай. Будем считать пространство евклидовым и рассмотрим случайные величины, являющиеся проекциями случайной точки единичного шара на каждое из подпространств, причём в каждом пространстве значения округляются с точностью $\varepsilon$. При этом возникают разные погрешности (проекция случайной точки шара не равномерна в круге; из-за округления проекции на $X$ и $Y$ не определяют проекцию на $X + Y$ однозначно, а лишь с точностью до конечного числа вариантов), но главные члены при $\varepsilon \to 0$ всё-таки пропорциональны размерностям.]

Эти рассуждения, однако, не применимы непосредственно к произвольным бесконечным полям, и необходимо более сложное рассуждение. Во-первых, тот факт, что над некоторым полем существует пространство и набор подпространств с заданными размерностями (их самих и их сумм), можно сформулировать на языке матриц: существует матрица определённого размера, в которой определённые мипоры равны нулю, а некоторые другие не равны нулю. Поэтому, если набор размерностей возможен для некоторого поля, то он возможен и для его расширений. Следовательно, можно ограничиться алгебраически замкнутыми полями. Поскольку алгебраически замкнутые поля одной характеристики элементарно эквивалентны, достаточно рассмотреть для каждой характеристики какое-то одно поле. Характеристику $0$ (комплексные числа) мы уже обсуждали. Для конечной характеристики рассмотрим алгебраическое замыкание поля вычетов по модулю $p$. Если в нём набор размерностей реализуется матрицей, то все элементы этой матрицы алгебраичны, и можно построить конечное расширение поля вычетов по модулю $p$, в которое они все войдут. Тем самым мы свели дело к конечному полю, где мы умеем переходить от подпространств к случайным величинам.

**294** Проведите это рассуждение подробно.

Заметим ещё, что переход от подпространств к соответствующим случайным величинам является довольно общим приёмом построения примеров точек из $\mathcal{C}$. В частности, все до сих пор встречавшиеся примеры элементов $\mathcal{C}$ могут быть получены как раз таким способом; существенно другие примеры появятся лишь в следующем разделе, когда будет идти речь об условно независимых случайных величинах.
◀ Перейдём теперь к доказательству неравенства Инглетона. Его нельзя непосредственно вывести из теоремы 216 (поскольку для энтропий оно не выполняется, как мы впоследствии увидим). Чтобы его доказать, надо установить ещё некоторые связи между энтропиями и размерностями.

В наших неравенствах для энтропий можно считать условную энтропию $H(\alpha|\beta)$ сокращением для $H(\alpha, \beta) - H(\beta)$. В соответствующем неравенстве для размерностей условная энтропия переводится как $\dim(A + B) - \dim B$, что равно размерности образа $A$ при линейном отображении, ядро которого равно $B$ (образа $A$ при факторизации по $B$). Как учит линейная алгебра, это можно переписать как $\dim A - \dim(A \cap B)$. Другое сокращение, $I(\alpha:\beta)$, расшифровывается как $H(\alpha) + H(\beta) - H(\alpha, \beta)$, что соответствует $\dim A + \dim B - \dim(A + B)$. Последнее выражение равно $\dim(A \cap B)$. Наконец, $I(\alpha:\beta|\gamma)$ можно развернуть (не до конца) в

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

и ему соответствует

$$\dim A/C + \dim B/C - \dim(A + B)/C,$$

если через $X/C$ обозначить пространство, получаемое из $X$ при линейном отображении с ядром $C$. Заметим, что последнее выражение нельзя переписать в виде $\dim(A \cap B)/C$: это выражение равно размерности пересечения образов подпространств $A$ и $B$ при факторизации по $C$, а это пересечение содержит образ $A \cap B$ при факторизации по $C$, но не обязано с ним совпадать. (Пусть, например, $A, B, C$ — три различных одномерных подпространства двумерного пространства.)

Возвращаясь к неравенству Инглетона для размерностей подпространств, мы можем переписать его так:

$$\dim(A \cap B) \le I(A:B|C) + I(A:B|D) + \dim(C \cap D)$$

(где $I(A:B|C)$ обозначает размерность пересечения образов $A$ и $B$ при факторизации по $C$). Обозначая $A \cap B$ через $X$, мы видим, что достаточно доказать

$$\dim X \le \dim X/C + \dim X/D + \dim(C \cap D),$$

поскольку $\dim X/C \le I(A:B|C)$ (образ пересечения при факторизации содержится в пересечении образов, хотя может быть и меньше). А это неравенство соответствует легко проверяемому неравенству

$$H(\xi) \le H(\xi|\gamma) + H(\xi|\delta) + I(\gamma:\delta)$$

для энтропий, и остаётся применить теорему 216. ▶

**295** Докажите неравенство $H(\xi) \le H(\xi|\gamma) + H(\xi|\delta) + I(\gamma:\delta)$ для энтропий. [Указание. Как легко заметить по картинке и проверить прямым вычислением,

$$H(\xi) + H(\xi|\gamma, \delta) + I(\gamma:\delta|\xi) = H(\xi|\gamma) + H(\xi|\delta) + I(\gamma:\delta),$$

так что рассматриваемое неравенство является суммой базисных.]
**296** Строго говоря, наше доказательство неравенства Инглетона годится для пространств над конечным полем (или над полем R, если воспользоваться соответствующей задачей). Как перенести его на случай произвольного поля? [Указание. Поле было существенно, когда мы переходили от неравенства для энтропий к неравенству для размерностей. Но это неравенство для энтропий является комбинацией базисных, а базисные неравенства верны для размерностей над произвольным полем.]

**297** Мы знаем, что неравенствам для энтропий соответствуют неравенства для размеров подгрупп и их пересечений. Покажите, что неравенству Инглетона соответствует неравенство, верное для подгрупп коммутативной группы. [Указание: Действуйте как при доказательстве теоремы 215, роль пересечения подпространств играет сумма подгрупп (которая будет подгруппой в коммутативном случае).]

В качестве побочного продукта наших рассмотрений получаем такое любопытное утверждение:

**298** Докажите, что любое линейное неравенство, выполненное для произвольных четвёрок подпространств, следует из базисных неравенств и неравенства Инглетона. [Указание. Как мы уже говорили, все рёбра конуса решений базисных неравенств, кроме упоминавшихся особых, реализуемы не только случайными величинами, но и подпространствами, а выбросив из числа образующих особых рёбра, мы получим конус, гранями которого являются базисные неравенства и неравенства Инглетона (для разных порядков переменных). Как обойтись здесь без длинных (ручных или компьютерных) вычислений, неясно.]

**299** Сформулируйте и докажите аналогичное утверждение для четырёх конечных подгрупп коммутативной группы.

## 10.12. Условно независимые случайные величины

Покажем теперь (как мы давно обещали), что неравенство Инглетона для произвольных случайных величин может нарушаться. А именно, иногда правая его часть обращается в нуль, а левая нет. Для этого мы используем технику условной независимости; дальнейшие результаты и ссылки можно найти в [131, 94].

Говорят, что случайные величины $\alpha$ и $\beta$ независимы при условии $\gamma$ (где $\gamma$ — третья случайная величина на том же вероятностном пространстве), если $I(\alpha: \beta | \gamma) = 0$. Легко проверить, что это равносильно следующему: для любого значения $\gamma_0$ величины $\gamma$, принимаемого с ненулевой вероятностью, условные распределения $\alpha$ и $\beta$ внутри события $\gamma = \gamma_0$ независимы.

**300** Проверьте это. [Указание: $I(\alpha: \beta | \gamma)$ есть среднее значение (по всем $\gamma_0$ с весами, равными их вероятностям) взаимной информации соответствующих распределений.]

Будем говорить, что случайные величины $\alpha$ и $\beta$ условно независимы, если найдутся (на том же вероятностном пространстве или на его измельчении) случайные
величины $\gamma$ и $\delta$ с такими свойствами:

* $\gamma$ и $\delta$ независимы;

* $\alpha$ и $\beta$ независимы при условии $\gamma$;

* $\alpha$ и $\beta$ независимы при условии $\delta$.

Благодаря нашей оговорке (разрешению измельчать вероятностное пространство, разбивая элементарные события на несколько событий нужной суммарной вероятности) свойство условной независимости становится свойством совместного распределения величин $\alpha$ и $\beta$ и не зависит от выбора вероятностного пространства. (Напомним, что здесь, как и всюду, мы рассматриваем лишь случайные величины с конечным числом значений.)

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

**Теорема 217.** Существуют условно независимые случайные величины, не являющиеся независимыми.

Для доказательства достаточно предъявить четвёрку случайных величин $\alpha, \beta, \gamma, \delta$, для которой бы выполнялись требования из определения условной независимости, но $\alpha$ и $\beta$ были бы зависимыми. Укажем такой пример, следуя А. Ромашенко. Каждая из четырёх величин принимает значения 0 и 1 с вероятностью $1/2$. Величины $\gamma$ и $\delta$ независимы, и каждая из четырёх комбинаций имеет вероятность $1/4$.

Величины $\alpha$ и $\beta$ определяются так: если $\gamma = \delta$, то это общее значение будет одновременно значением величин $\alpha$ и $\beta$ (которые в этом случае равны). Если же $\gamma \neq \delta$, то условное распределение вероятностей величин $\alpha$ и $\beta$ (в каждом из случаев $\gamma = 1, \delta = 0$ и $\gamma = 0, \delta = 1$) задаётся таблицей

<table><tr><td></td><td>0</td><td>1</td></tr><tr><td>0</td><td>1/8</td><td>3/8</td></tr><tr><td>1</td><td>3/8</td><td>1/8</td></tr></table>

Легко подсчитать, что (скажем) при фиксированном $\gamma = 0$ условное распределение вероятностей для $\alpha$ и $\beta$ будет полусуммой этой матрицы и матрицы

<table><tr><td></td><td>0</td><td>1</td></tr><tr><td>0</td><td>1</td><td>0</td></tr><tr><td>1</td><td>0</td><td>0</td></tr></table>

Оно равно

<table><tr><td></td><td>0</td><td>1</td></tr><tr><td>0</td><td>9/16</td><td>3/16</td></tr><tr><td>1</td><td>3/16</td><td>1/16</td></tr></table>

что есть распределение двух независимых величин, равных нулю с вероятностью $3/4$. Вместе с тем совместное распределение величин $\alpha$ и $\beta$ есть среднее арифмет-
тическое всех четырёх матриц условных распределений и равно

<table><thead><tr><th></th><th>0</th><th>1</th></tr></thead><tbody><tr><th>0</th><td>5/16</td><td>3/16</td></tr><tr><th>1</th><td>3/16</td><td>5/16</td></tr></tbody></table>

так что величины $\alpha$ и $\beta$ зависимы. ►

Следствием этой теоремы является такое утверждение: при $n = 4$ неотрицательные линейные комбинации векторов, соответствующих размерностям пространств, не исчерпывают всего $\mathcal{E}$ (поскольку для них выполнено неравенство Инглетона, которое верно не всегда). Наша нижняя оценка для замыкания множества $\mathcal{E}$ при $n = 4$ (неособые рёбра и их комбинации) оказывается, таким образом, не наилучшей.

Как мы увидим в следующем разделе, и верхняя оценка (конус решений базисных неравенств) тоже не является точной: при $n \ge 4$ существуют неравенства, не вытекающие из базисных, но верные для всех элементов $\mathcal{E}$.

## 10.13. Неравенства, не сводящиеся к базисным

Неравенства, не сводящиеся к базисным (их иногда называют нешенноновскими) были обнаружены в [193, 194], подробнее см. в [95]. Сейчас их известно довольно много; мы рассмотрим, пожалуй наиболее понятное (точнее, наименее непонятное) из них, приведённое в [95].

**Теорема 218.** Для любых случайных величин $\alpha, \beta, \gamma, \delta, \varepsilon$ выполняется неравенство

$$I(\alpha:\beta) \le I(\alpha:\beta|\gamma) + I(\alpha:\beta|\delta) + I(\gamma:\delta) + I(\alpha:\beta|\varepsilon) + I(\alpha:\varepsilon|\beta) + I(\beta:\varepsilon|\alpha).$$

Смысл и природа этого неравенства, увы, довольно загадочны. Но некоторые комментарии к нему (хотя бы для его запоминания) всё-таки сделать можно.

Его правая часть делится на две группы, без $\varepsilon$ и с $\varepsilon$ (по три члена в каждой). Первая группа знакома нам по неравенству Инглетона (если бы второй группы не было, то оно бы и получилось). Таким образом, наше неравенство является ослаблением неравенства Инглетона за счёт дополнительного (неотрицательного) слагаемого

$$W(\alpha, \beta, \varepsilon) = I(\alpha:\beta|\varepsilon) + I(\alpha:\varepsilon|\beta) + I(\beta:\varepsilon|\alpha).$$

Это слагаемое (символически показанное на рис. 10.5) содержит величину $\varepsilon$, которая в оставшуюся часть не входит. Так что можно сказать так: неравенство Инглетона справедливо с погрешностью, которая не превосходит $\inf_{\varepsilon} W(\alpha, \beta, \varepsilon)$.

Другое наблюдение: если взять в качестве $\alpha, \beta$ и $\varepsilon$ одну и ту же случайную величину $\xi$ (не одинаково распределённые величины, а именно одну и ту же), то $W(\alpha, \beta, \varepsilon)$ обращается в нуль, и мы получаем неравенство

$$H(\xi) \le H(\xi|\gamma) + H(\xi|\delta) + I(\gamma:\delta), \quad (*)$$
<figure><img src="image_34.png" /><figcaption>Рис. 10.5. Величина $W(\alpha, \beta, \varepsilon)$.</figcaption></figure>

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

Ещё одно замечание: частным случаем теоремы 218 является такое «условное неравенство»: если $W(\alpha, \beta, \varepsilon) = 0$ для некоторого $\varepsilon$, то

$$I(\alpha: \beta) \le I(\alpha: \beta | \gamma) + I(\alpha: \beta | \delta) + I(\gamma: \delta)$$

для любых $\gamma$ и $\delta$. Из него видно, что особое ребро из раздела 10.11 не принадлежит $\mathcal{E}$ (достаточно положить $\alpha = \xi_3, \beta = \xi_4, \gamma = \varepsilon = \xi_1, \delta = \xi_2$), хотя удовлетворяет всем базисным неравенствам, так что неравенство теоремы 218 действительно не следует из базисных.

Кстати, это условное неравенство можно доказать и непосредственно, применив неравенство (*) к величине $\xi$ из следующей теоремы (которую нужно применять к величинам $\alpha, \beta$ и $\varepsilon$).

**Теорема 219.** Если $W(\alpha, \beta, \gamma) = 0$, то у тройки величин $\alpha, \beta, \gamma$ выделяется общая информация в следующем смысле: найдётся такая величина $\xi$, что

$$H(\xi | \alpha) = H(\xi | \beta) = H(\xi | \gamma) = 0, \\ I(\alpha: \beta | \xi) = I(\beta: \gamma | \xi) = I(\alpha: \gamma | \xi) = 0.$$

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

Предположим сначала, что все элементы таблицы не равны нулю и покажем, что в этом случае величины $\alpha, \beta, \gamma$ независимы. Рассмотрим все одномерные сечения, параллельные первой координате, как векторы. Получится двумерная таблица, в каждой клетке которой стоит ненулевой вектор. По условию в каждом столбце все векторы пропорциональны, и то же самое для строк. Поскольку векторы ненулевые, то и все они пропорциональны, то есть все плоскости таблицы (в перпендикулярном векторам направлении) пропорциональны и имеют ранг 1, что и требовалось доказать.
Рассмотрим теперь общий случай. Покажем, что наша трёхмерная таблица —
блочно-диагональная. Это означает, что можно (при некотором *k*) представить та-
блицу как соединение *k* блоков, каждый из которых заполняет «параллелепипед»
(произведение множеств по каждой координате), и проекции этих *k* параллелепи-
педов на каждую координату не пересекаются, а вне блоков стоят нули.

Из ранее доказанного следует, что внутри каждого блока имеет место неза-
висимость, то есть это как раз соответствует утверждению теоремы (величина ξ,
номер блока, является функцией от любой из трёх величин α, β, γ и при известном
значении ξ величины α, β, γ независимы).

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

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

**301** Проведите эти рассуждения подробно.

**302** (а) Докажите следующее утверждение (иногда называемое леммой о двойном марковском свойстве): если $I(\beta:\gamma|\alpha) = 0$ и $I(\alpha:\gamma|\beta) = 0$, то найдётся такая величина $\xi$, что $H(\xi|\alpha) = 0$, $H(\xi|\beta) = 0$ и $I(\langle\alpha, \beta\rangle:\gamma|\xi) = 0$. (б) Выведите отсюда утверждение теоремы 219. [Указание к пункту (б). В качестве случайной величины $\xi$ в теореме 219 можно взять ту же случайную величину, что и в пункте (а). Независимость $\alpha$ и $\gamma$ при известном $\xi$ следует из независимости пары $\alpha\beta$ и $\gamma$ (и аналогично для $\beta$ и $\gamma$ при известном $\xi$). А из дополнительного условия независимости $\alpha$ и $\beta$ при известном $\gamma$ следует, что $\alpha$ и $\beta$ независимы при известном $\xi$ и что $\xi$ есть функция $\gamma$. Для установления первого можно сначала нарисовать диаграмму тройки случайных величин $\alpha\beta, \gamma, \xi$ и отметить нулевую область; из диаграммы видно, что $\xi$ имеет не меньше взаимной информации с парой $\alpha\beta$, чем имеет $\gamma$. С другой стороны, из условия $W(\alpha, \beta, \gamma) = 0$ следует, что взаимная информация $\alpha\beta$ и $\gamma$ равна $I(\alpha:\beta:\gamma) = I(\alpha:\beta)$. А из условий $H(\xi|\alpha) = H(\xi|\beta) = 0$ следует, что и взаимная информация $\alpha\beta$ и $\xi$ равна $I(\alpha:\beta:\xi)$ (что опять же видно из диаграмм). Поэтому $I(\alpha:\beta) \ge I(\alpha:\beta:\xi) \ge I(\alpha:\beta:\gamma) = I(\alpha:\beta)$ и все неравенства здесь обращаются в равенства. Равенство первых двух членов как раз и означает независимость $\alpha$ и $\beta$ при известном $\xi$. Наконец, энтропия $\xi$ при известном $\gamma$ не превосходит суммы энтропии $\xi$ при известном $\alpha$, энтропии $\xi$ при известном $\beta$ и общей информации $\alpha$ и $\beta$ при известном $\gamma$. В этой сумме все три слагаемых равны нулю.]

В [132] аналогичное теореме 219 утверждение было доказано и для колмого-
ровской сложности: если для тройки слов *a*, *b*, *c* величины *I*(*a*:*b*|*c*), *I*(*a*:*c*|*b*),
$I(b:c|a)$ малы (скажем, ограничены величиной $O(\log(|a| + |b| + |c|))$, то суще- ствует такое слово $d$, что условные сложности $KS(d|a)$, $KS(d|b)$, $KS(c|a)$, и величины относительной взаимной информации $I(a:b|d)$, $I(b:c|d)$, $I(a:c|d)$ также малы (тоже не превосходят $O(\log(|a| + |b| + |c|))$).

## Независимизация

Всё сказанное, однако, позволяет доказать теорему 218 лишь в частных случаях. Вот общее доказательство:

► Мы используем (до конца ещё, видимо, не понятый) приём «независимиза- ции», который состоит в следующем.

Переменные, входящие в неравенство, делятся на три группы:

$$ (1) \alpha, \beta; \quad (2) \gamma, \delta; \quad (3) \varepsilon. $$

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

Раз так, то достаточно доказать (вообще говоря, более слабое) неравенство

$$ \begin{aligned} I(\alpha:\beta) &\le I(\alpha:\beta|\gamma) + I(\alpha:\beta|\delta) + I(\gamma:\delta) + W(\alpha, \beta, \varepsilon) + \\ &\quad + I(\langle\gamma, \delta\rangle:\varepsilon|\langle\alpha, \beta\rangle) + \\ &\quad + I(\gamma:\varepsilon|\langle\alpha, \beta\rangle) + \\ &\quad + I(\delta:\varepsilon|\langle\alpha, \beta\rangle). \end{aligned} $$

В самом деле, если пара $(\gamma, \delta)$ независима с $\varepsilon$ при известных $\alpha, \beta$, то каждая из величин $\gamma$ и $\delta$ по отдельности также независима с $\varepsilon$ при известных $\alpha, \beta$. Последнее неравенство удивительным образом является суммой восьми базисных неравенств

$$ I(\langle\alpha, \beta\rangle:\varepsilon|\gamma, \delta) \ge 0, $$

$$ I(\alpha:\beta|\varepsilon, \gamma) \ge 0, $$

$$ I(\alpha:\beta|\varepsilon, \delta) \ge 0, $$

$$ I(\gamma:\delta|\varepsilon) \ge 0, $$

$$ I(\gamma:\varepsilon|\alpha) \ge 0, $$

$$ I(\gamma:\varepsilon|\beta) \ge 0, $$

$$ I(\delta:\varepsilon|\alpha) \ge 0, $$

$$ I(\delta:\varepsilon|\beta) \ge 0. $$
Это несложно проверить: если раскрыть все взаимные информации и сложить, то все лишние члены замечательным образом сокращаются. (Но почему так получается и как до этого можно было догадаться, неясно.) ►

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

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

## Удаление уникальной информации

Есть и другой приём вывода новых информационных неравенств. Он основан на следующей теореме Алсведе – Кёрнера [2], которую мы приводим без доказательства (оно приведено в [95], лемма 5).

**Теорема 220.** Пусть заданы совместно распределённые случайные величины $\alpha, \beta, \varepsilon$. Рассмотрим $n$ независимых копий этого распределения $\alpha_i, \beta_i, \varepsilon_i$ ($i = 1, \dots, n$) и обозначим

$$A = (\alpha_1, \dots, \alpha_n), B = (\beta_1, \dots, \beta_n), E = (\varepsilon_1, \dots, \varepsilon_n).$$

Тогда на одном вероятностном пространстве с $A, B, E$ можно определить случайную величину $E'$, для которой размеры всех семи областей на диаграмме тройки $A, B, E'$ (рис. 2.4) такие же, как у тройки $A, B, E$ (с точностью $o(n)$), за исключением области, содержащей информацию $o(E')$, не входящую в $A, B$, размер которой теперь равен $o(n)$. (Другими словами, $H(E'|A, B) = o(n)$.)

Неформально говоря, случайная величина $E'$ получается из $E$ удалением всей информации, которая не входит в пару $A, B$. Аналогичное утверждение верно для любого количества совместно распределенных случайных величин $\alpha_1, \dots, \alpha_k$: проведём серию из $n$ независимых испытаний, и обозначим через $A_1, \dots, A_k$ полученные случайные величины. Из случайной величины $A_k$ можно удалить «уникальную информацию», не входящую в $A_1, \dots, A_{k-1}$ (точнее, сделать её равной $o(n)$), изменяя размеры всех остальных областей на диаграмме для $A_1, \dots, A_k$ всего лишь на $o(n)$.

**303** Докажите теорему Алсведе – Кёрнера для $k = 2$.

Заметим, что переход к независимым испытаниям существен: если $\alpha$ и $\varepsilon$ — равномерно распределённые зависимые величины с двумя значениями, то построить $\varepsilon'$, которое было бы функцией от $\alpha$ и имело бы нужную энтропию, нельзя.
Теперь объясним, как из теоремы Алсведе – Кёрнера следует теорема 218. Пусть заданы некоторые совместно распределённые случайные величины $\alpha, \beta, \gamma, \delta, \varepsilon$. Сначала, не используя этой теоремы, докажем неравенство теоремы 218 с добавочным членом $3H(\varepsilon|\alpha, \beta)$ в правой части. Нетрудно убедиться, что оно получается следующим неравенством

$$ 
\begin{aligned}
H(\varepsilon|\gamma) &\le H(\varepsilon|\alpha) + H(\varepsilon|\beta) + I(\alpha:\beta|\gamma), \\
H(\varepsilon|\delta) &\le H(\varepsilon|\alpha) + H(\varepsilon|\beta) + I(\alpha:\beta|\delta), \\
H(\varepsilon) &\le H(\varepsilon|\gamma) + H(\varepsilon|\delta) + I(\gamma:\delta)
\end{aligned}
$$

с равенством

$$ I(\alpha:\beta) + 2H(\varepsilon|\alpha) + 2H(\varepsilon|\beta) = H(\varepsilon) + W(\alpha, \beta, \varepsilon) + 3H(\varepsilon|\alpha, \beta). $$

Третье неравенство нам уже встречалось (задача 295 на с. 382), а два предыдущих следуют из его условной версии. Все они являются линейными комбинациями базисных неравенств. Равенство же легко проверить, нарисовав диаграмму для случайных величин $\alpha, \beta, \varepsilon$.

Теорема Алсведе – Кёрнера позволит нам избавиться от «паразитного» члена $3H(\varepsilon|\alpha, \beta)$. Для этого рассмотрим $n$ независимых копий $\alpha_i, \beta_i, \gamma_i, \delta_i, \varepsilon_i$ (при $i=1, ..., n$) нашего распределения и положим $A = (\alpha_1, ..., \alpha_n), B = (\beta_1, ..., \beta_n), C = (\gamma_1, ..., \gamma_n), D = (\delta_1, ..., \delta_n) E = (\varepsilon_1, ..., \varepsilon_n)$. Энтропии $A, B, C, D, E$ в $n$ раз больше энтропий $\alpha, \beta, \gamma, \delta, \varepsilon$; то же самое верно для пар, троек и так далее. Применим к случайным величинам $\alpha, \beta, \varepsilon$ теорему Алсведе – Кёрнера и получим новую случайную величину $E'$, определённую на том же вероятностном пространстве, что и $A, B, C, D, E$. Затем применим к пятерке $A, B, C, D, E'$ только что доказанное неравенство с дополнительным членом $3H(E'|A, B)$ в правой части. Заменим в этом неравенстве дополнительный член на $o(n)$. Затем заменим всюду $E'$ на $E$. Все члены неравенства, содержащие $C$ или $D$, не содержат $E'$, поэтому они замены не почувствуют. (В этом месте мы используем ту же особенность нашего неравенства, что в методе независимизации.) А каждый из членов неравенства, содержавших только $A, B, E'$, является суммой размеров областей диаграммы $A, B, E'$, отличных от области $H(E'|A, B)$. Поэтому в результате замен неравенство сохранится с точностью $o(n)$. Наконец, сокращая на $n$ и переходя к пределу, получаем неравенство теоремы 218.

Полезно сравнить методы независимизации и удаления уникальной информации. И в том, и в другом случае мы модифицировали совместное распределение случайных величин $A, B, C, D, E$ (при независимизации мы тоже могли перейти к серии испытаний — это бы не помешало, но и не помогло). В первом случае мы сохраняли совместные распределения $A, B, E$ и $A, B, C, D$. Во втором случае мы сохраняли только совместное распределение $A, B, C, D$. В первом случае мы убивали член $I(CD: E|AB)$, а во втором — член $H(E|AB)$, не изменяя (или изменяя несущественно) все остальные члены в неравенстве.
# 11. Общая информация

## 11.1. Представление слов в несжимаемом виде

В какой степени можно представлять себе «информацию, содержащуюся в данном слове», как нечто материальное? Допустим, у нас есть слово х, «содержащее $n$ битов информации», то есть имеющее сложность $n$. Можно ли — как если бы эти биты были камешками — разложить их на две равные кучки? Этому вопросу можно придать формальный смысл: можно ли найти такие слова $x_1$ и $x_2$ сложности $n/2$, для которых $KS(x_1|x) \approx 0$, $KS(x_2|x) \approx 0$ (слова $x_1, x_2$ «не содержат новой информации по сравнению с х») и $KS(x|x_1, x_2) \approx 0$ («никакая информация не потеряна»)? Если, как обычно, понимать приближённое равенство как совпадение с точностью до $O(\log n)$, где $n$ — максимальная длина (или сложность) рассматриваемых слов, то ответ на этот вопрос положительный, как мы сейчас увидим.

Будем говорить, что слова х и у эквивалентны с точностью $c$, или с-эквивалентны, если $KS(x|y) \le c$ и $KS(y|x) \le c$. Это отношение не является, конечно, настоящим отношением эквивалентности: если х эквивалентно у, а у эквивалентно $z$ с точностью $c$, то мы можем утверждать лишь, что х эквивалентно $z$ с точностью $2c + O(\log c)$. (Можно было бы рассматривать не слова, а последовательности слов полиномиально растущей длины и говорить, что последовательность $x_0, x_1, \dots$ эквивалентна $y_0, y_1, \dots$, если $KS(x_i|y_i) = O(\log i)$ и $KS(y_i|x_i) = O(\log i)$; тогда бы это было настоящее отношение эквивалентности.)

Легко проверить, что сложности с-эквивалентных слов мало отличаются (отличаются не более чем на $O(c)$ и даже $c + O(\log c)$). Более общо, при замене слова на другое, с-эквивалентное первому, все сложности с его участием меняются на $O(c)$, так что, скажем, величина $I(x:y|z)$ меняется не более чем на $O(c)$ при замене любого из слов х, у, z (или всех трёх) на с-эквивалентное. Теперь мы можем сделать следующее (почти очевидное) наблюдение:

**Теорема 221.** Для всякого слова х существует слово х' длины $KS(x)$, эквивалентное х с точностью до $O(\log KS(x))$. Это слово является «несжимаемым» (сложность близка к длине) с той же точностью.

◀ В самом деле, возьмём в качестве $x'$ любое кратчайшее описание слова х, которое как раз имеет длину $KS(x)$ и сложность, отличающуюся от $KS(x)$ не более, чем на константу. Ясно, что $KS(x|x') = O(1)$, поскольку х восстанавливается по $x'$. С другой стороны, цепочка неравенств

$$KS(x) \le KS(x, x') \le KS(x') \le I(x') = KS(x)$$
(выполненных с точностью до константы), показывает, что все эти неравенства обращаются в равенства (с той же точностью), и потому $KS(x, x') \approx KS(x)$ и по теореме о сложности пары $KS(x'|x) \approx 0$ с точностью до $O(\log KS(x))$. ►

Из этого утверждения очевидно следует ответ на поставленный нами вопрос о разбиении слова на части: можно заменить слово на эквивалентное несжимаемое, и в качестве $x_1$ и $x_2$ взять просто-напросто левую и правую половины.

**304** Проверьте, что выполнены все требуемые свойства.

**305** Докажите, что если $KS(y|x) = n$, то существует такое («промежуточное») $z$, что $KS(z|x) \approx n/2$ и $KS(y|z) \approx n/2$ с точностью до $O(\log KS(x, y))$.

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

Пусть даны слова х и у, причём $KS(y|x) \approx 0$ («информация в слове у является частью информации в слове х»). Тогда существует несжимаемое слово $x'$, эквивалентное х, некоторое начало $y'$ которого эквивалентно у. (Такое начало автоматически будет несжимаемым и иметь длину $KS(y)$.) Более точно это утверждение формулируется так:

**Теорема 222.** Для любых слов х и у существуют слова $x'$ и $y'$, эквивалентные х и у (соответственно) с точностью до $O(KS(y|x) + \log KS(x, y))$ и несжимаемые с той же точностью, причём $y'$ является началом $x'$.

◄ Рассмотрим в качестве $y'$ кратчайшее описание слова у, оно несжимаемо и имеет длину $KS(y)$. Кроме того, оно эквивалентно у.

Теперь рассмотрим кратчайшее описание $z'$ слова х при известном слове у; оно также будет несжимаемым, а длина его равна $KS(x|y)$. Зная $y'$ и $z'$, можно восстановить сначала у, а потом и х, поэтому сложность пары $y', z'$ не меньше $KS(x,y)$. С другой стороны, суммарная длина слов $y'$ и $z'$ равна $KS(y) + KS(x|y) \approx KS(x,y)$, так что слово $x' = y'z'$ несжимаемо.

Как мы видели, $KS(x|x') \approx 0$. Осталось доказать, что $KS(x'|x) \approx 0$. Из равенства $KS(x|x') \approx 0$ следует $KS(x, x') \approx KS(x') \approx KS(x, y)$. Кроме того, $KS(x, y)$ примерно равно $KS(x)$ (с точностью $O(KS(y|x)))$. Следовательно, $KS(x, x') \approx KS(x)$, откуда по теореме Колмогорова – Левина отсюда следует $KS(x'|x) \approx 0$. ►

Эта теорема показывает, что пару слов х, у с $KS(y|x) \approx 0$ действительно можно себе представлять так: слово x состоит из $KS(x)$ почти что материальных битов, из которых первые $KS(y)$ битов образуют у.

### 11.2. Выделение общей информации

Можно пойти ещё дальше и интересоваться аналогичным утверждением для двух произвольных слов. Напомним, что три основных сложностных характеристики пары слов х, у — это их сложности $KS(x)$, $KS(y)$ и сложность пары $KS(x, y)$; через них, как мы говорили в разделе 2.3, выражаются (с логарифмической точ-
ностью) условные сложности и взаимная информация:

$$
\begin{align*}
KS(x|y) &= KS(x,y) - KS(y), \\
KS(y|x) &= KS(x,y) - KS(x), \\
I(x:y) &= KS(x) + KS(y) - KS(x,y)
\end{align*}
$$

(см. рис. 2.2 на с. 56). Там же говорилось, что иногда этот рисунок можно понимать буквально, взяв в качестве х и у пересекающиеся подслова длинного случайного слова. Можно предположить, что это общий случай, то есть верна следующая гипотеза:

для любых слов х и у существует несжимаемое слово *u* длины *KS(x, y)*,
эквивалентное (с логарифмической точностью) паре ⟨*x*, *y*⟩, причём на-
чало этого слова длины *KS(x)* эквивалентно *x*, а конец длины *KS(y)*
эквивалентен *y* (с той же точностью).

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

$$
\begin{align*}
KS(z|x) &= 0, \\
KS(z|y) &= 0, \\
KS(z) &= I(x:y)
\end{align*}
$$

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

**306** Покажите, что если общая информация выделяется (найдётся слово *z* с указанными тремя свойствами), то для пары слов х, у выполнена сформулированная выше гипотеза (найдётся слово *u* с указанными свойствами).

Построим опровергающий нашу гипотезу пример. Это можно сделать самыми разными способами, о которых мы ещё будем говорить, но, видимо, самый про- стой из них (предложенный Ан. А. Мучником в [115]) таков. Для определённости договоримся, что строимые нами слова х и у с невыделяемой общей информацией будут иметь сложность 2n, а общая информация будет равна n (с логарифмической точностью), то есть пара ⟨x, y⟩ должна иметь сложность 3n.

Мы хотим, чтобы из этой пары не выделялась общая информация, то есть чтобы не существовало слова *z* сложности *n*, для которого *KS(z|x)* и *KS(z|y)* обращаются в нуль (все равенства — с точностью *O(log n)*). Нам удобнее будет записать эти условия иначе: *KS(x|z) = n* и *KS(y|z) = n*. Это утверждение будет выполняться с некоторым запасом (мы разрешим сложностям быть даже немного больше *n*):

**Теорема 223.** Для любого *n* существуют слова *x* и *y*, для которых $KS(x) = 2n + O(\log n)$, $KS(y) = 2n + O(\log n)$, $I(x:y) = n + O(\log n)$, но не существует такого слова *z* сложности меньше $1,1n$, что $KS(x|z) < 1,1n$ и $KS(y|z) < 1,1n$.
◀ Как мы знаем, список всех слов сложности меньше *k* сам имеет сложность не больше *k* + *O*(log *k*) (чтобы его задать, достаточно, помимо числа *k*, указать число таких слов, которое имеет порядок *O*(2^k) и потому требует *k* битов).

Аналогичное рассуждение позволяет установить, что список всех пар слов ⟨u, v⟩, для которых $KS(u) < 1,1n$ и $KS(v|u) < 1,1n$, имеет сложность не больше $2,2n + O(\log n)$: помимо *n*, достаточно указать число таких пар, а оно есть $O(2^{2,2n})$.

По тем же причинам список всех слов сложности меньше $2n$ имеет сложность не больше $2n + O(\log n)$, а список слов сложности меньше $3n$ имеет сложность не больше $3n + O(\log n)$.

Что можно сказать о сложности всех этих списков вместе взятых? Её можно оценить суммой сложностей. Но оказывается, что есть лучшая оценка: сложность всех списков вместе не превосходит максимальной из наших оценок (с точностью до $O(\log n)$). В самом деле, при известном *n* каждый из этих списков задаётся числом своих элементов. Более того, достаточно знать суммарное число элементов в этих списках, поскольку их можно перечислять и ждать появления нужного числа элементов: достигнув нужной суммы, мы автоматически исчерпаем все списки. А сумма нескольких чисел требует для записи лишь на несколько битов больше, чем самое длинное из них.

Итак, все вместе эти списки имеют сложность $3n + O(\log n)$. Пусть эти списки у нас есть. Используя их, мы перебором находим пару слов х, у длины $2n + 2$ каждое, для которых:

* $KS(x) \ge 2n$;

* $KS(y) \ge 2n$;

* $KS(x, y) \ge 3n$;

* не существует слова z, для которого одновременно $KS(z) < 1,1n$, $KS(x|z) < 1,1n$ и $KS(y|z) < 1,1n$.

Все эти условия проверяются по нашим спискам, так что надо только убедиться, что такая пара существует. Заметим, что первое условие бракует не более четверти всех пар (всего слов х имеется $2^{2n+2}$, из них негодных не больше $2^{2n}$). Аналогично со вторым условием. Третье отбрасывает не более $2^{3n}$ пар, что ещё меньше. Наконец, четвертое условие бракует не более $2^{1,1n} \times 2^{1,1n}$ пар для каждого из не более чем $2^{1,1n}$ значений z, то есть всего не более $2^{3,3n}$ пар, что тоже очень мало по сравнению с общим числом пар.

Сложность найденной таким образом (первой в порядке перебора) пары будет не меньше $3n$ и не больше сложности наших списков, то есть $3n + O(\log n)$; сложность каждого слова будет не меньше $2n$ и не больше его длины, то есть $2n + O(1)$, и построение гарантирует, что общая информация не выделяется. ▶

Видно, что в нашем рассуждении есть «запас»; проведём подсчёты более аккуратно. Пусть мы хотим построить слова х и у сложности $2n$ с общей информацией *n*, но так, чтобы нельзя было найти слово *z*, для которого одновременно

$$KS(z) < \alpha, \quad KS(x|z) < \beta \quad \text{и} \quad KS(y|z) < \gamma.$$
Список всех пар $u, v$ с $KS(u) < \alpha$ и $KS(v|u) < \beta$ имеет сложность $\alpha + \beta$, поэтому возникает условие $\alpha + \beta < 3n$. Аналогично появляется условие $\alpha + \gamma < 3n$. Наконец, для существования пары нужно, чтобы запрешённых пар было меньше $2^{4n}$; это даёт условие $\alpha + \beta + \gamma < 4n$. Если все эти условия выполнены, то искомую пару $x, y$ построить можно.

Более того, мы можем параллельно проводить отбраковку пар для всех тро-
ек целых чисел $\alpha, \beta, \gamma$, удовлетворяющих указанным неравенствам. Таких троек
$O(n^3)$, поэтому если неравенства выполняются с логарифмическим запасом, то
останутся неотбракованные пары; сложность объединения полиномиального числа
перечислимых списков также увеличится на $O(\log n)$. Получаем такой результат:

**Теорема 224.** Для любого $n$ существуют слова $x$ и $y$ сложности $2n + O(\log n)$, для которых $KS(x, y) = 3n + O(\log n)$, и при этом для любого слова $z$ выполнено хотя бы одно из трёх неравенств:

$$
(a) \ KS(z) + KS(x|z) \geq 3n - O(\log n);
$$

$$
(\text{б}) \ KS(z) + KS(y|z) \geq 3n - O(\log n);
$$

$$
(в) \ KS(z) + KS(x|z) + KS(y|z) \geq 4n - O(\log n).
$$

Более подробно утверждение теоремы формулируется так: для некоторой кон-
станты $c$ и для всех $n$ существуют слова $x$ и $y$, сложности которых отличаются
от $2n$ не более чем на $c \log n$, сложность пары отличается от $3n$ не более чем на
$c \log n$ и для любого слова $z$ выполнено одно из трёх неравенств с заменой $O(\log n)$
в правой части на $c \log n$.

Построенная в этой теореме пара слов является «наихудшей» с точки зрения
возможности выделения общей информации. Это можно уточнить следующим обра-
зом. Для данной пары х, у можно рассмотреть множество C(x, y) ⊂ N³, состоящее
из всех троек α, β, γ, для которых существует слово z с

$$
KS(z) < \alpha, \ KS(x|z) < \beta \text{ и } KS(y|z) < \gamma.
$$

Множество $C(x, y)$ «наследственно вверх» (вместе с каждой тройкой содержит и все покоординатно большие) и зависит от пары $x, y$ (а не только от сложностей слов $x, y$ и сложности пары); как мы увидим на примере пар с $KS(x) = KS(y) = 2n$ и $KS(x, y) = 3n$, соответствующие множества могут сильно различаться. При этом для пары пересекающихся подслов несжимаемого слова множество $C(x, y)$ будет максимально возможным, а для построенной в теореме 224 — минимально возможным.

Рассмотрим этот вопрос более детально. Пусть даны слова $x, y$ сложности $2n$ с общей информацией $n$ (как обычно, мы допускаем отклонения порядка $O(\log n)$, не оговоривая этого особо). Любая тройка $\langle \alpha, \beta, \gamma \rangle$, принадлежащая $C(x, y)$, должна удовлетворять (с логарифмической точностью) очевидным неравенствам

$$
\alpha + \beta \geq 2n, \quad \alpha + \gamma \geq 2n, \quad \alpha + \beta + \gamma \geq 3n
$$

(поскольку $KS(x) \le KS(z) + KS(x|z)$ и так далее). Это означает, что множество $C(x,y)$ содержится в множестве $C_M$ всех троек, удовлетворяющих этим неравенствам. (И здесь аккуратная формулировка требовала бы оговорок о логарифмических погрешностях, которые мы для краткости опускаем.)
Как изобразить это множество наглядно? При каждых $\beta$ и $\gamma$ есть некоторое минимальное значение $\alpha_0(\beta, \gamma)$, начиная с которого $\langle \alpha, \beta, \gamma \rangle$ попадает в $C_M$. График функции $\langle \beta, \gamma \rangle \mapsto \alpha_0(\beta, \gamma)$, представляет собой поверхность, состоящую из трёх плоских частей (соответствующих трём неравенствам), которую можно изобразить с помощью линий уровня (рис. 11.1). Каждая линия уровня соответствует некоторому значению $\alpha$ и отделяет на плоскости $\beta, \gamma$ удовлетворяющие неравенствам пары от не удовлетворяющих.

<figure><img src="image_35.png" /><figcaption>Рис. 11.1. Множество $C_M$.</figcaption></figure>

<figure><img src="image_36.png" /><figcaption>Рис. 11.2. Множество $C_m$.</figcaption></figure>

Глядя на эту картинку, можно убедиться, что для случая пары $\langle x, y \rangle$ с полностью выделяемой общей информацией (пересекающиеся куски несжимаемого слова) множество $C(x, y)$ равно $C_M$, так что верхняя оценка $C_M$ для этого множества достигима. Несложно понять, как нужно выбирать слово $z$ для данных $\alpha, \beta$ и $\gamma$: при $\alpha < n$ выбираем $z$ внутри общей части, тем самым сокращая условную сложность обоих слов $x$ и $y$ на $\alpha$. При $\alpha > n$, помимо общей части, можно присоединить к $z$ куски из остатков слов $x$ и $y$ (в некоторой пропорции; изменение пропорции соответствует сдвигу по наклонному отрезку на рисунке).

Теорема 224 даёт пример пары $x, y$ с меньшим множеством $C(x, y)$. В самом деле, для построенной в этой теоремы пары множество $C(x, y)$ содержится не только в $C_M$, но и в объединении множеств решений неравенств

$$ \alpha + \beta \ge 3n, \quad \alpha + \gamma \ge 3n, \quad \alpha + \beta + \gamma \ge 4n $$

(соответствующих неравенствам (а)-(в) этой теоремы). Пересекая $C_M$ с этим объединением, мы получаем меньшее множество, которое мы назовём $C_m$; оно изображено на рисунке 11.2.

Таким образом, для построенной в теореме пары $x, y$ множество $C(x, y)$ содержится в $C_M$. Оказывается, что оно совпадает с $C_M$; более того, для любой пары $x, y$ (а не только для пары из теоремы) множество $C_M$ содержится в $C(x, y)$.

Чтобы проверить это, надо для каждой точки $\langle \alpha, \beta, \gamma \rangle$ из $C_M$ указать подходящее $z$. Достаточно делать это для минимальных троек (поскольку увеличение не выводит из $C(x, y)$). Точки на наклонных линиях на рисунке соответствуют словам $z$, которые соединяют часть слова $x$ с частью слова $y$ в некоторой пропорции. Например, точка $(1,5n, 1,5n)$ при $\alpha = n$ соответствует слову $z$ длины $n$, состоящему из двух половин; левая половина содержит $n/2$ битов из кратчайшего описания
слова х, а правая содержит $n/2$ битов кратчайшего описания слова у. Аналогичным образом точка $(n, n)$ соответствует слову длины $2n$, содержащему по $n$ битов того и другого описаний. Точка $(n + h, h)$ (для $h$ от 0 до $n$) соответствует слову $z$ длины $2n - h$, являющемуся началом кратчайшего описания слова у. Тогда $KS(y|z)$ равно числу битов этого описания, не вошедших в $z$, то есть $h$. С другой стороны, $KS(x|z)$ не превосходит суммы сложности $x$ относительно $y$, равной $n$, и сложности $y$ относительно $z$, равной $h$. Наконец, точки вида $(h, 0)$ при $h$ от 0 до $n$ соответствуют словам $z$ сложности $3n - h$, которые содержат полностью всё слово $y$ и $n - h$ битов кратчайшего описания слова $x$ при известном $y$.

В итоге получаем такое утверждение:

**Теорема 225.** Для любой пары слов х, у множество $C(x, y)$ заключено (с обычными оговорками о логарифмической точности) между нижней оценкой $C_m$ и верхней $C_M$; обе оценки достигаются для некоторых пар.

Зная множество $C(x, y)$ для данных слов х, у, можно уже чисто формально получать разные следствия. Вот один пример:

**Теорема 226.** Пусть $C(x, y) = C_m$ (пара из теоремы 224). Тогда для любого слова $z$ выполняется неравенство

$$KS(z) \le 2 KS(z | x) + 2 KS(z | y).$$

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

◀ Можно считать, что $KS(z) = O(n)$ (для слов большой сложности $KS(z|x)$ и $KS(z|y)$ близки к $KS(z)$ и уж заведомо больше половины $KS(z)$).

Перепишем неравенство, выразив $KS(z|x)$ и $KS(z|y)$ через величины, входящие в определение $C(x, y)$:

$$KS(z) \le 2 KS(x, z) - 2 KS(x) + 2 KS(y, z) - 2 KS(y)$$

и далее

$$KS(z) \le 2 KS(z) + 2 KS(x|z) - 2 KS(x) + 2 KS(z) + 2 KS(y|z) - 2 KS(y),$$

то есть

$$2 KS(x) + 2 KS(y) \le 3 KS(z) + 2 KS(x|z) + 2 KS(y|z).$$

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

**307** Покажите, что при малых значениях $KS(z)$ верна лучшая оценка

$$KS(z) \le KS(z|x) + KS(z|y),$$

но если не ограничивать $z$, то константу 2 улучшить нельзя.
### 11.3. Комбинаторный смысл общей информации

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

Что означает, что для данных слов х и у найдётся слово z, при котором $KS(z) < \alpha$, $KS(x|z) < \beta$ и $KS(y|z) < \gamma$? Обозначим через $U_n(z)$ множество всех слов, сложность которых при известном z меньше n. Таких слов (примерно) $2^n$. Наше условие означает, что пара $(x, y)$ принадлежит одному из множеств $U_\beta(z) \times U_\gamma(z)$ при $KS(z) < \alpha$; всего таких множеств имеется (примерно) $2^\alpha$.

Таким образом, условие $(\alpha, \beta, \gamma) \in C(x, y)$ означает, что пара $(x, y)$ принадлежит объединению перечислимого семейства из $2^\alpha$ «прямоугольников» размера $2^\beta \times 2^\gamma$ (прямоугольником мы называем декартово произведение любых двух множеств слов). Верно и обратное: если пара $(x, y)$ покрывается объединением перечислимого семейства из $2^\alpha$ прямоугольников размера $2^\beta \times 2^\gamma$, то тройка $(\alpha, \beta, \gamma)$ (плюс сложность порождающего это семейство алгоритма и логарифмическая допавка) принадлежит $C(x, y)$. Таким образом, можно сказать, что множество $C(x, y)$ для данной пары зависит от того, какие (порождаемые простыми алгоритмами) перечислимые семейства прямоугольников её покрывают.

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

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

Свойство, которое будет гарантировать, что граф плохо покрывается прямоугольниками, совсем простое: мы будем рассматривать графы, в которых нет четырёхугольников (не существует таких вершин a, b в одной доле и c, d в другой, что все четыре ребра ac, ad, bc, bd входят в граф). Имеет место следующая простая комбинаторная

**Лемма.** Рассмотрим произвольный двудольный граф с l вершинами слева и L вершинами справа (считая для определённости, что $l \le L$). Если этот граф не содержит четырёхугольников, то плотность рёбер в нём (число рёбер, делённое на $L$) не превосходит большей из оценок $O(1/\sqrt{L})$ и $O(1/l)$.

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

**Доказательство.** Каждой из l вершин с левой стороны соответствует множество её соседей справа. Условие леммы (отсутствие четырёхугольников) означает, что пересечение любых двух таких множеств содержит не более одного элемента. Формула включений и исключений позволяет в таком случае оценить число эле-
ментов в объединении: оно не меньше суммы размеров всех множеств (эта сумма есть общее число рёбер графа) минус число пар множеств (которое не больше $l^2$). С другой стороны, объединение содержит не более L элементов.

Отсюда мы заключаем, что общее число рёбер графа не превосходит $L + l^2$, а их плотность не больше $1/l + l/L$. Это даёт необходимую оценку при $l \le \sqrt{L}$, когда первый член больше второго. Если же $l \ge \sqrt{L}$, то мы получаем оценку $O(l/L)$, что недостаточно (мы хотим $O(1/\sqrt{L})$). Чтобы получить требуемое, заметим, что мы можем оставить от графа лишь $\sqrt{L}$ вершин в левой доле, для которых число соседей максимально. От этого его плотность лишь возрастёт, а после этого наше рассуждение даёт необходимую оценку. Лемма доказана.

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

Такой граф проще всего построить геометрически. Рассмотрим произвольное конечное поле $F$ и плоскость (двумерное векторное пространство) над этим полем. Элементами левой доли будут точки плоскости, элементами правой доли — прямые. Четырёхугольников нет, потому что (как учил ещё Евклид) через две различные точки проходит не более одной прямой.

Оценим число вершин и рёбер такого графа. Если поле содержит (примерно) $2^n$ элементов, то вершин с каждой стороны будет примерно $2^{2n}$, а рёбер — примерно $2^{3n}$ (на каждой прямой примерно $2^n$ точек, и через каждую точку проходит примерно $2^n$ прямых). Таким образом, для большинства ребер $(x, y)$ этого графа сложности $KS(x)$ и $KS(y)$ близки к $2n$, сложность пары $KS(x,y)$ близка к $3n$, а $I(x:y)$ примерно равно $n$.

**308** Показите, что $I(x:y) = n + O(\log n)$ для всех рёбер этого графа, сложность которых больше $3n - O(\log n)$.

Чтобы дать новое доказательство теоремы 223, посмотрим, какую часть построенного графа (множества пар) можно покрыть $2^{1,1^n}$ прямоугольниками размера $2^{1,1^n} \times 2^{1,1^n}$ (мы используем те же) значения параметров $\alpha, \beta$ и $\gamma$, что и в теореме 223). К каждому такому прямоугольнику можно применить доказанную лемму, по которой плотность рёбер в нём не превосходит $2^{-0,55n}$, так что общее число рёбер, покрытых всеми прямоугольниками, не больше

$$2^{1,1^n} \times 2^{1,1^n} \times 2^{1,1^n} \times 2^{-0,55n} = 2^{2,75n} \ll 2^{3n}.$$

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

**309** Показите, что любое ребро $(x, y)$, сложность которого близка к $3n$, не допускает выделение общей информации (в смысле теоремы 223). [Указание: множество покрытых рёбер перечисляется простым алгоритмом.]

В этом построении (если рассматривать его как альтернативное доказательство теоремы 223) есть один тонкий момент: нам нужно иметь поле из $2^n$ элементов (или хотя бы из близкого числа элементов). Поле из $2^n$ элементов может быть построено
как расширение степени $n$ поля из двух элементов (поле разложения многочлена $x^{2^n} - x$); кроме того, можно воспользоваться известным из теории чисел фактом, что между $m$ и $2m$ всегда есть простое число («постулат Бертрана», который для больших $m$ следует, например, из теоремы о плотности распределения простых чисел).

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

Ради симметрии можно было бы перейти к проективной плоскости (что мало влияет на сложность, так как бесконечно удалённые точки составляют небольшую долю). Или можно говорить о случайной паре ортогональных (относительно скалярного произведения произведения $x_1y_1 + x_2y_2 + x_3y_3$) прямых в трёхмерном векторном пространстве над конечным полем.

Было бы интересно построить аналогичный пример на основе точек на вещественной сфере (прямых в трёхмерном пространстве). При естественном подходе (дискретизировать с какой-то точностью) возникает проблема: когда $x$ и $y$ близки, то им сразу много точек почти ортогональны, и надо это как-то оценивать.

Как и раньше, наугад взятый коэффициент $(1,1)$ не оптимален. Ровно то же самое рассуждение можно проводить для любых $\alpha, \beta, \gamma$, и оно окончится успешно (то есть число покрытых рёбер будет меньше $3n$), если числа $\alpha, \beta, \gamma$ не слишком велики. Применяя лемму (ровно в той форме, как она сформулирована), мы получаем, что множество $C(x, y)$ для нашего примера (случайной пары точка-прямая) содержится (с точностью до $O(\log n)$) в множестве $S$, граница которого изображена (в виде линий уровня) на рисунке 11.3. (Линия уровня для $\alpha = 3n$ состоит из начала координат.)

<figure><img src="image_37.png" /><figcaption>Рис. 11.3. Множество $S$.</figcaption></figure>

При $\beta \le \gamma$ множество состоит из всех решений неравенства

$$ \alpha + \gamma/2 + \max\{\gamma/2, \beta\} \ge 3n, $$

а при $\gamma \le \beta$ из симметричного ему множества решений неравенства

$$ \alpha + \beta/2 + \max\{\beta/2, \gamma\} \ge 3n. $$
Это множество можно ещё пересечь с $С_М$ (поскольку $С(x, y) \subset С_М$ для любой пары $(x, y)$); получатся более замысловатые линии уровня, которые мы рисовать не будем.

Заметим, что в отличие от ранее приведённых примеров, это лишь верхняя оценка для множества $С(x, y)$; каково это множество в точности, мы не знаем. При исследовании этого вопроса надо иметь в виду следующее. Может оказаться, что множество $С(x, y)$ зависит от выбора поля $\mathbb{F}$. Это кажется вполне правдоподобным, как показывает следующая задача.

**310** Пусть мощность поля $\mathbb{F}$ есть полный квадрат: $|\mathbb{F}| = q^2$ (тогда $q$ — степень простого числа). Пусть $u$ — случайная прямая в $\mathbb{F}^2$, а $v$ — случайная точка на прямой $u$. Докажите, что $С(u, v)$ содержит тройку $(1, 5n; n; n)$, где $n = \log |\mathbb{F}| = 2 \log q$, лежащую на границе множества $S$ на рис. 11.3 (игнорируя логарифмические добавки). (А для произвольного поля мощности примерно $2^n$ доказать это не удаётся.)

[Указание. Воспользуйтесь тем, что существует подполе $\mathbb{G}$ поля $\mathbb{F}$ мощности $q$. По этой причине каждый элемент из $\mathbb{F}$ может быть представлен в виде $t + s\alpha$, где $t, s \in \mathbb{G}$, а $\alpha$ — некоторый фиксированный элемент $\mathbb{F}$ (называемый примитивным элементом $\mathbb{F}$ над $\mathbb{G}$). Пользуясь этим, можно множество всех пар (прямая, точка на прямой) разбить на $q^3$ множеств, каждое из которых состоит из $q^3$ пар. При этом каждое из этих множеств содержит не более $q^2$ различных точек и не более $q^2$ различных прямых. Для построения такого разбиения будем задавать каждую прямую уравнением $y = kx + b$ (игнорируя прямые, не задающиеся таким уравнением — все они не случайны) и представим коэффициенты этого уравнения в виде $k = f + r\alpha$ и $b = h + s\alpha$, где $f, r, h, s \in \mathbb{G}$. А абсциссу $x$ каждой точки $(x, y)$ на этой прямой представим в виде $x = g + t\alpha$ (откуда нетрудно найти, что $y = fg + h + (ft + gr + s)\alpha + rt\alpha^2$). Фиксируя $r, t, s$ (что можно сделать как раз $q^3$ способами), мы получаем разбиение множества всех пар (прямая, точка на ней). При этом каждое из разбивающих множеств содержит $q^2$ прямых (что хорошо) и $q^3$ точек (что плохо). Сократить количество точек можно с помощью следующего трюка. Будем представлять коэффициенты каждой прямой в виде $k = f + r\alpha$, $b = h + (s - ft)\alpha$, а точки на ней в виде $(g + t\alpha, fg + h + (gr + s)\alpha + rt\alpha^2)$ (где по-прежнему все коэффициенты $f, g, h, s, r, t$ принадлежат $\mathbb{G}$). Фиксируя $r, t, s$, мы получаем уже множество, содержащее как $q^2$ прямых (однозначно задаваемых парами $(f, h)$), так и $q^2$ точек (однозначно задаваемых парами $(g, fg + h)$).]

**311** Докажите, что от выбора случайного ребра $(x, y)$ в графе точек и прямых множество $С(x, y)$ не зависит (с логарифмической точностью): принадлежность тройки $(\alpha, \beta, \gamma)$ этому множеству определяется тем, какое максимальное число рёбер может быть в прямоугольнике $2^\beta \times 2^\gamma$. А именно, для попадания в $С(x, y)$ необходимо и достаточно, чтобы это число, умноженное на $2^\alpha$, было больше общего числа рёбер (умноженного или делённого на многочлен от $n$).

[Указание (И. Разенштейн, [129]). Граф транзитивен: для любой пары рёбер существует перестановка точек и перестановка прямых, переводящая граф в себя и совмешающая эти рёбра. Поэтому, если есть прямоугольник с большим числом рёбер, то можно покрыть граф случайными копиями этого прямоугольника, взяв их
количество с полиномиальным запасом; если же все прямоугольники маленькие, то в них не хватит рёбер.]

Как и в предыдущем разделе, из доказанных утверждений следует неравенство, оценивающее безусловную сложность z через условные:

**Теорема 227.** Пусть х, у — случайная пара точка — прямая на плоскости над конечным полем из (примерно) $2^n$ элементов. Тогда для любого слова z выполняется неравенство

$$KS(z) \le 2 KS(z|x) + 2 KS(z|y) + O(\log n).$$

◀ Как и раньше, это сводится к проверке неравенства

$$8n \le 3\alpha + 2\beta + 2\gamma$$

для всех $\langle \alpha, \beta, \gamma \rangle \in C(x, y)$. А для этого достаточно проверить, что это неравенство верно для всех точек множества из $S \cap C_M$. Без потери общности можно считать, что $\beta \le \gamma$. Если при этом $\beta$ больше половины $\gamma$, то искомое неравенство получается сложением удвоенного неравенства $\alpha + \gamma/2 + \beta \ge 3n$, входящего в определение $S$, и неравенства $\alpha + \gamma \ge 2n$, входящего в определение $C_M$. А иначе оно получается сложением неравенства $\alpha + \gamma \ge 3n$ из определения $S$ и неравенств $\alpha + \beta \ge 2n$ и $\alpha + \beta + \gamma \ge 3n$ из определения $C_M$. ▶

Итак, у нас есть два разных построения пар с невыделяемой общей информацией. Первое из них даёт лучшие оценки для множества $C(x, y)$; в чём же тогда преимущества второго? Наиболее явное, хотя и неформализуемое преимущество состоит в том, что мы нашли комбинаторную причину невыделяемости общей информации (существование графов, плохо покрываемых прямоугольниками), а также простое достаточное условие для этого (отсутствие четырёхугольников).

Более формально можно сказать, что во втором случае мы построили пример, являющийся «стохастическим»: наша пара является элементом максимальной сложности в некотором простом множестве.

В первом (неконструктивном) доказательстве это, видимо, не так; но можно построить и пример стохастических объектов, достигающих наилучших оценок для множества $C(x, y)$, доказав вероятно с существование графа, который плохо покрывается прямоугольниками (см. [129]).

Ещё один способ объяснить, чем второе доказательство лучше — это рассмотреть сложность с оракулом. Фактически мы доказали, что для любого оракула А существуют слова х, у сложности (обычной, без оракула) $2n$ с общей информацией $n$, для которых не существует слова $z$ с $KS^A(z) < 1,1n$, $KS^A(x|z) < 1,1n$ и $KS^A(y|z) < 1,1n$. В самом деле, для любого оракула получаются также прямоугольники, и потому они покрывают лишь небольшую часть множества пар, и в качестве х, у нужно взять какую-либо непокрытую (и не являющуюся простой) пару. (Естественно, результат будет зависеть от оракула, поскольку любая пара становится простой при подходящем оракуле.)

**312** Сформулируйте аналогичное утверждение, используя вместо оракула дополнительное условие $\mathcal{U}$ произвольной сложности.
Вопрос о том, что происходит с общей информацией и её выделением при добавлении оракула, рассмотрен в [119]. При этом предполагается, что оракул независим с парой слов (иначе и взаимная информация может измениться). Ясно, что если информация выделялась без оракула, то общая информация сохранится и при добавлении оракула. Оказывается, что верно и обратное (правда, доказать это удаётся не с логарифмической точностью, как хотелось бы, а с худшей).

Комбинаторные оценки размеров множеств в графе применимы и к другим ал-
гебраическим конструкциям. Можно, например, рассмотреть пару случайных пер-
пендикулярных одномерных подпространств в четырёхмерном пространстве или
(что то же самое с точностью до бесконечно удалённых точек) случайную пару
(точка трёхмерного пространства, проходящая через неё плоскость). Про возника-
ющий граф, правда, уже нельзя утверждать, что в нём нет четырёхугольников: для
любых двух одномерных подпространств есть двумерное подпространство, им ор-
тогональное, и любое его одномерное подпространство будет соединено с обоими
подпространствами левой доли. Тем не менее, таких одномерных подпространств
довольно мало, и можно применить аналогичную оценку с формулой включений и
исключений (подробнее это рассуждение проведено в доказательстве теоремы 5 в
[28]).

Существует множество аналогичных примеров. Например, можно рассмотреть пару пересекающихся прямых в трёхмерном пространстве над конечным полем. Ещё одна серия примеров: фиксируем число $n \ge 3$ и числа $k, l$, для которых $0 < k < l < n$. Теперь рассмотрим в $n$-мерном пространстве над конечным полем случайную пару вида ($k$-мерное подпространство, содержащее его $l$-мерное подпространство). Как показал А. Ромащенко в [131], в этом случае выделение общей информации также невозможно. Доказательство основано на том, что после нескольких шагов блуждания в возникающем двудольном графе (слева стоят $k$-мерные подпространства, справа $l$-мерные, рёбра соответствуют отношению включения) распределение вероятностей приближается к равномерному.

11.4. Условная независимость и общая информация

Существует ещё один способ построения пары слов, из которых не выделяется
общая информация, довольно загадочный [94, 131]. Для начала вспомним неравен-
ство задачи 295 (с. 382):

$$
H(\xi) \le H(\xi | \alpha) + H(\xi | \beta) + I(\alpha; \beta),
$$

а точнее, соответствующее неравенство для колмогоровских сложностей:

$$
KS(z) \le KS(z|x) + KS(z|y) + I(x:y)
$$

(логарифмические члены мы опускаем для краткости). В случае, когда $I(x:y) = 0$,
из него следует оценка сложности через условные сложности:

$$
KS(z) \le KS(z|x) + KS(z|y),
$$
что не удивительно: если взаимной информации нет, так она и не выделяется. Казалось бы, это ничего дать не может. Но оказывается, что аналогичную оценку можно получить и в случае, когда х и у условно независимы относительно двух независимых слов, то есть существуют слова u и v, для которых $I(x:y|u) = 0$, $I(x:y|v) = 0$ и $I(u:v) = 0$. А именно, имеет место такое неравенство:

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

$$KS(z) \le 2 KS(z|x) + 2 KS(z|y) + I(x:y|u) + I(x:y|v) + I(u:v)$$

для произвольных слов х, у, z, u, v с точностью $O(\log KS(x, y, u, z, v))$.

Заметим, что это неравенство можно было бы вывести из предыдущего и из неравенства Инглетона:

$$I(x:y) \le I(x:y|u) + I(x:y|v) + I(u:v),$$

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

◄ Начнём с уже надоевшего неравенства

$$KS(z) \le KS(z|u) + KS(z|v) + I(u:v)$$

и оценим $KS(z|u)$ и $KS(z|v)$, пользуясь релятивизованными аналогами того же самого неравенства:

$$KS(z|u) \le KS(z|x, u) + KS(z|y, u) + I(x:y|u),$$

$$KS(z|v) \le KS(z|x, v) + KS(z|y, v) + I(x:y|v).$$

После этого остаётся лишь заметить, что добавление нового условия лишь уменьшает сложность: $KS(z|x, u) \le KS(z|x)$. ►

Эту теорему можно применить для построения слов с плохо выделяемой общей информацией. Возьмём условно независимые, но не независимые случайные величины (теорема 217, с. 384): пусть величины $\alpha$ и $\beta$ независимы при известных $\gamma$ или $\delta$, причём $\gamma$ и $\delta$ независимы.

Искомые слова можно получить в результате последовательности независимых испытаний величин $\alpha, \beta$: с большой вероятностью значения $\alpha$ и значения $\beta$ образуют два слова, из которых не выделяется общая информация. Чтобы доказать это, нам достаточно представить себе, что испытания проводятся параллельно для $\gamma$ и $\delta$ и применить уже известные нам результаты к четырём возникающим словам.

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

Возьмём четвёрку слов х, у, u, v длины $N$, частоты в которой совпадают с вероятностями для величин $\langle \alpha, \beta, \gamma, \delta \rangle$. Это значит, что число позиций $i = 1, \dots, N$, в которых в словах х, у, u, v стоят буквы a, b, c, d соответственно, равняется

$$\text{Pr}[\alpha = a, \beta = b, \gamma = c, \delta = d] \cdot N + O(1)$$
(нам пришлось добавить $O(1)$ для округления, поскольку произведение вероятности на длину $N$ может не быть целым).

Как мы знаем из раздела 7.3 (теорема 146), для большинства слов с указанными частотами сложности самих этих слов и их комбинаций равны энтропиям соответствующих случайных величин (умноженным на $N$) с точностью $O(\log N)$. Таким образом, мы получаем четвёрку слов $x, y, u, v$, для которых

$$I(x:y|u) = O(\log N), \quad I(x:y|v) = O(\log N), \quad I(u:v) = O(\log N),$$

и при этом

$$I(x:y) = NI(\alpha:\beta) + O(\log N),$$

причём, напомним, $I(\alpha:\beta) \neq 0$. Остаётся воспользоваться теоремой 228 и заключить, что для любого $z$ выполняется неравенство

$$KS(z) \leq 2 KS(z|x) + 2 KS(z|y)$$

с точностью до $O(\log N)$, в то время как сложности слов $x$ и $y$ и их взаимная информация с той же точностью пропорциональны $N$ (с ненулевыми коэффициентами пропорциональности)

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

**313** Мы уже знаем (теорема 217, с. 384), что существуют условно независимые случайные величины $\alpha$ и $\beta$, каждая из которых равномерно распределена на $\{0,1\}$, и которые оказываются равны друг другу с вероятностью $5/8$. Показите, что это утверждение можно обобщить: для любого $c$ ($3/8 \le c \le 5/8$) можно построить пару условно независимых случайных величин, каждая из которых равномерно распределена на $\{0,1\}$, которые принимают равные значения с вероятностью $c$.

Если $c$ слишком далеко от $1/2$, то аналогичное утверждение уже неверно. Тем не менее, для любых $0 < c < 1$ можно доказать свойство невыделяемости общей информации у слов, полученных независимыми испытаниями случайных величин, равных с вероятностью $c$. Мы разделим это утверждение на две задачи:

**314** Пусть случайные величины $\alpha$ и $\beta$ равномерно распределена на $\{0,1\}$ и принимают одинаковые значения с некоторой вероятностью $c \in (0,1)$. Докажите, что существуют конечные цепочки случайных величин $\alpha_1, \dots, \alpha_k$ и $\beta_1, \dots, \beta_k$, для которых $\alpha$ и $\beta$ независимы относительно $\alpha_1$ и относительно $\beta_1$; величины $\alpha_1$ и $\beta_1$ в свою очередь независимы относительно $\alpha_2$ и относительно $\beta_2$, которые независимы относительно $\alpha_3$ и $\beta_3$,..., которые независимы относительно $\alpha_k$ и относительно $\beta_k$, которые уже независимы безо всяких условий. [Указание. Если утверждение истинно для некоторого $c \ge 1/2$, то оно истинно и для $c' = (c^2 + 1)/2$. Чтобы установить это, нужно применить конструкцию из доказательства теоремы 217; в качестве случайных величин $\gamma$ и $\delta$ надо взять случайные величины, для
которых утверждение выполнено при данном с. При этом условные распределения пары α, β при известных исходах γ = 0, δ = 1 и γ = 1, δ = 0 нужно подправить так, чтобы случайные величины α и β стали независимыми при известном γ и при известном δ. Наконец, нетрудно убедиться, что любое число от 1/2 до 1 может быть получено из некоторого числа от 1/2 до 5/8 конечным числом применений функции $c \mapsto (c^2 + 1)/2$. Для доказательства утверждения для $c < 1/2$ можно инвертировать одну из случайных величин α, β.

**315** Пусть случайные величины α и β удовлетворяют утверждению задачи 314. Возьмём максимально сложную пару двоичных слов x, y длины n, у которых все частоты совпадают с соответствующими вероятностями α и β. Докажите, что у этих слов x и y не выделяется общая информация. Более точно, для любого слова z выполнено неравенство $K(z) \le O(K(z|x) + K(z|y) + \log n)$ (константа в $O(\cdot)$) может зависеть от длины цепочки условно независимых случайных величин).

Решение задачи 314 можно обобщить на алфавиты большего размера и на неравномерные распределения вероятностей. Существует простой критерий, показывающий, когда случайные величины α, β удовлетворяют утверждению задачи 314. Это оказывается возможным тогда и только тогда, когда в матрице совместного распределения α и β нельзя так переставить строки и столбцы, чтобы получилась блочная матрица вида

$$ \left( \begin{array}{c|c} A & 0 \\ \hline 0 & B \end{array} \right) $$

(в обоих недиагональных блоках все элементы равны нулю). В этом случае общая информация (из типичных слов, получаемых при n испытаниях α и β) не выдается. А если блочное представление возможно, то некоторая часть информации (указывающая, в какой из блоков мы каждый раз попадаем) выделяется. Это рассуждение [94] даёт новое доказательства критерия, впервые полученного Гачем и Кёрнером [47].
# 12. Алгоритмическая теория информации
## для нескольких источников

### 12.1. Постановка задачи о передаче информации

Рассмотрим ориентированный граф, рёбра которого играют роль «линий связи», а вершины — узлов обработки информации. В некоторые вершины извне поступает какая-то информация; в результате обработки информации (в вершинах) и её передачи (по рёбрам) некоторая другая информация должна попасть в заданные вершины. Такая задача традиционно рассматривается в шенноновской теории информации с несколькими источниками; здесь мы хотим проанализировать её с точки зрения алгоритмической теории информации, следуя [155].

Более формально. Пусть задан некоторый конечный ориентированный ациклический граф. Некоторые его вершины объявлены входами, и для каждого входа указано входное слово. Другие его вершины объявлены выходами, и для каждой из них указано выходное слово. Возникает задача: на каждом ребре графа написать некоторое двоичное слово (передаваемое по данному ребру), причём для каждой вершины v должно выполняться такое условие:

если $X$ — любое выходящее из вершины $v$ слово (указанное изначально выходное слово или передаваемое по исходящим из $v$ рёбрам), а $Y_1, \dots, Y_k$ — все входящие в эту вершину слова (заданные изначально входные слова или передаваемые по входящим в $v$ рёбрам), то

$$KS(X | Y_1, \dots, Y_k) \approx 0.$$

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

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

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

<figure><img src="image_38.png" /><figcaption>Рис. 12.1. Простейшая задача передачи информации.</figcaption></figure>

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

$$KS(X|A) \approx 0, \quad KS(B|X) \approx 0, \quad l(X) \le k.$$

Ясно, что это возможно только при $KS(B|A) \approx 0$ и $KS(B) \le k$ (последнее не-равенство также понимается «с точностью до логарифма»); с другой стороны, эти необходимые условия являются также и достаточными, так как в качестве X можно взять кратчайшее описание для В.

Более формально это можно сказать так: пусть имеется последовательность слов $A_n$ и $B_n$, а также последовательность натуральных чисел $k_n$, причём длины слов $A_n$ и $B_n$, а также числа $k_n$, ограничены сверху некоторым многочленом от n. Тогда следующие два свойства равносильны:

(1) существует последовательность слов $X_n$, для которых $l(X_n) \le k_n + O(\log n)$, а также $KS(X_n|A_n) = O(\log n)$ и $KS(B_n|X_n) = O(\log n)$;

(2) $KS(B_n|A_n) = O(\log n)$ и $KS(B_n) \le k_n + O(\log n)$.

Эквивалентность (1) и (2) вытекает из того, что

$$KS(B|A) \le KS(B|X) + KS(X|A) + O(\log KS(A, B, X)), \\ KS(B) \le l(X) + KS(B|X) + O(\log KS(B|X))$$

при любых А, В, X (отсюда следует импликация (1) ⇒ (2)), а также того, что

$$\text{для любых } A, B, k \text{ найдётся слово } X, \text{ при котором } l(X) \le KS(B), \\ KS(X|A) \le KS(B|A) + O(\log KS(B)) \text{ и } KS(B|X) = O(1),$$

что даёт импликацию (2) ⇒ (1); во втором случае в качестве X надо взять кратчайшее описание слова В.

При $A = B$ наше утверждение приобретает совсем простой вид: передача слова А по каналу связи с пропускной способностью k возможна, когда сложность слова А не превосходит k.

Перейдём к более содержательным примерам.
## 12.2. Условное кодирование

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

<figure><img src="image_39.png" /><figcaption>Рис. 12.2. Передача А при известном В.</figcaption></figure>

Эта задача разрешима тогда и только тогда, когда $KS(A|B) \le k$. В самом деле, в пункте декодирования, помимо слова В (или какого-то слова, из него полученного, и не содержащего новой по сравнению с В информации) известны k битов, поэтому раскодирование возможно, лишь если $KS(A|B) \le k$. С другой стороны, если $KS(A|B) \le k$, то в качестве слова X, передаваемого по каналу ограниченной пропускной способности, надо взять кратчайшее описание В при известном А, а по двум другим каналам передавать слово В. Заметим, что сложность кратчайшего описания относительно пары (A, B) логарифмическая, так как зная длину этого описания, можно параллельно пробовать все слова этой длины, пока не найдётся одно из кратчайших описаний.

316 В этом рассуждении достаточно одного кратчайшего описания; покажите, тем не менее, что все кратчайшие описания А при известном В имеют относительно пары (A, B) сложность, не превосходящую $O(\log KS(A, B))$.

317 Дайте точную формулировку приведённого только что критерия возможности передачи слова А при известном В по аналогии с разобранным ранее применом, рассмотрев последовательности $A_n, B_n$ и $k_n$, и докажите его.

## 12.3. Условное кодирование: теорема Мучника

Следующий замечательный результат Ан. А. Мучника [116] является аналогом теоремы Вольфа – Слепяна из шенноновской теории информации [159] и говорит, что в предыдущем примере не обязательно использовать слово В при кодировании. Рассмотрим граф, получающийся из предыдущего удалением одного ребра (рис. 12.3).
<figure><img src="image_40.png" /><figcaption>Рис. 12.3. Передача А при известном В: теорема Мучника.</figcaption></figure>

Оказывается, что эта задача разрешима при тех же условиях, что и предыдущая, то есть при $KS(A|B) \le k$. Необходимость этих условий очевидна (граф стал только меньше); вот точная формулировка утверждения о достаточности.

**Теорема 229.** Пусть А и В — произвольные слова сложности не более п. Тогда найдётся слово Х длины не более $KS(A|B) + O(\log n)$, при котором $KS(X|A) = O(\log n)$ и $KS(A|B, X) = O(\log n)$.

Имеется в виду, что скрытая в $O(\log n)$ константа не зависит от $n$ и от выбора слов А и В.

Теорему Мучника можно переформулировать так: для любых слов А и В существует программа, переводящая В в А, имеющая логарифмическую сложность относительно А и безусловную сложность $KS(A|B)$ (плюс логарифмическая допавка). Другими словами, дополнительное ограничение, состоящее в простоте программы относительно А, приводит к росту (безусловной) сложности программы не более чем на $O(\log KS(A, B))$.

Пусть слово А имеет сложность $a$. Заменим это слово на его (кратчайшее) описание длины $a$. От этого величины $KS(A|B)$, $KS(X|A)$ и $KS(A|B, X)$ изменяются не более чем на $O(\log n)$, поэтому мы можем далее предполагать, что слово А имеет длину (а не сложность) $a$.

Пусть сложность $KS(A|B)$ равна $m$. В самом первом приближении идею доказательства можно объяснить так. Рассмотрим хеш-функцию $\chi: \mathbb{B}^a \to \mathbb{B}^m$, которая каждому слову длины $a$ ставит в соответствие хеш-значение (отпечаток, fingerprint) длины $m$.

Для данного слова В имеется $2^m$ слов Z длины $a$, для которых $KS(Z|B) \le m$ (на самом деле их $O(2^m)$, но мы пока что пренебрегаем такими мелочами). Пусть $S_B \subset \mathbb{B}^a$ — множество этих слов. Слово А — один из элементов множества $S_B$.

Пусть хеширование прошло исключительно удачно в том смысле, что у всех слов из $S_B$ хеш-значения оказались различными. Тогда любое слово $P \in S_B$ может быть однозначно восстановлено по $\chi(P)$ при известном В (и $\chi$). Поэтому можно в качестве $X$, существование которого утверждается в теореме, взять $\chi(A)$: оно имеет правильную длину, просто относительно А (если функция $\chi$ проста) и вместе с В позволяет восстановить А (перечисляем множество $S_B$, пока не обнаружится слово с правильным хеш-значением).
Разумеется, так просто всё не выходит. Какова бы ни была хеш-функция $\chi$, при $a > m$ найдётся как минимум $2^{a-m}$ слов, имеющих одно и то же хеш-значение (а при простой $\chi$ можно найти много простых слов с одним хеш-значением, и они будут просты относительно $B$ при любом $B$), так что хеширование не будет удачным.

Поэтому мы модифицируем этот план и будем сопоставлять с каждым словом $Z \in \mathbb{B}^a$ не одно хеш-значение, а несколько (в количестве $\text{poly}(n)$). Таким образом, вместо хеш-функции мы рассматриваем двудольный граф $E \subset \mathbb{B}^a \times \mathbb{B}^m$, в котором каждая вершина $Z$ в левой доле (из $\mathbb{B}^a$) имеет $\text{poly}(n)$ соседей в правой доле. Этих соседей мы будем называть **отпечатками** вершины $x$.

Доказывая теорему, мы будем искать слово $X$ среди отпечатков слова $A$. Это гарантирует нам, что $\text{KS}(X|A) = O(\log n)$, если сам граф $E$ прост (имеет сложность $O(\log n)$). В самом деле, для задания $X$ при известном $A$ достаточно указать порядковый номер $X$ среди отпечатков слова $A$.

Если для данного $A \in S_B$ найдётся отпечаток $X$, уникальный для $A$ внутри $S_B$ (это значит, что в $S_B$ нет других слов, имеющих $X$ своим отпечатком), то слово $A$ можно восстановить, перечисляя $S_B$ и ожидая появления слова, имеющего $X$ среди своих отпечатков. В этом случае $\text{KS}(A|B, X) = O(\log n)$ (мы, как и раньше, предполагаем, что граф $E$ имеет сложность $O(\log n)$).

Более того, это верно и в случае, когда в $S_B$ имеется $\text{poly}(n)$ слов с отпечатком $X$, нужно лишь дополнительно указать порядковый номер $A$ среди этих слов (в порядке перечисления множества $S_B$), что потребует дополнительных $O(\log n)$ битов.

Таким образом, нам хотелось бы следующего: у слова $A$ имеется правый сосед, у которого мало ($\text{poly}(n)$) левых соседей. Говоря о соседях, мы рассматриваем сужение графа $E$ на $S_B$ как двудольный граф с левой долей $S_B$ и правой долей $\mathbb{B}^m$. Отметим, что в этом уменьшенном графе число вершин слева и справа примерно одинаково — порядка $2^m$.

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

Дальнейший план действий таков: справа плохих вершин мало, так как в графе мало рёбер (число рёбер оцениваем как число вершин слева, умноженное на максимальную степень левых вершин, которая есть $\text{poly}(n)$), а каждая плохая вершина справа даёт большой вклад в число рёбер. Так мы добьёмся, чтобы доля плохих вершин справа была не больше $1/p(n)$ для заданного полинома $p$ (при этом придётся полиномиально увеличить границу, при превышении которой вершина объявляется плохой).

Отсюда можно заключить, что и слева плохих вершин мало, если граф $E$ обладает следующим свойством типа экспандера: для всякого множества $T$ в левой доле мощности не более $2^{m-1}$ множество $E(T)$ всех соседей всех элементов множества $T$ содержит не меньше элементов, чем само множество $T$. В самом деле, возьмём в качестве $T$ множество плохих вершин слева. Все их правые соседи будут плохими, поэтому слева не больше плохих вершин, чем справа. (Заметим, что указанное свойство графа $E$ сохраняется при его сужении на $S_B$.)
Остаётся объяснить, откуда мы возьмём граф *E* с нужными свойствами и что делать, если нужное нам слово *А* попадёт в (пусть и небольшое) число плохих вершин слева.

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

Последнее: может ли слово А оказаться плохим? Заметим, что плохие слова справа можно алгоритмически перечислять при известных В (и Е); по мере обнаружения новых элементов в S<sub>B</sub> множество плохих слов справа растёт. Поскольку граф Е мы считаем известным, можно перечислять и плохие слова слева. Таким образом, каждое плохое слово можно задать (при известном В) его порядковым номером, что меньше *m* битов, так как плохих слов заметно меньше 2<sup>m</sup>. (Ешё нужно O(log n) битов, чтобы задать *m*, а и Е, но и с учётом этой добавки получится меньше *m*, как мы увидим.) А мы с самого начала предполагали, что сложность А при известном В равна *m* (так выбиралось число *m*). Поэтому А не может оказаться плохим.

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

**Лемма.** Пусть $a$ и $m$ — натуральные числа, причём $a \ge m$. Тогда существует двудольный граф $E \subset B^a \times B^m$, в котором степень вершин в левой доле ($B^a$) не превосходит $a + m + 2$, обладающий следующим свойством: для любого множества $T \subset B^a$, содержащего не более $2^{m-1}$ элементов, множество $E(T)$ всех правых соседей всех элементов из $T$ содержит больше элементов, чем само $T$.

**Доказательство.** Докажем, что случайный граф обладает указанным свойством с положительной вероятностью. Говоря о случайном графе, мы имеем в виду, что для каждой точки в левой доле случайно выбираются $a+m+2$ соседей, равномерно распределённых в правой доле. При этом этот выбор делается независимо (для разных точек и для разных соседей одной точки).

Если указанное в лемме свойство не выполняется, то существует некоторое (непустое) множество $T$ в левой доле и некоторое множество $U$ в правой доле, для которых $|U| = |T|$, но все соседи элементов из $T$ принадлежат $U$. Мы подсчитаем вероятность такого события для данных $T$ и $U$ и покажем, что сумма этих вероятностей по всем $T$ и $U$ меньше единицы.

Пусть фиксированы $T$ и $U$; обозначим число элементов в них через $t$. По предположению, $t \le 2^{m-1}$, поэтому вероятность того, что случайный элемент правой доли попадёт в $U$, не больше $1/2$. Вероятность того, что это случится $t(a+m+2)$
раз при независимых испытаниях (по $a + m + 2$ испытаний для $t$ элементов множества $T$) не превосходит $2^{-t(a+m+2)}$.

Просуммируем вероятность сначала по всем парам множеств $T$ и $U$ размера $t$. Число различных $T$ не превосходит $(2^a)^t$ (выбираем $t$ раз один из $2^a$ элементов; совпадения и возможность перестановки лишь уменьшают число вариантов), число различных $U$ не превосходит $(2^m)^t$. Таким образом, сумма вероятностей по множествам размера $t$ не превосходит

$$2^{mt} \cdot 2^{at} \cdot 2^{-t(m+a+2)} = (1/4)^t.$$

Остаётся заметить, что сумма ряда $\sum (1/4)^t$ (по всем $t \ge 1$) меньше 1 (равна $1/3$). Лемма доказана.

Пусть $E_{m,a}$ — первый в каком-нибудь естественном порядке граф, удовлетворяющий лемме (для данных $m$ и $a$). Его сложность не превосходит $2 \log a + O(1)$ (достаточно указать числа $a$ и $m$, отведя для них первую и вторую половины описания длины $2 \log a$).

Для данного слова $B$ и для данных $m$ и $a$ рассмотрим множество $S_B$ слов длины $a$, имеющих относительно $B$ сложность не более $m$. В нём не более $2^{m+1}$ слов. Рассмотрим ограничение графа $E_{m,a}$ на $S_B$. В этом двудольном графе не более $2^{m+1} \cdot (a+m+2) \le a2^{m+3}$ рёбер (каждая из не более чем $2^{m+1}$ вершин имеет не более чем $a+m+2$ соседей). Объявим плохими вершины в правой доле, имеющие не менее $a^4$ соседей слева. Тогда число плохих вершин будет не более $k = 2^{m+3}/a^3$.

Слева мы объявим плохими вершины (слова из $S_B$), у которых все соседи справа плохие. По построению графа $E_{m,a}$ число плохих вершин слева также не превосходит $k = 2^{m+3}/a^3$. В самом деле, мы можем предполагать, что $a$ настолько велико, что $k < 2^{m-1}$. Если бы нашлось $k+1$ плохих вершин, то по свойству графа количество соседей этих $k+1$ вершин превосходило бы $k$ и все они были бы плохие. Плохие вершины слева можно перечислять (при известных $m$, $a$ и $B$), поэтому плохое слово можно задать его порядковым номером (на что требуется $m - 3 \log a + O(1)$ битов), так что

$$KS(P | B, m, a) \le m - 3 \log a + O(1)$$

для любого плохого слова $P$. Видно, что запас больше $2 \log a$, необходимых для указания $m$ и $a$, так что все плохие слова имеют условную сложность (относительно $B$) меньше $m$ и слово $A$ среди них оказаться не может.

Следовательно, у него есть хороший сосед справа. Обозначим его через $X$. Тогда $KS(X|A) \le (3+\varepsilon) \log a + O(1)$ (надо указать $m$, $a$ и порядковый номер $X$ среди соседей $A$ в $E_{m,a}$; $\varepsilon$-добавка требуется для кодирования пар). Длина $X$ равна $m$, то есть $KS(A|B)$. Наконец, $KS(A|B, X)$ не превосходит $(6+\varepsilon) \log a$ (из коих $4 \log a$ уходит на указание порядкового номера $A$ среди $a^4$ левых соседей вершины $X$, а $2 \log a$ требуется для указания $m$ и $a$; $\varepsilon$ нужно для кодирования пар).

Теорема Мучника доказана. ►

**318** Покажите, что фактически доказано более сильное утверждение, чем объявлено: в условии теоремы требовалось, чтобы слово $B$ имело сложность не более $n$, но это нигде не использовано.
Напомним, что все неравенства в теореме Мучника верны с точностью $O(\log n)$, где $n$ максимальная из сложностей исходных слов $A, B$. Можно ли усилить формулировку теоремы, потребовав, чтобы все неравенства были выполнены с точностью $O(\log m)$, где $m$ максимальная из условных сложностей $KS(A|B)$ и $KS(B|A)$? Оказывается, что нет и это доказано в работе [179, Раздел 5] (мы это доказательство воспроизводить не будем).

## 12.4. Комбинаторный смысл теоремы Мучника

Многие утверждения о колмогоровской сложности имеют комбинаторный эквивалент — равносильное утверждение чисто комбинаторного характера, в котором о сложности ничего не говорится. Во многих случаях эквивалентом является утверждение о существовании выигрышной стратегии в некоторой игре. (См. об этом для случая общей теории алгоритмов в [113] и в [117] применительно к колмогоровской сложности.)

Для доказанной только что теоремы 229 также имеется комбинаторный эквивалент. Рассмотрим для данных чисел $a, b$ и $m$ (считаем, что $m \le a$) игру двух игроков: Математика (М) и его Противника (П). Игра имеет также параметр $c$ (соответствующий константе в $O(\log n)$, как мы увидим).

Математик имеет право указать для каждого слова $A$ длины $a$ не более чем $c(a+b)^c$ слов длины $m$, которые он условно именует простыми относительно $A$. Кроме того, он для каждой пары слов $B$ (длины $b$) и $X$ (длины $m$) имеет право указать до $c(a+b)^c$ слов длины $a$, называя их простыми относительно пары $B, X$.

Противник для каждого слова $B$ длины $b$ может указать до $2^m$ слов длины $a$, назвав их $m$-простыми относительно $B$.

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

М выиграл, если для всякого слова $B$ длины $b$ и для всякого слова $A$ длины $a$, которое П объявил $m$-простым относительно $B$, найдётся слово $X$ длины $m$, которое М объявил простым относительно $A$ и для которого М объявил $A$ простым относительно $B$ и $X$.

Теперь можно сформулировать комбинаторный эквивалент теоремы 229.

**Теорема 230.** Существует такая константа $c$, что для любых натуральных $a, b, m$ (для которых $m \le a$) в описанной игре с параметрами $a, b, m$ и с выигрывает М.
Объясним, почему это комбинаторное утверждение действительно является комбинаторным эквивалентом теоремы 229. Предположим, что оно верно для некоторого $c$. Рассмотрим Противника, который делает свои ходы, не обращая внимания на Математика, и объявляет $m$-простыми слова длины $a$, которые имеют сложность менее $m$ (относительно соответствующего $B$). Поведение Противника в этом случае задаётся алгоритмом, для задания которого надо знать значения $a, b, m$. Выигрышная стратегия Математика (существующая по предположению) может быть найдена перебором (при известных $a, b$ и $m$). Поэтому слова, которые Математик объявляет простыми, будут и в самом деле иметь малую колмогоровскую сложность (условную) — для их задания, помимо порядкового номера (который записывается $\log c + c \log(a+b)$ битами), достаточно указать $a, b, m$, что требует ещё $O(\log(a+b))$ битов. Таким образом, мы получаем утверждение теоремы 229. (Техническое пояснение: в оценке $c(a+b)^c$ первый множитель $c$ нужен для малых значений $a$ и $b$ и соответствует слагаемому $O(1)$ в оценках колмогоровской сложности, которое, строго говоря, надо было бы явно добавлять к $O(\log n)$ на случай $n=1$ и $\log n=0$.)

В обратную сторону: предположим теперь, что утверждение теоремы 229 верно (с некоторой константой в $O(\log n)$, которую мы будем обозначать $c'$) и докажем, что для некоторого достаточно большого $c$ выполнено комбинаторное утверждение. Рассуждая от противного, допустим, что для всех $c$ для некоторых $a, b, m$ Математик проигрывает, а значит Противник имеет выигрышную стратегию. Эту стратегию вместе с тройкой $a, b, m$ можно найти перебором. Поэтому, если эта стратегия объявила некоторое $A$ простым относительно $B$, то условная сложность $A$ при известном $B$ и в самом деле невелика — она не превышает $m + O(KS(c))$. Мы получим противоречие, дав этой стратегии сыграть против следующей «слепой» стратегией Математика: не обращая внимания на ходы противника называть простыми слова $X$, для которых $KS(X|A) < c \log(a+b) + \log c$, а также слова $A$, для которых $KS(A|B, X) < c \log(a+b) + \log c$.

Ограничения на количество слов, объявляемых простыми, не нарушены. Поэтому осталось доказать, что эта стратегия Математика обыграет выигрышную стратегию Противника. Пусть даны слова $A, B$ длин $a, b$ для которых Противник объявил $A$ простым относительно $B$. По теореме 229 существует слово $X'$ длины $KS(A|B) + c' \log(a+b)$, для которого выполняется утверждение теоремы. Поскольку $KS(A|B)$ не превосходит $m + O(KS(c))$, длина слова $X'$ ненамного превышает $m$. Оставим от него первые $m$ битов, полученное слово обозначим $X$. Сложности $KS(X'|A)$ и $KS(A|B, X')$ невелики по условию, а количество отрезанных у $X'$ битов тоже невелико. Поэтому сложности $KS(X|A)$ и $KS(A|B, X)$ также малы, и при правильном выборе $c$ меньше $c \log(a+b) + \log c$ (а значит, Математик выигрывает).

Осталось привести оценки. Условная сложность $KS(X|A)$ не превосходит

$$c' \log(a+b) + O(\log m)$$

(сложность $X'$ относительно $A$ плюс длина префиксного кода $m$). Условная сложность $KS(A|B, X)$ не превосходит суммы

$$c' \log(a+b) + O(KS(c))$$
(сложность А относительно пары В, X плюс длина отрезанного конца X'). Видно, что можно подобрать число с вида $2^i$ так, что обе суммы не превосходили $c \log(a+b) + \log c$ (для чисел $c = 2^i$ сложность с, входящая в верхнюю оценку для $KS(A|B, X)$, значительно меньше $\log c$).

Таким образом, мы установили, что комбинаторное утверждение теоремы 230 действительно эквивалентно сложностному утверждению теоремы 229 (и, в частности, истинно).

На комбинаторный язык можно перевести не только формулировку теоремы 229, но и её доказательство. В ходе доказательства Математик не использует своё право указывать простые относительно А слова по ходу игры, а указывает их все сразу (в соответствии с графом-экспандером). Далее он объявляет слово А, соседнее с X, простым относительно X и В, если к моменту объявления А простым относительно В среди слов, объявленных Противником простыми относительно В, мало слов, соседних с X. В результате ему — для каждого В — удастся обслужить большинство слов, объявленных простыми относительно этого В. Оставшееся меньшинство слов, объявленных простыми относительно В, передаётся на следующий уровень обслуживания, где делается всё то же самое, но с уменьшенным на единицу m. И так далее. В итоге количество слов, объявленных простыми относительно А, вычисляется как сумма убывающей вдвое геометрической прогрессии, и потому вдвое больше первоначально взятого, но это не страшно.

Тот факт, что Математик указывает слова сразу (а не по ходу игры), имеет и некоторые алгоритмические следствия:

**[319]** Докажите, что для любого слова А длины n существует слово X длины KS(A), для которого $KS(A|X) = O(\log n)$ и тотальная условная сложность X при известном А (минимальная сложность всюду определённой программы, переводящей А в X) есть $O(\log n)$. Показите, что заменить обе сложности $KS(A|X)$ и $KS(X|A)$ на тотальные нельзя. [Указание. Для первого можно использовать рассуждение Мучника; во втором случае можно использовать существование нестохастических слов (см. главу 14 об алгоритмической статистике).]

Эта задача показывает, что рассуждение Мучника даёт содержательные результаты даже в случае пустого слова В. При непустом В мы можем получить вариант теоремы, в котором $KS(X|A)$ заменено на тотальную сложность X при известном А (а остальные условные сложности оставлены без изменений); нужно только дополнительно предположить, что длина слова А (а не только его сложность) не превосходит n.

## 12.5. Отступление: on-line паросочетания

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

Рассмотрим двудольный граф. Вершины левой доли образуют множество A, вершины правой доли — множество B, рёбра графа образуют множество $E \subset A \times B$. Задача о паросочетании обычно ставится так: имеется некоторое множество $A' \subset A$,
надо для каждой вершины $a \in A'$ выбрать одного из её соседей в B (то есть вершину из B, соединённую с a ребром), причём выбранные соседи разных вершин должны быть различны.

Рассмотрим более сложный вариант этой задачи, который можно назвать «паросочетанием в режиме on-line»: нам по очереди указывают вершины в левой доле, и мы для них должны указать парную вершину в правой доле (и не имеем возможности впоследствии изменить этот выбор). Будем говорить, что граф $E \subset A \times B$ допускает on-line паросочетание размера $k$, если существует способ, гарантирующий спаривание любых $k$ вершин левой доли (в том порядке, в котором их указывают). Другими словами, рассматривается игра на графе, в которой противник указывает нам по очереди $k$ вершин из A, и после каждого его хода мы обязаны выбрать одного из соседей для только что указанной им вершины (и при этом не повторяться).

Заметим, что это определение несимметрично (мы выбираем вершины справа, а противник — слева). Ещё из определения видно, что свойство «допускать on-line паросочетание данного размера» лежит в PSPACE. (Интересно было бы узнать, есть ли какие-нибудь лучшие верхние оценки сложности.)

**Теорема 231.** Для некоторой константы с при любых $a$ и $m$ (где $a \ge m$) существует двудольный граф с $2^a$ вершин в левой доле и $2^m a^c$ вершин в правой доле, в котором каждая вершина слева имеет не более $a^c$ соседей справа и который допускает on-line паросочетание размера $2^m$.

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

Прежде чем доказывать теорему 231, объясним, как из неё вытекает утверждение теоремы 229. Как и раньше, для начала заменим слово А на его кратчайшее описание длины $a$. Положим $m$ равным $KS(A|B) + 1$ и применим теорему 231; получится некоторый двудольный граф ($2^a$ вершин слева и $a^c 2^m$ вершин справа, степень левых вершин не более $a^c$). Раз граф с указанными свойствами существует, то его можно найти перебором. Фиксируем этот граф и алгоритм построения on-line паросочетания. Далее для данного В можно перечислять слова, имеющие сложность меньше $m$ относительно этого В. Их не больше $2^m$ и среди них есть слово А. По очереди подбираем для них пару в графе. Рассмотрим слово $X$, парное к слову А. Как и все правые соседи А (которых мало), оно имеет малую сложность относительно А. (Поскольку граф и алгоритм построения on-line паросочетания были найдены перебором, то они задаются параметрами $a$ и $m$ и имеют логарифмическую сложность.) С другой стороны, зная В и $X$ (а также все числовые параметры), можно восстановить процесс построения паросочетания и дождаться, пока слово $X$ будет соединено со некоторым словом, тем самым восстановив А.

◀ Перейдём теперь к доказательству теоремы 231. Заметим, что достаточно доказать более слабое утверждение, разрешив подыскивать пары не для всех $2^m$ элементов, указываемых в левой доле, а только для половины (по нашему выбору).
В самом деле, если мы умеем это делать, то для необслуженных элементов можно параллельно запустить аналогичный процесс (с уменьшенным на 1 значением $m$ и соответствующим графом, возможно, другим), число необслуженных уменьшится ещё вдвое и так далее. В итоге мы найдём паросочетание в графе, в котором левая доля общая, а правая является объединением правых долей всех использованных графов (для $m, m-1, m-2, \dots$ вплоть до нуля).

Остаётся заметить, что такому (ослабленному) требованию удовлетворяет граф со свойствами экспандера, о котором мы говорили. Алгоритм построения паросочетания будет самым простым: если у вершины есть ещё не использованный сосед, то его и выбираем, а если все соседи уже заняты, то сдаёмся и вершину не обслуживаем. Несложно сообразить, что в результате будет обслужена как минимум половина вершин. В самом деле, если обслужено меньше, то и справа использовано ровно столько же, то есть менее $2^{m-1}$ вершин. С другой стороны, для каждой необслуженной вершины, каковых существует более $2^{m-1}$, все её соседи использованы. (Иначе почему мы её не обслужили?) А это противоречит свойству экспандера: согласно этому свойству множество из $2^{m-1}$ элементов (и потому любое большее) не может иметь меньше $2^{m-1}$ соседей. ►

Естественный вопрос, возникающий в связи с этим доказательством — его соотношение с доказательством теоремы Вольфа — Слепяна. Было бы интересно указать комбинаторный факт, из которого легко следуют как теорема Мучника, так и теорема Вольфа — Слепяна. Интересно было бы также изучить другие конструкции on-line паросочетаний (прямое вероятностное доказательство, не использующее дублирования уровней, или явные конструкции.)

Другое доказательство теоремы Мучника можно получить, используя (хорошо известную) комбинаторную конструкцию, так называемые экстракторы. Эта идея была предложена (в другой ситуации и ещё до Мучника) в статье [14], и применена к доказательству теоремы Мучника в [125]. Преимущество такого подхода в том, что можно использовать известные явные конструкции экстракторов и другую технику теории сложности (например, псевдослучайные генераторы, как предложил А. Ромащенко) для доказательства варианта теоремы Мучника, где используется сложность с ограничением на используемую память [123, 124]. (Вообще сложность с ограничением на ресурсы — важная отдельная тема, которую мы в нашей книге не обсуждаем.)

### 12.6. Относительное кодирование пары слов

В следующей задаче для данной пары слов А и В мы хотим передать по пунктирному каналу слово Х длины не более $k$, которое позволяет получить А из В и одновременно позволяет получить В из А (рис. 12.4).

Сразу же ясно, что это возможно лишь при $\text{KS}(A|B) \le k$ и $\text{KS}(B|A) \le k$. В самом деле, сложности слов, передаваемых по нижним наклонным линиям, не превосходят $k$ (поскольку по определению эти слова просты относительно $X$), а вместе с тем эти слова позволяют получить В из А (формально говоря, из некоторого слова, простого относительно $A$) и наоборот.
<figure><img src="image_41.png" /><figcaption>Рис. 12.4. Теорема Беннета – Гача – Ли – Витаньи – Цурека.</figcaption></figure>

Получаем необходимое условие разрешимости задачи:

$$ \max(\mathrm{KS}(A|B), \mathrm{KS}(B|A)) \le k $$

(как всегда, все неравенства понимаются с точностью до логарифмических слагаемых). Как показали Беннет, Гач, Ли, Витаньи и Цурек в [5], это необходимое условие является на самом деле и достаточным. Вот точная формулировка:

**Теорема 232.** Пусть А, B — произвольные слова, для которых $\mathrm{KS}(A|B) < k$ и $\mathrm{KS}(B|A) < k$. Тогда существует слово Х длины k, для которого $\mathrm{KS}(A|B, X) = O(\log k)$, $\mathrm{KS}(B|A, X) = O(\log k)$ и $\mathrm{KS}(X|A, B) = O(\log k)$.

▲ Рассмотрим все пары слов $\langle A, B \rangle$, для которых $\mathrm{KS}(A|B) < k$ и одновременно $\mathrm{KS}(B|A) < k$. Получаем перечислимое бинарное отношение (на парах слов), все сечения которого (вертикальные, при фиксированном А, и горизонтальные, при фиксированном B) содержат не более $2^k$ элементов.

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

Сейчас мы покажем, как разбить построенное множество пар на не более чем $2^{k+1}$ классов, каждый из которых является взаимно однозначным соответствием (не содержит двух пар на одной вертикали или горизонтали). В терминах графов: как раскрасить рёбра графа в $2^{k+1}$ цветов так, чтобы любые два ребра, имеющие общую вершину (слева или справа), имели разные цвета.

А именно, пронумеруем классы от 0 до $2^{k+1} - 1$. По мере появления новых пар в перечислении будем относить их к минимальному допустимому классу (в котором ещё нет пар с тем же первым или вторым элементом). (Другими словами, мы выбираем для вновь появившегося ребра первый цвет, не использованный для рёбер с общим концом.)

Ясно, что классов хватит, поскольку использованных классов меньше $2^k + 2^k$ (пар с тем же первым членом меньше $2^k$, равно как и пар с тем же вторым членом). В терминах графа: новое ребро имеет общий левый конец менее чем с $2^k$ рёбрами и общий правый конец менее чем с $2^k$, так что запрещены менее $2^{k+1}$ цветов.

Теперь в качестве X возьмём номер класса. Он содержит $k+1$ битов, но отбрасывание одного бита меняет все условные сложности не более на $O(1)$. Ясно, что зная А, число k и номер класса, можно порождать множество пар, классифицировать их описанным способом и подождать появления на А-вертикали пары из класса
с данным номером $X$, поэтому $KS(A|B, X, k) = O(1)$ и $KS(A|B, X) = O(\log k)$. Аналогично и для $KS(B|A)$. Наконец, $KS(X|A, B, k) = O(1)$, поскольку зная $A, B$ и $k$, можно дождаться классификации пары $\langle A, B \rangle$ и найти $X$. ►

**320** Докажите более сильное утверждение о двудольных графах: если для (конечного) двудольного графа степень каждой вершины в левой и правой доле не превосходит $N$, то можно так раскрасить его рёбра в $N$ цветов, чтобы рёбра одного цвета не имели общих концов. Объясните, почему в доказательстве теоремы 232 не удаётся сослаться на этот факт, а нужно доказывать его (ослабленный) вариант заново. [Указание. Можно считать, что степень равна $N$, после чего применить теорему Форда – Фалкерсона или теорему Холла о паросочетаниях. Нам этого не-достаточно, так как в нашем случае граф не задан целиком, а строится постепенно, и рёбра надо красить on-line.]

Можно заметить ещё, что цвет (номер класса) кодируется словом из $k+1$ битов, поэтому он даёт информацию и о $k$, так что сложности $KS(A|B, X)$ и $KS(B|A, X)$ будут $O(1)$, а не только $O(\log k)$. Это же соображение в терминах программ: для любых слов $A$ и $B$ существует программа сложности

$$ \max(\mathrm{KS}(A|B), \mathrm{KS}(B|A)) + O(1), $$

которая переводит $A$ в $B$ и $B$ в $A$. (Программа эта ищет ребро данного цвета среди соседей входа.)

**321** Пусть $A$ и $B$ — два независимых случайных слова длины $n$ (то есть $KS(A) \approx n$, $KS(B) \approx n$ и $KS(\langle A, B \rangle) \approx 2n$. Укажите явно слово $X$, удовлетворяющее условиям теоремы 232. [Ответ: годится побитовая сумма слов $A$ и $B$.]

Если сложности $KS(A|B)$ и $KS(B|A)$ различны, то теорему 232 можно уточнить следующим образом. Пусть, скажем, $KS(A|B)$ — большая из них (легче получить $B$ из $A$, чем наоборот). Оказывается, тогда можно разделить слово $X$ на две части: на информацию, необходимую для преобразования $A$ в $B$ (в лёгкую сторону, длиной $KS(B|A)$) и остаток (длины $KS(A|B) - KS(B|A)$), добавление которого позволяет сделать и обратное преобразование.

Формально говоря, верно такое утверждение:

**Теорема 233.** Пусть $KS(A|B) < k$, $KS(B|A) < l$ и $k > l$. Тогда можно найти такое слово $X$ длины $k$, что $KS(X|A, B) = O(\log k)$, $KS(A|B, X) = O(\log k)$, а также $KS(B|A, X') = O(\log k)$, где $X'$ — начало $X$ длины $l$.

◄ Рассуждаем аналогично доказательству теоремы 232, относя пары к $2^{l+1}$ классам и требуя, чтобы на одной вертикали было не более одной точки каждого класса, а на одной горизонтали — не более $2^{k-l}$ точек каждого класса. Тогда номер класса позволяет восстановить $B$ по $A$, а для восстановления $A$ по $B$ нужно ещё $k-l$ битов информации (порядковый номер появления среди элементов данного класса). ►

**322** Докажите утверждение теоремы 233 в форме, приведённой в [5]: в предположениях теоремы 233 найдутся слово $Y$ сложности $k-l$ и слово $X$ сложности $l$, для которых $KS(B, Y|A, X) = O(\log k)$ и $KS(A|B, Y, X) = O(\log k)$.
## 12.7. Кодирование при двух условиях

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

<figure><img src="image_42.png" /><figcaption>Рис. 12.5. Кодирование С при условиях А, В.</figcaption></figure>

Если в этой схеме положить $A = B$, то получится схема передачи информации раздела 12.3 (симметрично продублированная). Если же положить $C = \langle A, B \rangle$, то мы приходим к задаче раздела 12.6 (в каждом из нижних узлов одно из слов А и В известно, поэтому восстановить пару означает восстановить второе слово).

Необходимыми условиями разрешимости задачи являются неравенства

$$KS(C|A) \le k, \quad KS(C|B) \le k.$$

Как установил Ан. А. Мучник [116], эти условия являются и достаточными. Вот точная формулировка:

**Теорема 234.** Пусть А, В и С — произвольные слова сложности не более $n$, а $k$ — натуральное число, причём $KS(C|A) \le k$ и $KS(C|B) \le k$. Тогда найдётся слово Х длины не более $k + O(\log n)$, при котором $KS(X|C) = O(\log n)$, $KS(C|A, X) = O(\log n)$ и $KS(C|B, X) = O(\log n)$.

В терминах программ эта теорема звучит так: для любых трёх слов А, В, С длины не более $n$ существует программа сложности $\max(KS(C|A), KS(C|B)) + O(\log n)$, имеющая логарифмическую сложность относительно С, переводящая любое из слов А и В в С. (Как и раньше, в эту программу надо включить информацию, позволяющую различить А и В; она имеет логарифмическую сложность.)

Заметим, что это утверждение остаётся содержательным, даже если не требовать простоты программы относительно С: никакого другого доказательства его в этом частном случае не известно. Другими словами, доказательство достаточности (пока?) не удаётся упростить, даже если добавить два новых ребра (рис. 12.6).

Можно также сформулировать следующее обобщение теоремы 234 на случай различных условных сложностей:

**Теорема 235.** Пусть А, В и С — произвольные слова сложности не более $n$, а $k \ge l$ — натуральные числа, причём $KS(C|A) \le k$ и $KS(C|B) \le l$. Тогда найдётся слово Х длины $k$, для которого $KS(X|C) = O(\log n)$, $KS(C|A, X) = O(\log n)$ и $KS(C|B, X') = O(\log n)$ для слова Х' длины $l$, являющегося началом слова Х.
<figure><img src="image_43.png" /><figcaption>Рис. 12.6. Дополнительные рёбра.</figcaption></figure>

**323** Сформулируйте утверждение этой теоремы в терминах передачи информации по некоторой сети. [Указание: X передаётся по ребру пропускной способности *k*, из конца которого выходит ребро пропускной способности *l*.]

Все эти утверждения доказаны в той же работе Мучника [116]; приведём доказательство теоремы 235.

Будем использовать тот же метод «отпечатков», что и раньше: слово X будет одним из немногих отпечатков слова C.

Однако рассуждение требует некоторых изменений. Если $k$ и $l$ отличаются, то отпечатки должны быть разных длин. Даже и в случае $k = l$ возникает очевидная проблема: среди отпечатков может найтись X, для которого $\text{KS}(C|A, X)$ мало, а также $X'$, для которого $\text{KS}(C|B, X')$ мало, но нам ведь нужно одно и то же слово и для A, и для B.

Можно пытаться найти среди отпечатков «вдвойне хорошее» слово X, которое порождает мало коллизий и в $S_A$, и в $S_B$ (через $S_A$ и $S_B$ мы обозначаем множества слов, простых относительно A и B соответственно). Такие слова существуют и их даже большинство (по тем же причинам, что и раньше: в $S_A \cup S_B$ лишь вдвое больше слов, чем в каждом из множеств $S_A$ и $S_B$ в отдельности), так что продолжая рассуждение с экспандером, можно заключить, что для большинства слов в $S_A$ и для большинства слов в $S_B$ найдётся вдвойне хороший правый сосед. Но дальше рассуждение не проходит: мы хотели бы сказать, что остальные слова имеют малую сложность, поскольку их мало и их можно порождать, но для их порождения надо знать сразу и A, и B, а у нас в условии лишь одно из слов А и B.

Что же делать? Будем рассматривать условия А и В независимо, но требовать, чтобы у слова C был не просто один хороший отпечаток, а чтобы больше половины отпечатков были хорошими. Если этого удаётся добиться для А и для В в отдельности, отсюда следует существование отпечатка, одновременно хорошего и для А, и для В.

Соответственно придётся изменить и свойство типа экспандера, которого мы требуем от двудольного графа $E \subset P \times Q$ (с левой долей P и правой долей Q). Теперь мы хотим, чтобы для любого множества $U \subset Q$ не слишком большого размера множество тех вершин $x \in P$, у которых половина или более соседей справа попадает в U, было бы малым. (Раньше мы считали плохими вершины, у которых все соседи попадали в U, а теперь достаточно половины.)
Более того, поскольку теперь нас интересуют разные условные сложности, мы будем рассматривать не только сами отпечатки, но и их начала (сразу всех длин, так проще). Утверждение о существовании графа с нужными свойствами теперь выглядит так (через $[u]_m$ обозначается начало слова $u$, имеющее длину $m$):

**Лемма.** Пусть даны натуральные числа $n$ и $N$, а также положительное число $\varepsilon$, причём

$$n2^{N+2n+1}\varepsilon^{N/2} < 1.$$

Тогда существует семейство отображений

$$\chi_1, \dots, \chi_N : \mathbb{B}^n \to \mathbb{B}^n$$

с таким свойством: для любого $m \in \{1, \dots, n\}$ и для любого непустого подмножества $U \subset \mathbb{B}^m$, число элементов в котором не превосходит $\varepsilon 2^m$, количество тех $x \in \mathbb{B}^n$, для которых

$$[\chi_i(x)]_m \in U \quad \text{для половины или более значений } i \in \{1, \dots, N\}, \\ \text{меньше } |U| \text{ (числа элементов в } U\text{).}$$

**[Пояснение:** мы говорим не о графе со степенью вершин $N$ в левой доле, а о семействе $N$ отображений, поскольку допускаем кратные рёбра ($\chi_i(x) = \chi_j(x)$ при $i \neq j$).]**

**Доказательство.** Покажем, что для случайно выбранных функций $\chi_1, \dots, \chi_N$ (все значения $\chi_i(x)$ при всех $i$ и $x$ независимы и равномерно распределены в $\mathbb{B}^n$) вероятность нарушения указанного свойства меньше единицы. Эту вероятность мы оценим сверху. Для каждого $m \le n$, для каждого $t \le \varepsilon 2^m$ и для любых множеств $T \subset \mathbb{B}^n$ и $U \subset \mathbb{B}^m$, содержащих по $t$ элементов, оценим вероятность того, что для каждого элемента $x \in T$ не менее половины значений $[\chi_i(x)]_m$ (при $i = 1, \dots, n$) попадает в $U$. Для фиксированного $x \in T$ вероятность того, что не менее половины его соседей попадает в $U$, не превосходит $2^N \varepsilon^{N/2}$, поскольку для каждого из не более чем $2^N$ подмножеств множества $\{1, \dots, N\}$, содержащих более $N/2$ элементов, вероятность того, что все входящие в него значения $i$ ведут внутрь $U$, не превосходит $\varepsilon^{N/2}$ (значения $[\chi_i(x)]_m$ при разных $i$ независимы и равномерно распределены в $\mathbb{B}^m$, а доля $U$ среди элементов $\mathbb{B}^m$ не превосходит $\varepsilon$). Такое событие должно произойти независимо для всех $x \in T$, так что полученную оценку надо возвести в степень $t$.

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

$$\sum_{m=1}^{n} \sum_{t=1}^{\varepsilon 2^m} \sum_{T \subset \mathbb{B}^n, |T|=t} \sum_{U \subset \mathbb{B}^m, |U|=t} (2^N \varepsilon^{N/2})^t.$$

Число различных множеств $T$ не превосходит $2^{nt}$ (столько есть последовательностей длины $t$, составленных из элементов $\mathbb{B}^n$); число различных множеств $U$ не превосходит $2^{mt}$. Учитывая это, получаем верхнюю оценку

$$\sum_{m=1}^{n} \sum_{t=1}^{\varepsilon 2^m} 2^{tn} 2^{tm} 2^{tN} \varepsilon^{Nt/2}$$
или

$$ \sum_{m=1}^{n} \sum_{t=1}^{\varepsilon 2^{m}} (2^n 2^m 2^N \varepsilon^{N/2})^t $$

Внутренняя сумма представляет собой геометрическую прогрессию. В условиях леммы знаменатель этой прогрессии меньше $1/2$, и потому сумма прогрессии не превосходит удвоенного первого члена, который не зависит от $t$. Учитывая это, получаем верхнюю оценку

$$ 2n \cdot (2^{N+n+m} \varepsilon^{N/2}) \le n 2^{N+2n+1} \varepsilon^{N/2}, $$

что меньше единицы по условию леммы. Лемма доказана.

Мы будем использовать эту лемму при $\varepsilon = 1/8$. В этом случае можно переписать условие леммы как

$$ n 2^{N+2n+1} < 8^{N/2} $$

или

$$ \log n + N + 2n + 1 < 3N/2. $$

Видно, что можно положить $N = 6n$, и условие леммы будет выполнено при всех достаточно большой $n$.

Продолжим доказательство теоремы 235. Как и раньше, можно заменить слово $C$ его кратчайшим (безусловным) описанием и считать его словом длины $n$, то есть элементом $\mathbb{B}^n$. (Сложность слов $A$ и $B$ роли не играет; в частности, она может быть и больше $n$.) Согласно лемме при $N = 6n$ и $\varepsilon = 1/8$ можно найти $N$ отображений $\chi_1, \dots, \chi_N: \mathbb{B}^n \to \mathbb{B}^n$ с указанными в лемме свойствами. При этом, как уже говорилось, взяв первый в каком-либо естественном порядке набор функций с такими свойствами, мы можем считать, что сложность этого набора есть $O(\log n)$, поскольку для его задания достаточно указать число $n$.

Пусть $KS(C|A) = k$ и $KS(C|B) = l$. (В условии теоремы были неравенства $KS(C|A) \le k$ и $KS(C|A) \le l$, но мы имеем право доказывать теорему для уменьшенных значений $k$ и $l$, от этого утверждение становится только сильнее.) Оставляя от хеш-значений только $k$ или $l$ первых битов, мы получим $N$ отображений $\mathbb{B}^n$ в $\mathbb{B}^k$ (соответственно в $\mathbb{B}^l$). Эти семейства задают двудольные графы на $\mathbb{B}^n \times \mathbb{B}^k$ и $\mathbb{B}^n \times \mathbb{B}^l$, в которых степень каждой вершины слева равна $N$ (считая кратные рёбра). Нас интересуют ограничения этих графов на $S_A$ и $S_B$, где $S_A$ состоит из слов длины $n$, имеющих сложность не более $k$ относительно $A$, а $S_B$ состоит из слов длины $n$, имеющих сложность не более $l$ относительно $B$. Мы выделяем в $\mathbb{B}^k$ плохие вершины, имеющие более $n^c$ соседей в $S_A$; аналогичным образом плохими вершинами в $\mathbb{B}^l$ мы считаем те, у которых имеется более $n^c$ соседей в $S_B$. (Точное значение достаточно большой константы с мы выберем позже.)

Число плохих вершин в обоих случаях не превосходит соответственно

$$ 2N \cdot 2^k / n^c \text{ и } 2N \cdot 2^l / n^c, $$

так как степень плохой вершины больше $n^c$, общее число рёбер в графе не больше $|S_A| \cdot N$ (соответственно $|S_B| \cdot N$), а $|S_A| < 2 \cdot 2^k$ и $|S_B| < 2 \cdot 2^l$.
Назовём плохими в $S_A$ те вершины, у которых половина или более соседей в графе на $S_A \times \mathbb{B}^k$ (с учётом кратности) являются плохими. Лемма гарантирует, что число плохих вершин в $S_A$ меньше

$$2N \cdot 2^k / n^c$$

(мы считаем, что $c$ достаточно велико, поэтому оценка на число плохих вершин меньше $\varepsilon 2^k$, где $\varepsilon = 1/8$; напомним, что $N = 6n$). Поскольку плохие вершины можно перечислять, зная $n, k$ и $A$, сложность любой из них относительно $A$ не превосходит

$$\log(2N \cdot 2^k / n^c) + O(\log n) \le k - c \log n + O(\log n).$$

При достаточно большом $c$ все плохие вершины имеют сложность (относительно $A$) меньше $k$, и слово $C$ не попадает в их число. Это значит, что больше половины значений $[\chi_i(C)]_l$ (среди $N$ вариантов $i = 1, 2, \dots, N$) являются хорошими в $\mathbb{B}^k$.

Повторяя те же рассуждения для графа в $S_B \times \mathbb{B}^l$, мы получаем, что больше половины значений $[\chi_i(C)]_l$ хороши в $S_B$. Следовательно, найдётся значение $i$, которое даёт хороших соседей в обоих случаях. Тогда $X = [\chi_i(C)]_k$ и $X' = [\chi_i(C)]_l$ являются искомыми. ►

**324** Сформулируйте и докажите аналогичное утверждение для трёх условий (или для полиномиального их числа).

Может возникнуть желание ещё усилить результаты теорем 229 и 235. Нельзя ли ограничиться одним-единственным отпечатком? Скажем, нельзя ли для слова $A$ сложности $n$ найти такое слово $X$ длины $n/2$, что $\text{KS}(A|X, B) \approx 0$ для любого слова $B$, для которого $\text{KS}(A|B) \le n/2$?

Легко понять, что этого всё-таки добиться нельзя. В самом деле, пусть такое слово $X$ есть. Тогда условная сложность $A$ относительно $X$ не превосходит $n/2$ (это следует из неравенства $\text{KS}(A|X, B) \approx 0$ для $B$, равного половине кратчайшего описания $A$). Если взять $X$ в качестве $B$, то в условиях $X$ и $B$ информация будет дублироваться, и сложность $\text{KS}(A|X, B)$ будет примерно равна $n/2$ (а не нулю, как нам хотелось).

**325** Покажите, что двух (и любого фиксированного числа) отпечатков недостаточно. [Указание. Допустим, можно обойтись $k$ отпечатками. Без ограничения общности можно считать их все несжимаемыми. Для каждого $i$ и каждого отпечатка рассмотрим слово, составленное из начала длины $i$ этого отпечатка, и обозначим через $B_i$ конкатенацию полученных слов. При некотором $i = i_0$ условная сложность $A$ относительно $B_i$ примерно равна $n/2$. В самом деле, условная сложность $A$ относительно конкатенации целых отпечатков не больше $n/2$ (поскольку это верно даже если в условии оставить только отпечаток, обслуживающий слово $B$, составленное из $n/2$ первых битов минимального описания $A$) и при увеличении $i$ на 1 условная сложность $\text{KS}(A|B_i)$ изменяется незначительно. Ясно, что это $i_0$ не меньше $n/2k$. Ни один из $k$ отпечатков не может обслужить $B_{i_0}$, поскольку при добавлении его к условию сложность $\text{KS}(A|B_{i_0})$ понижается максимум на $n/2 - i_0 \le n/2 - n/2k$ (так как $i_0 k$ его битов уже есть в условии), а должна на $n/2$.]
## 12.8. Поток информации через разрез

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

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

Выделим произвольное множество $I$ вершин графа (разрез) и будем изучать поток информации, проходящей через этот разрез (идущей извне множества $I$ внутрь него). Рассмотрим пропускные способности всех рёбер, начало которых лежит вне $I$, а конец внутри $I$. Если среди них есть хоть одно ребро с неограниченной пропускной способностью, то никакого необходимого условия для такого $I$ не получится. Пусть все пропускные способности этих рёбер ограничены и равны $u_1, \dots, u_k$. Пусть $V_1, \dots, V_l$ — все входные слова для вершин из $I$, а $W_1, \dots, W_m$ — все выходные слова для вершин из $I$. Тогда можно записать такое необходимое условие:

$$KS(W_1, \dots, W_m | V_1, \dots, V_l) \le u_1 + \dots + u_k.$$

(Как всегда, неравенства рассматриваются с точностью до логарифма суммарных длин входящих в них слов.) В самом деле, если мы знаем все слова $V_1, \dots, V_l$, а также все слова, написанные на ведущих внутрь $I$ рёбрах, то можем восстановить (с логарифмической дополнительной информацией) все слова, выходящие из вершин множества $I$, включая $W_1, \dots, W_m$. Это нужно делать, рассматривая вершины множества $I$ по очереди (начало любого ребра должно предшествовать его концу; такой порядок существует, так как в графе нет циклов).

По существу это рассуждение оценивает «поток информации через разрез».

Покажем на примере, как получаются необходимые условия в рассмотренных нами случаях. Рассмотрим схему передачи информации раздела 12.6 и в качестве множества $I$ возьмём множество из трёх вершин, показанное на рис. 12.7 внутри пунктирной линии.

<figure><img src="image_44.png" /><figcaption>Рис. 12.7. Разрез для теоремы Беннета – Гача – Ли – Витаньи – Цурека.</figcaption></figure>
В это множество входят слово А и слово длины *k* (по ребру ограниченной пропускной способности); два других ребра графа, пересекающие границу *I*, ведут изнутри наружу (напомним, что по нашему соглашению все рёбра идут сверху вниз). Получается условие $KS(B|A) \le k$, которое мы и рассматривали.

**326** Показайте, что все остальные необходимые условия, указанные нами для рассмотренных выше задач, также могут быть получены при подходящем выборе множества *I* на соответствующем графе.

## 12.9. Сети с одним источником

Возникает естественный вопрос: являются ли необходимые условия, указанные в предыдущем разделе (и взятые для всех множеств *I*, для которых они имеют смысл), одновременно и достаточными? В наших предыдущих примерах это оказывалось именно так. В общем случае, как мы увидим дальше, это неверно. Однако в случае, когда мы хотим передать какое-то одно слово А из одного источника в несколько мест назначения (другими словами, когда входное слово только одно, а все выходные слова равны входному), наши условия будут и достаточными.

Для классической теории информации аналогичная задача была рассмотрена в работах [1, 86]; наше рассуждение следует использованной там схеме (с некоторыми изменениями, связанными с переходом от шенноновской энтропии к колмогоровской сложности).

Начнём с примера: пусть мы хотим передать слово А длины $2k$ в три пункта назначения, как показано на рис. 12.8; все каналы связи имеют неограниченную пропускную способность, кроме трёх первых, которые имеют пропускную способность *k* битов. Можно ли это сделать?

<figure><img src="image_45.png" /><figcaption>Рис. 12.8. Деление информации на части.</figcaption></figure>

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

Стандартный способ («разделение секрета с помощью линейных отображений») состоит в том, чтобы передать по трём каналам слова $A_1, A_2$ и $A_1 \oplus A_2$, где $A_1$ и $A_2$ — две половины слова А (каждая содержит $k$ битов), а $A_1 \oplus A_2$ — побитовая сумма слов $A_1$ и $A_2$ по модулю 2. По любым двум из этих трёх $k$-битовых слов можно восстановить третье (оно равно их побитовой сумме), а потому можно восстановить и слово А.

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

**Теорема 236.** Рассмотрим схему передачи информации с единственным входным словом А длины $n$ и выходными словами А, в которой заданы целые ограничения на пропускные способности некоторых рёбер.

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

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

(Константа, подразумеваемая в $O(\log n)$, зависит от графа, но не зависит от числа $n$, пропускных способностей и слова А.)

► Рассмотрим сначала случай одного выходного слова. В этом случае требуется передать некоторый объём информации (а именно, $n$ битов) из одной вершины (назовём её $s$) в какую-то другую вершину $t$ (только одну!) по рёбрам.

Запакуем каждый бит в отдельный конверт; получится $n$ конвертов, которые изначально находятся в вершине $s$. Организуем доставку этих конвертов в вершину $t$ по рёбрам графа. При этом мы следим за пропускной способностью и требуем, чтобы по ребру с ограничением $k$ было перевезено не более $k$ конвертов.

Эта задача разрешима по теореме Форда – Фалкерсона о максимальном потоке и минимальном разрезе (см., например, [33]; поскольку все ограничения целочисленные, то и поток будет целочисленным).

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

Покажем, что выполнено ограничение на условную сложность. Рассмотрим вершину и слова на выходящих и входящих рёбрах этой вершины. Слова на выходящих рёбрах составлены путём перемешивания битов в словах на входящих рёбрах; схема
этого перемешивания не зависит от слова А и алгоритмически вычисляется, если известно число $n$ и пропускные способности рёбер. Без ограничения общности можно предполагать, что пропускные способности рёбер не больше $n$, поэтому схема перемешивания имеет сложность $O(\log n)$ (константа зависит от графа). А зная эту схему, можно получить выходящие слова по известным входящим.

### Случай передачи информации в одну вершину разобран.

Идея доказательства теоремы в общем случае состоит в том, чтобы производить линейное кодирование. До сих пор мы лишь перекоммутировали биты (перекладывали конверты из входящих линий в выходящие). Более общий способ: в каждом узле применяется линейное отображение. Каждый выходящий бит будет линейной функцией от входящих битов. Для начала будем рассматривать биты как элементы поля $\mathbb{F}_2$ (поле из двух элементов: нуля и единицы, при этом $1 + 1 = 0$). Тогда $l$-битовые слова будут элементами $l$-мерного векторного пространства над этим полем.

Пусть в некоторую вершину входят рёбра с пропускной способностью $i_1, \dots, i_p$, а выходящие рёбра имеют пропускные способности $j_1, \dots, j_q$. (Мы будем считать, что все пропускные способности рёбер конечны, заменив бесконечность на $n$, число битов в передаваемом слове.) Тогда преобразование информации в этой вершине задаётся матрицей размера $(j_1 + \dots + j_q) \times (i_1 + \dots + i_p)$; умножая её на столбец входных битов (со всех входящих рёбер), получаем столбец выходных битов (для всех выходящих рёбер). Заметим, что по ребру пропускной способности $k$ передается ровно $k$ битов (независимо от того, насколько это ребро кажется полезным).

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

Пусть для каждой вершины такие линейные преобразования (матрицы) заданы. Тогда для каждого выхода возникает отображение входа в этот выход — некоторое линейное отображение $n$-мерных пространств над полем $\mathbb{F}_2$. Нам хотелось бы, чтобы все эти отображения были обратимы; в этом случае каждое выходное слово содержало бы полную (с точностью до линейного взаимно однозначного соответствия) информацию о входных битах, и задача передачи информации была бы разрешима для произвольного входного слова А (на каждом ребре графа нужно было бы написать передаваемый по нему набор битов для слова А).

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

Проблема в том, что не всегда можно добиться одновременной обратимости всех отображений вход → выход.

327 Рассмотрим граф на рис. 12.9; входное слово имеет длину 2, пропускная способность всех рёбер равна 1. Покажите, что нельзя указать такие линейные преобразования в вершинах, чтобы все шесть отображений входа в выход были бы
<figure><img src="image_46.png" /><figcaption>Рис. 12.9. Двух элементов в поле мало.</figcaption></figure>

обратимыми. [Указание. Существует всего три ненулевых линейных функционала на $F_2$, поэтому в двух промежуточных вершинах будет одинаковая информация.]

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

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

Мы докажем, что если поле $F$ достаточно велико, то можно так выбрать преобразования в вершинах, чтобы отображения входа во все выходы были бы одновременно обратимы.

Будем считать элементы матриц преобразования в вершинах переменными (принимающими значения в $F$). Тогда элементами матрицы преобразования входа в выход будут многочлены от этих переменных, и потому её определитель тоже будет многочленом. Степень этого многочлена, как легко проверить, не превосходит $nE$, где $E$ — число рёбер графа (при движении от входа к выходу в каждом узле степень каждого матричного элемента увеличивается на единицу, а степень определителя матрицы $n \times n$ в $n$ раз больше степени матричных элементов).

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

**Лемма.** Многочлен степени $d$ от $m$ переменных над полем $F$ либо равен нулю тождественно, либо принимает нулевое значение с вероятностью не более $d/|F|$ (все элементы $F^m$ считаем равновероятными, $|F|$ — число элементов поля $F$).

(Говоря о степени многочлена, мы имеем в виду суммарную степень по всем переменным.)
Доказательство проходит индукцией по $m$. Для $m=1$ лемма утверждает, что число корней многочлена с одной переменной не превосходит его степени (и доказывается разложением на множители). Для больших $m$ запишем многочлен как многочлен некоторой степени $d_1$ от одной переменной, коэффициенты которого представляют собой многочлены от $m-1$ переменных. Обозначим через $d_2$ степень его старшего коэффициента как многочлена от $m-1$ переменной. Этот старший коэффициент может быть нулевым или ненулевым в зависимости от значений остальных переменных; вероятность того, что он окажется нулевым, не больше $d_2/|F|$ по предположению индукции, а если старший коэффициент ненулевой, то вероятность попасть в корень такого многочлена от одной переменной не больше $d_1/|F|$. Так что всего получаем $(d_2+d_1)/|F| \le d/|F|$. Лемма доказана.

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

Подсчитаем: степень многочлена не больше $nE$, выходных рёбер тоже не больше $E$, так что если $nE^2 < |F|$, то наше рассуждение доказывает, что есть линейные преобразования в вершинах, делающие сразу все отображения входа в выходы образумыми одновременно. (И такое преобразование можно найти перебором, так что среди них есть простые.)

Как это можно применить в ситуации, когда имеется слово из $n$ битов, а вовсе не элементов конечного поля? Как это принято в теории кодирования, будем разбивать слово на блоки некоторой длины $k$ (в количестве $n/k$) и считать каждый блок элементом поля из $2^k$ элементов (такое поле, как известно из алгебры, существует).

Если оказалось, что число $n$, а также все пропускные способности делятся на $k$, и при этом $2^k > (n/k)E^2$, то всё хорошо.

Как быть в общем случае? Для начала нужно выбрать значение $k$, при котором $2^k > nE^2$ (мы берём $k$ с запасом, пренебрегая делением на $k$ в правой части). Отметим, что при этом $k = O(\log n)$. Затем надо округлить $n$ и пропускные способности до целых кратных числа $k$; при этом $n$ надо округлять с уменьшением, а пропускные способности — с увеличением, чтобы не нарушить условия на пропускные способности разрезов. При этом погрешность будет порядка $O(\log n)$, и остаётся только воспользоваться доказанным утверждением. ►

### 328 Используя описанный метод, постройте вероятностный полиномиальный алгоритм отыскания величины максимального потока в ориентированном графе без циклов с целыми пропускными способностями. [Указание. Достаточно научиться определять, есть ли в графе поток размера $n$, и находить его, если есть (для любого данного $n$). Для этого сопоставим каждому ребру линейное отображение, как в доказательстве теоремы. При этом пропускные способности выходного и входного ребра будем считать равными $n$. Существование потока размера $n$ равносильно не вырожденности линейного отображения (вход → выход) для некоторых линейных отображениях на рёбрах. А существование таких линейных отображений на рёбрах можно проверять вероятностным алгоритмом с помощью алгебраической леммы.]

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

Один пример такого рода (где необходимые условия на поток информации не являются достаточными) мы по существу уже рассматривали. Это задача о выделении общей информации, рассмотренная в главе 11. В разделе 12.1 для данных слов х, у и чисел α, β и γ мы интересовались, найдётся ли слово z, для которого

$$KS(z) < \alpha, \quad KS(x|z) < \beta, \quad KS(y|z) < \gamma.$$

Легко понять, что с точностью до логарифмических слагаемых эту задачу можно сформулировать как задачу передачи информации в графе рис. 12.10. В самом

<figure><img src="image_47.png" /><figcaption>Рис. 12.10. Задача выделения общей информации.</figcaption></figure>

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

Видно, что условия на пропускные способности разрезов соответствуют неравенствам

$$KS(x) \le \alpha + \beta, \quad KS(y) \le \alpha + \gamma, \quad KS(x,y) \le \alpha + \beta + \gamma,$$

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

## 12.11. Упрощение программы

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

Рассмотрим задачу рис. 12.11 (её предложил М. Вьюгин). Разница с теоремой Мучника в том, что внизу требуется не восстановить одно из двух входных слов (P и A), а получить некоторое третье слово B. Оказывается, что и в этой задаче

<figure><img src="image_48.png" /><figcaption>Рис. 12.11. Задача упрощения программы.</figcaption></figure>

необходимые условия на поток информации $KS(B|A) \le k$ и $KS(B|A, P) = 0$ (как всегда, рассматриваемые с логарифмической точностью) не являются достаточными.

Подробно эта задача рассмотрена в статье [121], где приводятся игровое, вероятностное и комбинаторное объяснения этого факта.

## 12.12. Минимальная достаточная статистика

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

<figure><img src="image_49.png" /><figcaption>Рис. 12.12. Два канала ограниченной пропускной способности.</figcaption></figure>

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

Эта задача связана с понятием «минимальной достаточной статистики» в теории вероятностей. Пусть имеется пара совместно распределённых случайных величин $\theta$ и $X$. Первую из них считают «параметром» и для каждого её значения рассматривают условное распределение $X_\theta$ второй величины. Например, можно считать, что
$\theta$ выбирается равномерно на отрезке $[0, 1]$, после чего в качестве $X$ берётся результат $n$ независимых испытаний с вероятностью успеха $\theta$ (условное распределение $X_\theta$ представляет собой бернуллиево распределение с параметром $\theta$ на множестве $\mathbb{B}^n$ слов длины $n$).

Предположим, что мы хотим восстановить значение неизвестного параметра $\theta$, зная его априорное распределение и наблюдая значение величины $X_\theta$. Не вся информация, содержащаяся в $X_\theta$, при этом существенна. В нашем примере важно лишь число успехов, а какие именно испытания были успешными, роли не играет. Формально говоря, величина $N(X)$, равная числу единиц в $X$, содержит всю информацию о $\theta$, которую можно извлечь из $X$:

$$I(N(X):\theta) = I(X:\theta).$$

Для произвольной функции $N$ левая часть не превосходит правой; те функции, где это неравенство обращается в равенство, называют достаточными статистиками. Это же условие можно сформулировать иначе: $\theta$ и $X$ независимы при известном $N(X)$. Ещё одна переформулировка: $H(\theta|N(X)) = H(\theta|X)$.

Сама величина $X$, очевидно, является достаточной статистикой; из примера видно, что статистика может содержать много «лишней информации». Достаточную статистику называют минимальной, если она является функцией любой другой достаточной статистики. Для случайных величин с конечным числом значений минимальная достаточная статистика всегда существует: надо склеить те значения $X$, которым соответствуют одинаковые условные распределения параметра $\theta$. Минимальная достаточная статистика имеет наименьшую энтропию среди всех достаточных статистик.

**329** Предположим, что все возможные значения $\theta$ имеют ненулевую вероятность. Докажите, что в определении достаточной статистики важны только условные вероятности $P[X = x | \theta = t]$ для всех пар $x, t$. [Указание. Сопоставим каждому $x$ вектор, состоящий из чисел $P[X = x | \theta = t]$ для всех возможных значений $t$ случайной величины $\theta$. Тогда функция $N$ является достаточной статистикой тогда и только тогда, когда любые два склеенных ей слова имеют пропорциональные вектора.]

Задачу поиска минимальной достаточной статистики можно сформулировать так: среди величин $X'$, для которых $H(X'|X) = 0$ (т. е. $X'$ есть функция от $X$) мы выделяем те, для которых $H(\theta|X')$ минимально возможная (равна $H(\theta|X)$), и среди них минимизируем $H(X')$.

В сложностной постановке мы имеем дело с двумя словами $A$ (соответствует параметру $\theta$) и $B$ (соответствует $X$). Мы хотим извлечь из $B$ некоторую часть информации $B'$, для которой $KS(A|B')$ минимально возможная (приближается к $KS(A|B)$), и $KS(B')$ как можно меньше. На рисунке $B'$ передаётся по каналу с ограничением $q$, а условное описание $A$ при известном $B'$ передаётся по каналу с ограничением $p$. Минимальная достаточная статистика соответствует минимизации $q$ при минимально возможном $p \approx KS(A|B)$.

Мы рассматриваем более общий вопрос: при каких $p$ и $q$ передача информации по указанной схеме возможна. Необходимые условия, связанные с потоками
информации через разрезы, таковы: $KS(A) \le p+q$ и $KS(A|B) \le p$. (Как всегда, мы опускаем оговорки о логарифмических поправках.)

**330** Нарисуйте соответствующие разрезы.

Для некоторых пар слов эти необходимые условия являются также и достаточными.

**331** Проверьте, что если у слов А и В полностью выделяется общая информация (например, слова А и В являются перекрывающими кусками случайного слова), то эти необходимые условия являются также и достаточными. [Указание. Условие $KS(A|B) \le p$ позволяет передать по левому каналу часть слова А, не попавшую в В, и ещё сколько-то, а остаток можно передать по правому каналу (условие $KS(A) \le p+q$ гарантирует, что места в канале хватит).]

Однако в общем случае необходимые условия могут не быть достаточными. Для наглядности зафиксируем сложности и условные сложности слов А и В: пусть оба слова А и В имеют сложность $2n$, а пара $\langle A, B \rangle$ имеет сложность $3n$ (и потому условные сложности равны $n$). Необходимые условия $p+q \ge 2n$ и $p \ge n$ для этого случая показаны на рис. 12.13.

<figure><img src="image_50.png" /><figcaption>Рис. 12.13. Необходимые условия.</figcaption></figure>

Теперь попытаемся понять, при каких $p$ и $q$ задача заведомо разрешима (для любой пары слов А и В указанной сложности). Можно передавать слово А целиком по левому каналу, поэтому задача разрешима при $p=2n, q=0$ (а также для всех больших $p$ и $q$). Можно передавать слово В целиком по правому каналу, поэтому задача разрешима при $p=n, q=2n$ (а также для всех больших $p$ и $q$). Это соответствует двум квадрантам с вершинами в $(2n, 0)$ и $(n, 2n)$. Более того, если от В отрезать (скажем, последние) $k$ битов, то условная сложность $KS(A|B)$ увеличится не более чем на $k$, поэтому задача разрешима при $q=2n-k$, $p=n+k$. Таким образом, вся тёмно-серая область на рисунке 12.14 (обозначенная там как $G$) соответствует параметра $\langle p, q \rangle$, для которых задача разрешима.

Как и в случае с выделением общей информации (глава 11), можно сказать, что «профиль» пары слов А, В (множество пар $\langle p, q \rangle$, при которых задача разрешима) зависит от того, какую именно пару слов (с данной сложностью и условной сложностью) мы возьмём. Как мы видели в задаче 331, для некоторых пар слов
<figure><img src="image_51.png" /><figcaption>Рис. 12.14. Достаточные условия.</figcaption></figure>

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

Нужно только понять, как это правильно сформулировать. Хотелось бы сказать, что для всех $B'$, простых относительно $B$, пара $\langle KS(A|B'), l(B') \rangle$ находится в $O(\log n)$-окрестности множества $G$, причём константа в $O(\log n)$ не зависит ни от $n$, ни от $B'$. Однако выражение «простые относительно $B$» требует количественного уточнения: мы должны указать некоторую границу $r$ и рассматривать слова $B'$, для которых $KS(B'|B) < r$. Естественно ожидать, что чем больше $r$, тем дальше может отходить пара $\langle KS(A|B'), l(B') \rangle$ от $G$. Как мы увидим, связь тут линейная.

**Теорема 237.** При любом $n$ существуют слова $A, B$ сложности $2n + O(\log n)$, для которых $KS(A, B) = 3n + O(\log n)$ и для любого $B'$ пара $\langle KS(A|B'), l(B') \rangle$ находится в $O(\log n + KS(B'|B))$-окрестности множества $G$.

◀ Утверждение этой теоремы, как обычно, соответствует некоторой игре. Мы опишем эту игру, укажем выигрышную стратегию и выведем отсюда утверждение теоремы.

Пусть фиксировано значение $n$; при каждом $n$ будет своя игра. В этой игре мы имеем право для каждого $B$ длины $2n$ указать до $2^n$ слов длины $2n$, условно именуя их «*n*-простыми относительно $B$».

Противник для каждого $p, q$ и $r$ (из некоторого множества $M$ допустимых троек натуральных чисел; это множество мы опишем позднее) имеет право:

* для каждого слова $B$ длины $2n$ указать до $2^r$ слов длины $q$, которые условно именуются «*r*-простыми относительно $B$»;

* для каждого слова $B'$ длины $q$ указать до $2^p$ слов длины $2n$, которые условно именуются «*p*-простыми относительно $B'$».

Для каждой тройки $\langle p, q, r \rangle$ (из множества допустимых троек) это происходит независимо. Можно сказать, что мы играем против команды противника, в которой для каждой тройки $\langle p, q, r \rangle$ есть свой игрок, делающий свои объявления и подчиняющийся своим ограничениям, но цель игры у них общая.
Кроме этого, в команде противника есть ещё два дополнительных игрока. Один из них имеет право браковать слова длиной $2n$ (но не более $2^{2n-1}$ штук, то есть половины всех слов), называя их «плохими». Второй имеет право для каждого слова $B$ длины $2n$ забраковать до $2^{n-2}$ слов длины $2n$ (свои для каждого $B$), объявляя их «плохими для данного $B$». (Рассматриваемый далее противник будет браковать слова длиной $2n$, имеющие сложность менее $2n-1$, а также для каждого слова $B$ браковать слова $A$, для которых $KS(A|B) < n-2$, но в определение игры это не входит.) Мы используем границу $n-2$ (а не, скажем, $n-1$), поскольку нам потребуется некоторый запас, см. ниже.

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

Остаётся определить, кто выигрывает в предельной позиции. Будем считать, что выиграл противник, если для каждой пары слов $\langle A, B \rangle$ длины $2n$ (каждое), в которой слово $A$ объявлено $n$-простым относительно слова $B$, причём $A$ и $B$ не забракованы (не объявлены плохими) и $A$ не забраковано для данного $B$ (не объявлено плохим для этого $B$), найдётся допустимая тройка $\langle p, q, r \rangle$ и слово $B'$ длины $q$, для которой

* $B'$ объявлено $r$-простым относительно $B$;

* $A$ объявлено $p$-простым относительно $B'$.

Мы укажем простую стратегию, позволяющую выигрывать в этой игре (при некотором множестве допустимых троек $\langle p, q, r \rangle$), а затем выведем из этого утверждение теоремы.

Выигрывающая стратегия состоит в том, что на каждый ход противника (любого из участников противостоящей команды), состоящий в объявлении нового «простого» или «плохого» слова, мы отвечаем одним своим ходом. Этот ход состоит в добавлении (для некоторого слова $B$ длины $2n$) одного $n$-простого слова $A$ длины $2n$, которое помешало бы противнику выиграть (если он не сделает нового хода). Для этого нужно, чтобы выполнялись следующие условия:

* выбранные слова $A$ и $B$ (ещё) не забракованы (не объявлены плохими);

* слово $A$ (ещё) не объявлено плохим относительно $B$;

* ни для одной допустимой тройки $\langle p, q, r \rangle$ не найдётся слова $B'$ длины $q$, которое было бы объявлено $\langle p, q, r \rangle$-игроком команды противника $r$-простым относительно $B$, и для которого $A$ объявлено этим же игроком $p$-простым относительно $B'$.

Почему это возможно? На любой момент игры имеется не менее $2^{2n-1}$ незабракованных слов. Взяв в качестве $B$ одно из них, мы имеем право объявить любое слово $n$-простым относительно $B$, если только уже не объявили $2^n$ слов простыми относительно $B$. Но если такое случилось для всех незабракованных $B$, это значит, что мы уже сделали $2^{2n-1} \cdot 2^n = 2^{3n-1}$ ходов, отвечая одним своим ходом на каж-