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

Естественно ожидать, что если мы приходим в Kasino, где играют в орлянку, заранее наметив какое-то правило выбора такого рода, и делаем ставки в те моменты, когда правило выбора включает очередной член в подпоследовательность, то никакого преимущества мы не получим и предельная частота единиц в подпоследовательности будет равна 1/2. Но это верно лишь при условии, что правило выбора фиксировано заранее: задним числом (зная последовательность) легко можно подобрать правило выбора, которое бы у этой последовательности выиграло. Другими словами, имеет место такой очевидный факт: для каждой последовательности ω существует множество R, при котором последовательность $S_R(ω)$ состоит из одних нулей или одних единиц, и потому не сбалансирована. Поэтому нельзя определить коллектив как последовательность ω, для которой подпоследовательность $S_R(ω)$ сбалансирована (или конечна) для всех множеств R: при таком определении коллективов вообще не будет.

Однако, как заметил Вальд [188], для любого счётного семейства правил выбора $S_{R_i}$ (соответствующего счётному семейству множеств $R_i$) существует последовательность ω, которая обладает свойством устойчивости частот относительно всех правил этого семейства: при любом i последовательность $S_{R_i}(ω)$ сбалансирована (или конечна).

Это легко следует из вероятностных соображений:

**Теорема 166.** Пусть R — произвольное множество слов. Тогда множество тех последовательностей ω ∈ Ω, для которых $S_R(ω)$ бесконечна, но не сбалансирована, имеет меру нуль (относительно равномерной меры на пространстве бесконечных последовательностей нулей и единиц).

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

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

**Лемма.** Пусть $U ⊂ Ω$ — множество меры нуль. Тогда его прообраз $S_R^{-1}(U)$ имеет меру нуль.

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

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

Формально это рассуждение проводится так:

Рассмотрим множество $Σ_х$ всех конечных и бесконечных продолжений слова х и два его подмножества $Σ_{x0}$ и $Σ_{x1}$. Докажем, что прообразы этих подмножеств при
отображении $S_R$ имеют равную меру (другими словами, что появление в подпоследовательности нуля и единицы после данного слова х одинаково вероятно).

В самом деле, рассмотрим все слова $z$, из которых при выборе по правилу $S_R$ получается $x$ и для которых $z \in R$. Они соответствуют ситуациям, когда слово $x$ уже выбрано и вот-вот будет выбран следующий бит. Из определения следует, что два таких слова не сравнимы друг с другом. Поэтому множества $\Omega_{z0}$ для всех таких $z$ не пересекаются, и, как легко понять, вместе составляют прообраз множества $\Sigma_{x0}$. Аналогично прообраз множества $\Sigma_{x1}$ есть объединение непересекающихся множеств вида $\Omega_{z1}$. Мы разбили прообразы на равные части и, значит, меры прообразов равны.

Из доказанного по индукции легко следует, что мера прообраза множества $\Sigma_x$ не превосходит $2^{-l(x)}$. Поэтому прообраз нулевого множества $U \subset \Omega$ является нулевым. В самом деле, возьмём покрытие множества $U$ интервалами $\Omega_{x_i}$ с малой суммой мер; рассмотрим прообразы множеств $\Sigma_{x_i}$; каждый из них есть объединение счётного числа интервалов. Объединив все эти интервалы, получим покрытие множества $S_R^{-1}(U)$ с малой суммой мер. Лемма (а с ней и теорема 166) доказана. ►

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

$$ \mu(S_R^{-1}(U)) \le \mu(U) $$

для любого измеримого множества $U \subset \Omega$. В случае, когда $S_R(\omega)$ бесконечно для всех (или почти всех) $\omega$, верно и более сильное утверждение: $S_R(\omega)$ имеет равномерное распределение, то есть

$$ \mu(S_R^{-1}(U)) = \mu(U) $$

для любого измеримого $U$. (Рассмотрим $U$ и его дополнение.)

**253** Пусть фиксировано некоторое множество $R$. Покажите, что если $\omega$ имеет бернуллиево распределение (испытания независимы и имеют одну и ту же вероятность успеха), то подпоследовательность $S_R(\omega)$ имеет то же распределение (предполагая, что она бесконечна с вероятностью 1).

Итак, понятие коллектива становится непустым (коллективы существуют), если из всех возможных правил выбора (соответствующих всем возможным подмножествам $R \subset \Xi$) выбрать некоторое счётное семейство. Но что это может быть за семейство?

## 9.3. Случайность по Мизесу – Чёрчу

С появлением теории вычислимых функций стало ясно, что естественно рассматривать правила выбора $S_R$, соответствующие всевозможным разрешимым множествам $R$. Это предложил А. Чёрч [32], поэтому такие правила выбора называют допустимыми по Чёрчу, а соответствующие последовательности (сохраняющие
устойчивость частот при всех допустимых по Чёрчу правилах) называют случайными по Мизесу – Чёрчу. В англоязычной литературе используют термин *Church stochastic*.

Мы уже знаем, что таковые существуют и образуют множество меры 1. Верно и более сильное утверждение:

**Теорема 167.** Всякая случайная в смысле Мартин-Лёфа последовательность (относительно равномерной меры) случайна по Мизесу – Чёрчу.

◀ Эффективный вариант усиленного закона больших чисел (теорема 32, с. 78; см. также раздел 8.4) говорит, что множество *U* несбалансированных последовательностей (у которых предел частот не существует или не равен 1/2) является эффективно нулевым.

Покажем, что если $S_R$ — допустимое по Чёрчу правило выбора, то прообраз эффективно нулевого множества будет эффективно нулевым. В самом деле, при разрешимом *R* конструкция в доказательстве теоремы 166 становится эффективной (все интервалы, составляющие прообраз данного интервала, можно эффективно перечислять). Поэтому случайная по Мартин-Лёфу последовательность не принадлежит этому прообразу, то есть её образ сбалансирован (или конечен). ►

Что можно доказать про случайные по Мизесу – Чёрчу последовательности, кротом усиленного закона больших чисел, которому они удовлетворяют по определению? Например, можно доказать, что частоты появления не только букв, но и подслов таковы, какими они должны быть:

**Теорема 168.** Пусть $\omega$ — случайная по Мизесу – Чёрчу последовательность, а $U$ — некоторое двоичное слово. Рассмотрим те позиции $k$, начиная с которых $U$ встречается в $\omega$ (то есть $U_0U_1... = \omega_k\omega_{k+1}...$). Тогда доля таких позиций среди первых $N$ позиций стремится к $1/2^l(U)$ при $N \to \infty$.

◀ По условию нули встречаются примерно в половине позиций. Рассмотрим правило «выбирать после нулей». По предположению в выбранной подпоследовательности будет примерно половина нулей, что означает, что после нулей одинаково часто бывают нули и единицы (то есть что частота груп 00 и 01 стремится к 1/4). Теперь рассмотрим правило «выбирать после 00» (или после 01) и так далее. ►

**254** Докажите, что если случайную по Мизесу – Чёрчу последовательность разрезать на блоки длиной $k$, то каждый из $2^k$ возможных блоков будет встречаться с частотой, стремящейся к $1/2^k$. [Указание. Это утверждение отличается от предыдущей теоремы тем, что здесь учитываются блоки не на всех местах, а лишь на кратных $k$; его доказательство аналогично.]

Последовательности из теоремы 168, в которых каждая комбинация символов встречается с одинаковой частотой (в пределе), рассматривались и до Мизеса и назывались «нормальными». Действительные числа, двоичными записями которых являются нормальные последовательности, называются нормальными по основанию 2. Аналогично определяются действительные числа, нормальные по основанию $b$ (normal in base $b$); числа, нормальные по всем основаниям, называются абсолютно нормальными (absolutely normal).
**255** Покажите, что нормальность числа по основаниям b и $b^k$ равносильны.

Нормальность по разным основаниям, вообще говоря, не равносильна, но это — нетривиальный теоретико-числовой результат [138], и мы не приводим его доказательства.

**256** Будем рассматривать последовательность битов как двоичную запись числа в промежутке $[0, 1]$. Тогда её хвосты образуют последовательность точек в $[0, 1]$, являющуюся орбитой отображения $x \mapsto \{2x\}$, где фигурные скобки обозначают дробную часть. Покажите, что исходная последовательность битов нормальна тогда и только тогда, когда эта последовательность точек равномерно распределена на отрезке (в том смысле, что предельная доля точек, попадающих в некоторый подотрезок, пропорциональна его длине).

**257** Покажите, что при умножение на целое число нормальность действительного числа сохраняется. [Указание. Используйте предыдущую задачу. В результате $n$-кратного применения отображения $x \mapsto \{2x\}$ к исходной точке $x$ получается число $\{2^n x\}$. Ясно, что для любого целого $k$ число $\{2^n (kx)\}$ получается из числа $\{2^n x\}$ преобразованием $y \mapsto \{ky\}$. Поэтому достаточно доказать, что последнее преобразование сохраняет равномерное распределение на отрезке $[0, 1]$.]

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

Среди нормальных последовательностей есть и вычислимые: например, если выписать подряд числа 1, 2, 3, ... в двоичной записи и объединить цифры в одну последовательность, то получится нормальная последовательность

11011100101101111000100110101011...

(пример Чампернауна [26]; он рассматривал десятичную систему счисления, но большой разницы тут нет).

**258** Докажите это. [Указание. Каков бы ни был размер блока $k$, начиная с некоторого места границы между записями натуральных чисел не сильно меняют частоты, а в среднем по всем натуральным числам заданной длины частоты правильны. (Тут нужна аккуратность, если мы останавливаемся посередине чисел некоторой длины.)]

Это построение годится только для одной системы счисления. Но существуют и числа, запись которых в любой системе счисления будет вычислимой нормальной последовательностью. (Это наблюдение было сделано ещё Тьюрингом в оставшихся неопубликованными заметках, см. [4].)

**259** Докажите существование таких чисел. [Указание. Ненормальные в данной системе числа образуют нулевое в смысле Шнорра множество; объединение таких множеств по всем системам тоже будет нулевым по Шнорру множеством, и вне него существует вычислимая последовательность.]

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

**Теорема 169.** Для любого всюду определённого алгоритма, который пытается предсказывать следующий член последовательности по её предыдущим членам, доля успешных предсказаний на случайной по Мизесу – Чёрчу последовательности стремится к 1/2.

◀ В самом деле, каждому предсказывающему алгоритму соответствуют два пра-
вила выбора: одно отбирает те члены, где предсказан нуль, другое — где единица.
Тем самым последовательность разбивается в «смесь» двух своих подпоследова-
тельностей. Каждая из них сбалансирована (или конечна, но тогда всё очевидно),
и потому на ней доля успешных предсказаний стремится к 1/2. Значит, и общая
доля успешных предсказаний стремится к 1/2. ▶

Это утверждение можно ещё несколько обобщить. Представим себе такую игру:
перед появлением следующего члена последовательности мы можем поставить не-
которую сумму (неотрицательное рациональное число, не превосходящее единицы)
на один из исходов (нуль или единицу). Если мы угадали, то ставка удваивается,
если не угадали — пропадает. Наша стратегия в такой игре задаётся функцией $S$,
определённой на двоичных словах и принимающей рациональные значения в отрез-
ке $[-1, 1]$. (Положительные значения соответствуют ставке на 0, отрицательные —
на 1.) Суммарный выигрыш стратегии $S$ на начальном отрезке $\omega_0 \dots \omega_{n-1}$ можно
записать как

$$
\sum_{i=0}^{n-1} S(\omega_0 \dots \omega_{i-1}) \cdot (-1)^{\omega_i}.
$$

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

**Теорема 170.** Пусть $S$ — всюду определённая вычислимая стратегия опи-
санного вида, а $\omega$ — случайная по Мизесу – Чёрчу последовательность. Тогда
выигрыш $S$ на начальном отрезке длины $n$ последовательности $\omega$ есть $o(n)$.

◀ Пусть сначала стратегия принимает только значения 1 и -1. Тогда её деятель-
ность сводится к уже рассмотренному угадыванию следующего члена; доля успехов
стремится к 1/2, что в точности и означает, что средний выигрыш (в расчёте на
одну игру) стремится к нулю.

Если стратегия *S* принимает лишь значения, кратные 1/*k* для некоторого це-
лого *k* (от −1 до 1 с шагом 1/*k*), то её можно представить как среднее арифмети-
ческое 2*k* стратегий, принимающих значения −1 и 1; при этом выигрыш *S* будет
средним арифметическим выигрышей всех этих стратегий, и если для каждой из
них выигрыш есть *o*(*n*), то и для среднего арифметического он будет равен *o*(*n*).
(Мы предполагаем, что число *k* фиксировано и не зависит от *n*.)

Осталось перейти к случаю вычислимой стратегии с произвольными рациональ-
ными значениями. Для произвольного ε > 0 мы должны показать, что выигрыш S
на начальном отрезке длины n не превосходит (по модулю) εn для всех достаточно
больших n.
Выберем $k$ так, чтобы $1/k$ было меньше $\varepsilon$, и приблизим нашу стратегию $S$ стратегией $S'$ со значениями, кратными $1/k$ (заменив каждое значение на ближайшее кратное; ошибка будет не больше $\varepsilon/2$). Для стратегии $S'$ выигрыш есть $o(n)$ и потому меньше $(\varepsilon/2)n$ для достаточно больших $n$, а разница между выигрышем для $S$ и $S'$ не превосходит $(\varepsilon/2)n$. ►

Ещё одно естественное свойство (упоминавшееся фон Мизесом как одно из основных свойств коллективов):

**Теорема 171.** Применение допустимого по Чёрчу правила выбора к случайной по Мизесу – Чёрчу последовательности даёт либо конечную, либо случайную по Мизесу – Чёрчу последовательность.

◀ В самом деле, последовательное применение двух правил выбора сводится к однократному: если мы сначала предварительно отбираем члены в подпоследовательность, а потом просматриваем члены подпоследовательности и выбираем из них только часть, то в конечном счёте решение определяется предыдущими членами. (А композиция разрешимых правил будет, очевидно, разрешимой.) ►

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

Естественный вопрос: как соотносится случайность по Мизесу – Чёрчу и Мартин-Лёфу? Как мы впоследствии увидим, случайность по Мартин-Лёфу — более сильное требование. Но сначала ещё несколько замечаний по поводу определения Мизеса.

### 9.4. Пример Вилля

Мы уже знаем, что для любого счётного семейства множеств $R_i$ существует последовательность, которая обладает свойством устойчивости частот относительно всех правил выбора $S_{R_i}$ — поскольку множество таких последовательностей имеет меру 1. Но можно дать и более прямую конструкцию такой последовательности, следуя работам А. Вальда [188], Ж. Вилля [180] и Д. Лавлэнда [88].

Для начала рассмотрим случай единственного правила $S_R$, соответствующего множеству $R$. В этом случае легко построить последовательность $\omega$, для которой $S_R(\omega) = 01010101\dots$ (нули и единицы чередуются) и потому последовательность $S_R(\omega)$ сбалансирована. В самом деле, будем строить $\omega$ постепенно (слева направо). Когда правило $S_R$ предлагает выбрать очередной член подпоследовательности, мы смотрим, каким по счёту будет этот член среди выбранных (чётным или нечётным) и в зависимости от этого ставим в $\omega$ нуль или единицу. (Те члены $\omega$, которые не выбраны правилом $S_R$, можно сделать любыми.)

Пусть теперь имеется конечное число множеств $R_1, \dots, R_m$. Мы хотим построить последовательность $\omega$, в которой выполнено свойство устойчивости частот относительно любого из правил $S_{R_i}$. Для каждого члена $\omega_n$ последовательности
ω посмотрим, какие из правил $S_{R_i}$ (при $i = 1, ..., m$) включают его в подпоследовательность, и составим $m$-битовый вектор, содержащий эту информацию. Тем самым любая последовательность $ω$ расслаивается на $2^m$ подпоследовательностей, соответствующих $2^m$ значениям этого битового вектора — мы включаем член $ω_n$ в подпоследовательность, задаваемую $m$-битовым вектором $v$, если те (и только те) правила $S_{R_i}$ выбирают $ω_n$, для которых $i$-й бит $v$ равен 1. Некоторые из этих подпоследовательностей могут быть конечны.

Построим последовательность $ω$, для которой все эти $2^m$ подпоследовательностей будут иметь вид $010101...$ (конечная или бесконечная последовательность, в которой нули и единицы чередуются, начиная с нуля). В самом деле, пусть $ω_0...ω_{n-1}$ уже известны. Как определить $ω_n$? К этому моменту уже ясно, какой битовый вектор соответствует $ω_n$ (какие правила его выберут) и тем самым известно, в какую из $2^m$ подпоследовательностей попадёт $ω_n$. Остаётся посмотреть, каким по счёту (чётным или нечётным) членом этой подпоследовательности будет $ω_n$.

Заметим, что $S_{R_i}(ω)$ будет смесью $2^{m-1}$ подпоследовательностей, а именно, тех, у которых в битовом векторе на $i$-м месте стоит единица. Поэтому $S_{R_i}(ω)$ обладает свойством устойчивости частот (любой начальный отрезок последовательности $S_{R_i}(ω)$ содержит не меньше нулей, чем единиц, а разница в количестве нулей и единиц ограничена числом $2^{m-1}$, поскольку в каждой подпоследовательности разница не больше единицы).

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

Пусть уже построен некоторый начальный отрезок $ω_0...ω_{n-1}$ последовательности $ω$. Тем самым уже известно, каким из множеств $R_i$ он принадлежит (и какие правила $S_{R_i}$ выберут следующий, пока ещё не построенный, член $ω_n$ последовательности). Теперь эта информация является не $m$-битовым вектором, а бесконечной последовательностью битов $u_1u_2...$ (бит $u_i$ равен единице, если правило $S_{R_i}$ выбирает следующий член). Другими словами, у нас имеется путь $u_1u_2...$ в бесконечном двоичном дереве.

Зафиксируем достаточно быстро растущую последовательность $k_0 < k_1 < k_2 < ...$ натуральных чисел. Например, пусть $k_i = 2^{2i}$. На каждом шаге конструкции (то есть для каждого члена последовательности) одна из вершин двоичного дерева будет считаться активной. А именно, двигаясь вдоль пути $u_1u_2...$, найдём первую вершину, которая была активной менее $k_i$ раз, где $i$ — высота вершины в дереве, и объявим активной её. Другими словами, активной вершиной в момент построения $ω_n$ будет кратчайшее слово $x$, для которого

* $i$-й бит $x$ равен единице тогда и только тогда, когда правило $S_{R_i}$ выбирает $ω_n$;

* до сих пор (в процессе построения начального отрезка $ω_0...ω_{n-1}$) вершина $x$ была активна менее $k_{l(x)}$ раз.

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

Как и раньше, мы строим последовательность $\omega$ так, чтобы каждая из этих подпоследовательностей имела вид $010101...$; теперь, правда, последовательность $\omega$ будет смесью бесконечного числа (конечных) последовательностей, и надо аккуратно проверить, что правило выбора $S_{R_i}$ выберет из неё сбалансированную последовательность.

Выбранная правилом $R_i$ подпоследовательность состоит из членов двух типов. Во-первых, она содержит члены, для которых активные вершины короче $i$ (и правило $S_{R_i}$ вообще не учитывалось при определении этих членов). Во-вторых, она содержит члены, которым соответствуют активные вершины, в которых $i$-й бит равен единице. Количество членов первого типа ограничено (не больше $2^0 k_0 + \dots + 2^{i-1} k_{i-1}$) и в дальнейшем мы ими пренебрегаем.

Что касается членов второго типа, то для каждой использованной активной вершины числа нулей и единиц, ей соответствующих, отличаются не более чем на 1. Поэтому, если самая длинная активная вершина, встретившаяся при построении некоторого начального отрезка последовательности $S_{R_i}$, имеет длину $N \ge i$, то разница между числом нулей и единиц (второго типа) в этом начальном отрезке не больше числа активных вершин, использованных при его построении, то есть $O(2^N)$, а длина отрезка не меньше $k_{N-1}$, поскольку предшествующие активные вершины должны быть использованы полностью, прежде чем мы перейдём к более длинной. Остаётся заметить, что $2^N = o(k_{N-1})$.

Итак, мы описали явную конструкцию последовательности, обладающей свойством устойчивости частот для любого счётного семейства правил выбора. Что даёт нам эта конструкция (по сравнению с уже известным нам доказательством существования по соображениям меры)? Например, можно заметить, что поскольку каждая из смешиваемых последовательностей $010101...$ начинается с нуля, то любой начальный отрезок их смеси содержит не меньше нулей, чем единиц. Отсюда получаем такое следствие (пример Вилля [180]):

**Теорема 172.** Существует случайная по Мизесу – Чёрчу последовательность, в любом начальном отрезке которой не меньше нулей, чем единиц.

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

**260** Покажите, что в данном случае достаточно знать, что указанное множество нулевое, и что из этого можно вывести, что оно эффективно нулевое. [Указание. Пусть $p_n$ — вероятность того, что вплоть до длины $n$ начальные отрезки содержат не меньше нулей, чем единиц. Очевидно, последовательность $p_n$ убывает и вычислима, и её предел есть мера указанного множества, поэтому для любого рационального $\varepsilon > 0$ можно дождаться момента, когда $p_n$ станет меньше $\varepsilon$. Можно также использовать понятие случайности по Курцу (с.83).]
**261** Докажите, что указанное множество является эффективно нулевым, не ссылаясь на закон повторного логарифма. [Указание. Для каждого $n$ вероятность того, что в начальном отрезке длины $n$ нулей не меньше, чем единиц, примерно равна $1/2$. Если взять быстро растущие значения $n$, то эти события близки к независимым (отклонение на меньшем отрезке мало по сравнению с ожидаемым отклонением на большем отрезке).]

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

**Теорема 173.** Существует случайная по Мизесу – Чёрчу последовательность $\omega = \omega_0\omega_1\dots$, для которой

$$KS(\omega_0 \dots \omega_{n-1}) = O(\log n).$$

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

Мы можем подряд перебирать все программы, но надо знать, какие из этих программ задают разрешимые множества (остальные программы можно пропустить, заменив каким-либо фиксированным правилом выбора). Такая информация для первых $m$ программ занимает $m$ битов (по одному для каждой программы) и позволяет проводить нашу конструкцию, пока мы не дойдём до активных слов длины $m$. А к этому моменту построенная последовательность будет иметь длину не меньше $k_{m-1} = 2^{2m-2}$. Тем самым объём дополнительной информации — логарифмический (по отношению к длине начального отрезка), что и требовалось. ▶

Отметим ещё раз уже упоминавшееся следствие:

**Теорема 174.** Существует случайная по Мизесу – Чёрчу последовательность, не являющаяся случайной по Мартин-Лёфу.

Возникает естественный вопрос: не следует ли усилить требования к последовательности, предъявляемые определением случайности по Мизесу – Чёрчу? Например, можно разрешить переменные ставки, а также немонотонные правила выбора. В следующих разделах этой главы мы рассмотрим получающиеся при этом определения.

## 9.5. Мартингалы

Говоря о существовании коллективов, мы апеллировали к азартным играм. Но с этой точки зрения, надо признать, рассматриваемая ситуация выглядит довольно странно: клиент приходит в казино, где бросают честную монету, выбирает некоторые бросания и затем «выигрывает» (точнее, опровергает гипотезу о чест-
ности монеты), если результаты выбранных бросаний не имеют предельной частоты $1/2$.

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

Более естественным представляется другой вариант игры, который предложил Вилль. Пусть мы приходим в казино, имея рубль. Перед каждым бросанием мы делим наш капитал на две части, которые ставим на нуль и на единицу. Та часть, где мы не угадали, пропадает, а где угадали — удваивается, и мы продолжаем игру. (Напимер, если мы поделили капитал поровну между 0 и 1, то в любом случае останемся «при своих». Отсюда ясно, что отдельно предусматривать возможность вообще не ставить часть капитала не нужно.)

Наша стратегия в такой игре представляет собой функцию, которая (по начальному отрезку последовательности) говорит, сколько нужно ставить на нуль и сколько на единицу. Технически удобнее говорить о несколько другой функции. А именно, пусть $m(x)$ — капитал, который у нас будет после начального отрезка $x$ при данной стратегии. Такая функция однозначно определяет стратегию: по-sle появления слова $x$ мы ставим $m(x0)/2$ на нуль и $m(x1)/2$ на единицу. При этом

* $m(\Lambda) = 1$ (в начале игры, при пустом слове, наш капитал равен единице);

* $m(x) = (m(x0) + m(x1))/2$ (мы ставим то, что у нас есть к данному моменту).

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

Пусть $\nu$ — произвольная мера на пространстве нулей и единиц. Легко прове-рить, что отношение $\nu(\Omega_x)/\mu(\Omega_x)$ (где $\mu$ — равномерная мера на $\Omega$, а $\Omega_x$ есть множество всех продолжений слова $x$) есть мартингал, и что всякий мартингал соответствует некоторой мере $\nu$.

**262** Убедитесь в этом.

Имеет место следующий почти очевидный факт (называемый иногда неравен-ством Колмогорова):

**Теорема 175.** Пусть фиксирован некоторый мартингал $t$ и число $k$. Рассмотрим те слова, на которых значение мартингала не меньше $k$, и множество всех последовательностей, у которых есть начальный отрезок с таким свойством. Тогда (равномерная) мера этого множества не превосходит $1/k$.
◀ Рассмотрим стратегию, соответствующую мартингалу $m$, и решим, что как только наш капитал достигнет (или превысит) $k$, мы заканчиваем игру и уходим из казино. Ясно, что в силу «честности» игры средний выигрыш при любой стратегии не больше 1, поэтому доля тех случаев, когда он больше или равен $k$, не превосходит $1/k$.

Формально это проще сказать на языке мер. Пусть $m(x)$ равно $\nu(\Omega_x)/\mu(\Omega_x)$ для некоторой меры $\nu$ (а $\mu$ — равномерная мера). Мы рассматриваем те $x$, у которых $\nu$-мера конуса $\Omega_x$ превосходит $\mu$-меру этого же конуса в $k$ или более раз. Из них можно оставить только минимальные (не имеющие начал с тем же свойством), которым соответствуют непересекающиеся конусы. Суммарная $\mu$-мера этих конусов по крайней мере в $k$ раз меньше их суммарной $\nu$-меры, которая не превосходит единицы. ▶

**263** Покажите, что если мартингал $m$ перечислим снизу, то точная верхняя грань его значений на начальных отрезках последовательности, рассматриваемая как функция последовательности, представляет собой ограниченный по вероятности тест в смысле раздела 3.5.

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

**Теорема 176.** Пусть имеется открытое подмножество $U \subset \Omega$ меры $\varepsilon > 0$. Тогда существует мартингал $m$ с таким свойством: у каждой последовательности $\omega \in U$ существует начальный отрезок, на котором $m$ не меньше $1/\varepsilon$.

◀ Рассмотрим меру $\nu$, для которой $\nu(X) = \mu(X \cap U)/\varepsilon$. (Вне множества $U$ — нуль, внутри $U$ — в $(1/\varepsilon)$ раз больше равномерной.) Отношение $m(x) = \nu(\Omega_x)/\mu(\Omega_x)$ и будет искомым мартингалом. В самом деле, если $\omega \in U$, то существует начало $x$ последовательности $\omega$, при котором $\Omega_x \subset U$ и $m(x) = 1/\varepsilon$. ▶

Эту теорему можно объяснить следующим образом. Пусть сотрудники казино — жулики и торгуют, как теперь говорят, «инсайдерской информацией». А именно, они готовы заранее указать открытое множество $U$, в котором окажется будущая последовательность бросаний. Какова «рыночная цена» такой информации вместе с правом после этого начать игру с капиталом 1? Ответ: $1/\mu(U)$. Например, зная результаты первых $N$ бросаний (что соответствует множеству меры $1/2^N$), мы можем $N$ раз подряд выигрывать и в итоге получить $2^N$. Доказанная теорема говорит, что это верно и для более сложно устроенных множеств $U$. Например, если известно, что некоторая последовательность невозможна («в нашем казино никогда не бывает $N$ нулей подряд с начала игры»), то и это позволит гарантированно выиграть (правда, совсем немного, увеличив начальный капитал 1 до $2^N/(2^N - 1)$).

Легко понять, какова соответствующая стратегия игрока (из доказательства теоремы). Если гарантированное множество $U$ на первом ходу делится в пропорции $a_0 : a_1$ (между последовательностями, начинающимися на нуль и на единицу), то мы должны ставить наш капитал в этой самой пропорции. (Напимер, если все элементы $U$ начинаются на 0, то весь капитал нужно ставить на нуль.) Тогда
отношение

текущий капитал

доля U среди продолжений текущей позиции

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

Аналогичные утверждения о связи мартингалов и мер можно сделать и в «пре-
дельном» случае. Будем говорить, что мартингал $t$ выигрывает на последователь-
ности $ω$, если значения $t$ на начальных отрезках последовательности $ω$ не огра-
ничены. Следующая теорема Вилля была для него одной из главных мотивировок
понятия мартингала (которое он и ввёл):

**Теорема 177.** (а) Пусть $t$ — произвольный мартингал. Тогда множество тех последовательностей $ω \in Ω$, на которых он выигрывает, имеет меру нуль.

(б) Пусть $X$ — произвольное множество меры нуль. Тогда существует мар-
тингал $t$, который выигрывает на всех последовательностях из $X$.

◀ (а) Множество $U_k$ тех последовательностей, на начальных отрезках которых мартингал достигает значений $k$ или больше, имеет меру не более $1/k$ (и является открытым); все последовательности, на которых $t$ выигрывает, принадлежат этому множеству.

(б) Для каждого $k$ рассмотрим открытое множество $U_k$, имеющее меру не боль-
ше $1/k$, содержащее $X$, и соответствующий мартингал $t_k$, который гарантирует
выигрыш не меньше $k$ на всех элементах $U_k$ (и тем самым на всех элементах $X$).
Теперь из всех этих мартингалов нужно собрать один. Заметим, что взвешенная
сумма мартингалов есть мартингал (мы можем разделить наш капитал на конеч-
ное или счётное число частей, и с каждой частью играть отдельно, применяя свой
мартингал). Будем использовать мартингалы $t_{4^n}$ с начальным капиталом $2^{-n}$ па-
раллельно при всех $n$ (разложив начальный капитал 1 в сумму ряда $\Sigma 2^{-n}$); тогда
для последовательностей из $U_{4^n}$ (и потому для всех последовательностей из $X$)
гарантирован выигрыш $4^n \cdot 2^{-n} = 2^n$. Значит, общий выигрыш на любой последо-
вательности из $X$ не ограничен. ►

Доказательство этой теоремы сильно напоминает доказательство критерия слу-
чайности (теорема 90, с. 167), который можно рассматривать как эффективный
вариант только что доказанной теоремы.

По существу мы доказали более сильное утверждение. Будем говорить, что мар-
тингал $t$ сильно выигрывает на последовательности $ω$, если его значения на на-
чальных отрезках последовательности $ω$ стремятся к бесконечности. Построенный
в теореме 177 мартингал, как легко видеть, сильно выигрывает на всех элемен-
тах $X$. (В самом деле, мартингал из доказательства теоремы 176 равен $1/ε$ на всех
достаточно длинных начальных отрезках.)

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

**Теорема 178.** Для всякого мартингала $m$ существует мартингал $m'$, который сильно выигрывает у всех последовательностей, у которых выигрывает мартингал $m$.

◀ Мартингал $m'$ должен действовать как запасливый игрок: достигнув выигрыша 2 (по $m$-стратегии), он откладывает половину «на чёрный день» (это означает, что эту часть выигрыша игрок ставит поровну на нуль и единицу), а с другой половиной поступает как $m$ (но только все суммы вдвое меньше). Когда будет достигнут выигрыш 4 (что соответствует выигрышу 8 для $m$), откладываем половину (то есть 2) на чёрный день, а остаток снова пускаем в игру в соответствии с $m$, и так далее.

Можно привести и другое рассуждение (которое имеет то преимущество, что годится для перечислимых снизу мартингалов). Для каждого мартингала $m$ и числа $c > 0$ рассмотрим мартингал $m_c$, который играет как $m$, пока и если капитал не достигнет $c$, после чего игра прекращается. Ясно, что $m_c$ в пределе достигает $c$ на всех последовательностях, где $m$ хотя бы раз достиг $c$. Остаётся сложить $m_c$ с весами, скажем, взяв сумму $m_4^k$ с весами $2^{-k}$. ▶

Более аккуратный выбор весов позволяет доказать общее утверждение [148, 35]: пусть $f: [1, +\infty) \to [0, +\infty)$ — неубывающая непрерывная функция, причём интеграл $\int_1^\infty f(t)/t^2 dt$ не превосходит 1. Тогда для всякого мартингала $m$ существует мартингал $m'$ с таким свойством: если на какой-то последовательности мартингал $m$ хотя бы раз был больше $c$, то с этого момента мартингал $m'$ на той же последовательности будет больше $f(c)$. (Это утверждение точное: оценку на $f$ нельзя ослабить.)

До сих пор мы предполагали, что вероятности выпадения нуля и единицы (декларируемые казино) равны, и потому ставки и на нуль, и на единицу удваиваются. Но это не обязательно. Пусть, например, вероятность появления нуля считается равной $1/3$, а вероятность единицы, соответственно, $2/3$. Тогда ставка на нуль должна утраиваться, а на единицу — увеличиваться всего лишь в полтора раза. Соответственно и определение мартингала изменится: $m(x)$ (капитал после $x$) должен быть равен сумме его части, поставленной на нуль (то есть $m(x0)/3$ и его части, поставленной на единицу (то есть $2m(x1)/3$):

$$m(x) = \frac{1}{3}m(x0) + \frac{2}{3}m(x1).$$

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

Дадим формальное определение. Пусть $\pi$ — произвольное распределение вероятностей на $\Omega$ (декларируемое казино распределение вероятностей для монеты). Соответствующую функцию на словах будем также обозначать буквой $\pi$, положив $\pi(x) = \pi(\Omega_x)$.

Функция $m(x)$, определённая на двоичных словах и принимающая неотрицательные действительные значения, называется мартингалом относительно $\pi$ (с
единичным начальным капиталом — в дальнейшем это особо не оговаривается), если $m(\Lambda) = 1$ и

$$m(x)\pi(x) = m(x0)\pi(x0) + m(x1)\pi(x1)$$

при всех х. (Это определение соответствует предыдущему: поделив на $\pi(x)$, мы по-лучим в правой части условные вероятности $\pi(x0)/\pi(x)$ и $\pi(x1)/\pi(x)$ появления нуля и единицы после х.)

Другими словами, функция $m(x)\pi(x)$ задаёт меру, так что мартингал относительно $\pi$ (π-мартингал) — это отношение некоторой другой меры к $\pi$.

Далее всё аналогично случаю равномерной меры. А именно:

(1) вероятность того, что π-мартингал достигнет $k$ на начальном отрезке последовательности $\omega$, распределённой по мере $\pi$, не превосходит $1/k$;

(2) для всякого открытого множества $U$ существует мартингал, который достигает значения $1/\pi(U)$ на всех последовательностях из $U$;

(3) множество $X$ имеет π-меру нуль тогда и только тогда, когда существует π-мартингал, который выигрывает (вариант: сильно выигрывает) у любой последовательности из $X$.

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

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

◄ Согласно неравенству Колмогорова мартингал ограничен с вероятностью 1. Остаётся доказать, что для любых рациональных $p, q$ с $0 < p < q$ множество тех последовательностей, на которых мартингал бесконечное число раз колеблется, переходя промежуток $[p, q]$ в обе стороны, имеет меру нуль. Это можно сделать, указав другой мартингал, который неограничен на всех таких последовательностях. А именно, будем следовать стратегии "buy low, sell high", применяя стратегию исходного мартингала с того момента, когда он имел значение меньше $p$, до того момента, когда он приобрёл значение больше $q$ (и сохраняя капитал в промежутках). На каждом таком участке мы нарашиваем капитал в ($q/p$) раз, а участков бесконечно много по предположению. ►

Эта теорема может быть использована для определения условной вероятности. Пусть дана некоторая мера $\mu$ на произведении $\Omega \times \Omega$. Тогда можно рассмотреть проекцию $\mu_1$ меры $\mu$ на первую координату. Кроме того, возникает желание определить условную вероятность по второй координате при условии «первая координата равна $\alpha$», где $\alpha$ — некоторая последовательность. Обычное определение условной вероятности тут не годится, поскольку само по себе событие «первая координата равна $\alpha$» имеет меру нуль. Однако можно применить теорему Дуба, чтобы определить условную вероятность для почти всех $\alpha$. Пусть $A$ — произвольное событие по второй координате. Тогда можно определить условную вероятность $A$ при условии «первая координата начинается на $a_0...a_{k-1}$». Заметим, что при фиксированном $A$ и переменном начале мы получаем $\mu_1$-мартингал (после нормировки), и по теореме Дуба предел существует почти всегда. (Возможен случай, когда некоторое
начало имеет вероятность нуль и условная вероятность не определена. Но тогда последовательности, имеющие это начало, и так образуют нулевое множество.)

В заключение отметим следующее почти очевидное обстоятельство:

**Теорема 180.** Для всякого мартингала существует последовательность, у которой он не выигрывает (и даже не превосходит единицы на всех её начальных отрезках).

◀ В самом деле, из определения следует, что одно из чисел $m(x0)$ и $m(x1)$ не больше $m(x)$, поэтому любое слово можно продолжить на один бит, не увеличивая мартингал. ▶

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

## 9.6. Отступление: мартингалы в теории вероятностей

Теорему 177 можно интерпретировать так:

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

(б) этот метод можно применить к любому нулевому множеству (найдя соответствующий мартингал).

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

В качестве иллюстрации изложим в таком стиле доказательство усиленного закона больших чисел. Рассмотрим бернуллиево распределение вероятностей $B_p$, в котором испытания независимы и вероятность появления единицы равна $p$.

Для данного $q > p$ докажем, что вероятность события «частота единиц в последовательности бесконечно много раз превосходит $q$» равна нулю. (Для $q < p$ и для события «частота меньше $q$» рассуждение симметрично.) Для этого рассмотрим мартингал (относительно меры $B_p$), равный отношению мер $B_q/B_p$. Другими словами, рассмотрим мартингал, который на последовательности $z$ длины $n$ с частотой единиц $r$ (из $nr$ единиц и $n(1-r)$ нулей) принимает значение

$$ \frac{q^{nr}(1-q)^{n(1-r)}}{p^{nr}(1-p)^{n(1-r)}}, $$

а его логарифм равен

$$ n[(r \log q + (1-r) \log(1-q)) - (r \log p + (1-r) \log(1-p))]. $$

Поскольку $q > p$, то это выражение является возрастающей (линейной) функцией от $r$: коэффициент при $r$ равен $\log[q/p] + \log[(1-p)/(1-q)]$, и оба слагаемых положительны. Значит, при $r > q$ (интересующий нас случай) замена $r$ на $q$ лишь
уменьшит это выражение и логарифм мартингала не меньше

$$n[(q \log q + (1 - q) \log(1 - q)) - (q \log p + (1 - q) \log(1 - p))]$$

Согласно неравенству Гиббса (с. 241) коэффициент в квадратных скобках, то есть расстояние Кульбака – Лейблера между распределениями $(q, 1-q)$ и $(p, 1-p)$, положителен. Таким образом, построенный мартингал неограничен на интересующих нас последовательностях (где частота бесконечно много раз превосходит $q$).

Это доказательство усиленного закона больших чисел не совсем соответствует описанной схеме, так как для разных $q$ получаются свои мартингалы. Каждый из них используется для оценки меры своего множества, а лишь затем мы замечаем, что объединение счётного числа нулевых множеств нулевое.

Можно действовать и в другом порядке: взять счётное семейство $q_i$, соответствующие мартингалы, а затем сложить эти мартингалы с положительными весами. Если хотя бы один из мартингалов неограничен, то и сумма будет неограниченной.

Примерно то же самое мы уже делали в разделе 3.2 (задача 67, с. 69), только говорили о конечных последовательностях и не употребляли слова «мартингал», ограничиваясь упоминаниями двух мер. (По существу те же рассуждения встретятся и в дальнейшем, в разделе 9.13.)

Во-вторых, можно смотреть на мартингалы с более философской точки зрения. Что значит доказать некоторую теорему теории вероятностей с помощью мартингала? Это значит предъявить некоторое свойство последовательностей $L$ (скажем, закон больших чисел) и некоторый мартингал $m$ и доказать, что для любой последовательности $\omega$ верно (хотя бы) одно из двух:

* последовательность $\omega$ обладает свойством $L$;

* мартингал $m$ выигрывает на $\omega$.

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

> случайность последовательности нулей и единиц — это не свойство последовательности как таковой, а тип гарантии, с которой она продается.

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

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

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

Подробно такой подход к теории вероятностей обсуждается в книге Вовка и Шейфера [149].

## 9.7. Перечислимые мартингалы

Доказанные нами результаты о мартингалах имеют естественные эффективные аналоги. Нулевые множества, как мы видели, соответствуют мартингалам. Поэтому можно ожидать, что эффективно нулевые множества соответствуют некоторому классу «эффективных» мартингалов, и так оно и есть.

Мы будем рассматривать вычислимые меры и перечислимые снизу мартингалы относительно этих мер. Фиксируем некоторую вычислимую меру и будем рассматривать мартингалы (а также нулевые множества и случайные по Мартин-Лёфу последовательности) относительно этой меры, если не оговорено иное. При этом мы будем разрешать начальному капиталу (значению мартингала на пустом слове) быть произвольным числом, не превосходящим единицы. (Определение перечислимости снизу было дано в разделе 4.1; функция $m$ перечислима снизу, если множество пар $\langle r, x \rangle$, для которых рациональное число $r$ меньше $m(x)$, перечислимо.)

**264** Показите, что перечислимый снизу мартингал $m$, для которого $m(\Lambda) = 1$, вычислим.

Вычислимых мартингалов нам недостаточно, поэтому мы и отказались от требованиям $m(\Lambda) = 1$. Теперь можно сформулировать эффективный вариант теоремы Вилля (теорема 177), предложенный Шнорром [143]:

**Теорема 181.** (а) Пусть $m$ — произвольный перечислимый снизу мартингал. Тогда множество тех последовательностей $\omega \in \Omega$, на которых он выигрывает, является эффективно нулевым.
(б) Пусть Х — произвольное эффективно нулевое множество. Тогда существует перечислимый снизу мартингал t, который выигрывает на всех последовательностях из Х.

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

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

Остаётся (как в доказательстве теоремы 177) сложить построенные для разных чисел $k$ мартингалы с надлежащими (вычислимыми) коэффициентами; это не нарушает перечислимость снизу. ▶

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

Во вторых, можно рассматривать не только перечислимые снизу мартингалы, но и перечислимые снизу супермартингалы, или, как иногда говорят, полумартингалы. Они соответствуют играм, в которых игрок может отказываться от части выигранных денег. То есть, мы разрешаем неравенство

$$m(x) \geq (m(x_0) + m(x_1))/2$$

(для равномерной меры) или

$$m(x)\pi(x) \geq m(x_0)\pi(x_0) + m(x_1)\pi(x_1)$$

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

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

$$m(x) = a(x)/\pi(x),$$
где $a$ — максимальная перечислимая полумера на дереве (см. раздел 5.2), а $\pi(x)$ — вероятность множества $\Omega_x$ по мере $\pi$. Максимальность понимается с точностью до мультиликативной константы.

Отсюда получается новое доказательство теоремы Левина – Шнорра для приорной вероятности (теорема 91, с. 169): последовательность $\omega$ случайна по вычислимой мере $\pi$ тогда и только тогда, когда на её начальных отрезках отношение $a(x)/\pi(x)$ ограничено.

## 9.8. Вычислимые мартингалы

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

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

Будем называть последовательность $\omega$ случайной по мере $\pi$ относительно вычислимых мартингалов, если никакой вычислимый $\pi$-мартингал на ней не выигрывает — другими словами, если любой вычислимый $\pi$-мартингал ограничен на её начальных отрезках. В англоязычной литературе для таких последовательностей употребляется термин computably random.

**265** (а) Показайте, что это определение не изменится, если ограничиться мартингалами, отделёнными от нуля (скажем, потребовав, чтобы все значения были не меньше $1/2$); (б) если $\pi(\Omega_x)$ — рациональные числа, вычислимые по $x$ (как конечные объекты), то можно ограничиться мартингалами, принимающими лишь рациональные значения (и вычислимыми в том же смысле). [Указание. (а) Можно взять среднее арифметическое любого мартингала и постоянного мартингала 1. (б) Если мартингал отделён от нуля, то можно приближать рациональными числами пропорцию, в которой делится капитал, с быстро возрастающей точностью.]

Как связан этот вариант понятия случайности с другими?

Первые два утверждения следующей теоремы относятся к общему случаю случайности по вычислимой мере $\pi$; два других — к случайности по равномерной мере (и легко обобщаются на бернуллиеву меру $B_p$ с вычислимой вероятностью успеха $p$).

**Теорема 182.** (а) Всякая случайная в смысле Мартин-Лёфа последовательность случайна относительно вычислимых мартингалов.

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

(в) Всякая случайная относительно вычислимых мартингалов последовательность случайна по Мизесу – Чёрчу.
(г) Не всякая случайная по Мизесу – Чёрчу последовательность случайна относительно вычислимых мартингалов.

◀ (а) Случайность по Мартин-Лёфу гарантирует, что даже и перечислимые снизу мартингалы не выигрывают (теорема 181).

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

Если мартингал вычислим, то можно найти вычислимую последовательность, на которой он ограничен. Это немного сложнее: мы не можем сравнить значения мартингала на двух продолжениях х0 и х1 слова х, так как знаем эти значения лишь с некоторой точностью. Но это и не нужно, достаточно на $n$-м шаге выбрать такое продолжение, где мартингал растёт менее чем на $1/2^n$ (а это можно сделать, находя всё более точные приближения и ожидая приближения, которое это гарантирует).

(Кстати, отсюда немедленно следует, что среди вычислимых мартингалов не существует максимального. Именно поэтому переход к перечислимым снизу мартингалам или супермартингалам с существен.)

Следующий шаг: пусть даны два вычислимых мартингала; как найти вычисливую последовательность, на которой они оба ограничены? Для этого достаточно взять взвешенную сумму этих мартингалов, в которую они оба входят с положительным коэффициентом (например, полусумму). Получится снова вычислимый мартингал. Если хотя бы один из двух мартингалов не ограничен на некоторой последовательности $\omega$, то и их полусумма не ограничена на $\omega$ (напомним, что мартингалы всегда неотрицательны), поэтому можно применить предыдущее утверждение.

То же рассуждение годится, если есть вычислимая последовательность вычислимых мартингалов (точнее, программ, эти мартингалы задающих). Тогда их можно сложить, взяв $i$-й мартингал с весом $2^{-i}$.

Все вычислимые мартингалы нельзя расположить в вычислимую последовательность (это, кстати, следует из только что нами доказанного: ведь тогда можно было бы найти вычислимую последовательность, на которой все вычислимые мартингалы ограничены). Поэтому построение последовательности $\omega$, на которой все вычисляемые мартингалы ограничены, не может быть алгоритмическим. Дополнительная информация, которая нам нужна — это сведения о том, какие из программ задают мартингалы, а какие нет, то есть по биту на программу. Чтобы получить последовательность с логарифмической сложностью, мы должны эти биты использовать очень понемногу, включая в рассмотрение $i$-ю программу, когда последовательность будет уже достаточно длинной (экспоненциальной от $i$ длины или ещё длиннее).

Опишем этот процесс подробнее. В каждый момент мы имеем некоторое слово $x$, а также некоторую линейную комбинацию с положительными коэффициентами, $m_1(x) + \varepsilon_2 m_2(x) + \dots + \varepsilon_k m_k(x)$, где $m_i$ — мартингал, задаваемый $i$-й программой (или его заменитель — скажем, тождественный нуль, если дополнительная информация об $i$-й программе говорит, что она не задаёт мартингал). При этом
мы следим, чтобы это выражение (для текущего слова х) было строго меньше 2.
(Вначале, когда у нас только $m_1$ и слово х пусто, это выражение равно 1.)

Как мы видели, слово х всегда можно продолжить на один бит так, чтобы это выражение оставалось меньше двух (и такое продолжение можно алгоритмически найти, если мы знаем программы для мартингалов). Также время от времени мы будем добавлять новый член $\varepsilon_k m_k(x)$ к сумме, подбирая $\varepsilon_k$ настолько малым, чтобы сумма осталась меньше 2 (чем ближе текущая сумма к 2 и чем больше значение $m_k(x)$ для текущего слова х, тем меньше берётся $\varepsilon_k$).

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

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

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

Более того, если $R$ — некоторое множество слов, а $S_R$ — соответствующее правило выбора, то легко построить мартингал, который выигрывает на любой последовательности $\omega$, для которой подпоследовательность $S_R(\omega)$ не сбалансирована. В самом деле, нужно играть лишь с теми членами последовательности, которые отбираются правилом $S_R$ (а в остальных случаях сохранять значение мартингала неизменным, пропуская ход).

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

Поэтому для всякой неслучайной по Мизесу – Чёрчу последовательности существует вычислимый мартингал, который на ней не ограничен.

(г) Рассмотрим (для случая равномерной меры) случайную по Мизесу – Чёрчу последовательность, у которой любой начальный отрезок содержит не меньше нулей, чем единиц (теорема 172). Пусть $p_n$ — вероятность того, что все начальные отрезки длины не более $n$ содержат не меньше нулей, чем единиц. Как мы уже обсуждали (задачи 260, 261), последовательность $p_n$ вычислима, убывает и стремится к нулю. Для каждого $n$ можно эффективно указать мартингал $M_n$, который выигрывает $1/p_n$ у любой последовательности, начальные отрезки (вплоть до длины $n$) которой содержат не меньше нулей, чем единиц. Взяв теперь взвешенную сумму некоторых $M_n$ (выбранных так, чтобы выигрыши росли быстрее, чем убывали коэффициенты), получим вычислимый мартингал, который не ограничен на любой последовательности, у которой во всех начальных отрезках не меньше нулей, чем единиц.

Это же рассуждение можно после некоторых модификаций использовать для произвольной бернуллиевой меры (одновременно модифицировав конструкцию те-
оремы 172). Можно также применить конструкцию с двумя мерами (см. ниже раздел 9.13). ►

**266** Укажите мартингал, описанный в доказательстве п. (г), явно. [Указание. Пусть мы пришли в CASINO и нам говорят, что в любом начальном отрезке игры не меньше орлов, чем решек. Тогда мы можем ставить на орла фиксированную сумму, зная, что не разоримся. Если разница между орлами и решками стремится к бесконечности, это и будет выигрышной стратегий. Если это не так, найдётся такой момент *t* и такое число *n*, что с момента *t* разница между орлами и решками не меньше *n* и бесконечно много раз равна *n* (нижний предел). Тогда после *t*, когда разница равна *n*, мы можем смело ставить на орла, не рискуя проиграть. Получаем один мартингал для первого случая и семейство мартингалов для второго с параметрами *n*, *t*. Остаётся соединить их в один мартингал.]

Заметим, что из утверждений (б) и (в) вытекает, что существуют случайные по Мизесу – Чёрчу последовательности с логарифмической сложностью начальных отрезков. Тем самым мы получили другое доказательство теоремы 173 (следуя работе [102]).

**267** Докажите следующее усиление п. (б): если $f$ — произвольная неубывающая неограниченная вычислимая функция, то существует случайная относительно вычислимых мартингалов последовательность $\omega$, для которой $\text{KS}(\omega_0 \dots \omega_{n-1} | n) \le \frac{\|f(n) + O(1)\|}{2}$. [Указание: новый мартингал, обходящийся в один бит дополнительной информации, мы добавляем, когда увеличившееся значение функции $f$ это позволяет.]

Более того, можно построить одну последовательность $\omega$, которая случайна относительно вычислимых мартингалов и для которой указанное неравенство выполнено для любой неубывающей неограниченной вычислимой функции $f$ [102].

**268** Покажите, что для вычислимой меры $P$ на пространстве $\Omega \times \Omega$ и для любой последовательности $\omega$, случайной относительно вычислимых мартингалов по первой проекции меры $P$, можно корректно определить условную вероятность, используя вычислимый вариант теоремы Дуба (с. 307).

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

## 9.9. Мартингалы и случайность по Шнорру

Понятие случайности относительно вычислимых мартингалов тесно связано с понятием случайности по Шнорру (см. раздел 3.4). Оба этих понятия были введены и изучены в книге Шнорра [143]. Там же была доказана и следующая теорема.

**Теорема 183.** Пусть дана некоторая вычислимая мера $\pi$, относительно которой все интервалы $\Omega_x$ имеют положительную меру. Последовательность $\omega$
не случайна по Шнорру относительно $\pi$ тогда и только тогда, когда существует вычислимый $\pi$-мартингал $m$ и вычислимая неубывающая неограниченная функция $g: \mathbb{N} \to \mathbb{N}$ с таким свойством:

$$m(\omega_0\omega_1\dots\omega_{n-1}) \ge g(n)$$

для бесконечно многих $n$.

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

◀ Пусть последовательность $\omega$ не случайна по Шнорру. Тогда, как мы видели в разделе 3.4 (задача 90, с. 83), существует последовательность слов $x_0, x_1, x_2, \dots$, для которых ряд $\sum \pi(x_i)$ вычислимо сходится, причём бесконечно многие среди $x_i$ являются началами $\omega$.

Разобьём члены ряда

$$\pi(x_0) + \pi(x_1) + \pi(x_2) + \dots + \pi(x_i) + \dots$$

на группы из конечного числа подряд идущих членов. Сделаем это так, чтобы сумма членов $k$-й группы была не больше $4^{-k}$ (отбросим начальный отрезок ряда, если это необходимо). Поскольку ряд вычислимо сходится, это можно сделать алгоритмически. Можно считать дополнительно, что слова разных групп разделены по длинеам: есть вычислимая последовательность чисел $n_0 < n_1 < n_2 < \dots$, и слова $k$-й группы имеют длину в интервале $[n_k, n_{k+1})$. В самом деле, любое слово в покрытии Соловея можно заменить на набор всех его продолжений большей длины, и мы можем по очереди обрабатывать слова разных групп, используя длины больше длины предыдущей группы. Суммы по группам от этого не изменятся.

Рассмотрим отдельно слова $k$-й группы. Они покрывают множество меры меньше $4^{-k}$ и можно построить мартингал $m_k$, который достигает на них значения $4^k$. Теперь смешаем эти мартингалы и получим мартингал $m = \sum 2^{-k}m_k$. Этот мартингал достигает значения $2^k$ на словах $k$-й группы. Остаётся положить $g(n) = 2^k$ для всех $n$ в интервале $[n_k, n_{k+1})$ и заметить, что в бесконечно многих групах встречаются начала последовательности $\omega$.

Напротив, пусть есть вычислимый мартингал $m$ и неубывающая неограниченная вычислимая функция $g$. Нам надо покрыть последовательность $\omega$, про которую известно лишь, что для бесконечно многих $n$ значение $m(\omega_0 \dots \omega_{n-1})$ не меньше $g(n)$. При этом мера покрытия должна быть не больше некоторого $\varepsilon > 0$. Как это сделать?

Прежде всего, увеличим функцию $g$ на некотором начальном отрезке и будем считать, что она везде не меньше $1/\varepsilon + 1$. Далее будем рассматривать все слова в порядке возрастания длины и сравнивать значения $m$ и $g$ на этих словах. Будем отбирать те слова, где $m$ больше $g$. (Точнее говоря, поскольку $m$ нам известно лишь с некоторой точностью, будем отбирать с некоторым запасом: при этом для всех отобранных слов $m > g - 1$, и все слова с $m > g$ отобраны.)
По построению интервалы, соответствующие отобранным словам, заведомо по-
крывают последовательность $\omega$. Кроме того, поскольку в них мартингал больше
$1/\varepsilon$, их мера не превосходит $\varepsilon$. Наконец, сумма их мер вычислима: чтобы вычи-
слить её с любой точностью $\delta > 0$, надо подождать момента, когда функция $g$
станет больше $1/\delta + 1$: все следующие (более длинные) интервалы изменят сумму
мер не более чем на $\delta$. ►

Этот же метод можно использовать и для доказательства такого критерия слу-
чайности по Шнорру [6]:

**269** Докажите, что последовательность $\omega$ случайна по Шнорру относительно вычислимой меры $\mu$ тогда и только тогда, когда для любой вычислимой верхней оценки $K$ для префиксной сложности $KP$ и для любой монотонной вычислимой неограниченной функции $h$ выполнено неравенство

$$
K((\omega)_n) \geq -\log_2 \mu(\Omega_{(\omega)_n}) - h(n) - O(1)
$$

при всех $n$ (константа в $O(1)$ не зависит от $n$).

[Указание. Для вычислимых *K* и *h* покрытие из доказательства теоремы Леви-
на – Шнорра имеет вычислимую меру. Рассуждение в другую сторону аналогично
доказательству предыдущей теоремы: покрытие разобьём на конечные группы слов
одинаковой длины µ-меры меньше 4⁻ⁿ, увеличим суммарную меру слов из n-й
группы пропорционально до 2⁻ⁿ и по лемме о шторах получим вычислимую оцен-
ку для префиксной сложности; используя то, что в n-й группе все слова одинаковой
длины, можно получить и функцию h.]

Этот результат можно использовать, чтобы доказать существование случайных
по Шнорру (относительно равномерной меры) последовательностей, не случай-
ных по Мизесу – Чёрчу [6]. В самом деле, он показывает, что если KP((ω)ₙ) ≥
≥ n – h(n) – O(1) для некоторой неограниченной монотонной функции h, ко-
торая стремится к бесконечности медленнее любой вычислимой неограниченной
функции, то последовательность ω случайна по Шнорру. Такие функции h суше-
ствуют (диагональный аргумент), и остаётся выбрать любую из них и построить
последовательность с нужной оценкой, но не случайную по Мизесу – Чёрчу.

Как это делается? Можно взять случайную последовательность $\alpha$ и разбавить её редкими нулями — потом эти нули и образуют нулевую подпоследовательность, которая будет выбрана по Мизесу – Чёрчу. Нужно, чтобы (1) места этих нулей были вычислимы или хотя бы алгоритмически обнаруживаемы при чтении последовательности слева направо; (2) они были бы очень редкими, чтобы не сильно уменьшить сложность. Требование (2) означает, что функция $F: n \mapsto (\text{позиция } n\text{-го нуля})$ должна расти быстрее всех вычислимых функций. Ключевая идея: по теореме Кучеры – Гача можно взять любую функцию $F$ и затем $\alpha$, относительно которой $F$ вычислима. Правда, нам нужно вычислять $F(n)$, имея не всю последовательность $\alpha$, а только начальный отрезок — но это не страшно, если $F(n)$ вычислится позже, то мы просто используем вместо $F(n)$ большее значение, а именно, то место, где она уже определилась. При оценке сложности мы используем тот факт, что нули на предсказуемых позициях можно добавлять или вычёркивать, не меняя префиксной сложности.
**270** Проведите это рассуждение подробно и докажите, что существуют случайные по Шнорру, но не случайные по Мизесу – Чёрчу последовательности.

(Они не будут случайными и относительно вычислимых мартингалов, так что случайность по Шнорру строго слабее случайности относительно вычислимых мартингалов.)

**271** Докажите, что последовательность не случайна по Курцу (см. раздел 3.4, с. 83) тогда и только тогда, когда существует вычислимый мартингал, который на этой последовательности ограничен снизу некоторой неубывающей неограниченной вычислимой функцией.

[Указание. Множества малой меры, покрывающие $\omega$ и состоящие из конечно-го числа интервалов, можно преобразовать в мартингалы, при этом известно, до какого момента срабатывает каждый из них, и можно преобразовать это в вычисли-мую оценку для суммарного мартингала. Напротив, зная мартингал и оценку для него на начальных отрезках последовательности $\omega$, можно взять конечный набор интервалов, где мартингал больше заданного числа, и гарантированно покрыть $\omega$.]

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

## 9.10. Мартингалы и эффективная размерность

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

Начнём с классического варианта (без алгоритмов):

**Теорема 184.** Множество $A \subset \Omega$ является $\alpha$-нулевым тогда и только тогда, когда существует мартингал $m$ с таким свойством: для любого $\omega \in A$ отношение

$$ \frac{m(x)}{2^{(1-\alpha)l(x)}} $$

не ограничено на начальных отрезках $\omega$.

(При $\alpha = 1$ получается теорема 177.)

Немного более наглядная формулировка теоремы 184 такова: пусть игрок обла-гается налогом, в результате которого его капитал на каждом шаге (между двумя ставками) уменьшается в $2^{1-\alpha}$ раз, то есть умножается на $2^{\alpha-1}$. Тогда капитал игрока после $x$ будет не мартингалом, а функцией $m$, для которой

$$ 2^{\alpha-1} m(x) = \frac{m(x0)}{2} + \frac{m(x1)}{2}, $$
то есть

$$2^{\alpha}m(x) = m(x0) + m(x1).$$

Такие функции (следуя работе [92]) называют “α-gales”, что мы по-русски передаём как α-мартингалы. Они тоже соответствуют мерам: α-мартингал есть функция вида

$$p(x)2^{\alpha l(x)},$$

где $p(x)$ — мера интервала $\Omega_x$ относительно некоторого распределения. Аналогично можно определять и α-супермартингалы, где допускаются дополнительные потери игрока (помимо налога):

$$2^{\alpha}m(x) \geq m(x0) + m(x1).$$

Теперь можно пересказать утверждение теоремы 184 так: множество тех последовательностей, на начальных отрезках который данный α-мартингал неограничен, является α-нулевым, и всякое α-нулевое множество содержится в множестве такого вида.

◀ Доказательство по существу повторяет рассуждение из теоремы 177. Пусть $m$ — произвольный α-мартингал. Доказем, что множество тех последовательностей, для которых он неограничен (на начальных отрезках), имеет α-меру нуль. Для этого достаточно показать, что слова, где $m$ достигает значения $k$ (или больше) впервые, имеют сумму α-степеней мер не больше $1/k$. Если записать α-мартингал $m(x)$ как $p(x)2^{\alpha l(x)}$, то для выбранных слов $x$ имеем $p(x) \geq k2^{-\alpha l(x)}$. Все выбранные слова несравнимы (одно не является началом другого), поэтому сумма $p$-мер не больше единицы, поэтому сумма величин $2^{-\alpha l(x)}$ по всем выбранным словам $x$ (= сумма α-мер соответствующих интервалов) не превосходит $1/k$.

Обратно, пусть дано некоторое множество α-меры нуль. Нам надо построить α-мартингал, который неограничен на всех его элементах. Возьмём покрытие интервалами с суммой α-мер меньше $1/k$, и построим α-мартингал $m_k$, который достигает значения $k$ на этих элементах. (Затем можно сложить $m_{4k}$ с коэффициентами $2^{-k}$, сумма α-мартингалов есть также α-мартингал.) Как построить $m_k$? Для данного слова $x$ можно построить α-мартингал, который равен 1 на $x$ и равен 0 на всех словах той же длины $l(x)$, продолжив его на более короткие слова (однозначно) и на более длинные (любым способом). На пустом слове значение этого α-мартингала будет $2^{-\alpha l(x)}$, то есть как раз α-мера соответствующего интервала. Значит, сумма этих α-мартингалов для всех $x$ будет не больше $1/k$, и умножив её на $k$, получим искомый α-мартингал. ▶

Теперь попытаемся сформулировать эффективный вариант теоремы. Пусть $\alpha$ — вычислимое действительное число из $(0, 1]$. Естественно определяются понятие перечислимого снизу α-мартингала и α-супермартингала. Как и в случае $\alpha = 1$, значение перечислимого снизу мартингала на пустом слове не обязательно равно единице — это произвольное (перечислимое снизу) число, не превосходящее единицы.

Можно предположить, что α-мартингалам (и супермартингалам) соответствуют введённые в разделе 5.8 эффективно α-нулевые множества и что доказательство
этого факта повторяет только что приведённое доказательство теоремы 184. В одну сторону это действительно так:

**Теорема 185.** Пусть $\alpha \in (0, 1]$ — вычислимое действительное число и множество $A \subset \Omega$ является эффективно $\alpha$-нулевым. Тогда существует перечислимый снизу $\alpha$-мартингал, который неограничен на начальных отрезках любой последовательности $\omega \in A$.

◀ В самом деле, приведённая выше конструкция даёт перечислимые снизу $\alpha$-мартингалы $m_k$, и смешивание сохраняет перечислимость снизу. ►

В другую сторону мы встречаемся с трудностью. Пусть $m$ — перечислимый снизу $\alpha$-мартингал. Рассмотрим множество тех слов, на которых $m(x) > k$. Это множество перечислимо. Кроме того, сумма $\alpha$-мер его минимальных элементов не превосходит $1/k$. Но множество минимальных элементов может быть неперечислимым, а если оставить все элементы (не только минимальные), не получается оценка для суммы мер. Поэтому доказать, что множество тех последовательностей, на которых перечислимый снизу $\alpha$-мартингал неограничен, является эффективно $\alpha$-нулевым, этим способом не удаётся.

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

**Теорема 186.** Пусть $m$ — перечислимый снизу $\alpha$-мартингал и $\beta > \alpha$. Тогда множество тех последовательностей, на (начальных отрезках) которых $m$ неограничен, является эффективно $\beta$-нулевым.

(Напомним, что в данных нами определениях предполагается, что $\alpha$ и $\beta$ вычислимы.)

◀ Пусть $k$ — положительное натуральное число. Рассмотрим те слова $x$, для которых $m(x) > k$, и соответствующие им интервалы. Получится покрытие интересующего нас множества. Найдём сумму $\beta$-мер этих интервалов. Как мы видели, если выбрать несравнимое множество из этих интервалов, то сумма $\alpha$-мер будет не больше $1/k$. В частности, для каждой длины $N$ сумма $\alpha$-мер интервалов этой длины (из покрытия) не превосходит $1/k$. А сумма $\beta$-длин будет меньше в $2^{N(\beta-\alpha)}$ раз. Поэтому суммирование по длинеам приведёт лишь к умножению на сумму бесконечно убывающей геометрической прогрессии, которая для каждого $\beta$ конечна (хотя и велика, если $\beta$ близко к $\alpha$), так что множество оказывается эффективно $\beta$-нулевым. ►

Из двух последних теорем вытекает такое следствие:

**Теорема 187.** Эффективная хаусдорфова размерность произвольного множества $A \subset \Omega$ равна точной нижней грани тех $\alpha$, при которых существует
перечислимый снизу $\alpha$-мартингал, неограниченный на всех элементах множества А.

В этом утверждении можно заменить мартингалы на супермартингалы.

Заметим, что отсюда легко получить другое доказательство теоремы 120. В этом деле, $\alpha$-супермартингалы получаются из полумер умножением на $2^{\alpha l(x)}$. Поэтому среди перечислимых снизу $\alpha$-супермартингалов есть максимальный (получающийся из максимальной перечислимой снизу полумеры $a$), и в последней теореме можно рассматривать только его. Значит, эффективная размерность множества $\{\omega\}$ равна точной нижней грани тех $\alpha$, при которых произведение $a(\omega_0\omega_1\dots\omega_{n-1})2^{\alpha n}$ не ограничено. Логарифм его равен $\alpha n - KA(\omega_0\omega_1\dots\omega_{n-1})$, и потому точная нижняя грань таких $\alpha$ есть

$$ \liminf \frac{KA(\omega_0 \dots \omega_{n-1})}{n} $$

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

## 9.11. Частичные правила выбора

Вернёмся теперь от мартингалов к правилам выбора и подпоследовательностям. Определяя случайность по Мизесу – Чёрчу, мы рассматривали правила выбора, соответствующие разрешимым множествам $R$. Такое правило никогда не «авertsится», решая вопрос о том, нужно или нет сделать ставку на очередной член последовательности.

Можно рассмотреть и более широкий класс правил выбора. А именно, пусть $r$ — частичная вычислимая функция на двоичных словах, принимающая значения 0 и 1. Имея начальный отрезок $\omega_0 \dots \omega_{n-1}$ и решая вопрос о том, включать ли следующий член $\omega_n$ в подпоследовательность, мы вычисляем значение $r(\omega_0 \dots \omega_{n-1})$. Если оно равно единице, то $\omega_n$ включается, если нулю — то нет, а если не определено — процесс выбора вообще на этом обрывается и получается конечная подпоследовательность. Формально говоря, это эквивалентно рассмотрению множества $R$, определённого следующим образом: слово $x$ принадлежит $R$, если функция $r$ определена на $x$ и на всех его началах, причём $r(x) = 1$. (Это множество может быть неразрешимым для вычислимых частичных $r$.) Таким образом, каждой вычислимой функции $r$ описанного вида соответствует правило выбора, которое мы будем обозначать $S_r$.

Получаем более широкий класс правил выбора, чем допустимые по Чёрчу. Этот класс рассматривал Дэли [34] и мы будем называть такие правила допустимыми по Чёрчу – Дэли. Последовательность называется случайной по Мизесу – Чёрчу – Дэли, если любое допустимое по Чёрчу – Дэли правило выбора даёт сбалансированную или конечную последовательность.

**272** Докажите, что применение допустимого по Чёрчу – Дэли правила к случайной по Мизесу – Чёрчу – Дэли последовательности даёт случайную по Мизесу – Чёрчу – Дэли последовательность.
При таком расширении класса допустимых правил класс случайных последовательностей уменьшается. Это следует из теоремы 173 (с. 302) и такого утверждения (доказанного Меркле [102]):

**Теорема 188.** Не существует случайной по Мизесу – Чёрчу – Дэли последовательности $\omega$, для которой

$$KS(\omega_0 \dots \omega_{n-1}) = O(\log n).$$

### Пусть

$$KS(\omega_0 \dots \omega_{n-1}) < c \log n$$

для некоторого $c$ и для всех достаточно больших $n$. Мы хотим показать, что такая последовательность не может быть случайной по Мизесу – Чёрчу – Дэли, то есть построить правило выбора, нарушающее устойчивость частот.

Для начала рассмотрим случай, когда $c < 1$. Множество всех слов, имеющих сложность не больше $c \log n$, представляет собой перечислимое множество из не более чем $n^c$ элементов, и при больших $n$ число элементов в этом множестве (обозначим его $C_n$) не больше $n/10$. Зафиксируем одно такое $n$. Читая слева направо начальный отрезок длины $n$, будем пытаться предсказывать следующий бит по предыдущим. Оказывается, что из первых $n$ битов можно гарантированно отгадать 90%. Это делается так. Начнём перечислять $C_n$ и дождёмся появления первого элемента. Этот элемент мы объявляем «текущим кандидатом» и предсказываем те биты, которые в нём стоят, пока не ошибёмся. Такая ошибка означает, что начальный отрезок последовательности $\omega$, хотя и принадлежит $C_n$, но отличается от найденного нами элемента. Поэтому продолжим перечисление $C_n$, пока в нём не обнаружится другой элемент, не противоречащий уже известным битам, и будем использовать этот элемент для предсказаний — снова до первой ошибки. Ясно, что число ошибок не больше числа различных элементов в $C_n$, и поэтому как минимум $0,9n$ членов мы предскажем правильно.

Будем применять такой метод предсказания для быстро возрастающей последовательности значений $n_0 < n_1 < n_2...$ и достаточно большого $n_0$ (начиная с которого сложность меньше $c \log n$). Используя $C_{n_i}$ на участке $[n_{i-1}, n_i]$, мы допускаем не более $0,1n_i$ ошибок. Если $n_{i-1}/n_i$ мало (скажем, меньше 0,1), то в целом среди первых $n_i$ предсказаний будет не более $0,2n_i$ ошибок. (Мы реально используем $C_{n_i}$ на отрезке $[n_{i-1}, n_i]$ вместо $[0, n_i]$, а до этого может быть в самом худшем случае лишь $n_{i-1} < 0,1n_i$ ошибок.)

Осталось заметить, что (как и в теореме 169) алгоритм предсказания соответствует двум правилам выбора: одно выбирает те члены, где мы предсказывали единицу, а второе — где предсказывали нуль, и одна из подпоследовательностей будет сильно несбалансированной.

Что же делать при $c > 1$? Пусть, скажем, $c = 1,5$. Тогда оценка для числа элементов в $C_n$ будет $n^{1,5}$, что много больше $n$, так что наше рассуждение не проходит. Но можно сделать так. Разделим слово $\omega_0...\omega_{n-1}$ на две половины $u$ и $v$ (по $n/2$ битов каждая). Пара $(u,v)$ имеет сложность не более $1,5 \log n$. Но сложность пары равна сумме $KS(u) + KS(v|u)$ с точностью до членов порядка
$O(\log KS(u, v)) = O(\log \log n)$, поэтому либо $KS(u) < 0,8 \log n$, либо $KS(v|u) < 0,8 \log n$. В каждом случае мы можем применить уже разобранный метод угадывания, поскольку оценка сверху для числа кандидатов, $n^{0,8}$, менее одной десятой от числа угадываемых битов ($n/2$). (Заметим, что при предсказании битов второй половины мы уже знаем первую половину, так что можем перечислять слова, у которых условная сложность меньше $0,8 \log n$)

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

Тут, однако, возникает существенная трудность. Всё сказанное относилось к одному значению $n$; далее нам нужно соединить наши алгоритмы предсказания для разных $n_i$ в один. Проблема в том, что если мы пытались предсказывать биты (скажем, в левой половине), считая, что $KS(u) < 0,8n$, в то время как на самом деле это было не так, то наш алгоритм не только не будет успешным (это было бы не страшно), но вообще «ависнет» и тем самым никаких предсказаний не даст не только для этого $n$, но и для всех следующих $n$ из последовательности $n_i$.

Чтобы преодолеть эту трудность, надо вспомнить, как доказывалась формула для сложности пары (теорема 21, с. 47) и встроить её доказательство в нашу конструкцию. Вот что при этом получится.

Мы по-прежнему будем отдельно предсказывать левую и правую половины (u и v) начального отрезка длины $n$, но делать это несколько иначе. Предсказывая v слева направо (при известном u), мы перечисляем множество $C_n$ сложений начального отрезка (состоящее из всех слов длины $n$ и сложности меньше $1,5 \log n$), ожидая появления кандидата, согласованного с u и уже известными битами в v. Когда такой кандидат найден, мы используем его для предсказания, пока не ошибёмся (после чего ищем следующего кандидата). Успешность таких предсказаний (при данном u) зависит от того, сколько существует различных v, при которых $uv \in C_n$. Если их много, то мы можем ошибаться каждый раз (и каждый раз заменять кандидата). А если таких v мало, скажем, не больше $n^{0,8}$, то наши предсказания будут успешными. Важно, что в любом случае этот способ предсказания никогда не «ависнет», если только $uv$ действительно содержится в $C_n$. (А это можно гарантировать, взяв $n_0$ достаточно большим.)

Теперь о предсказании левой половины. Здесь мы в качестве кандидатов будем рассматривать такие слова $u$, для которых существует не менее $n^{0,8}$ значений $v$, при которых $uv \in C_n$. Эти предсказания будут удачными, если левая половина попадёт в число кандидатов (что обязательно случится, если предсказания в правой половине будут неудачными). Но если левая половина не окажется среди кандидатов, то этот способ предсказания «ависнет» (в некоторый момент мы будем ждать появления кандидата, согласованного с уже известными членами, и никогда не дождёмся).

Что произойдёт при объединении этих алгоритмов для разных $n_i$? Сначала рассмотрим алгоритмы предсказания правых половин. Эти алгоритмы никогда не захватывают (считаем, что $n_0$ достаточно велико, так что все начальные отрезки длин $n_i$ имеют сложность меньше $1,5 \log n_i$). Если бесконечное число среди этих алгоритмов успешно (соответствующие множества малы), то соединённый алгоритм будет
успешен (доля успешных предсказаний не стремится к 1/2). Значит, достаточно рассмотреть случай, когда лишь конечное число среди этих алгоритмов успешно. Тогда при всех достаточно больших $i$ число кандидатов $v$ (при данном $u$) будет больше $n_i^{0.8}$, и потому, отбросив некоторый начальный отрезок, мы можем считать левый алгоритм предсказания всегда успешным. Таким образом, и в этом случае последовательность не будет случайной по Мизесу – Чёрчу – Дэли.

Что же делать, если наша константа $c$ ещё больше? Надо действовать аналогично, только разбивать последовательность на большее число частей. Алгоритм предсказания для самой правой части никогда не зависает. Если он успешен в бесконечном числе случаев, всё доказано. Если с некоторого момента он неуспешен, то с этого момента следующий алгоритм (для предпоследней части) никогда не зависает. Если он успешен в бесконечном числе случаев, всё доказано. Если нет, то рассмотрим предыдущую часть и так далее.

(Аккуратное изложение со всеми деталями см. в статье [102].) ►

Таким образом, сложность начальных отрезков случайных по Мизесу – Чёрчу – Дэли последовательностей не может быть логарифмической. Но она может расти лишь чуть быстрее (скажем, быть $O(\log n \log \log n)$, как показано в [102]:

**Теорема 189.** Пусть $f: N \to N$ — всюду определённая неубывающая вычислимая неограниченная функция. Тогда существует случайная по Мизесу – Чёрчу – Дэли последовательность, у которой сложность начального отрезка длины $n$ не больше $f(n) \log n + O(1)$ (при всех $n$).

◀ Вспомним, как строились случайные по Мизесу – Чёрчу последовательности малой сложности (теорема 173). Тогда дополнительная информация состояла в том, какие из правил действительно являются правилами (какие программы всюду определены) — по одному биту на правило. Теперь этого уже мало. Для каждой программы надо знать, в какой момент она перестала быть определённой (то есть первый момент, когда она не определена на текущем начальном отрезке), чтобы с этого момента её заменить на что-нибудь безобидное. Таким образом, если при построении начального отрезка длины $n$ в игру вводятся $f(n)$ программ, то для его описания при известном $n$ достаточно $f(n) \log n$ битов информации (для каждой программы нужно $\log n$ битов, чтобы указать момент её неопределённости).

Заметим, что наличие $n$ в качестве условия не существенно, так как меняет сложность на $O(\log n)$, что соответствует изменению функции $f$ на $O(1)$. ►

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

<footnote n="1">¹С точки зрения игры естественно предполагать также, что $m(x_0)$ и $m(x_1)$ определены одновременно, так как к следующему бросанию монеты можно приступить, только когда сделаны обе ставки. Это можно предполагать без ограничения общности: если $m(x)$ и $m(x_0)$ определились, то по ним можно вычислить $m(x_1)$.</footnote>
что такой частичный мартингал выигрывает на некоторой последовательности, если он определён на всех её начальных отрезках и не ограничен на них. Будем говорить, что последовательность случайна (по равномерной мере) относительно частичных вычислимых мартингалов, если не существует вычислимого частичного мартингала, выигрывающего на ней. Теперь можно доказать, следуя [102], такое обобщение предыдущей теоремы 189:

**Теорема 190.** (а) Всякая последовательность, случайная относительно частичных вычислимых мартингалов, случайна по Мизесу – Чёрчу – Дэли.

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

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

◀ (а) Применим ту же самую конструкцию, преобразующую правило выбора в мартингал, что и в теореме 182, пункт (в). Если правило $R$ не всюду определено, то и мартингал будет частичным. Но если правило в применении к некоторой последовательности $\omega$ даёт бесконечную подпоследовательность, то соответствующий ему мартингал будет определён на всех начальных отрезках последовательности $\omega$.

(б) И здесь практически без изменений проходит рассуждение из теоремы 182, пункт (б). Для каждого вводимого в игру мартингала нам надо знать, в какой момент он становится неопределённым (чтобы с этого момента заменить его чем-нибудь безобидным, например, его последним значением). Эта информация занимает не более $\log n$ битов для каждого мартингала, использованного при построении начального отрезка длины $n$, и если к этому моменту ввести в дело не больше $f(n)$ мартингалов, получится как раз требуемая оценка. ►

## 9.12. Немонотонные правила выбора

До сих пор наши правила выбора были монотонны (сохраняли порядок членов в исходной последовательности). Немонотонные правила были предложены Колмогоровым [62] и независимо Лавлэндом [88, 89].

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

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

Наша стратегия в такой игре задаётся двумя функциями. Первая функция $F$ отображает двоичные слова в натуральные числа и говорит, какую карточку надо переворачивать следующей (в зависимости от того, что мы увидели на уже перевёрнутых карточках). Мы предполагаем, что значения функции $F$ на любых двух словах, из которых одно является началом другого, различны (никакая карточка не переворачивается дважды в ходе игры).
Вторая функция G определена также на двоичных словах и принимает значе-
ния 0 и 1; договоримся, что значение 0 означает, что очередная карточка перево-
рачивается «для информации», а 1 означает, что на неё «делается ставка» (соответ-
ствующий член включается в подпоследовательность).

Формально говоря, для любой частичной функции F (с указанным свойством)
и для любой частичной функции G мы определяем отображение (правило выбо-
ра) S<sub>F,G</sub>: Ω → Σ следующим образом: сначала строим конечную или бесконечную
последовательность натуральных чисел n<sub>0</sub>, n<sub>1</sub>, ... по формулам

$$
n_0 = F(\Lambda), n_1 = F(\omega_{n_0}), n_2 = F(\omega_{n_0} \omega_{n_1}), \dots
$$

(построение прерывается, как только очередное значение *F* не определено). Наше
условие на функцию *F* гарантирует, что все номера *n*ᵢ различны.

Затем отбираются те члены ω<sub>n<sub>1</sub></sub>, при которых значение G на слове ω<sub>n<sub>0</sub></sub>ω<sub>n<sub>1</sub></sub> ... ω<sub>n<sub>f-1</sub></sub> определено и равно 1, а значения G на всех началах этого слова определены (и могут быть любыми). Соответствующие ω<sub>n<sub>f</sub></sub> (в порядке возрастания *i*) и образуют последовательность S<sub>F,G</sub>(ω).

Правила выбора S<sub>F,G</sub>, соответствующие частичным вычислимым функциям F и G, называются допустимыми по Колмогорову – Лавлэнду. Последовательность ω ∈ Ω называется случайной по Мизесу – Колмогорову – Лавлэнду относительно равномерной меры, если любое допустимое по Колмогорову – Лавлэнду правило выбора даёт сбалансированную (или конечную) последовательность. Английский термин: Kolmogorov – Loveland stochastic (или KL-stochastic).

Аналогично определяется случайность по Мизесу – Колмогорову – Лавлэнду и относительно бернуллиевой меры (независимые испытания с вероятностью успе- ха *p*) при любом *p*.

Следующее простое, но неожиданное наблюдение сделал Меркле [101]:

**Теорема 191.** В определении случайности по Мизесу – Колмогорову – Лавлэнду можно ограничиться лишь всюду определёнными вычислимыми функциями F и G; получится тот же самый класс последовательностей.

◀ Пусть имеются частичные функции F и G, выбирающие из некоторой последовательности ω бесконечную несбалансированную подпоследовательность. Разобьём эту последовательность на две, в зависимости от чётности порядкового номера в исходной последовательности ω. Одна из них будет бесконечной, но не сбалансированной. Поэтому без ограничения общности можно считать, что наше правило включает в подпоследовательность лишь (скажем) чётные члены последовательности. Тогда нечётные члены можно читать заранее, это не повредит, так как в последовательность включены они всё равно не будут. Поэтому, если частичное правило долго работает, можно параллельно про запас читать нечётные члены последовательности. Такое модифицированное правило задаётся всюду определёнными функциями F и G. (Если исходный алгоритм «завис», то новый будет читать подряд нечётные члены последовательности, но ничего так и не выберет.) ►

(В этом доказательстве мы свели одно правило с частичными функциями к двум
правилам со всюду определёнными функциями.)
Как соотносится новое определение с уже известными нам? Частичный ответ на этот вопрос даёт следующая теорема.

**Теорема 192.** (а) Всякая случайная по Мизесу – Колмогорову – Лавлэнду последовательность случайна по Мизесу – Чёрчу – Дэли (и, следовательно, по Мизесу – Чёрчу).

(б) Всякая случайная по Мартин-Лёфу последовательность случайна по Мизесу – Колмогорову – Лавлэнду.

Точнее, пункт (а) имеет место для любого действительного $p \in (0, 1)$; пункт (б) дополнительно предполагает, что $p$ вычислимо и случайность по Мартин-Лёфу понимается относительно бернуллиевой меры с параметром $p$.

◀ (а) Допустимые по Мизесу – Чёрчу – Дэли (и тем более по Мизесу – Чёрчу) правила выбора являются частными случаями допустимых по Колмогорову – Лавлэнду правил.

(б) По существу это рассуждение повторяет аналогичное рассуждение для случайности по Мизесу – Чёрчу. Мы предполагаем, что фиксировано некоторое вычислимое $p$, для которого изучается случайность по Мизесу – Колмогорову – Лавлэнду (предел частот в подпоследовательностях должен быть равен $p$) и по Мартин-Лёфу (рассматривается вычислимая мера $\mu_p$ на $\Omega$, соответствующая независимым испытаниям, в каждом из которых вероятность успеха равна $p$).

Пусть фиксированы вычислимые функции $F$ и $G$, задающее допустимое по Мизесу – Чёрчу правило выбора.

Для каждого целого $n$ и рационального $q$ рассмотрим множество $D_{n,q}$ всех двоичных слов длины $n$, у которых доля единиц больше $q$. Мы знаем, что при фиксированном $q > p$ и при возрастающем $n$ мера множества $D_{n,q}$ (точнее, $\mu_p$-мера множества $D_{n,q}$ всех последовательностей, имеющих начало в $D_{n,q}$) экспоненциально убывает.

Рассмотрим теперь прообраз этого множества относительно $S_{F,G}$, то есть множество всех последовательностей $\omega$, для которых описанный процесс выбора даёт подпоследовательность длины не меньше $n$ и частота единиц среди первых $n$ выбранных членов больше $q$. Легко заметить, что $\mu_p$-мера этого прообраза не больше $\mu_p(D_{n,q})$.

Неформально говоря, мы замечаем, что результат выбора имеет то же самое бернуллиево распределение, что и исходная последовательность, если отвлечься от того, что он может быть конечным. Подробнее: пусть $t$ — некоторое двоичное слово длины $k-1$. Рассмотрим условную вероятность того, что $k$-я по счёту выбранная (включённая в подпоследовательность) карточка содержит единицу, при условии что предыдущие члены подпоследовательности образуют слово $t$ и до выбора $k$-й карточки вообще дело дойдёт. Эта условная вероятность равна $p$, поскольку к моменту переворачивания $k$-й карточки её содержимое ещё никак не использовалось и мы можем «отложить» бросание монеты до этого момента. Более формально, событие, которое фигурирует в качестве условия, является счётным объединением неперескающихся вариантов, каждый из которых соответствует конкретному ходу процесса выбора вплоть до момента, когда выбрана (но ещё не перевёрнута) $k$-я карточка подпоследовательности (какие карточки перевёрнуты и что в них
оказалось). В каждом из вариантов уже определено, какая карточка будет следующей выбрана, и этот вариант разбивается на две части в пропорции $p : (1 - p)$ в зависимости от содержания этой карточки. Отсюда по индукции легко следует выделенное курсивом утверждение.

Остаётся заметить, что упомянутый прообраз не только имеет малую меру (быстро убывающую с ростом $n$), но ещё и перечислим (любой из вариантов зависит от конечного числа значений функций $F$ и $G$ и потому рано или поздно обнаружится), поэтому, как и в усиленном законе больших чисел, возникает эффективно нулевое множество (для каждого $q$ — своё). Все эти эффективно нулевые множества (а также аналогичные множества для последовательностей с частотами меньше $p$) содержатся в максимальном эффективно нулевом множестве. ►

В следующем разделе мы докажем такое усиление утверждения (б): если вычислимая последовательность $p_n$ действительных чисел в интервале $(0, 1)$ вычислимо сходится к пределу $p \in (0, 1)$, то всякая последовательность, случайная по Мартин-Лёфу относительно произведения мер (испытания независимы, вероятность удачи в $i$-м испытании равна $p_i$), случайна по Мизесу – Колмогорову – Лавлэнду с параметром $p$. Это позволит нам строить примеры случайных по Мизесу – Колмогорову – Лавлэнду последовательностей с плохими свойствами (неслучайные по Мартин-Лёфу, содержащие больше единиц, чем нулей, и другие).

Пока же мы хотим действовать в другом направлении и показать — для случая равномерной меры, — что случайная по Мизесу – Колмогорову – Лавлэнду последовательность (в отличие от случайных по Мизесу – Чёрчу и Мизесу – Чёрчу – Дэли) имеет достаточно большую сложность начальных отрезков:

**Теорема 193.** Пусть $\omega \in \Omega$ такова, что $KS(\omega_0...\omega_{n-1}) < \alpha n$ для некоторого $\alpha < 1$ и всех достаточно больших $n$. Тогда последовательность $\omega$ не случайна по Мизесу – Колмогорову – Лавлэнду.

Этот результат (доказанный Ан. А. Мучником в конце 1980-х годов) впоследствии был усилен: оказалось, что если неравенство верно для бесконечно многих $n$, то последовательность не случайна по Мизесу – Колмогорову – Лавлэнду. Мы ограничимся доказательством первоначального результата.

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

Представим себе, что крупье бросает монету раз за разом, и перед каждым бросанием мы можем сделать ограниченную ставку $u \in [-1, 1]$ (положительные $u$ соответствуют ставкам на единицу, отрицательные — на нуль). После этого мы получаем $u$ рублей, если выпадает единица, и $(-u)$ рублей, если выпадает нуль.

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

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

Например, если А содержит единственный элемент (то есть мы заранее знаем результаты всех бросаний), то можно выиграть *n* рублей (что не удивительно: в каждой партии мы выигрываем рубль). (В рассмотренном выше «мартингальном» варианте игры выигрыш был гораздо больше: в $2^n$ раз.) Если мы знаем результаты каких-то фиксированных *k* бросаний, то по лемме можем выиграть *k* рублей (что тоже не удивительно). Чуть более сложный пример: пусть мы знаем, что число орлов будет чётно (что соответствует $s = n - 1$). Лемма говорит, что на этом можно выиграть рубль. Легко понять, как: нужно делать нулевые ставки до последнего момента, а результат последнего бросания нам фактически известен, и на него надо сделать максимальную ставку.

После этих примеров общее доказательство выглядит довольно естественно. В каждый момент нам известен некоторый начальный отрезок $w$ последовательно-сти (пусть его длина $j$). Имеется $2^{n-j}$ продолжений слова $w$, имеющих длину $n$, однако не все они принадлежат А. Рассмотрим условную вероятность попадания в А после $w$ (долю продолжений, попадающих в А); минус логарифм этой веро-ятности назовём информационным капиталом игрока.

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

Почему это возможно? Пусть в данный момент информационный капитал равен $(-\log p)$ (где $p$ — текущая доля элементов из А среди продолжений). Зная А, мы можем найти этот капитал, а также узнать, как он изменится после появления нуля и единицы: после появления нуля он будет равен $(-\log p_0)$, а после единицы будет равен $(-\log p_1)$, где $p_0$ и $p_1$ — соответствующие доли. Ясно, что $p = (p_0 + p_1)/2$. Нам нужно найти такой размер очередной ставки $d$, чтобы в обоих случаях сумма информационного и реального капитала не уменьшилась:

$$- \log p_0 - d \geq - \log p,$$

$$- \log p_1 + d \geq - \log p,$$

или, разрешая эти неравенства относительно $d$,

$$- \log p_0 + \log p \geq d \geq - \log p + \log p_1,$$

$$- \log(p_0/p) \geq d \geq \log(p_1/p).$$

Ясно, что такое $d$ можно выбрать, если и только если $p/p_0 \geq p_1/p$, то есть $p^2 \geq p_0 p_1$ (а это так согласно неравенству о среднем арифметическом и геом-трическом). Заметим также, что $p_0$ и $p_1$ не больше $2p$, поэтому границы для $d$ (и тем самым само $d$) не выходят за пределы промежутка $[-1, 1]$. Лемма доказана.
<figure><img src="image_27.png" /><figcaption>Рис. 9.1. Пространство выбора для игрока: слева в обычных координатах, справа — в логарифмических. Пунктиром показано пространство выбора для игры с суммированием ограниченных ставок.</figcaption></figure>

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

Теперь легко доказать такое утверждение:

**Теорема 194.** Пусть $K$ — произвольная вычислимая всюду определённая верхняя оценка для функции $KS$, а последовательность $\omega \in \Omega$ такова, что

$$K(\omega_0 \dots \omega_{n-1}) \le \alpha n$$

для некоторого $\alpha < 1$ и для всех достаточно больших $n$. Тогда последовательность $\omega$ не случайна по Мизесу – Чёрчу.

◀ Для каждого $n$ можно алгоритмически построить список $A_n$ всех слов длины $n$, для которых значение функции $K$ не превосходит $\alpha n$. Этот список будет содержать не более $2^{\alpha n+O(1)}$ слов. Мы знаем, что при достаточно больших $n$ начальный отрезок последовательности $\omega$ попадает в $A_n$. Для этих $n$ построенная по лемме (для множества $A_n$) стратегия будет выигрывать не меньше $(1 - \alpha)n - O(1)$ рублей при игре с начальным отрезком последовательности $\omega$ длины $n$.

Рассмотрим последовательность быстро растущих $n_i$ (насколько быстро, что $n_{i-1}/n_i \to 0$) и соединим стратегии для $A_{n_i}$ в одну. Фактически стратегия для $A_{n_i}$ будет применяться не на всем начальном отрезке длины $n_i$, а лишь после окончания предыдущего отрезка $n_{i-1}$, что, по нашему предположению, составляет бесконечно малую долю от $n_i$. Поэтому соединённая стратегия будет успешна в том смысле, что выигрыш её на начальном отрезке длины $n$ будет превосходить $\varepsilon n$ для фиксированного $\varepsilon > 0$ и для бесконечно многих $n$. (Достаточно взять $\varepsilon < 1 - \alpha$ и $n = n_i$ при больших $i$.)

А это противоречит случайности по Мизесу – Чёрчу (теорема 170, с. 298). ▶

Теперь мы уже готовы к доказательству теоремы 193.

◀ По аналогии с только что проведённым доказательством, мы можем рассмотреть множество $A_n$ всех слов длины $n$, имеющих сложность не более $\alpha n$. Оно
содержит примерно $2^{\alpha n}$ слов, среди которых заведомо имеется начальный отрезок последовательности $\omega$. Но теперь мы не можем алгоритмически построить список всех слов множества $A_n$, а можем лишь перечислять эти слова (не зная ни в какой момент, все ли слова уже появились или ещё нет). Преодолеть эту трудность можно, вспомнив, что нам разрешено использовать немонотонные правила выбора. Вот как это делается.

Снова рассмотрим быстро растущую вычислимую последовательность $n_i$, например, $n_i = i!$ Разобьём последовательность на отрезки, проведя границы в точках $n_i$; длина $i$-го отрезка будет $n_i - n_{i-1}$. Немного увеличив $\alpha$, мы можем считать, что сложность $i$-го отрезка последовательности не больше $\alpha$, умноженного на его длину. Другими словами, мы будем считать, что удельная (в расчёте на букву) сложность $i$-го отрезка последовательности не превосходит $\alpha$. Пусть $A_i$ — множество всех слов длины $n_i - n_{i-1}$, для которых удельная сложность не больше $\alpha$. Мы знаем, что $i$-й отрезок последовательности $\omega$, который мы обозначим через $\omega^i$, лежит в $A_i$ (по крайней мере при достаточно больших $i$), и можем перечислять множество $A_i$, зная $i$.

Пусть $t_i$ — число шагов этого перечисления, которое нужно сделать, прежде чем $\omega^i$ появится в $A_i$. Будем отдельно рассматривать чётные и нечётные номера, и сравним соседние значения $t_{2m}$ и $t_{2m+1}$. Тривиальное замечание: либо $t_{2m} \le t_{2m+1}$, либо $t_{2m+1} \le t_{2m}$ (а может, и то, и другое). Что это нам даёт? А вот что: одна стратегия может посмотреть (не делая ставок, в порядке информации) участок $\omega^{2m}$, после чего перечислять $A_{2m}$ до появления $\omega^{2m}$, и тем самым найти число $t_{2m}$. Затем эта стратегия делает столько же (то есть $t_{2m}$) шагов перечисления множества $A_{2m+1}$, надеется на то, что неизвестное ей $\omega^{2m+1}$ принадлежит перечисленной части множества $A_{2m+1}$ и делает ставки как в предыдущей теореме. Это приведёт к успеху, если $t_{2m} \ge t_{2m+1}$; в противном случае мы можем всё проиграть. Но тогда парная стратегия, которая просматривает $\omega^{2m+1}$, находит $t_{2m+1}$, а затем делает столько же шагов перечисления $A_{2m}$, будет успешной.

Таким образом, при каждом $m$ у нас есть пара стратегий (со ставками в промежутке $[-1, 1]$), одна из которых является успешной (выигрывает не менее $1 - \alpha$ в расчёте на каждую сделанную ставку). (Формально говоря, такие стратегии имеют лишь при достаточно больших $m$, но мы можем все меньше пропустить.) Одна из этих стратегий монотонна и (как в теореме 170) приближается средним арифметическим конечного числа правил выбора, допустимых по Чёрчу. Число правил зависит от допустимой погрешности; нам нужно, чтобы погрешность была мала по сравнению с $1 - \alpha$, и этого можно добиться для фиксированного (не зависящего от $m$) числа правил, которое мы обозначим через $N$. Другая стратегия немонотонна, и потому получаются $N$ правил выбора, допустимых по Колмогорову – Лавлэнду. Всего получается $2N$ правил выбора, имеющих дело с двумя соседними участками последовательности.

Соединяя правила для разных отрезков, получим $2N$ допустимых по Колмогорову – Лавлэнду правил выбора. Вспоминая, что $n_{i-1}/n_i$ мало и результа́т выбора на предыдущем отрезке почти не меняет частоту на следующем, получаем, что для каждого $m$ хотя бы одно из построенных $2N$ правил даёт значительное отклонение
частоты. Значит, одно из них даёт такое отклонение для бесконечно многих m, и
последовательность ω не случайна по Мизесу – Колмогорову – Лавлэнду.

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

Из неё (и теоремы 189) вытекает такое следствие:

**Теорема 195.** Существуют случайные по Мизесу – Чёрчу – Дэли последовательности, не являющиеся случайными по Мизесу – Колмогорову – Лавлэнду.

В связи с теоремой 193 возникает естественный вопрос: пусть известно, что сложность (конечного) слова x мала. Существует ли немонотонное правило выбора небольшой колмогоровской сложности, выбирающее из x сильно несбалансированную подпоследовательность. В аккуратной постановке этой задачи имеется несколько параметров: длина n слова x, его дефект случайности d, сложность правила выбора (при известном n) и несбалансированность (разница между количеством нулей и единиц) отобранной подпоследовательности. В работе [41] получен следующий (далеко не окончательный) результат в этом направлении: существует правило выбора сложности O(log(n/d)) при известном n, отбирающее подпоследовательность, несбалансированность которой равна Ω(n/ log(n/d)). В частности, если дефект случайности, как в теореме 193, пропорционален n, то правило отбора имеет ограниченную сложность, а несбалансированность отобранной подпоследовательности пропорциональна длине исходной последовательности n.

## 9.13. Случайность по изменённой мере

В этом разделе мы изложим метод (предложенный Ламбальгеном [73]), с помощью которого можно строить случайные по Мизесу – Колмогорову – Лавлэнду последовательности с разными «патологическими» свойствами (не случайные по Мартин-Лёфу, с превышением нулей над единицами в начальных отрезках и другие).

### 9.13.1. Случайность по двум мерам

Для начала обсудим вопрос, имеющий и более общее значение: насколько зависит случайность (относительно данной меры) от выбора меры?

Вот два примера противоположного характера.

**Пример 1.** Рассмотрим равномерную меру μ, а также меру μ', в которой испытания независимы, причём во всех, кроме первого, вероятность успеха равна 1/2, а в первом она равна, скажем, 2/3. Интуитивно ясно, что случайными должны быть одни и те же последовательности: в самом деле, в первом испытании возможны оба исхода (и по той, и по другой мерам), а дальше меры одинаковы. Это действительно так для всех разумных определений случайности. Можно заметить, что эффективно нулевые множества относительно мер μ и μ' одни и те же (поскольку меры любого множества отличаются не более чем в два раза). Отсюда ясно, что случайными в смысле Мартин-Лёфа по этим мерам будут одни и те же последовательности.

273 Как доказать это, исходя из критерия случайности в терминах сложности?
**274** Докажите, что случайными относительно вычислимых мартингалов (по мерам $\mu$ и $\mu'$) будут одни и те же последовательности.

**Пример 2.** Рассмотрим равномерную меру $\mu$, а также меру $\mu'$, в которой испытания независимы и вероятность успеха в каждом из них равна $2/3$. Может ли одна и та же последовательность быть случайной (скажем, по Мартин-Лёфу) относительно $\mu$ и $\mu'$? В полном согласии с нашей интуицией, нет — в самом деле, для случайной последовательности предел частот равен вероятности успеха, а $1/2 \neq 2/3$.

Возникает следующий естественный вопрос. Пусть имеются две последовательности чисел $p_i, p'_i \in (0, 1)$. Рассмотрим меры $\mu$ и $\mu'$ на $\Omega$, соответствующие неавыкисимым испытаниям, вероятность успеха в $i$-м равна $p_i$ для меры $\mu$ и $p'_i$ для меры $\mu'$. Что можно сказать о классах случайных последовательностей относительно этих двух мер? Естественно ожидать, что при близких $p_i$ и $p'_i$ случайными должны быть одни и те же последовательности, а при сильно отличающихся $p_i$ и $p'_i$ классы случайных последовательностей не должны пересекаться.

Мы докажем, что это так и есть для случая отделённых от 0 и 1 вероятностей, когда все $p_i$ и $p'_i$ лежат в интервале $(\varepsilon, 1-\varepsilon)$ для некоторого положительного $\varepsilon$. Кроме того, мы предполагаем, что последовательности $p_i$ и $p'_i$ являются вычислыми последовательностями вычислимых действительных чисел (иначе не имеет смысл говорить о случайности по Мартин-Лёфу).

Имеет место такой критерий, доказанный Вовком в [181] (конструктивный аналог классической теоремы Какутани [55]):

**Теорема 196.** (а) Если сумма ряда $\sum (p_i - p'_i)^2$ конечна, то классы случайных по Мартин-Лёфу последовательностей относительно мер $\mu$ и $\mu'$ совпадают.

(б) Если сумма ряда $\sum (p_i - p'_i)^2$ бесконечна, то эти классы не пересекаются.

Классический вариант этой теоремы [55] утверждает, что в первом случае любое нулевое множество относительно одной меры является нулевым относительно другой, а во втором случае меры ортогональны (существует множество меры 0 по одной и меры 1 по другой).

◀ Кажется естественным доказывать пункт (а) следующим образом. Пусть по-следовательность $\omega \in \Omega$ случайна по мере $\mu$, соответствующей вероятностям $p_i$. Тогда (монотонная) сложность её начального отрезка длины $n$ близка к логарифму его вероятности, которая равна произведению

$$ \prod_{i=0}^{n-1} r_i, $$

где $r_i = p_i$ при $\omega_i = 1$ и $r_i = 1 - p_i$ при $\omega_i = 0$. Если $p_i$ близко к $p'_i$, то $r_i$ близко к $r'_i$ (где $r'_i$ определяется аналогичным образом для другой меры). Поэтому произведение всех $r_i$ близко к произведению всех $r'_i$, так что случайность по одной мере влечёт за собой случайность и по другой.
Это рассуждение несложно формализовать, но при этом нам придётся предположить, что разность

$$ \sum_{i=0}^{n-1} (-\log r_i) - \sum_{i=0}^{n-1} (-\log r'_i) $$

ограничена; легко проверить, что это так, когда $\sum |p_i - p'_i| < \infty$ (напомним, что мы предполагаем $p_i$ и $p'_i$ отделёнными от нуля и единицы). А это больше, чем нам дано по условию; нам известно лишь, что сумма квадратов ограничена.

Как же быть? Заметим, что на самом деле нам достаточно, чтобы упомянутая разность была ограничена для любой случайной по мере $\mu$ последовательности $\omega$. Мы знаем, что тогда

$$ KM(\omega_0 \dots \omega_{n-1}) = \sum_{i=0}^{n-1} (-\log r_i) + O(1) $$

(сложность отличается от логарифма вероятности не более чем на константу), поэтому верхняя оценка для сложности (которая имеет место для любой вычислимой меры, в частности, для $\mu'$) даёт нам

$$ \sum_{i=0}^{n-1} (-\log r_i) \le \sum_{i=0}^{n-1} (-\log r'_i) + O(1). $$

Обозначим разницу между $r'_i - r_i$ через $\delta_i$. Используя это обозначение и переходя к произведениям, получим (верное с точностью до мультипликативной константы) неравенство

$$ \prod_{i=0}^{n-1} r_i \ge \prod_{i=0}^{n-1} (r_i + \delta_i). $$

Мы знаем, что $\sum_i \delta_i^2 < \infty$ и, в частности, $\delta_i \to 0$ при $i \to \infty$. Поэтому почти все $\delta_i$ меньше числа $\varepsilon$, отделяющего наши вероятности от нуля и единицы. Изменив конечное число членов $p'_i$ (что не влияет на случайность), мы можем считать, что это верно для всех $i$. Тогда можно рассмотреть меру $\mu''$, «симметричную» мере $\mu'$ относительно $\mu$ (это означает, что $p_i$ есть середина отрезка $[p'_i, p''_i]$). Для этой меры можно записать аналогичное неравенство, которое будет отличаться лишь знаком при $\delta_i$:

$$ \prod_{i=0}^{n-1} r_i \ge \prod_{i=0}^{n-1} (r_i - \delta_i) $$

(оно также верно с точностью до константы). Перемножим эти два неравенства:

$$ \prod_{i=0}^{n-1} r_i^2 \ge \prod_{i=0}^{n-1} (r_i^2 - \delta_i^2). $$

А это неравенство (само по себе очевидное, и даже безо всякой константы), в силу наших предположений о $\delta_i$ является равенством (с точностью до ограниченного и отделённого от нуля множителя): как известно из курса математического анализа,
бесконечное произведение $\Pi(1 - h_i)$ больше нуля (при $0 < h_i < 1$) тогда и только тогда, когда $\sum h_i < \infty$.

Следовательно, и оба перемножаемых неравенства являются равенствами с точностью до константы. После этого критерий случайности (теорема 90) говорит, что последовательность $\omega$ случайна и по мере $\mu'$ (а также $\mu''$, что для нас неважно). Утверждение (а) доказано.

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

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

**275** Пусть $p_0, p_1, p_2, \dots$ и $p_0', p_1', p_2', \dots$ находятся в интервале $(\varepsilon, 1 - \varepsilon)$ для некоторого $\varepsilon > 0$, а меры $\mu$ и $\mu'$ соответствуют независимым испытаниям с вероятностями $p_i$ и $p_i'$. Докажите, что $\sum (p_i - p_i')^2 < \infty$, то нулевыми по мерам $\mu$ и $\mu'$ являются одни и те же множества. Докажите, что если $\sum (p_i - p_i')^2 = \infty$, то меры $\mu$ и $\mu'$ ортогональны (существует множество меры 0 по одной из них и меры 1 по другой). [Указание. Воспользуйтесь теоремой 196 в релятивизованном варианте и заметьте, что для всякого нулевого множества можно найти оракул, относительно которого меры вычислимы, а множество эффективно нулевое. Во втором случае рассмотрите множества случайных по этим мерам последовательностей.]

Пусть $\mu$ — произвольная мера на пространстве $\Omega$, а $p(x)$ — соответствующая функция на двочных словах: $p(x) = \mu(\Omega_x)$. Для каждого слова $x$, которое имеет положительную вероятность появления в качестве начального отрезка последовательности (что означает $p(x) > 0$), рассмотрим условную вероятность появления единицы после $x$, то есть отношение $p(1|x) = p(x1)/p(x)$. (Если бросания независимы, то эта величина зависит лишь от длины слова $x$ и обозначалась нами раньше через $p_i$.)

Если теперь, помимо меры, задана ещё и последовательность $\omega \in \Omega$, то можно рассмотреть условные вероятности появления единицы на каждом шаге для этой последовательности, то есть последовательность чисел

$$p_i = p(1 | \omega_0 \dots \omega_{i-1}) = p(\omega_0 \dots \omega_{i-1} 1) / p(\omega_0 \dots \omega_{i-1})$$

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

**Теорема 197.** Если последовательность $\omega$ случайна в смысле Мартин-Лёфа по двум мерам $\mu$ и $\mu'$, и числа $p_i$ и $p_i'$, построенные описанным образом для этих мер, все находятся в интервале $(\varepsilon, 1 - \varepsilon)$ для некоторого $\varepsilon > 0$, то

$$\sum_i (p_i - p_i')^2 < \infty.$$
Заметим, что отсюда прямо следует утверждение теоремы 196. Отметим также, что для случайной последовательности числа $p_i$ определены, так как знаменатель дроби $p(x1)/p(x)$ не может обращаться в нуль (слово, имеющее нулевую вероятность, не может быть началом случайной последовательности).

◀ Рассмотрим третью меру $\tilde{\mu}$, которая усредняет вероятности появления единицы для мер $\mu$ и $\mu'$. А именно, вероятность появления единицы после любого слова х с точки зрения меры $\tilde{\mu}$ равна среднему арифметическому вероятностей появления единицы после того же х с точки зрения мер $\mu$ и $\mu'$. (Заметим, что это не соответствует усреднению мер: если положить $\tilde{\mu}(X) = (\mu(X) + \mu'(X))/2$, тоже получится мера, но совсем другая!)

Если последовательность случайна, то для сложности её начальных отрезков можно записать равенство

$$KA(\omega_0 \dots \omega_{n-1}) = \sum_{i=0}^{n-1} (-\log r_i) + O(1),$$

где, как и раньше, $r_i = p_i$ при $\omega_i = 1$ и $r_i = (1 - p_i)$ при $\omega_i = 0$. Аналогичное равенство можно записать и для $r'_i$ (построенных для меры $\mu'$), а для $\tilde{r}_i$ (построенных по мере $\tilde{\mu}$) можно записать лишь неравенство (сложность не больше минус логарифма меры).

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

$$\sum_{i=0}^{n-1} (-\log r_i) \le \sum_{i=0}^{n-1} (-\log \tilde{r}_i) + O(1),$$

$$\sum_{i=0}^{n-1} (-\log r'_i) \le \sum_{i=0}^{n-1} (-\log \tilde{r}_i) + O(1).$$

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

$$\sum_{i=0}^{n-1} \frac{(-\log r_i) + (-\log r'_i)}{2} \le \sum_{i=0}^{n-1} (-\log \tilde{r}_i) + O(1).$$

Вспоминая, что $\tilde{r}_i = (r_i + r'_i)/2$ и перенося всё в одну часть, получаем

$$\sum_{i=0}^{n-1} \left( \frac{(-\log r_i) + (-\log r'_i)}{2} - \left( -\log \frac{r_i + r'_i}{2} \right) \right) \le O(1).$$

Каждое слагаемое суммы в левой части неотрицательно (выпускость логарифма) и по порядку величины равно $(r_i - r'_i)^2$, поэтому $\Sigma(r_i - r'_i)^2 \sim \Sigma(p_i - p'_i)^2 < \infty$, что и требовалось доказать.

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

Отметим, что в этой теореме говорится лишь о близости мер вдоль последовательности $ω$, случайной по обеим мерам; на других последовательностях они могут и сильно различаться.

**276** Приведите соответствующий пример. [Указание. Рассмотрим две меры, которые на левой половине отрезка равномерны, а на правой сильно различаются.]

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

Приведённое доказательство имеет естественную игровую интерпретацию. Представим себе, что имеются два тотализатора, принимающих ставки на одну и ту же последовательность событий (каждое событие имеет два исхода: нуль и единицу). Однако их организаторы по-разному оценивают шансы и поэтому принимают ставки на разных условиях. В одном случае вероятности появления единицы и нуля считаются равными $p$ и $q$ (и потому поставленная на 1 [0] сумма возвращается с коэффициентом $1/p$ [1/$q$]), а в другом случае вероятности считаются равными $p'$ и $q'$ (а коэффициенты равны $1/p'$ и $1/q'$). (Вероятности $p, p', q, q'$ могут меняться от события к событию).

В этом случае можно одновременно участвовать в двух играх (в каждой — со своим капиталом; передавать деньги из одного игрового зала в другой нельзя), причём делать это так, чтобы по крайней мере в одной выиграть. Более того, в случае, когда все $p, q, p', q'$ отделены от нуля и сумма $\Sigma(p - p')^2$ (по всей последовательности событий) бесконечна, то хотя бы в одной из игр наш выигрыш будет неограничен.

Как этого добиться? Пусть в первой игре у нас имеется капитал $u$, оценки вероятностей для следующего события равна $p, p', q, q'$. Поделим $u$ между двумя ставками так, чтобы после игры наш капитал был равен $(p + p')u/2p$ (если выпадет единица) и $(q + q')u/2q$ (если выпадет нуль). (Легко проверить, что это допускается правилами игры, то есть что математическое ожидание капитала после партии равно $u$.) Во второй игре капитал $v$ превращается после игры в $(p + p')v/2p'$ (если выпадет единица) и $(q + q')v/2q'$ (если выпадет нуль). Будем следить за произведением капиталов в обеих играх. Оно умножается либо на $(p + p')^2/4pp'$, либо на $(q + q')^2/4qq'$. Неравенство о среднем арифметическом и среднем геометрическом показывает, что в обоих случаях произведение $uv$ возрастает. Переходя к логарифмам и оценивая этот рост, легко заметить, что (для отделённых от нуля $p, p', q, q'$) при $\Sigma(p - p')^2 = \infty$ произведение капиталов стремится к бесконечности, и, следовательно, хотя бы в одной игре капитал не ограничен.

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

Усиленный закон больших чисел говорит, что для любого $p \in (0, 1)$ и соответствующей ему бернуллиевой меры $\mu_p$ (испытания независимы, вероятность успеха в каждом равна $p$) множество последовательностей, у которых предел частот равен $p$, имеет меру 1 (а его дополнение, то есть множество последовательностей, не имеющих предела частот или имеющих другой предел частот, является нулевым).

Пусть теперь вероятности не постоянны, и в $i$-м испытании вероятность успеха равна $p_i$. Естественно ожидать, что если $p_i \to p$, то предел частот для почти всех последовательностей будет равен $p$. Не вполне строго это можно объяснить так: возьмём какое-то $\epsilon > 0$. Все частоты $p_i$, кроме конечного числа (а им можно пренебречь), меньше $p + \epsilon/2$. Мы знаем, что если заменить вероятности $p_i$ на $p + \epsilon/2$, то почти наверное начиная с некоторого места частота будет меньше $p + \epsilon$. Значит, это тем более так для $p_i < p + \epsilon/2$ по монотонности.

Это рассуждение можно (с некоторым трудом, впрочем) сделать строгим, но мы предпочитаем доказать более общую оценку, которая полезна во многих случаях. Она относится к произвольной мере $\mu$ на пространстве $\Omega$; пусть $p$ — соответствующая ей функция на словах. Для любого конечного слова $x = x_0 \dots x_{n-1}$ длины $n$ рассмотрим число единиц $m$ в этом слове, а также сумму $p_0 + \dots + p_{n-1}$ условных вероятностей появления единицы в каждой его позиции:

$$p_i = p(x_0 \dots x_{i-1})/p(x_0 \dots x_{i-1}).$$

Обе эти величины зависят от слова $x$; наша оценка утверждает, что с большой вероятностью (по мере $\mu$) для данной длины $n$ эти величины будут близки. Вот точная формулировка (смысл $m$ и $p_i$ объяснён только что, вероятность берётся по мере $\mu$):

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

$$\mathrm{Pr}[|m - (p_0 + \dots + p_{n-1})| > d] \le 2e^{-d^2/4n}.$$

Заметим, что бесконечные последовательности в этой формулировке по существу не нужны; фактически речь идёт о неравенстве, верном для любого распределения вероятностей на последовательностях нулей и единиц длины $n$. Это неравенство является ослабленной формой неравенства Азумы – Хёфдинга, известного в теории вероятностей; мы приведём простое рассуждение по аналогии с уже встречавшимися (сравнение мер), хотя и не дающее наиболее сильного утверждения (можно было бы заменить константу 4 на 2).

◀ Отдельно оцениваем вероятность избытка и недостачи; оба варианта симметричны, поэтому достаточно доказать, что

$$\mathrm{Pr}[m - (p_0 + \dots + p_{n-1}) > d] \le e^{-d^2/4n}.$$

Мы используем обычный приём: строим другую меру $\mu'$, для которой отношение $\mu'/\mu$ велико на всех последовательностях, попадающих в событие из левой части.
(Отношение $\mu'/\mu$ будет мартингалом, который велик, а именно, не меньше $e^{d^2/4n}$ на всех таких последовательностях.)

Поскольку мы хотим увеличения меры для последовательностей, в которых много единиц, то естественно, что в новой мере нужно условную вероятность единицы увеличить (по сравнению с $\mu$). А именно, если раньше после некоторого слова $x$ условные вероятности единицы и нуля были $p$ и $q$, то теперь мы положим их равными

$$p' = p + \epsilon pq, \quad q' = q - \epsilon pq,$$

где $\epsilon$ — некоторое положительное число, меньше $1/2$ (его мы выберем позже). Легко проверить, что $p'$ и $q'$ не выйдут за пределы отрезка $[0, 1]$.

Получаем новое распределение вероятностей на последовательностях нулей и единиц длины $n$. Во сколько раз оно отличается от исходного на некотором слове $x$ длины $n$? Каждый новый символ слова $x$ даёт множитель $p'/p$ (если это была единица) или $q'/q$ (если это был нуль), где $p, q, p', q'$ — условные вероятности единицы и нуля в исходной и изменённой мерах. Переходя к логарифмам, видим, что логарифм интересующего нас отношения равен сумме величин

$$\ln(p'/p) = \ln(1 + \epsilon q) \ge \epsilon q - (\epsilon q)^2 \ge \epsilon(1 - p) - \epsilon^2$$

или

$$\ln(q'/q) = \ln(1 - \epsilon p) \ge -\epsilon p - (\epsilon p)^2 \ge -\epsilon p - \epsilon^2$$

для всех букв слова $x$ (с соответствующими вероятностями $p$ и $q$); первый вариант для единицы и второй вариант для нуля. (Мы использовали неравенство $\ln(1+h) \ge h - h^2$, выполненное при всех $|h| \le 1/2$.)

Что получится, если сложить все величины? Помимо общего множителя $\epsilon$, в правой части будет число единиц $m$ (от каждого слагаемого $(1-p)$ по единице) минус сумма всех $p_i$, где $p_i$ — условная вероятность единицы на очередном месте в слове $x$, и ещё минус $n\epsilon^2$:

$$\ln \frac{p'(x)}{p(x)} \ge \epsilon(m - \sum p_i) - n\epsilon^2.$$

Для тех $x$, которые нас интересуют (у которых превышение больше $d$) имеем

$$\ln \frac{p'(x)}{p(x)} > \epsilon d - n\epsilon^2 = \epsilon(d - n\epsilon).$$

Это верно при всех $\epsilon \in (0, 1/2)$, поэтому выберем то из них, при котором правая часть наибольшая, а именно $\epsilon = d/2n$ (ясно, что случай $d > n$ можно не рассматривать, так как число единиц никогда не превосходит $n$, поэтому $\epsilon = d/2n < 1/2$).

Получаем, что

$$\ln \frac{p'(x)}{p(x)} > d^2/4n \quad \text{и} \quad \frac{p'(x)}{p(x)} > e^{d^2/4n},$$

что нам и требовалось. ►
(Поучительно посмотреть, какая оценка получается для простейшего случая, когда нули и единицы равновероятны. Вероятность того, что число единиц превосходит ожидаемое $n/2$ более чем на $2\sqrt{n}$, меньше $1/e$, а превышение более чем на $2k\sqrt{n}$ имеет вероятность не больше $1/e^k$. Видно, что наша оценка не оптимальная — теорема Муавра — Лапласа даёт немного лучше — но близка к ней, отличие лишь в коэффициенте в показателе экспоненты.)

Теперь можно повторить доказательство усиленного закона больших чисел с этой новой оценкой и получить такую теорему, верную для произвольной меры $\mu$ на пространстве $\Omega$:

**Теорема 199.** Для последовательности $\omega = \omega_0\omega_1\dots$, распределённой по мере $\mu$, почти наверное выполнено такое свойство:

$$ \lim_{n \to \infty} \left( \frac{m}{n} - \frac{p_0 + \dots + p_{n-1}}{n} \right) = 0, $$

где $m$ — число единиц среди $\omega_0, \omega_1, \dots, \omega_{n-1}$, а $p_i$ — условная вероятность появления единицы после $\omega_0\omega_1\dots\omega_{i-1}$.

В частности, из этой теоремы следует, что если испытания независимы, а вероятности успеха $p_i$ стремятся к некоторому пределу $p$, то с вероятностью единица предел частот равен $p$ (поскольку предел средних $(p_0 + \dots + p_{n-1})/n$ равен $p$).

Мы, однако, хотим большего — чтобы с вероятностью единица последовательность $\omega$ была случайной по Мизесу (в том или ином варианте), то есть чтобы не только для самой последовательности, но и для её «законно выбранных» подпоследовательностей предел частот равнялся $p$.

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

### 9.13.3. Закон больших чисел для подпоследовательностей

Докажем обобщение теоремы 198, включив туда правила выбора. В этой теореме мы рассматривали меру $\mu$ на пространстве $\Omega$ и соответствующие вероятности $p(x) = \mu(\Omega_x)$ и $p(1|x) = p(x1)/p(x)$. Для данной последовательности $\omega$ и данного числа $n$ можно рассмотреть две величины:

* число единиц среди первых $n$ битов $\omega$;

* сумму условных вероятностей единицы на первых $n$ позициях, то есть

$$ p(1|\Lambda) + p(1|\omega_0) + p(1|\omega_0\omega_1) + \dots + p(1|(\omega_0\dots\omega_{n-1})). $$

Теорема 198 гарантирует, что при любом $n$ две эти величины могут сильно отличаться лишь для небольшой (по мере $\mu$) части последовательностей $\omega$, а именно, $\mu$-мера множества тех последовательностей $\omega$, где разница превышает $d$, не больше $2e^{-d^2/4n}$.

Теперь мы добавляем в эту схему правило выбора $S_R$, задаваемое некоторым множеством $R$ (тех слов, после которых надо выбирать следующий член). В любой последовательности $\omega$ правило выбора $S_R$ указывает позиции $i_0, i_1, \dots$, в которых стоят члены выбираемой подпоследовательности $(S_R(\omega) = \omega_{i_0}\omega_{i_1}\dots)$. Теперь мы сравниваем
• число единиц среди первых $n$ выбранных членов;

• сумму условных вероятностей появления единицы на первых $n$ выбранных позициях, то есть

$$p(1|\omega_0\omega_1\dots\omega_{i_0-1}) + p(1|\omega_0\omega_1\dots\omega_{i_1-1}) + \dots + p(1|\omega_0\omega_1\dots\omega_{i_n-1}).$$

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

**Теорема 200.** При любых $R$ и $n$ вероятность (по мере $\mu$) того, что эти две величины отличаются на $d$, не превосходит $2e^{-d^2/4n}$.

Вообще говоря, для некоторых последовательностей $\omega$ выбранная подпоследовательность $S_R(\omega)$ содержит менее $n$ членов; такие $\omega$ не входят в событие, вероятность которого оценивается в этой теореме.

**Пример.** Рассмотрим произвольную меру и правило выбора, которое отбирает те члены последовательности, для которых условная вероятность появления единицы меньше 0,5. Тогда утверждение теоремы гарантирует, что доля единиц среди первых $n$ выбранных членов превышает 51% лишь с малой (экспоненциально убывающей с ростом $n$) вероятностью.

◀ Эта теорема также является простым следствием общего неравенства Азумы – Хёфдинга, для мартингалов в смысле теории вероятностей, но можно обойтись и без ссылки на него, действуя так же, как при доказательстве теоремы 198.

Теперь в формулировке теоремы нельзя ограничиться фиксированным числом битов в последовательности $\omega$ (поскольку выбранные $n$ членов могут быть сколь угодно далеко). Но можно доказать конечный вариант этой теоремы для последовательностей длины $N$, а затем по непрерывности меры устремить $N$ к бесконечности.

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

Доказанная теорема позволяет, следуя Ламбальгену [73], строить случайные по Мизесу – Чёрчу – Дэли последовательности. Вот как это делается.

Пусть $p_0, p_1, \dots$ — вычислимая последовательность вычислимых действительных чисел, вычислимо сходящаяся к числу $p \in (0, 1)$. (Вычислимая сходимость означает, что по данному $\varepsilon > 0$ можно алгоритмически указать то $N$, начиная с которого члены последовательности отстоят от предела меньше чем на $\varepsilon$; ясно, что тогда $p$ вычислимо.) Рассмотрим вычислимую меру $\mu$, соответствующую независимым испытаниям с вероятностями $p_i$.

**Теорема 201.** Всякая случайная в смысле Мартин-Лёфа по мере $\mu$ последовательность является случайной по Мизесу – Чёрчу – Дэли с пределом частот $p$.
◀ Пусть фиксированы некоторое (рациональное) $\varepsilon > 0$ и некоторое допустимое в смысле Чёрча-Дэли (вычислимое, возможно не всюду определённое) правило выбора $R$. Мы должны показать, что множество $U$ тех последовательностей, для которых применение этого правила даёт бесконечную последовательность и частота единиц в ней бесконечно много раз превышает $p + \varepsilon$, является эффективно нулевым. (Аналогично для частот, меньших $p - \varepsilon$.)

Фиксируем некоторое $n$ и рассмотрим множество $U_n$ тех $\omega$, для которых выбранная подпоследовательность имеет длину не менее $n$ и доля единиц среди первых $n$ членов больше $p + \varepsilon$. Это множество эффективно открыто (применяя правило выбора вдоль всех ветвей, мы можем перечислять все последовательности, продолжения которых попадают в $U_n$).

Теорема 200 даёт верхнюю оценку для множества $U_n$; для достаточно больших $n$ среднее арифметическое вероятностей не больше $p + \varepsilon/2$ (и граничу можно найти, пользуясь вычислимой сходимостью), и даваемая этой теоремой оценка экспоненциально убывает с ростом $n$. Поэтому можно покрыть $U$ перечислимым семейством интервалов сколь угодно малой меры (взяв все интервалы, образующие множества $U_N, U_{N+1}, U_{N+2}, \dots$ для достаточно большого $N$; напомним, что всякий элемент $U$ по определению входит в бесконечно много разных $U_n$). Следовательно, $U$ является эффективно нулевым и не может содержать случайной в смысле Мартин-Лёфа последовательности. ►

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

**Теорема 202.** Всякая случайная в смысле Мартин-Лёфа по мере $\mu$ последовательность является случайной по Мизесу-Колмогорову-Лавлэнду с тем же пределом частот $p$.

◀ Применение допустимого по Колмогорову-Лавлэнду правила $S_{F,G}$ к последовательности можно разбить на два этапа. Сначала с помощью функции $F$ выбирается подпоследовательность просмотренных членов (как выбранных, так и не выбранных). Затем с помощью функции $G$ производится выбор, и эта вторая часть соответствует применению допустимого по Чёрчу-Дэли правила.

Посмотрим на результат первого этапа. Как распределена получающаяся последовательность $\omega_F$, если исходная последовательность $\omega$ получается в результате независимых испытаний с вероятностью успеха $p_i$ в $i$-м испытании? Будем для начала считать, что функции $F$ и $G$ всюду определены.

Первый член $\omega_F$ имеет в $\omega$ заранее известный номер $n_0 = F(\Lambda)$ (наше правило начинает с просмотра этого члена). Вероятность появления единицы в начале $\omega_F$ есть, таким образом, $p_{n_0}$. Какой член будет вторым в $\omega_F$? Это уже зависит от результата первого просмотра. Соответственно для вероятности появления единицы на втором месте есть две возможности, соответствующие двум разным позициям в $\omega$. Общее правило: вероятность появления 1 после некоторого слова $x$ в $\omega_F$ равна $p_F(x)$, поскольку в этом случае следующим будет просмотрен член с номером $F(x)$. Заметим, что в силу ограничений на $F$ (никакой член не просматривается дважды) условные вероятности вдоль любой ветви образуют подпоследовательность последовательности $p_i$ без повторений, и потому среди них вне интервала $(p - \varepsilon/2, p + \varepsilon/2)$ окажется не больше, чем в исходной последовательности.
Это позволяет применить оценку теоремы 200 к последовательности $\omega_F$ и пра-
вилу выбора, задаваемому функцией $G$, как и в доказательстве теоремы 201.

Та же самая оценка верна и для частичных $F$ и $G$, поскольку от их произволь-
ного продолжения (вычислимого может не быть, но это и не нужно) оцениваемое
множество может только увеличиться.

Поскольку функции $F$ и $G$ вычислимы, множество тех последовательностей $\omega$, у которых правило выбора $S_{F,G}$ даёт подпоследовательность, начинающееся на данное слово $x$, может быть эффективно перечислено по $x$, так что после получения оценки на вероятность больших уклонений частоты от $p$ мы легко строим нужное нам эффективно нулевое множество. ►

**Замечание.** Можно было бы дать и более прямое доказательство теоремы 202. Вот одно из возможных рассуждений (заимствованное из [153]).

Пусть фиксированы некоторое (рациональное) $\varepsilon > 0$ и функции $F, G$, задающие допустимое в смысле Колмогорова–Лавлёнда правило выбора $R$. Мы должны показать, что множество $U$ тех последовательностей, для которых применение этого правила даёт бесконечную последовательность и частота единиц в ней бесконечно много раз превышает $p + \varepsilon$, является эффективно нулевым относительно меры $\mu$. (Аналогично для частоты, меньшей $p - \varepsilon$.)

Обозначим через $U_n$ множество тех последовательностей $\omega$, для которых $S_{F,G}(\omega)$ содержит не менее $n$ членов и частота единиц среди первых $n$ членов больше $p + \varepsilon$. Достаточно доказать, что ряд $\sum \mu(U_n)$ вычислимо сходится (где $\mu$ — рассматриваемая нами мера, соответствующая независимым испытаниям с вероятностями упеша $p_i$).

Обозначим через $\alpha_{n,k}(r_1, \dots, r_n)$ вероятность того, что в $n$ независимых испы-
таниях с вероятностями успеха $r_1, \dots, r_n$ случилось не менее $k$ успехов. Функция
$\alpha_{n,k}$ неубывает по всем своим аргументам (и, кстати, является полилинейной, то
есть многочленом от $r_i$ степени не более 1 по каждому аргументу). Кроме того,
$\alpha_{n,k} \le \alpha_{n,l}$ при $k \ge l$.

Мы утверждаем, что $\mu(U_n) \le \alpha_{n,k}(r_1, \dots, r_n)$, где $k = n(p+\varepsilon)$, а $r_i = i-j$ по
величине член последовательности $p_0, p_1, \dots$ ($r_1$ — максимальный, $r_2$ — макси-
мальный из оставшихся и т. д.; точнее, $r_1$ — точная верхняя грань всех $p_i$; $r_2$ —
точная верхняя грань минимумов пар $\min(p_i, p_j)$ при $i \ne j$ и так далее).

Покажем, как из этой оценки можно получить сходимость ряда $\mu(U_n)$. Очевидно, что $r_1 \ge r_2 \ge \dots$ и $\lim_{i \to \infty} r_i = p$. Заменим те $r_i$, которые больше $p+\varepsilon/2$, на единицу (пусть их количество равно $s$), а остальные — на $p+\varepsilon/2$. Получим, что

$$
\mu(U_n) \le \alpha_{n-s,k-s} (p + \varepsilon/2, \dots, p + \varepsilon/2),
$$

так что мы свели дело к оценке уклонений для случая постоянных вероятностей, который мы уже многократно разбирали. (Важно отметить, что при больших $n$ отношение $(k-s)/(n-s)$ примерно равно $p+\varepsilon$ и заметно больше $p+\varepsilon/2$.)

Осталось доказать указанную оценку для $\mu(U_n)$. Можно представлять себе (как мы уже обсуждали), что члены последовательности написаны на карточках, лежащих лицом вниз, и что правило выбора говорит, какие карточки нужно перевернуть для просмотра и какие — для включения в выбранную подпоследовательность.
При этом сведения о том, какие карточки переворачивались, и что на них оказалось, записываются в протокол применения правила выбора к последовательности. Пусть $\pi$ — начальный отрезок такого протокола. Через $n(\pi)$ обозначим количество членов, включённых в подпоследовательность на отрезке $\pi$, а через $k(\pi)$ — количество единиц среди этих членов. Через $r_i(\pi)$ обозначим $i$-й по величине член последовательности, получаемой из $p_0, p_1, \dots$ выкидыванием членов, соответствующим перевёрнутым в ходе $\pi$ карточкам (независимо от того, были ли они включены в подпоследовательность или только просмотрены).

Через $\mu(U_n|\pi)$ обозначим условную вероятность события $U_n$ при условии того, что протокол применения правила выбора начинается на $\pi$. Мы докажем следующее обобщение интересующего нас неравенства: при $n(\pi) \le n$

$$ \mu(U_n|\pi) \le \alpha_{n-n(\pi),k-k(\pi)}(r_1(\pi), r_2(\pi), \dots) \quad (*) $$

(при пустом $\pi$ получаем интересующую нас оценку). Если $n(\pi) = n$, то это неравенство превращается в равенство (левая и правая части одновременно равны либо нулю, либо единице). Пусть $n(\pi) < n$ и $m$ — номер карточки, переворачиваемой сразу после $\pi$ (если такой нет, то $\mu(U_n|\pi) = 0$). Тогда

$$ \mu(U_n|\pi) = p_m\mu(U_n|\pi_1) + (1-p_m)\mu(U_n|\pi_0), $$

где $\pi_0$ и $\pi_1$ — протоколы, получаемые добавлением к $\pi$ информации о нуле (единице) на $m$-й карточке. Покажем, что если доказываемое нами неравенство (*) верно для $\pi_0$ и $\pi_1$, то оно верно и для $\pi$. В самом деле, тогда $\mu(U_n|\pi)$ не превосходит

$$ p_m \alpha_{n-n(\pi_1),k-k(\pi_1)}(r_1(\pi_1), \dots) + (1-p_m) \alpha_{n-n(\pi_0),k-k(\pi_0)}(r_1(\pi_0), \dots). \quad (**) $$

Если $m$-я карточка была выбрана только для просмотра, то $n(\pi_0) = n(\pi_1) = n(\pi)$ и $k(\pi_0) = k(\pi_1) = k(\pi)$, и остаётся воспользоваться монотонностью $\alpha_{n,k}$ и тем, что $r_i(\pi_0) = r_i(\pi_1) \le r_i(\pi)$. Если же $m$-я карточка включена в подпоследовательность, то $n(\pi_0) = n(\pi_1) = n(\pi) + 1$, $k(\pi_0) = k(\pi)$ и $k(\pi_1) = k(\pi) + 1$, а выражение (**) равно

$$ \alpha_{n-n(\pi),k-k(\pi)}(p_m, r_1(\pi_1), r_2(\pi_2), \dots) $$

(заметим, что $r_i(\pi_1) = r_i(\pi_0)$) и тем самым не превосходит

$$ \alpha_{n-n(\pi),k-k(\pi)}(r_1(\pi), r_2(\pi), \dots). $$

Это завершает доказательство неравенства (*) в том случае, когда все начальные отрезки протоколов $\pi$ с $n(\pi) = n$ имеют ограниченную длину. Если же это не так, то приведённые рассуждения позволяют получить оценку для $\mu(U_{n,t}|\pi)$, где $U_{n,t}$ — множество тех последовательностей, для которых после не более чем $t$ переворачиваний карточек будет выбрана подпоследовательность длины не меньше $n$ с числом единиц (в начальном отрезке длины $n$) не менее $k$. Остаётся лишь перейти к пределу при $t \to \infty$.
9.13.4. Примеры

Теперь уже легко построить примеры случайных по Мизесу – Колмогорову – Лавлэнду последовательностей с различными патологическими свойствами.

**Теорема 203.** (а) Существует случайная по Мизесу – Колмогорову – Лавлэнду последовательность с частотой $1/2$, не случайная по Мартин-Лёфу относительно равномерной меры.

(б) Существует случайная по Мизесу – Колмогорову – Лавлэнду последовательность с частотой $1/2$, любой начальный отрезок которой содержит не меньше нулей, чем единиц.

(в) Существует случайная по Мизесу – Колмогорову – Лавлэнду последовательность с частотой $1/2$, из которой с помощью допустимого по Мизесу – Колмогорову – Лавлэнду (и даже по Чёрчу) правила выбора получается не случайная по Мизесу – Колмогорову – Лавлэнду последовательность.

(г) Существует случайная по Мизесу – Чёрчу – Дэли последовательность, становящаяся неслучайной по Мизесу – Чёрчу после вычислимой перестановки.

▲ (а) Рассмотрим вычислимую последовательность рациональных чисел из интервала $(0, 1)$, которая сходится к $1/2$, но медленно, например,

$$p_i = \frac{1}{2} - \frac{1}{\sqrt{i+5}}$$

(число 5 добавлено, чтобы $p_i$ были положительны). Рассмотрим (вычислимую) меру $\mu$, соответствующую независимым испытаниям с вероятностями успеха $p_i$.

Поскольку ряд $\sum (p_i - 1/2)^2$ расходится, никакая случайная по Мартин-Лёфу (относительно меры $\mu$) последовательность $\omega$ не будет случайной по Мартин-Лёфу относительно равномерной меры (теорема 197). С другой стороны, любая такая последовательность будет случайной по Мизесу – Колмогорову – Лавлэнду с предельной частотой $1/2$ (теорема 202).

(б) Это утверждение можно доказать аналогично предыдущему, только нужно взять последовательность $p_i$, ещё медленнее стремящуюся к пределу $1/2$. Пусть, например,

$$p_i = \frac{1}{2} - \frac{1}{\log(i+5)}.$$

Какова вероятность (по мере $\mu$) события «начальный отрезок длины $n$ содержит меньше нулей, чем единиц»? Другими словам, насколько вероятно, что частота единиц в этом начальном отрезке больше $1/2$? По теореме 198 эта вероятность (обозначим её $\delta_n$) не больше $e^{-n/O(\log^2 n)}$ (граница $d$ в этой теореме есть примерно $n/O(\log n)$, и $d^2/4n = n/O(\log^2 n)$). Ряд $\sum_n \delta_n$ сходится, и поэтому для некоторого $N$ остаточный член ряда меньше единицы, и тем самым вероятность события «все начальные отрезки, имеющие длину $N$ и более, содержат не меньше нулей, чем единиц» положительна. Множество положительной $\mu$-меры обязано содержать хотя бы одну случайную в смысле Мартин-Лёфа (относительно меры $\mu$) последовательность, поэтому существует случайная в смысле Мартин-Лёфа относительно меры $\mu$ последовательность, у которой все начальные отрезки, начиная с длины $N$, содержат не меньше нулей, чем единиц. Легко понять, что заменив первые $N$ членов
<figure><img src="image_28.png" /><figcaption>Рис. 9.2. Участок номер $k$: вероятности.</figcaption></figure>

на нули, мы получим случайную по Мартин-Лёфу относительно меры $\mu$ последовательность, у которой все начальные отрезки содержат не меньше нулей, чем единиц. Остаётся сослаться на теорему 202.

(в) И здесь нужный пример, как выяснил Меркле [101], доставляет последовательность, случайная относительно меры $\mu$, соответствующей независимым испытаниям с вероятностью успеха $p_i$. Однако $p_i$ будут устроены некоторым более сложным образом. Разобьём последовательность на участки; $k$-й по счёту участок состоит из одного члена, для которого вероятность равна $1/2$, и двух кусков одинаковой (и достаточно большой) длины $n_k$. В первом из них вероятности одинаковы и чуть больше $1/2$, а во втором — одинаковы и чуть меньше $1/2$ (рис. 9.2).

При этом $\varepsilon_k$ положительно и стремится к нулю с ростом $k$, но достаточно медленно. Точнее говоря, нам нужно такое соотношение между $n_k$ и $\varepsilon_k$: вероятность того, что среди $n_k$ независимых испытаний, в каждом из которых вероятность единицы равна $\frac{1}{2} + \varepsilon_k$, будет больше единиц, чем нулей, не меньше $1 - 2^{-(k+3)}$. (Этого несложно добиться для любых $\varepsilon_k$, если взять $n_k$ достаточно большими.)

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

Следовательно, существует случайная по Мартин-Лёфу (относительно построенной нами меры $\mu$) последовательность $\omega$ с таким дисбалансом. По теореме 202 она будет случайной по Мизесу – Колмогорову – Лавлэнду.

Покажем теперь, как использовать дисбаланс, чтобы построить (допустимое по Чёрчу) правило выбора, выбирающее из $\omega$ неслучайную подпоследовательность $\omega'$. Правило это совсем простое: первый член каждого участка («ключ») выбирается всегда, а в зависимости от его значения (0 или 1) выбирается целиком левый кусок (без правого) или целиком правый (без левого).

Почему $\omega'$ не будет случайна по Мизесу – Колмогорову – Лавлэнду? Это совсем просто: условие дисбаланса позволяет восстановить значение ключа по числу единиц в следующем за нём куске длиной $n_k$. (Мы сначала читаем «в порядке информации» $n_k$ членов, идущих за ключом, а потом отгадываем значение ключа.)

Это доказывает утверждение (в). Попутно можно заметить, что последовательность $\omega'$ случайна по Мизесу – Чёрчу – Дэли (поскольку двукратное применение допустимого по Чёрчу – Дэли правила сводится к однократному). С другой стороны, если мы подвергнем $\omega'$ вычислимой перестановке членов, переместив ключ
в позицию после управляемого им участка, то получится последовательность, не случайная по Мизесу – Чёрчу. Утверждение (г) доказано. ►

Заметим, что эта теорема в значительной степени дискредитирует наши уточнения случайности в стиле Мизеса. Дело в том (такое свойство коллективов отмечал ещё сам Мизес), что применение допустимого правила выбора к коллективу должно давать коллектив. Утверждение (в) показывает, что определение Мизеса – Колмогорова – Лавлэнда этим свойством, увы, не обладает. Определения с монотонными правилами (Мизеса – Чёрча и Мизеса – Чёрча – Дэли) этим свойством обладают (двукратное применение монотонных правил сводится к однократному), но зато неустойчивы относительно вычислимых перестановок, что тоже нехорошо.

**278** Докажите, что применение допустимого по Мизесу – Колмогорову – Лавлэнду правила к случайной по Мизесу – Колмогорову – Лавлэнду последовательности даёт случайную по Мизесу – Чёрчу – Дэли последовательность.

**279** Покажите, что существует случайная по Мизесу – Колмогорову – Лавлэнду последовательность (с частотой 1/2), не случайная даже по Курпу. [Указание. Возьмём случайную по двинутой мере последовательность: для неё один из мартингалов, построенных в доказательстве теоремы 197, ограничен, поэтому второй имеет вычислимую стремящуюся к бесконечности нижнюю оценку.]

Приведённые в этом разделе примеры показывают, что определение случайности по Мизесу – Колмогорову – Лавлэнду, видимо, накладывает слишком слабые требования на последовательность. То же самое можно сказать и про определение случайности относительно вычислимых мартингалов. Возникает естественный вопрос: что будет, если скомбинировать эти определения, то есть разрешить играть с последовательностью битов, написанных на карточках, переворачивая карточки в произвольном порядке (по выбору игрока) и ставя любую часть капитала на тот или иной исход (алгоритмически)? Легко видеть, что получится класс последовательностей (их иногда называют «непредсказуемыми»; английское название – Kolmogorov – Loveland random sequences), содержащий все случайные по Мартин-Лёфу последовательности, но до сих пор так и не выяснено, совпадают ли эти два класса. Можно заметить ещё, что для немонотонных мартингалов не имеет значения, являются ли они всюду определёнными (применимо то же соображение Меркле, что и в теореме 191, с. 326).

В заключение попытаемся резюмировать соотношения между рассмотренными определениями случайности (рис. 9.3). У нас есть две линии последовательно ослабляющихся определений: одна линия (игровая, восходящая к Виллю) говорит о мартингалах, другая (частотная, восходящая к Мизесу) — о правилах выбора подпоследовательностей. Обе они начинаются с определения Мартин-Лёфа (которое равносильно определению с перечислимыми мартингалами) и определения с немонотонными вычислимыми мартингалами, которое то ли более слабое, то ли эквивалентно (как мы только что говорили). Правая колонка соответствует уменьшающимся классам допустимых правил выбора. Левая колонка соответствует усиливающимся требованиям к выигрышу на неслучайных последовательностей (см. раздел 9.9, теорема 183 и задача 271). Отсюда сразу видно, что соответствующие классы последовательностей возрастают (пока что нестрого) сверху вниз.
Чтобы понять, почему других стрелок (кроме нарисованных на картинке и их следствий, а также, возможно, стрелки с вопросом) нет, посмотрим на связи между колонками. Как мы видели, из случайности по Мизесу – Колмогорову – Лавлэнду не следует даже случайность по Курцу (см. задачу 279), поэтому ни из какого утверждения правой колонки не следует никакое утверждение левой.

Слева направо: из случайности относительно частичных вычислимых мартингалов следует случайность по Мизесу – Чёрчу – Дэли (теорема 190, с. 325), из случайности относительно вычислимых мартингалов следует случайность по Мизесу – Чёрчу (теорема 182, с. 312), а из случайности по Шнорру вытекает усиленный закон больших чисел (задача 92, с. 83). Но более сильные утверждения уже выwesti нельзя: из случайности по Курцу не вытекает закон больших чисел (задача 92, с. 83), из случайности по Шнорру не следует случайность по Мизесу – Чёрчу (задача 270, с. 318), из случайности относительно вычислимых мартингалов не следует случайность по Мизесу – Чёрчу – Дэли, поскольку в первом случае возможен O(log n)-рост сложности для начал длины n (теорема 182, с. 312), а во втором – нет (теорема 188, с. 322); наконец, из случайности относительно частичных вычислимых мартингалов не следует случайность по Мизесу – Колмогорову – Лавлэнду, поскольку в первом случае возможна сублинейная сложность начальных отрезков (теорема 190, с. 325), а во втором нет (теорема 193, с. 328).

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

<figure><img src="image_29.png" /><figcaption>Рис. 9.3. Соотношения между разными определениями случайности.</figcaption></figure>
# 10. Неравенства для энтропии, сложности и размера

## 10.1. Постановка задачи и результаты

Первой публикацией Колмогорова, где давалось определение сложности конечного объекта, была статья «Три подхода к определению понятия «количество информации»» [63]. Эти три подхода назывались там комбинаторным, вероятностным и алгоритмическим.

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

Мы уже приводили некоторые результаты о связи этих трёх подходов. Например, теорема 8 (с. 29) связывает комбинаторный и алгоритмический подходы, будучи уточнением такого (абсурдного при буквальном понимании) утверждения: «слово х имеет сложность меньше $n$, если и только если оно принадлежит множеству из менее чем $2^n$ элементов». С другой стороны, результаты раздела 7.3 связывают колмогоровскую сложность и шенноновскую энтропию.

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

Пусть $x_1, \dots, x_n$ — двоичные слова. Для каждого непустого множества индексов $I \subset \{1, 2, \dots, n\}$ рассмотрим набор слов с индексами из $I$, который мы будем обозначать $x_I$, и его колмогоровскую сложность. Например, при $n=3$ имеется 7 таких наборов и, соответственно, 7 сложностей:

$$KS(x_1), KS(x_2), KS(x_3), KS(x_1, x_2), KS(x_1, x_3), KS(x_2, x_3), KS(x_1, x_2, x_3).$$

Несколько примеров линейных неравенств, их связывающих:

$$\bullet KS(x_1, x_2) \le KS(x_1) + KS(x_2) + O(\log N);$$

$$\bullet KS(x_1, x_2, x_3) \le KS(x_1) + KS(x_2, x_3) + O(\log N);$$
$$ \bullet \ KS(x_1, x_2, x_3) + KS(x_1) \le KS(x_1, x_2) + KS(x_1, x_3) + O(\log N); $$

$$ \bullet \ 2KS(x_1, x_2, x_3) \le KS(x_1, x_3) + KS(x_2, x_3) + KS(x_1, x_2) + O(\log N) $$

(мы предполагаем, что $x_1, x_2, x_3$ — слова длины не больше $N$).

Общий вид линейного неравенства для сложностей:

$$ \sum_{I} \lambda_{I} KS(x_{I}) \le O(\log N) $$

(суммирование по всем непустым подмножествам множества $\{1, \dots, n\}$, коэффициенты $\lambda_I$ могут быть любого знака; предполагается, что все слова имеют длину не больше $N$).

Нас интересует, какие неравенства такого вида верны, то есть, говоря более формально, при каких наборах действительных чисел $\lambda_I$ найдётся такое число $c$, что

$$ \sum_{I} \lambda_{I} KS(x_{I}) \le c \log N $$

для любого $N$ и для любых слов $x_1, \dots, x_n$ длины не больше $N$. Ответ на этот вопрос неизвестен, есть лишь некоторые частичные результаты.

Первый из них (доказанный А. Ромащенко) говорит, что неравенство для сложностей верно тогда и только тогда, когда верно неравенство для шенноновских энтропий с теми же коэффициентами. Оно получается, если вместо слов $x_1, \dots, x_n$ рассматривать случайные величины $\xi_1, \dots, \xi_n$ с произвольным совместным распределением:

$$ \sum_{I} \lambda_{I} H(\xi_{I}) \le 0. $$

Здесь $\xi_I$ — случайная величина, составленная из величин $\xi_i$ при $i \in I$, или, другими словами, проекция случайного вектора $\langle \xi_1, \dots, \xi_n \rangle$ на $I$-координаты.

В одну сторону это сразу же вытекает из результатов раздела 7.3: теорема 147 (с. 256) говорит, что энтропия есть математическое ожидание сложности, и если линейное неравенство верно для сложностей, то оно верно и для их математических ожиданий (с нулём в правой части, поскольку при $N \to \infty$ отношение $O(\log N)/N$ стремится к нулю).

Более подробно. Пусть величина $\xi_i$ принимает значения в множестве $X_i$. Тогда значение $\xi = \langle \xi_1, \dots, \xi_n \rangle$ можно изобразить в виде столбца высот $n$. Готовься применить теорему 147, для произвольного $N$ рассмотрим $N$ независимых величин, имеющих то же распределение, что и $\xi$. Вместе они образуют величину $\xi^N$, значениями которой являются прямоугольные таблицы шириной $N$ и высотой $n$. По теореме 147 математическое ожидание сложности такой таблицы есть $NH(\xi) + O(\log N)$ (в этой теореме речь шла о префиксной сложности при условии $N$, но с точностью до $O(\log N)$ это не играет роли).

Такую таблицу можно также читать по строкам, рассматривая её как набор из $n$ строк, каждая из которых есть слово длины $N$ в соответствующем алфавите. При этом теорему 147 не обязательно применять ко всем строкам: можно оставить лишь строки с номерами из некоторого множества $I \subset \{1, 2, \dots, n\}$. Математическое ожидание сложности этой части таблицы будет $NH(\xi_I) + O(\log N)$.
Если неравенство

$$ \sum_I \lambda_I KS(x_I) \le O(\log N) $$

справедливо для любых слов $x_1, \dots, x_n$, то оно справедливо и для строк нашей таблицы. Поэтому, переходя к математическим ожиданиям, имеем

$$ \sum_I \lambda_I NH(\xi_i) \le O(\log N). $$

Левая часть равна

$$ \left( \sum_I \lambda_I H(\xi_i) \right) \cdot N, $$

поэтому это возможно лишь при

$$ \sum_I \lambda_I H(\xi_i) \le 0, $$

что и требовалось.

Более сложен обратный переход (если неравенство верно для энтропий, то оно верно и для сложностей с логарифмической точностью). Здесь надо, начав с неготорого набора слов $x_1, \dots, x_n$, построить набор случайных величин $\xi_1, \dots, \xi_n$ так, чтобы энтропии этих величин и их комбинаций были близки к соответствующим сложностям. Это делается с помощью предложенного А. Ромащенко метода «типизации»: мы рассматриваем множество всех наборов $x'_1, \dots, x'_n$, которые имеют не большие сложности и условные сложности, чем $x_1, \dots, x_n$, и затем рассматриваем случайный элемент этого множества. Подробности см. ниже, в разделе 10.6 (теорема 212).

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

$$ KS(x_1, x_2) \le KS(x_1) + KS(x_2) + O(\log N) $$

и попытаемся понять, что ему соответствует при комбинаторном подходе. Пусть $X_1$ и $X_2$ — конечные множества, из которых берутся сообщения $x_1$ и $x_2$, а $A \subset \subset X_1 \times X_2$ — множество возможных пар сообщений. Тогда для пары $\langle x_1, x_2 \rangle$ возможно $|A|$ вариантов (здесь $|A|$ — число элементов в множестве $A$). Для первой компоненты $x_1$ число возможностей равно числу элементов в первой проекции множества $A$ (в множестве тех $x_1$, для которых $\langle x_1, x_2 \rangle \in A$ при некотором $x_2 \in X_2$). Обозначая это число $m(1)$, а размер проекции на вторую ось $m(2)$, можно записать комбинаторный аналог рассматриваемого неравенства:

$$ \log |A| \le \log m(1) + \log m(2) $$

или, в мультипликативной форме,

$$ |A| \le m(1)m(2) $$
(размер множества не больше произведения размеров его проекций, что очевидно).

Менее очевидное неравенство получается из другого неравенства для сложностей (теорема 26; аналогичное неравенство для энтропий составляет содержание задачи 230):

$$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) + O(\log N).$$

Действуя по аналогии, можно предположить, что для любого подмножества А картова произведения $X_1 \times X_2 \times X_3$ справедливо неравенство:

$$2 \log |A| \le \log m(1, 2) + \log m(1, 3) + \log m(2, 3)$$

(здесь $m(i, j)$ — число элементов в проекции множества А на оси $i$ и $j$, рис. 10.1). В мультипликативной записи:

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

<figure><img src="image_30.png" /><figcaption>Рис. 10.1. Три проекции.</figcaption></figure>

И действительно, это не только верно, но может быть выведено из неравенства для сложностей с помощью следующего простого рассуждения. Рассмотрим произвольное натуральное $N$ и множество $A^N$. Изображая элемент $\langle x_1, x_2, x_3 \rangle \in A$ в виде столбца высоты 3, мы представляем элемент $A^N$ как таблицу ширины $N$ и высоты 3. Таких таблиц имеется $|A|^N$, и потому среди них есть таблицы сложности не меньше $\log(|A|^N) = N \log |A|$. Но каждую такую таблицу можно считать тройкой строк $\bar{x}_1, \bar{x}_2, \bar{x}_3$ (каждая из трёх строк имеет длину $N$) и применить неравенство для сложностей:

$$2 \mathrm{KS}(\bar{x}_1, \bar{x}_2, \bar{x}_3) \le \mathrm{KS}(\bar{x}_1, \bar{x}_2) + \mathrm{KS}(\bar{x}_1, \bar{x}_3) + \mathrm{KS}(\bar{x}_2, \bar{x}_3) + O(\log N).$$
Далее можно оценить каждое слагаемое: например, пара $\langle \bar{x}_1, \bar{x}_2 \rangle$, которую можно представить таблицей ширины $N$ и высоты $2$, представляет собой набор из $N$ столбцов, каждый из которых принадлежит проекции $A$ на первую и вторую координату. Для каждого столбца имеется $m(1, 2)$ возможностей, а для всей таблицы $m(1, 2)^N$ возможностей, и потому её сложность (при известных $N$ и $A$) не превосходит $N \log m(1, 2) + O(1)$. Множество $A$ не зависит от $N$, а сложность $N$ есть $O(\log N)$, поэтому в итоге мы получаем

$$2N \log |A| \le N \log m(1, 2) + N \log m(1, 3) + N \log m(2, 3) + O(\log N),$$

что при $N \to \infty$ даёт нам искомое неравенство

$$2 \log |A| \le \log m(1, 2) + \log m(1, 3) + \log m(2, 3).$$

**280** Докажите то же неравенство, исходя из неравенства

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

[Указание: рассмотрите тройку случайных величин, равномерно распределённую в множество $A$, и воспользуйтесь тем, что энтропия любой случайной величины с $k$ значениями не превосходит $\log k$.]

**281** Докажите то же неравенство непосредственно, без использования сложностей или энтропий. [Указание. Его можно вывести из неравенства теоремы 164.]

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

$$KS(x_1, x_2) \le KS(x_1) + KS(x_2 | x_1)$$

соответствует (очевидное) неравенство

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

выполненное для произвольного множества $A \subset X_1 \times X_2$, если под $m(1, 2)$ понимать число элементов в $A$, под $m(1)$ понимать число элементов в проекции $A$ на первую координату, а под $m(2|1)$ понимать максимальный размер сечения множества $A$, получаемого фиксацией первой координаты.

[Объясним, почему именно это неравенство естественно считать комбинаторным аналогом неравенства для сложностей. «Комбинаторное количество информации» в $x_1$ есть $\log m(1)$; при фиксированном $x_1$ у нас имеется не более $m(2|1)$ возможных сообщений $x_2$, и потому количество информации в $x_2$ при известном $x_1$ (согласно комбинаторному подходу) не превосходит $\log m(2|1)$. А количество информации в паре $\langle x_1, x_2 \rangle \in A$ считается равным $\log A = \log m(1, 2)$.]
**282** Покажите, что любому линейному неравенству вида $L \le R$ с неотрицательными коэффициентами, справедливому для сложностей (безусловных и условных), в котором в левой части $L$ стоит только одно слагаемое, соответствует (описанным образом) истинное комбинаторное неравенство.

Неравенства такого вида, в которые не входят условные сложности, можно полностью описать. Рассмотрим неравенство

$$KS(x_1, \dots, x_n) \le \sum_{I} \lambda_I KS(x_I) + O(\log N),$$

где в правой части все коэффициенты неотрицательны, а сумма берётся по неполным множествам, не совпадающим с полным множеством индексов $\{1, 2, \dots, n\}$. (Ясно, что только такие неравенства представляют интерес: если в левой части отсутствует некоторое слово, то это слово можно удалить и из правой части: при его замене на пустое слово сложность правой части только уменьшится.)

**Теорема 204.** Это неравенство выполнено тогда и только тогда, когда для любого $i \in \{1, 2, \dots, n\}$ сумма коэффициентов в правой части при членах, собрывающих $i$, не меньше единицы.

◀ Если сумма коэффициентов при $x_i$ меньше единицы, то неравенство не выполняется даже в случае, когда все остальные слова (кроме $x_i$) пусты.

С другой стороны, пусть при всех $i$ сумма коэффициентов в правой части не меньше единицы. Разложим каждое слагаемое в сумму, заменив, скажем,

$$KS(x_1, x_2, x_3, \dots, x_n)$$

на

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

при этом во всех случаях будем использовать один и тот же порядок (возрастание индексов). Посмотрим отдельно на члены вида $KS(x_i|\dots)$ с различными условиями. В левой части в качестве условия используются все предыдущие слова $x_1, \dots, x_{i-1}$, а в правой части могут быть разные подмножества этого условия, но от уменьшения условия сложность лишь возрастает. Остаётся вспомнить, что по предположению сумма коэффициентов не меньше единицы. ▶

**283** Покажите, что для префиксной сложности неравенства, о которых идёт речь в только что доказанной теореме, выполнены с точностью до $O(1)$ (без логарифма длин). [Указание. Приведённое рассуждение показывает, что это неравенство является линейной комбинацией базисных неравенств, которые верны для префиксной сложности с точностью до $O(1)$ (теорема 70, с. 128). В самом деле, если временно переопределить условную сложность, положив $KP(u|v)$ равным $KP(u,v) - KP(v)$, то неравенство типа $KP(z|x,y) \le KP(z)$ сводится к базисному неравенству.]

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

$$KS(x_1) + KS(x_1, x_2, x_3) \leq KS(x_1, x_2) + KS(x_1, x_3) + O(\log N).$$

По аналогии с предыдущим можно было бы предположить, что для произвольного множества $A \subset X_1 \times X_2 \times X_3$ выполнено неравенство

$$m(1) \cdot m(1, 2, 3) \leq m(1, 2) \cdot m(1, 3).$$

Однако это не так. Это неравенство верно (и обращается в равенство) для любого «параллелепипеда» $a \times b \times c$: в этом случае $m(1) = a$, $m(1, 2, 3) = abc$, $m(1, 2) = ab$ и $m(1, 3) = ac$. Но если мы добавим к параллелепипеду $a \times b \times c$ с большими $a, b, c$ ещё и параллелепипеда $a' \times 1 \times 1$, взяв $a'$ много больше $a$, но много меньше $ab$ и $ac$, то от такого добавления $m(1, 2)$, $m(1, 3)$ и $m(1, 2, 3)$ изменятся мало, но $m(1)$ сильно возрастёт, и неравенство нарушится.

Другой пример. Рассмотрим обратное неравенство для сложности пары:

$$KS(x_1) + KS(x_2 | x_1) \leq KS(x_1, x_2) + O(1).$$

Как перевести его на комбинаторный язык? Неравенство

$$m(1) \cdot m(2 | 1) \leq m(1, 2)$$

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

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

## 10.2. Однородные множества

Напомним использованные нами обозначения. Пусть $A \subset X_1 \times \dots \times X_n$ — некоторое непустое подмножество декартова произведения $n$ конечных множеств $X_1, \dots, X_n$. Для каждого множества индексов $I \subset \{1, \dots, n\}$ можно рассмотреть проекцию $A$ на соответствующие координаты. Она является подмножеством произведения $\prod_{i \in I} X_i$. Число элементов в этой проекции мы будем обозначать $m_A(I)$. Помимо проекций, можно рассматривать и их сечения. Пусть $I$ и $J$ — два непересекающих множества индексов. Фиксируем произвольным образом $I$-координаты (выбрав некоторую точку в $\prod_{i \in I} X_i$) и рассмотрим множество всех $J$-координат точек из $A$ с заданными $I$-координатами. Таким образом каждой точке множества $\prod_{i \in I} X_i$ соответствует некоторое подмножество произведения $\prod_{j \in J} X_j$. Максимальный размер такого подмножества мы будем обозначать $m_A(J|I)$. (Если множество $A$ ясно из контекста, мы будем опускать индекс $A$ в этих обозначениях.)
Естественно считать, что $m(\emptyset) = 1$, а также $m(\emptyset | J) = 1$ при любом $J$. С другой стороны, $m(I | \emptyset)$ естественно положить равным $m(I)$.

Пусть, например, имеется некоторое множество $A \subset X_1 \times X_2$ (рис. 10.2).

<figure><img src="image_31.png" /><figcaption>Рис. 10.2. Плоское множество и его характеристики.</figcaption></figure>

Тогда $m_A(\{1\})$ — число элементов в проекции множества А на горизонтальную ось, $m_A(\{2\})$ — число элементов в проекции на вертикальную ось, $m_A(\{2\} | \{1\})$ — максимальное число элементов в вертикальных сечениях, а $m_A(\{1\} | \{2\})$ — в горизонтальных. Общее число элементов в множестве есть $m_A(\{1, 2\})$.

Имеет место очевидное неравенство:

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

(для краткости мы опускаем индекс А и фигурные скобки в множествах индексов). В самом деле, каждое из $m(1)$ вертикальных сечений содержит не более $m(2|1)$ элементов.

Для $n$-мерного множества аналогичное неравенство выглядит так:

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

В самом деле, для каждого из $m(1)$ возможных значений первой координаты есть не более $m(2|1)$ значений второй, для каждого из которых есть не более $m(3|1, 2)$ значений третьей и так далее. Порядок координат роли не играет:

$$m(k_1, \dots, k_n) \le m(k_1) \cdot m(k_2 | k_1) \cdot m(k_3 | k_1, k_2) \cdot \dots \cdot m(k_n | k_1, \dots, l_{n-1})$$

для любой перестановки $k_1, k_2, \dots, k_n$ чисел $1, 2, \dots, n$ (в левой части так или иначе записывается общее число элементов в множестве А).

Будем называть множество А однородным, если все эти неравенства (для любой перестановки $k_1, \dots, k_n$) обращаются в равенства. Простейший пример однородного множества — «параллелепипед», то есть произведение подмножеств $A_i \subset X_i$. Однако бывают и другие однородные множества. Например, шестиэлементное дву-
мерное множество на рис. 10.3 является однородным (все ненулевые сечения состоят из двух элементов, а проекции на обе оси — из трёх).

<figure><img src="image_32.png" /><figcaption>Рис. 10.3. Однородное множество.</figcaption></figure>

Пусть *I*, *J*, *K* — непересекающиеся множества индексов. Тогда для произвольного множества *A* выполнено неравенство

$$m(J \cup K | I) \le m(J | I) \cdot m(K | I \cup J)$$

(при фиксированных *I*-координатах есть не более $m(J|I)$ возможных значений *J*-координат, для каждого из которых есть не более $m(K|I \cup J)$ значений *K*-координат).

С помощью этого неравенства можно доказать ранее упоминавшее неравенство

$$m(k_1, \dots, k_n) \le m(k_1) \cdot m(k_2 | k_1) \cdot m(k_3 | k_1, k_2) \dots m(k_n | k_1, \dots, l_{n-1}),$$

группируя сомножители в правой части. Например, произведение

$$m(k_3 | k_1, k_2) \cdot m(k_4 | k_1, k_2, k_3)$$

не меньше

$$m(k_3, k_4 | k_1, k_2),$$

после чего произведение

$$m(k_2 | k_1) \cdot m(k_3, k_4 | k_1, k_2)$$

можно (не увеличивая) заменить на

$$m(k_2, k_3, k_4 | k_1)$$

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

$$m(J \cup K | I) \le m(J | I) \cdot m(K | I \cup J)$$

обращается в равенство для любых *I*, *J*, *K*, поскольку можно подобрать цепочку неравенств, в которой оно встречается. Равенство

$$m(J \cup K | I) = m(J | I) \cdot m(K | I \cup J)$$
можно считать определением однородных множеств (требуя его выполнения для
любых непересекающихся множеств индексов *I*, *J*, *K*).

**284** Докажите, что это свойство действительно равносильно однородности.

**285** Докажите, что проекция однородного множества на любое множество индексов является однородным множеством.

**286** Докажите, что сечение однородного множества (мы фиксируем одну координату и рассматриваем множество возможных значений остальных координат) является однородным множеством.

Однородные множества важны как источники случайных величин. Пусть $A \subset X_1 \times \dots \times X_n$ — произвольное множество. Рассмотрим случайную точку в $A$, принимающую все значения в $A$ с равной вероятностью. Её проекция на $i$-ю координату есть случайная величина $\xi_i$ со значениями в $X_i$.

**Теорема 205.** Множество $A$ однородно тогда и только тогда, когда для любого $I = \{i_1, \dots, i_k\}$ величина $\xi_I = \langle \xi_{i_1}, \dots, \xi_{i_k} \rangle$ принимает все свои значения с равными вероятностями.

◀ Пусть *I* — некоторое множество индексов, а *J* — его дополнение до полного
множества индексов {1, 2, ..., *n*}. Тогда равенство

$$
m(1, 2, \dots, n) = m(I) \cdot m(J|I)
$$

означает, что средний размер (непустого) сечения, получающегося фиксацией *I*-ко-
ординат, то есть *m(1, 2, ..., n)*/*m(I)*, равен его максимальному размеру *m(J|I)*,
то есть что все сечения одинаковы. А это и значит, что все значения случайной
величины *ξ*<sub>*I*</sub> равновероятны.

Напротив, пусть для некоторого множества А для любого множества индексов I
все значения случайной величины ξI равновероятны. Взяв I = {1, ..., n - 1}, мы
получаем, что все (непустые) сечения, получаемые фиксацией первых n - 1 коор-
динат, имеют одинаковый размер, и потому

$$
m(1, 2, \dots, n) = m(n|1, 2, \dots, n-1) \cdot m(1, 2, \dots, n-1). \quad (*)
$$

Кроме того, поскольку совместное распределение величин ξ₁, ξ₂, ..., ξₙ₋₁ равно-
мерно в проекции множества А на координаты 1, 2, ..., n − 1, то в этой проекции
мы имеем ту же картину: ξ₁, ..., ξₙ₋₁ суть случайные величины, получающиеся
проектированием на разные оси случайной точки некоторого множества, равномер-
но распределённой в этом множестве. Рассуждая по индукции, можно предпола-
гать, что это множество однородно, и тогда равенство (*) можно продолжить:

$$
m(1, 2, \dots, n) = \\
\qquad = m(n|1, 2, \dots, n-1) \cdot m(n-1|1, 2, \dots, n-2) \cdot \dots \cdot m(3|1, 2) \cdot m(2|1) \cdot m(1).
$$

Поскольку порядок координат мог быть любым, мы заключаем, что множество А
является однородным в смысле нашего определения. ►
**Следствие.** Для построенных таким образом величин $\xi_1, \dots, \xi_n$ энтропия на-бора $\xi_I$ равна $\log m(I)$ (при любом $I \subset \{1, 2, \dots, n\}$).

Отсюда мы заключаем, что

**Теорема 206.** Каждому неравенству для энтропий случайных величин соответствует неравенство, выполненное для размеров проекций однородных множеств.

Например, для однородного множества $A \subset X_1 \times X_2 \times X_3$ выполнено неравенство

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

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

В следующем разделе мы, следуя [27], докажем обратное к теореме 206 утверждение, для чего по данному набору случайных величин построим однородное множество, имеющее соответствующие размеры проекций.

## 10.3. Построение однородного множества

Пусть имеется некоторый набор случайных величин $\eta_1, \dots, \eta_n$ с конечным числом значений. Мы хотим построить однородное множество $A$, для которого размеры проекций соответствуют энтропиям величин $\eta_I$. Идеально было бы, чтобы

$$\log m_A(I) = H(\eta_I)$$

для всех $I \subset \{1, \dots, n\}$. Тогда можно было бы сразу заключить, что неравенство, верное для (логарифмов) размеров проекций однородных множеств, верно и для любых случайных величин.

Однако это, как легко понять, невозможно: энтропия вовсе не обязана быть логарифмом целого числа. Но если нас интересуют линейные неравенства, достаточно, чтобы энтропии были бы пропорциональны логарифмам проекций, и даже чтобы они были приблизительно (с малой ошибкой) пропорциональны им. Сейчас мы построим однородное множество для случая, когда вероятности всех значений для набора $\langle\eta_1, \dots, \eta_n\rangle$ рациональны. Ясно, что для неравенств рассматриваемого нами вида этого достаточно: по непрерывности любое неравенство, выполненное для случайных величин с рациональными вероятностями, верно и для любых случайных величин.

Итак, пусть имеется набор случайных величин $\eta_1, \dots, \eta_n$. Каждое его значение будем изображать столбцом высоты $n$, в котором сверху вниз записаны значения величин. Каждый столбец имеет некоторую (по предположению рациональную) вероятность. Приведя все эти вероятности к общему знаменателю $N$, можно составить таблицу из $N$ столбцов, в которой частота (доля) каждого столбца равна его вероятности как значения случайной величины $\langle\eta_1, \dots, \eta_n\rangle$.

Такую таблицу можно читать и «по строкам», тогда i-я строка есть слово длины $N$ в алфавите, буквами которого являются возможные значения величины $\eta_i$. Множество таких слов мы обозначим $X_i$ (длина $N$ у нас фиксирована, поэтому
мы её не указываем в обозначении). А вся таблица есть набор из $n$ слов длины $N$ (каждое в соответствующем алфавите), то есть элемент множества $X_1 \times \dots \times X_n$.

Рассмотрим теперь всевозможные таблицы, получающиеся из данной перестановкой столбцов. Другими словами, рассмотрим все таблицы ширины $N$, в которых частоты столбцов такие же, то есть соответствуют распределению вероятности для случайной величины. Получится некоторое подмножество $U$ множества $X_1 \times \dots \times X_n$. Оно и будет интересующим нас однородным подмножеством.

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

Это свойство останется верным, если из таблицы удалить некоторые строки. Следовательно, проекция случайной равномерно распределённой в $U$ точки на любой набор координат также равномерно распределена, так что множество является однородным.

Теперь надо найти размеры проекций. Для начала найдём размер самого множества. Пусть в нём имеется $m$ различных типов столбцов, которые встречаются с частотами $q_1, \dots, q_m$. Тогда общее число вариантов, которые можно получить перестановками столбцов, равно

$$ \frac{N!}{(q_1 N)!(q_2 N)! \dots (q_m N)!} $$

и его логарифм по формуле Стирлинга оценивается как

$$ Nh(q_1, \dots, q_m) + O(\log N), $$

где $h(q_1, \dots, q_m) = \sum q_i (-\log q_i)$ — шенноновская энтропия величины, принимающей $m$ значений с вероятностями $q_1, \dots, q_m$, то есть — в нашем случае — величины $\langle \eta_1, \dots, \eta_n \rangle$. Так что логарифм размера множества примерно в $N$ раз больше энтропии набора случайных величин. То же самое рассуждение применимо и к любой проекции этого множества и показывает, что логарифм размера проекции на множество индексов $I$ примерно в $N$ раз больше энтропии величины $\eta_I$.

Если теперь у нас есть линейное неравенство, справедливое для логарифмов проекций однородных множеств, то оно будет справедливо для множества $U$. Увеличивая $N$ (умножая его на большое целое число) и переходя к пределу, мы видим, что $O(\log N)/N$ стремится к нулю, и заключаем, что то же линейное неравенство верно и для энтропий любых $n$ случайных величин с рациональным распределением вероятностей. По непрерывности это верно и для любого (не обязательно рационального) распределения вероятностей. Приходим к такому утверждению [27]:

**Теорема 207** (Чен – Янг). Всякому неравенству для размеров проекций однородных множеств соответствует неравенство, выполненное для произвольных случайных величин.
10.4. Однородные множества и орбиты

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

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

Пусть имеется произвольная конечная группа G и конечные множества $X_1, \dots, X_n$. Пусть заданы действия группы G на каждом из $X_i$. Они вместе задают действие G на множестве $X_1 \times \dots \times X_n$. Рассмотрим произвольную точку $\langle x_1, \dots, x_n \rangle \in X_1 \times \dots \times X_n$ и орбиту U этой точки.

**Теорема 208.** Орбита *U* является однородным подмножеством множества
*X*₁ × ... × *X*ₙ.

◀ Подействуем на точку x = ⟨x₁, ..., xₘ⟩ случайным элементом группы G (считая все элементы равновероятными). Результат будет случайной величиной, значением которой являются точки из U. При этом все точки равновероятны. В самом деле, элементы группы, переводящие x в заданную точку y, образуют смежный класс при факторизации по стабилизатору точки x (подгруппе, состоящей из тех элементов G, которые оставляют точку x на месте), а все смежные классы имеют один и тот же размер.

Аналогичное утверждение верно и для любой части индексов, поэтому случай-
ный элемент множества *U* имеет равную вероятность спроектироваться в любую
точку проекции, и потому множество *U* является однородным. ►

Во что превращаются при этом неравенства для размеров проекций однородных
множеств? Размер орбиты *U* равен отношению размера *G* и размера стабилизатора
точки *x*. Этот стабилизатор есть пересечение стабилизаторов точек *x*₁, ..., *x*ₙ при
соответствующих действиях. Аналогичным образом размер проекции на индексы
из *I* равен отношению размера *G* и размера пересечения стабилизаторов для *x*ᵢ
при *i* ∈ *I*. Заметим, что любая подгруппа *H* группы *G* может быть стабилизатором
некоторого элемента при некотором действии (достаточно рассмотреть действие *G*
на множестве смежных классов по *H*). Поэтому любое неравенство для размеров
проекций однородных множеств превращается в неравенство, справедливое для лю-
бых подгрупп произвольной конечной группы.

Например, неравенство m(1, 2) ≤ m(1) · m(2) превращается в неравенство, вер-
ное для любых подгрупп H₁ и H₂ произвольной конечной группы G:

$$
\frac{|G|}{|H_1 \cap H_2|} \le \frac{|G|}{|H_1|} \cdot \frac{|G|}{|H_2|} \\
\text{или } |H_1 \cap H_2| \ge |H_1| \cdot |H_2| / |G|.
$$

А неравенство $m(1,2,3)^2 \le m(1,2)m(1,3)m(2,3)$ даёт неравенство

$$
|H_1 \cap H_2 \cap H_3|^2 \ge |H_1 \cap H_2| \cdot |H_1 \cap H_3| \cdot |H_2 \cap H_3| / |G|.
$$
Доказательство теоремы 207 показывает, что верно и обратное: всякому неравенству для размеров пересечений подгрупп (в котором они перемножаются в некоторых степениях) соответствует неравенство для случайных величин (поскольку мы можем приближать случайные величины с помощью орбит), а потому и для проекций однородных множеств. Получаем следующий удивительный результат [27]:

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

## 10.5. Почти однородные множества

Мы называли множество $A \subset X_1 \times \dots \times X_n$ однородным, если неравенство

$$m(k_1, \dots, k_n) \le m(k_1) \cdot m(k_2 | k_1) \cdot m(k_3 | k_1, k_2) \dots m(k_n | k_1, \dots, k_{n-1})$$

обращается в равенство для любой перестановки $k_1, \dots, k_n$ чисел $1, \dots, n$. Будем говорить, что множество с-однородно, если правая часть этого неравенства не более чем в с раз превосходит левую (для любой перестановки).

Таким образом, 1-однородные множества — это однородные множества в смысле старого определения.

Многие свойства однородных множеств переносятся (с «потерей точности») на с-однородные множества.

**Теорема 210.** Пусть множество А является с-однородным.

(а) Если $I, J, K$ — непересекающиеся множества индексов, то в неравенстве

$$m(J \cup K | I) \le m(J | I) \cdot m(K | I \cup J)$$

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

(б) Проекция с-однородного множества на любой набор координат с-однородна.

(в) Пусть $A'$ — подмножество множества А, составляющее в нём долю не менее $\varepsilon$. Тогда множество $A'$ является с/$\varepsilon$-однородным.

(г) Пусть $\xi$ — случайная величина, равномерно распределённая в А. Тогда её проекция $\xi_I$ на любое множество индексов I имеет энтропию не больше $\log m(I)$ и не меньше $\log m(I) - \log c$.

(д) Пусть $I$ и $J$ — непересекающиеся множества индексов. Тогда $H(\xi_J | \xi_I)$ не больше $\log m(J | I)$ и не меньше $\log m(J | I) - \log c$.

▲ (а) В правой части неравенства

$$m(k_1, \dots, k_n) \le m(k_1) \cdot m(k_2 | k_1) \cdot m(k_3 | k_1, k_2) \dots m(k_n | k_1, \dots, k_{n-1})$$

можно группировать сомножители, пользуясь неравенством

$$m(J | I) \cdot m(K | I \cup J) \ge m(J \cup K | I).$$
При этом произведение будет постепенно уменьшаться, пока правая часть не превратится в левую. Если исходное неравенство отличалось от равенства не более чем в с раз, то и на каждом шаге уменьшение будет не более чем в с раз, а порядок действий можно выбрать так, чтобы пройти через любую тройку *I*, *J*, *K*.

(б) По предположению

$$m(n|1, \dots, n-1) \cdot m(n-1|1, \dots, n-2) \cdots m(2|1) \cdot m(1) \le cm(1, \dots, n)$$

и это неравенство можно продолжить:

$$cm(1, \dots, n) \le cm(n|1, \dots, n-1) \cdot m(1, \dots, n-1).$$

Сокращая теперь на $m(n|1, \dots, n-1)$, получаем условие с-однородности для про-
екции на координаты $1, 2, \dots, n-1$ (порядок координат может быть любым, а не
только $1, 2, \dots, n$, как в нашем примере).

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

(г) Случайная величина $\xi_I$ принимает $m(I)$ значений, поэтому её энтропия не превосходит $\log m(I)$. С другой стороны, если $J = \{1, 2, \dots, n\} \setminus I$, то

$$m(I) \cdot m(J|I) \le cm(1, 2, \dots, n),$$

поэтому каждое значение величины $\xi_I$ имеет вероятность не больше

$$m(J|I)/m(1, 2, \dots, n) \le c/m(I),$$

и потому её энтропия не меньше $\log m(I) - \log c$.

(д) Сравним равенство

$$H(\xi_1, \dots, \xi_n) = H(\xi_n | \xi_1, \dots, \xi_{n-1}) + H(\xi_{n-1} | \xi_1, \dots, \xi_{n-2}) + \dots \\ \qquad \qquad \qquad \qquad \qquad \qquad \qquad + H(\xi_2 | \xi_1) + H(\xi_1)$$

с неравенством

$$\log m(1, \dots, n) \le \log m(n|1, \dots, n-1) + \log m(n-1|1, \dots, n-2) + \dots \\ \qquad \qquad \qquad \qquad \qquad \qquad \qquad + \log m(2|1) + \log m(1).$$

Левые части у них совпадают, поскольку $\xi$ равномерно распределена в множестве А. Каждая энтропия в правой части не превосходит соответствующего логарифма (условная энтропия есть математическое ожидание энтропии при данном значении условия, которая не больше логарифма соответствующего сечения). Кролме того, в силу однородности неравенство отличается от равенства не более чем на $\log c$. Отсюда следует, что каждая энтропия может отличаться от соответствующего логарифма не более чем на $\log c$. Переставляя и группируя члены подходящим образом, мы можем тем же способом доказать неравенство

$$\log m(J|I) - \log c \le H(\xi_J | \xi_I) \le \log m(J|I)$$

для произвольных непересекающихся множеств *I*, *J*. ►
Непосредственное следствие утверждений (г) и (д): если некоторое линейное неравенство выполнено для энтропий, то оно выполнено для логарифмов проекций и сечений с-однородных множеств с ошибкой не более $\lambda \log c$, где $\lambda$ — сумма абсолютных величин всех коэффициентов неравенства. (Чем больше с, тем менее однородно множество, и тем больше возможная ошибка.)

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

## 10.6. Метод типизации

Следующая теорема по любому набору слов $x_1, \dots, x_n$ строит почти однородное подмножество $A$ некоторого декартова произведения $X_1 \times X_2 \times \dots \times X_n$ конечных множеств, для которого $\log m(J|I) \approx KS(x_J | x_I)$ с логарифмической (от сложности слов) погрешностью. Вот точная формулировка.

**Теорема 211** (Ромашенко). Для всякого $n$ существует число $d$, при котором верно следующее утверждение: для любого числа $N > 1$ и любого набора слов $x_1, \dots, x_n$ сложности не более $N$ найдутся конечные множества $X_1, \dots, X_n$ и $N^d$-однородное подмножество $A \subset X_1 \times \dots \times X_n$, для которых

$$|\log m(J|I) - KS(x_J | x_I)| \le d \log N$$

для любых непересекающихся множеств $I, J \subset \{1, \dots, n\}$.

Заметим, что множества $X_i$ в этой теореме не очень по существу: можно говорить о конечном множестве $n$-ок произвольной природы с нужными размерами проекций. Отметим ещё, что странное условие $N > 1$ объясняется тем, что при $N = 1$ оценка $N^c$ не растёт с ростом $c$.

В доказательстве используется понятие сложностного вектора набора слов. А именно, сложностным вектором слов $x_1, \dots, x_n$ называется список всех сложностей $KS(x_I | x_J)$ для всех пар $(I, J)$ непересекающихся подмножеств множества индексов $\{1, \dots, n\}$. (Заметим, что этот вектор имеет экспоненциальное по $n$ число компонент: одних безусловных сложностей (при $J = \emptyset$) уже набирается $2^n - 1$, не считая пустого множества.) Будем обозначать сложностной вектор $\varkappa(x_1, \dots, x_n)$.

Для каждого набора слов $x_1, \dots, x_n$ рассмотрим множество $A(x_1, \dots, x_n)$ всех наборов $y_1, \dots, y_n$, у которых

$$\varkappa(y_1, \dots, y_n) \le \varkappa(x_1, \dots, x_n)$$

при покомпонентном сравнении векторов. При $n = 1$ это будет множество всех слов не большей сложности, чем $x_1$. При $n = 2$ мы рассматриваем все пары слов $y_1, y_2$, для которых

$$KS(y_1) \le K(x_1), \quad KS(y_2) \le K(x_2), \\ KS(y_1, y_2) \le K(x_1, x_2), \quad KS(y_1 | y_2) \le K(x_1 | x_2), \quad KS(y_2 | y_1) \le K(x_2 | x_1).$$

Множество $A(x_1, \dots, x_n)$ заведомо непусто: оно содержит набор $\langle x_1, \dots, x_n \rangle$. Мы хотим показать, что оно содержит достаточно много (примерно $2^{KS(x_1, \dots, x_n)}$) эле-