%%
%% А.Л.Семенов, Ан.А.Мучник
%% (A.L.Semenov, An.A.Muchnik)
%% version 22.12.2002
%%
%% codepage 866
%% Russified LaTeX2e, based on LaTeX2e 2001/06/01
%% Document Class: article 2001/04/21 v1.4e
%% Package: amsmath 2000/07/18 v2.13
%% Package: amssymb 1995/02/01 v2.2a
%% Package: amsthm 2000/10/26 v2.08
%% Package: russcorr 1996/03/24 (by S.Lvovski)
%%

\documentclass[12pt]{article}

\usepackage{amsmath,amssymb,amsthm}
\usepackage[indentheadings]{russcorr}
%% babel staff
%\usepackage[T2A]{fontenc}
%\usepackage[cp866]{inputenc}
%\usepackage[russian]{babel}


\newtheorem{thm}{Теорема}
\newcommand{\thmprimname}{Теорема}
\newtheorem*{thm_prim}{\thmprimname}
\newtheorem{claim}{Предложение}[thm]
\newtheorem{lem}{Лемма}
\newtheorem{prop}{Утверждение}
\newtheorem{statement}{Формулировка}
\theoremstyle{definition} \newtheorem{defn}{Определение}
\theoremstyle{remark} \newtheorem*{note}{Замечание}%[thm]
\renewcommand{\proofname}{Доказательство}


\newcommand*{\vct}[1]{\mathbf{#1}}
\newcommand*{\pair}[1]{\langle #1\rangle}
\newcommand*{\perems}[2]{#1_1,\dotsc,#1_{#2}}
\newcommand*{\Exp}[1]{\mathrm e^{#1}}

\newcommand{\rls}{\mathcal R}
\newcommand{\als}{\mathcal A}
\newcommand{\Dv}{\Delta}
\newcommand{\dv}{\delta}
\newcommand{\half}{\frac{1}{2}}
\newcommand{\lb}{\mathop{\rm lb}}

\newcommand{\nddash}{\nobreakdash--}

\renewcommand{\le}{\leqslant}
\renewcommand{\ge}{\geqslant}
\renewcommand{\epsilon}{\varepsilon}
\renewcommand{\phi}{\varphi}

%\let\?\relax

%\long\def\exclude#1{\relax}

\makeatletter
\def\@maketitle{%
  \newpage
  \null
  \vskip 2em%
  \begin{center}%
  \let \footnote \thanks
    {\LARGE \@title \par}%
    \vskip 1.5em%
    {\large
      \lineskip .5em%
      \begin{tabular}[t]{c}%
        \@author
      \end{tabular}\par}%
    \vskip .5em%
    {\itshape \@inst}%
    \vskip 1em%
    {\large \@date}%
  \end{center}%
  \par
  \vskip 1.5em}
\def\inst#1{\gdef\@inst{#1}}
\makeatother

\hfuzz=0.5pt
\tolerance=500

\author{Алексей Семенов\thanks{
        e-mail: alsemenov@mtu-net.ru,
        fax: +(095)9156963.}
        \and
        Андрей Мучник\thanks{
        e-mail: muchnik@lpcs.math.msu.ru,
        fax: +(095)9156963.}
       }

\inst{Институт новых технологий,\\
        109004, Москва, ул. Нижняя Радищевская, 10.}

\title{О роли закона больших чисел в
теории случайности\footnote{
Работа выполнена при поддержке
Российского фонда фундаментальных исследований,
гранты N~01-01-00505, N~02-01-10904,
N~02-01-22001 и
Совета поддержки научных школ при президенте РФ.}
}

\date{}

\begin{document}

\maketitle

\begin{abstract}
В первой части статьи решена проблема
уточнения условий существования
датчика случайных чисел,
поставленная А.~Н.~Колмогоровым в 1963 году
в~\cite{kolm}.


Колмогоровская теория сложности
впервые позволила строго определить
понятие случайности
индивидуальной последовательности нулей и единиц.
При этом для бесконечных последовательностей
речь ид\"ет о двузначном свойстве:
последовательность случайна или
последовательность неслучайна,
в то время как для конечных последовательностей
можно говорить только о непрерывном свойстве~---
мере их случайности.

Можно ли мерить случайность последовательности $\vct t$
по тому,
насколько выполнен закон больших чисел
во всех подпоследовательностях, полученных из $\vct t$
\glqq допустимым способом\grqq ?
Ситуация для бесконечных последовательностей
была изучена в~\cite{3avt}.

В качестве меры случайности (а точнее, неслучайности)
конечной последовательности мы рассматриваем
удельный дефект случайности $\delta$
(определение~\ref{def:alg_defect}).
Во второй части настоящей работы
показано, что функция
$\delta/\ln(1/\delta)$
характеризует связь между случайностью конечной
последовательности
и выполнением закона больших чисел.

\smallskip
\noindent{\bf Ключевые слова:}
сложность описания,
колмогоровская энтропия,
датчик случайных чисел,
допустимое правило выбора,
устойчивость частот,
дефект случайности.
\end{abstract}


\section*{Введение}

В 1930-е годы Андрей Николаевич Колмогоров
обосновал теорию вероятностей
с помощью теории меры.
В~\cite{kolm} он пишет об этом:
\glqq
теоретико-множественное обоснование теории
вероятностей \ldots
оказалось настолько эффективным с математической точки
зрения и с точки зрения практических приложений,
что многие исследователи
стали относиться  к философскому обоснованию
связи между математическими
результатами теории вероятностей
и их практическими применениями
как к чему-то второстепенному\grqq.

Однако сам Колмогоров считал вопрос об этом
обосновании принципиальным.
В 1962 году, во время пребывания в Индии,
он начал разрабатывать
новый подход к нему\footnote{
Первая публикация~\cite{kolm} появилась
в 1963 году
в индийском журнале
Sankhy\~a: The Indian Journal of Statistics.
}~---
теорию сложности описания.
За прошедшее время
начатые Колмогоровым исследования
выросли в очень богатую теорию,
имеющую важные связи
не только с теорией вероятностей,
но и с теорией алгоритмов, теорией кодирования,
теорией матроидов и другими областями математики.

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

Рассмотрим последовательность
независимых испытаний с двумя
равновероятными исходами $0$ и $1$.
Простейший и в то же время важнейший
признак случайности для последовательности
исходов~--- приблизительное равенство
количества нулей и
количества единиц.
Очевидно, одного этого требования недостаточно
(например, последовательность $0101010101\ldots$
по нашим представлениям неслучайна).
Однако если \emph{указанный признак выполняется
для всех последовательностей, получаемых из
исходной с помощью
\glqq допустимых\grqq{} правил выбора},
то такую последовательность уже
можно рассматривать как датчик случайных чисел.
Разумеется, понятие допустимого правила
должно быть математически уточнено\footnote{
Пример допустимого правила~--- выбрать
цифры, стоящие на ч\"етных местах.
Пример недопустимого правила~--- выбрать
цифры, стоящие на тех местах, где
в исходной последовательности нули.}.

Является ли сформулированный
частотный критерий случайности
универсальным?
Ряд известных фактов
о бесконечных последовательностях
скорее свидетельствовал об обратном.
К примеру (см.~\cite{lambalg}),
\begin{itemize}\label{utv:1}
\item[(i)]
существует такое множество $S$
бесконечных двоичных
последовательностей меры $0$,
что для любого сч\"етного семейства $R$
допустимых правил выбора
найд\"ется $s\in S$, для которого
закон больших чисел выполняется
во всех бесконечных
подпоследовательностях,
выбранных из $s$ с помощью
правил, принадлежащих $R$.
\end{itemize}
При этом построение множества $S$
и его свойство иметь меру нуль
достаточно конструктивны,
и следовательно, все его элементы
интуитивно неслучайны.

Колмогоров придавал особое значение
анализу конечных последовательностей,
а  не только предельных закономерностей.
Все результаты нашей статьи
лежат в конечной области.
Аналог~(i)
для конечных последовательностей
мог бы звучать так:
\begin{itemize}
\item[(ii)]\label{utv:2}
Пусть фиксировано натуральное $L$.
Существует такое множество $S$
двоичных последовательностей длины $L$,
что мощность $S$ достаточно мала
по сравнению с $2^L$ и
для любого не слишком большого
семейства $R$
допустимых правил выбора
найд\"ется $s\in S$, для которого
закон больших чисел выполняется
с достаточной точностью
во всех не слишком коротких
подпоследовательностях,
выбранных из $s$ с помощью
правил, принадлежащих $R$.
\end{itemize}
Разумеется, последняя формулировка
нуждается в уточнении.
Что значит \glqq достаточно мала\grqq,
\glqq не слишком большого\grqq,
\glqq с достаточной точностью\grqq,
\glqq не слишком коротких\grqq?
Замечательно, что
существует естественное
уточнение этих параметров,
при котором истинно
отрицание~(ii).
Тем самым уда\"ется установить
положительную связь
между \emph{частотной} и \emph{универсальной} случайностью
(теорема~\ref{thm:cover}).



\section{Анализ статьи Колмогорова 1963 года
\glqq О таблицах случайных чисел\grqq}

\subsection{Философская мотивировка}

По словам Колмогорова из~\cite{kolm},
в течение долгого времени он полагал, что:
\begin{enumerate}
\item предельные теоремы,
описывающие бесконечные последовательности испытаний, не имеют отношения к
практике;
\item связь с практикой вероятностных
теорем о конечных последовательностях
испытаний нельзя формализовать чисто математически.
\end{enumerate}
Мнение Колмогорова в отношении первого тезиса не изменилось\footnote{Хотя
в других работах Колмогоров подч\"еркивал,
что исследование бесконечных
последовательностей имеет большое эвристическое значение.}.
По поводу второго тезиса Колмогоров приш\"ел к выводу, что,
используя частотную концепцию случайности и уточнение понятия
сложности программы, можно чисто математически сформулировать
критерии применимости теории вероятностей к практике.

В работе~\cite{kolm} сообщается, что строгое определение
сложности программы будет дано в другой статье.
При этом в~\cite{kolm}
используется только тот факт, что количество простых объектов
не может быть слишком велико. Такой подход позже Колмогоров назвал
комбинаторным (см.~\cite{3appr}).
Определения, соответствующие алгоритмическому подходу,
были даны Колмогоровым в 1965 году (см.~\cite{3appr}).
Результатам из~\cite{kolm} можно сопоставить естественные
алгоритмические аналоги, и мы их приводим.
Параллель между комбинаторными и алгоритмическими формулировками
распространяется очень широко.
Поэтому в нашей статье почти все теоремы сформулированы в двух
вариантах~--- комбинаторном
и алгоритмическом~--- и имеют параллельную нумерацию
(алгоритмические варианты имеют номер со штрихом).

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

Математическая цель статьи~\cite{kolm}~---
оценить, насколько большую сложность можно допустить
для правил выбора, чтобы заведомо
существовал датчик случайных чисел.

\subsection {Определения}

В работе~\cite{kolm} Колмогоров
определил понятие (немонотонного) правила выбора из
конечной двоичной последовательности $\vct t$.

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


\begin{defn}\label{def:rule}
\emph{Правилом на последовательностях длины $L$} называется
функция $r$, определ\"енная на двоичных последовательностях
длины от $0$ до $L-1$, значениями которой являются пары из
множества
$\{1,\ldots,L\}\times\{\text{\glqq включить\grqq},
                   \text{\glqq не включить\grqq}\}$,
прич\"ем
первые компоненты значений функции на последовательности и
на е\"е собственном продолжении всегда различны. Пусть фиксирована
последовательность $\vct t$ длины $L$.
Для каждого $i$ от $0$ до $L$ построим индукцией по $i$
последовательность $\vct s_i$ двоичных цифр длины $i$.
Положим $s_0=\Lambda$, а $s_{i+1}$ получается из $s_i$
присоединением в конце цифры
последовательности $\vct t$ с номером $\pi_1(r(\vct s_i))$.
Подпоследовательность, выбранная правилом $r$ из $\vct t$, получается,
если из $\vct s_L$ удалить цифры с номерами $i$, для которых
$\pi_2(r(\vct s_{i-1}))=\text{\glqq не включить\grqq}$.
(Здесь $\pi_1$, $\pi_2$ обозначают первый и второй члены пары.)

Подпоследовательность, выбранная правилом $r$ из последовательности
$\vct t$, будет обозначаться $r[\vct t]$.
\end{defn}

Иногда полезно рассматривать более узкие классы правил.
\emph{Монотонные правила} всегда
переворачивают карты в их исходном
порядке\footnote{Монотонные правила впервые
рассмотрел Ч\"ерч в 1940 году.}.
\emph{Неадаптивные правила} сразу указывают некоторое
множество карт, и подпоследовательность состоит из
цифр, нарисованных на этих картах и расположенных
в исходном порядке.

\begin{defn}\label{def:gen}
Пусть $\rls_L$~--- некоторое
множество правил на последовательностях длины $L$.
Последовательность $\vct t$ длины $L$ называется
\emph{$(n,\epsilon)$-датчиком случайных чисел для $\rls_L$}, если
каждое правило из $\rls_L$
выбирает в $\vct t$ подпоследовательность $r[\vct t]$ с таким свойством:
\begin{itemize}
\item
при условии, что длина подпоследовательности не меньше $n$,\\
доля нулей в ней отличается от $\half$ менее чем на $\epsilon$.
\end{itemize}

Абсолютная величина разности между $\half$ и долей нулей в
последовательности называется \emph{отклонением}
(доли нулей).
\end{defn}

Заметим, что для каждого $p\in[0,1]$
можно рассматривать
$(n,\epsilon,p)$-датчики, для которых
доля нулей в подпоследовательностях
должна быть близка не к $\half$,
а к $p$.

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

При комбинаторном подходе
\emph{cложностью} конечного множества
называется двоичный логарифм его мощности.

В алгоритмическом подходе мы будем использовать \emph{простую энтропию}
конструктивного объекта, которая была
определена Колмогоровым в 1965 году\footnote{Сравнение простой энтропии с
префиксной энтропией и другими вариантами определения можно найти
в~\cite{UspSh}.}.
Фактически был определ\"ен класс функций энтропии, каждые две из которых
различаются не более чем на константу.
При этом Колмогоров надеялся, что удастся предложить какой-то
\glqq естественный\grqq{}
язык программирования, для которого функция энтропии
не более чем на $100$
превышала бы функцию энтропии любого другого
\glqq естественного\grqq{} языка
программирования.
Так как наши алгоритмические результаты в равной степени применимы к любой
функции энтропии, в их формулировках
может присутствовать константа $C$,
зависящая только от выбора языка программирования.
Отметим, что будет использоваться и понятие \emph{условной} энтропии,
также введ\"енное Колмогоровым.

Аналогия между комбинаторным и алгоритмическим подходами ос\-но\-ва\-на на
следующих двух утверждениях, доказанных Колмогоровым.

\begin{prop}\label{prop:num}
 Количество объектов, условная энтропия которых относительно
фиксированного объекта меньше $m$, не превышает \mbox{$2^m-1$}.
\end{prop}

\begin{prop}\label{prop:ent}
 Если множество перечисляется программой энтропии
меньше $\alpha$ и
имеет мощность меньше $2^m$, то энтропия его элементов меньше
$m+\alpha+2\lb\alpha+C$.
(Здесь и в
дальнейшем выражение $\lb$ будет обозначать двоичный логарифм.)
\end{prop}

Закон больших чисел влеч\"ет, что
множество последовательностей, из
которых фиксированное правило выбирает
длинную подпоследовательность с большим
отклонением, имеет малую мощность.
Однако если мы удалим требование большого отклонения,
мощность вс\"е равно может остаться малой.
В качестве примера можно рассмотреть
монотонное правило, которое включает
цифры в подпоследовательность, если
уже известные цифры образуют начало
последовательности $0101010101\ldots$;
при длине выборки равной длине
последовательности и без ограничений
на отклонение, соответствующее множество
содержит всего два элемента.

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

\begin{defn}\label{def:right_set}
Правило $r$, действующее на последовательностях длины $L$,
назов\"ем \emph{нормальным}, если из всех последовательностей
$r$ выбирает подпоследовательности одной и той же
положительной длины.

Для нормального правила $r$,
выбирающего подпоследовательности длины $n$,
и числа $\epsilon\in[0,\half]$,
определим множество $A_{r,\epsilon}$
последовательностей, в которых
$r$ выбирает подпоследовательности
с отклонением не менее $\epsilon$.
Такие множества назов\"ем \emph{правильными}.
\end{defn}

Введ\"ем обозначение, которое неоднократно понадобится
нам:
$$
d(n,\epsilon)\rightleftharpoons 2n\epsilon^2\lb\mathrm e\,.
$$
Следующие факты (подробно обсуждаемые в дальнейшем)
мотивируют введ\"енное обозначение.
Если нормальное правило $r$
выбирает подпоследовательности длины $n$,
то мощность правильного множества $A_{r,\epsilon}$
зависит только от $L$, $n$ и $\epsilon$.
Когда $\epsilon$ достаточно мало, а $n$ достаточно
велико по сравнению с $1/\epsilon$, то
$|A_{r,\epsilon}|\approx 2^{L-d(n,\epsilon)}$.


Существует эффективная операция (назов\"ем е\"е
\emph{$n$-нормализацией}), превращающая каждое правило в
нормальное с длиной выборки $n$, при\-ч\"ем так, что
выборки, уже имевшие длину ровно $n$, остаются неизменными.

Опишем процедуру $n$-нормализации.
Новое правило действует как и старое, но
с двумя исключениями.
Если старое правило уже выбрало $n$ цифр
в подпоследовательность,
то в новом правиле на этом выбор прекращается.
Если старое правило уже выбрало $k<n$ цифр
и остались неизвестными $n-k$ цифр, то новое
правило выбирает их все.


\subsection{Достаточные условия и необходимые
 условия существования датчика случайных чисел}

\begin{thm}[Колмогоров, 1963]\label{thm:kolm}
  Рассмотрим произвольные числа $L$ (длина последовательности),
$\epsilon>0$ (отклонение частоты от вероятности) и
$n\ge\epsilon^{-4}$ (длина выборки).
Для любого множества  правил $\rls_L$,
сложность которого меньше
$$
d(n,\epsilon)(1-\epsilon)\,,
$$
существует $(n,\epsilon)$-датчик случайных чисел.
\end{thm}
\begin{proof}
 В статье~\cite{kolm} Колмогоров только наметил доказательство этой
теоремы, и для полноты изложения мы его привед\"ем полностью.

Очевидно, можно считать, что $\epsilon\le\half$.
На последовательностях длины $L$
рассмотрим равномерную бернуллиевскую
меру (все цифры независимы и с вероятностью
$\half$ равны $0$ или $1$).
Вероятность каждой последовательности равна $2^{-L}$.

Зафиксируем некоторое правило выбора $r$.
Обозначим $k$-нор\-ма\-ли\-за\-цию правила $r$ через $r_k$.
Заметим, что для $r_k$ вероятность
выбрать данную подпоследовательность
длины $k$, равна $2^{-k}$,
поскольку независимость цифр сохраняется
при изменении порядка их расстановки.

Оценим вероятность того, что последовательность
$\vct t$ не является
$(n,\epsilon)$-датчиком для правила $r$
(то есть длина выборки больше или равна $n$,
а отклонение больше или равно $\epsilon$).
Если мы рассмотрим наименьшее $k\ge n$,
для которого отклонение в начале длины $k$
выборки $r[\vct t]$ больше или равно $\epsilon$,
то станет понятным, что
\begin{multline*}
\Pr\{\vct t\text{ не $(n,\epsilon)$-датчик для } r\}\le\:
  \Pr\{\text{отклонение в
         $r_n[\vct t]$ }\ge\epsilon\}\: +\\
  2\cdot\sum_{k=n}^L
   \Pr\left\{\text{количество нулей в $r_k[\vct t]$ }
      =\left\lceil k\left(\half+\epsilon\right)
       \right\rceil\right\}=\\
2\cdot\sum_{j=\lceil n(\half+\epsilon)\rceil}^n
  \binom{n}{j}\cdot 2^{-n} +
2\cdot\sum_{k=n}^L
  \binom{k}{\lceil k(\half+\epsilon)\rceil}\cdot 2^{-k}\,.
\end{multline*}

Для $j\ne k$ используем следующую оценку,
вытекающую из формулы Стирлинга:
$$
\binom{k}{j}\le\frac{\Exp{k\cdot h(j/k)}}{\sqrt{2\pi j(k-j)/k}}\,,
$$
где $h(x)=-x\ln x-(1-x)\ln(1-x)$~--- шенноновская функция энтропии.
Знаменатель этой оценки не может быть меньше
$\sqrt{2\pi\cdot (1-1/k)}\ge \sqrt{2\pi\cdot 15/16}$,
поскольку $k\ge n\ge\epsilon^{-4}\ge 16$.
Знак производной $h(x)$ показывает, что при $x\ge\half$
функция $h$ убывает;
поэтому $h(j/k)\le h(\half+\epsilon)$.
Дважды дифференцируя, можно доказать, что
$h(\half+\epsilon)\le \ln 2 - 2\epsilon^2$.

Таким образом, верхняя оценка вероятности
для правила $r$ не превышает
$$
2^{1-n}+\sqrt{\frac{8}{15\pi}}\Exp{-2n\epsilon^2}n+
\sqrt{\frac{8}{15\pi}}
      \frac{2\Exp{-2n\epsilon^2}}{1-\Exp{-2\epsilon^2}}\,.
$$

Простые вычисления показывают, что
последняя оценка строго меньше
$\Exp{-2n\epsilon^2(1-\epsilon)}$
для $\epsilon\le\half$ и $n\ge\epsilon^{-4}$
(при этом используется неравенство
$1-\Exp{-x}\ge x/\sqrt{\Exp{}}$ для $0\le x\le\half$).


Чтобы оценить
вероятность того, что последовательность не является
$(n,\epsilon)$-датчиком хотя бы для одного правила
из $\rls_L$, умножим на количество правил. Получим, что
вероятность того, что последовательность не является
$(n,\epsilon)$-датчиком для $\rls_L$, строго меньше единицы,
следовательно, существует последовательность,
являющаяся $(n,\epsilon)$-датчиком.
\end{proof}

\begin{note}
Теорема Колмогорова, как и следующие результаты, об\-об\-ща\-ет\-ся на
случай, когда  $0$ и $1$ появляются с частотами, близкими к $p$
и $1-p$ во всех длинных подпоследовательностях,
выбранных простыми правилами.
\end{note}

При алгоритмическом  подходе получается следующая

\renewcommand{\thmprimname}{Теорема~\ref{thm:kolm}$'$}
\begin{thm_prim}
  Рассмотрим произвольные числа $L$ (длина последовательности),
$\epsilon>0$ (отклонение частоты от вероятности) и
$n \ge \epsilon^{-4}$ (длина выборки).
Тогда для множества $\rls_L$,
состоящего из всех правил, условная энтропия которых при
известном $L$ меньше
$$
d(n,\epsilon)(1-\epsilon)\,,
$$
существует $(n,\epsilon)$-датчик случайных чисел.
\end{thm_prim}
\begin{proof}
 Из утверждения~\ref{prop:num} следует, что множество правил энтропии
меньше $d(n,\epsilon)(1-\epsilon)$ имеет сложность также меньше
$d(n,\epsilon)(1-\epsilon)$, и алгоритмический аналог тривиально
вытекает из комбинаторного результата.
\end{proof}

\begin{thm}[Колмогоров, 1963]\label{thm:rev_kolm}
  Рассмотрим произвольные числа $L$ (длина последовательности),
$\epsilon\in(0,1/20)$ (отклонение частоты от вероятности) и
$n\in[\epsilon^{-3},L/2]$ (длина выборки).
Существует множество неадаптивных правил $\rls_L$, сложность которого
меньше
$$
4n\epsilon(1+5\epsilon)\,,
$$
для которого не существует $(n,\epsilon)$-датчика случайных
чисел.
\end{thm}
\begin{proof}
Построим такое множество неадаптивных
правил выбора, что для любой последовательности
$\vct t$ в н\"ем найд\"ется правило $r$,
которое выбирает
длинную подпоследовательность $r[\vct t]$
с большим отклонением.

Положим
$$
 m=\left\lfloor\frac{1}{4\epsilon}+\half\right\rfloor\,,\quad
L'=2m\cdot\left\lceil\frac{n}{2m-1}\right\rceil\,.
$$
Просто проверить, что при заданных в теореме условиях
на $\epsilon$ и $n$ будет выполнено $L'<L$.

Наши правила будут выбирать подпоследовательности только из
первых $L'$ цифр последовательности. А именно, начало длины $L'$
разобь\"ем на $m$ отрезков равной длины $L'/m$.
Правило помещает в подпоследовательность ровно половину цифр одного
из этих отрезков и все цифры остальных.
Таким образом, правило зада\"ется
номером отрезка и $\frac{L'}{2m}$-элементным
подмножеством множества $\{1,\ldots,L'/m\}$.

Каждое правило выбирает подпоследовательность длины
$$
n'=(2m-1)\cdot\left\lceil\frac{n}{2m-1}\right\rceil\ge n\,.
$$

Зафиксируем последовательность $\vct t$ и докажем, что
найд\"ется правило $r$, для которого в подпоследовательности
$r[\vct t]$ отклонение больше $\epsilon$.
Обозначим начало $\vct t$ длины $L'$ через $\vct t'$.
Рассмотрим три возможных случая.
\begin{enumerate}
\item Среди отрезков $\vct t'$ есть два таких, что в первом
      не меньше половины цифр составляют нули,  а во втором~--- единицы.

      Рассмотрим два правила, $r_1$ и $r_2$. Для их задания
      достаточно указать, какие цифры они \emph{не} выбирают.
  \begin{itemize}
   \item Для $r_1$ все невыбранные цифры лежат
         в первом отрезке и являются
         нулями.
   \item Для $r_2$ все невыбранные цифры лежат
         во втором отрезке и являются
         единицами.
  \end{itemize}
      Количество нулей в $r_1[\vct t]$ равно количеству
      нулей в $\vct t'$
      минус $L'/2m$, а количество нулей в $r_2[\vct t]$
      равно количеству нулей в $\vct t'$.
      Таким образом, количества нулей в этих выборках
      различаются на $L'/2m$, следовательно,
      одно из них отстоит от
      $n'/2$ не менее чем на $L'/4m$.
      Либо в $r_1[\vct t]$, либо в
      $r_2[\vct t]$ отклонение не меньше
      $$
       \frac{L'/4m}{n'}=
       \frac{1}{2(2m-1)}\ge \epsilon\,.
      $$

\item Во всех отрезках $\vct t'$ не меньше
      половины цифр составляют нули.

      Тогда рассмотрим правило, которое
      из первого отрезка выбирает половину цифр, прич\"ем
      только нули. Количество нулей в этой выборке не меньше
      $$
       \frac{L'}{2m}+(m-1)\frac{L'/m}{2}=\frac{L'}{2}\,.
      $$
      Отклонение не меньше
      $$
       \frac{L'/2-n'/2}{n'}=\frac{2m-(2m-1)}{2(2m-1)}\ge\epsilon\,.
      $$
\item Во всех отрезках $\vct t'$ не меньше
      половины цифр составляют единицы.

      Этот случай полностью аналогичен предыдущему
      (с заменой нулей на единицы).
\end{enumerate}

Итак, мы доказали, что для построенного множества правил не существует
$(n,\epsilon)$-датчика.
Теперь оценим количество правил. Оно равно
$$
 m\cdot \binom{\scriptstyle L'/m}{\scriptstyle L'/2m}\le
  m\cdot\sqrt{\frac{2}{\pi L'/m}}\cdot 2^{L'/m}\,.
$$
Осталось заметить, что
$m\cdot\sqrt{2m/\pi L'}<1/4$
при $n\ge \epsilon^{-3}$ и $\epsilon<1/20$,
а $\frac{L'}{m}< 2+ 4n\epsilon(1+5\epsilon)$
при $\epsilon<1/20$.
\end{proof}

Теорема~\ref{thm:kolm} да\"ет нижнюю оценку, а теорема~\ref{thm:rev_kolm}
да\"ет верхнюю оценку на максимальное число $\tau$, для которого всякому
$L$ и всякому множеству правил, имеющему сложность меньше $\tau$,
соответствует хотя бы один $(n,\epsilon)$-датчик
случайных чисел длины $L$.
Поскольку
$d(n,\epsilon)=2n\epsilon^2\lb\mathrm e$ гораздо меньше
$4n\epsilon$ при малых $\epsilon$,
Колмогоров стремился устранить разрыв между степенями $\epsilon$ в
нижней и верхней оценках.
Как отмечено в~\cite{kolm}, ему это не удалось.
В предисловии к переводу~\cite{kolm} на русский
язык, опубликованному в~\cite{trans_kolm},
Колмогоров напоминает, что указанная проблема жд\"ет
своего решения.

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

\begin{thm}\label{thm:MS}
  Рассмотрим произвольные числа
$L\ge 2$ (длина последовательности),
$\epsilon\in(0,1/3)$ (отклонение частоты от вероятности)
и $n\in[2\epsilon^{-3}\lb L,L/2]$ (длина выборки).
Существует множество неадаптивных правил $\rls_L$,
сложность которого меньше
$$
d(n,\epsilon)\frac{1+\epsilon}{1-n/(L-1)}\,,
$$
для которого не существует $(n,\epsilon)$-датчика случайных
чисел.
\end{thm}
\begin{proof}
  Существование такого множества правил докажем, как и в
теореме~\ref{thm:kolm}, вероятностно. Однако теперь мы рассмотрим
распределение вероятностей на правилах  и покажем, что событие
\glqq{}для множества правил $\rls_L$ существует
$(n,\epsilon)$-датчик\grqq{} имеет вероятность
меньше единицы.\footnote{
В математике можно указать не один пример, когда
неявный способ построения даёт лучшую оценку,
чем все известные явные способы.
В книге~\cite{yaglom} на страницах 257\nddash261
и 273\nddash280 очень подробно разбирается
предложенное Колмогоровым доказательство
частного случая теоремы Шеннона
о помехоустойчивом кодировании.
Там особенно подч\"еркивается роль
\glqq неэффективности\grqq{} в рассуждении.
}

Нужное множество правил мы будем искать среди неадаптивных
правил, которые выбирают подпоследовательности длины ровно $n$,
то есть, правило зада\"ется $n$-элементным подмножеством
множества $1,\ldots,L$. Всего таких правил $\binom{L}{n}$; на них
мы введ\"ем равномерное распределение вероятностей.

Зафиксируем некоторую последовательность
$\vct t$ длины $L$ и оценим снизу
вероятность того, что она не является $(n,\epsilon)$-датчиком для
случайно взятого правила $r$, то есть,
отклонение в $r[\vct t]$ не меньше $\epsilon$.
Предположим, что нулей в $\vct t$ не меньше, чем единиц
(противоположный случай рассматривается симметрично).

Сначала рассмотрим ситуацию, когда числа
$L/2$ и $n(\half+\epsilon)$ являются целыми,
а в конце рассуждения объясним, что делать
в остальных случаях.
Поскольку нам нужна оценка снизу, достаточно оценить вероятность
такого отклонения, когда доля нулей в выборке
по крайней мере на $\epsilon$ больше половины;
очевидно, что эта вероятность минимальна,
если нулей и единиц в $\vct t$ поровну.
Достаточно оценить вероятность отклонения,
точно равного $\epsilon$. Итак, оцениваем снизу
вероятность выбрать из последовательности, содержащей
$L/2$ нулей и $L/2$ единиц, подпоследовательность
длины $n$, в которой
ровно $(\half+\epsilon)n$ нулей;
очевидно, эта вероятность равна
$$
\frac{\dbinom{L/2}{(\half-\epsilon)n}\dbinom{L/2}{(\half+\epsilon)n}}
     {\dbinom L n}\,,
$$
(считаем, что $\epsilon<\half$ и $n\le L/2$).

Как и в теореме~\ref{thm:kolm}, используем следующую оценку на
биномиальные коэффициенты, вытекающую из формулы Стирлинга:
$$
\frac{\Exp{k\cdot h(j/k)}}{\sqrt{8 j(k-j)/k}}\le
\binom{k}{j}\le\frac{\Exp{k\cdot h(j/k)}}{\sqrt{2\pi j(k-j)/k}}\,.
$$
Получим, что искомая вероятность не меньше
$$
\Exp{L\left(\half h((1-2\epsilon)\gamma)+
                        \half h((1+2\epsilon)\gamma)-h(\gamma)\right)}
 \times
 \frac{\sqrt{2\pi}/4}
{\sqrt{(1-4\epsilon^2)(1-4\epsilon^2\frac{\gamma^2}{(1-\gamma)^2})
  (1-\gamma)n}}\,,
$$
где $\gamma=n/L$.

Дважды дифференцируя, убеждаемся, что при
$\epsilon\le\frac{1}{\sqrt{8}}$
%%(в частности, при $\epsilon<\frac{19}{54}$)
и $\gamma\le\half$
выполнено
\begin{equation}\label{eq:hless}
{\half h((1-2\epsilon)\gamma)+\half h((1+2\epsilon)\gamma)-h(\gamma)
\ge -\frac{2\gamma\epsilon^2}{1-\gamma}(1+4\epsilon^2/3)}\,.
\end{equation}

Простая проверка показывает,
что второй сомножитель в оценке вероятности
больше $1/\sqrt{\Exp{}n}$.

Окончательно получим, что искомая вероятность больше
$\Exp{-K}$, где
$$
K=\frac{2n\epsilon^2}{1-\gamma}(1+4\epsilon^2/3)+\half(1+\ln n)\,.
$$

Таким образом, вероятность того,
что из фиксированной последовательности
одно правило не выберет подпоследовательность
с отклонением не менее $\epsilon$,
оказывается меньше $1-\Exp{-K}$.
Теперь укажем независимо $N$ случайных
правил\footnote{Некоторые из этих правил могут совпасть
друг с другом.}.
Вероятность того, что
фиксированная последовательность
$\vct t$ является $(n,\epsilon)$-датчиком
для множества указанных правил,
будет меньше
$$
(1-\Exp{-K})^N < \Exp{-N\Exp{-K}}
$$
(здесь использовано неравенство
$(1-\frac{1}{x})^{x} < \Exp{-1}$, верное
при всех $x>1$).
Умножив на количество последовательностей длины $L$,
получим строгую верхнюю оценку вероятности того,
что для множества указанных правил
есть хотя бы один $(n,\epsilon)$-датчик,
а именно
$$
2^L\Exp{-N\Exp{-K}}=\Exp{L\ln 2 -N\Exp{-K}}\,,
$$
что не превышает единицы для
$N = \left\lceil\Exp{K}L\ln 2\right\rceil <
\Exp{K}L $.
При этом сложность множества
указанных правил меньше
$$
\frac{2n\epsilon^2}{1-n/L}
   (1+4\epsilon^2/3)\lb\Exp{}+2\lb L\,.
$$
Легко убедиться, что
\begin{equation}
d(n,\epsilon)\frac{1+\epsilon}{1-n/L} >
\frac{2n\epsilon^2}{1-n/L}(1+4\epsilon^2/3)\lb\Exp{}+2\lb L
\label{eq:1}
\end{equation}
при $\epsilon<1/3$ и $n\ge 2\epsilon^{-3}\lb L$.

Теперь верн\"емся к нашему предположению
о том, что числа $L/2$ и
$n(\half+\epsilon)$~--- целые.
Если число $L$ неч\"етное, то можно провести
вс\"е рассуждение для начал исходных
последовательностей длины $L-1$.
При этом в окончательной формуле
$n/L$ заменится на $n/(L-1)$.
Число $n(\half+\epsilon)$ всегда можно сделать целым,
заменив $\epsilon$ на $\epsilon'\ge\epsilon$ так, что
$\epsilon'-\epsilon<\frac{1}{n}$.
Из условий теоремы просто следует, что
если $\epsilon < \frac{1}{3}$,
то $\epsilon'<\frac{1}{\sqrt{8}}$.
Поэтому истинность неравенства~(\ref{eq:hless})
сохраняется при замене
$\epsilon$ на $\epsilon'$,
истинность же неравенства~(\ref{eq:1})
сохраняется, если его левую часть оставить прежней,
а в правой заменить $\epsilon$ на $\epsilon'$.
\end{proof}

\begin{note}
 В доказательстве теоремы~\ref{thm:rev_kolm} множество
$\rls_L$ полиномиально
вычислимо, то есть построен алгоритм, который по
номеру правила из $\rls_L$ и его аргументу за полиномиальное время
вычисляет результат применения этого правила к аргументу.
Для множества $\rls_L$ из
теоремы~\ref{thm:MS} это может оказаться не так, поскольку
доказательство вероятностное.

{\bf Открытая проблема}: можно ли усовершенствовать доказательство
теоремы~\ref{thm:MS} так, чтобы множество
$\rls_L$ было полиномиально вычислимо
(неформально говоря, чтобы $\rls_L$ стало
явно заданным)?
\end{note}


\renewcommand{\thmprimname}{Теорема~\ref{thm:MS}$'$}
\begin{thm_prim}
  Рассмотрим произвольные числа $L\ge 2$
(длина последовательности),
рациональное $\epsilon\in(0,1/3)$
(отклонение частоты от вероятности) и
$n\in[2\epsilon^{-3}\lb L,L/2]$ (длина выборки).
Для множества $\rls_L(n,\epsilon)$
всех неадаптивных правил, у которых
условная энтропия при известных $L$,
$n$, $\epsilon$ меньше
$$
d(n,\epsilon)\frac{1+\epsilon}{1-n/L}+C\,,
$$
не существует $(n,\epsilon)$-датчика случайных чисел.
\end{thm_prim}
\begin{proof}
По предыдущей теореме для некоторого множества
неадаптивных правил, имеющего сложность меньше
$d(n,\epsilon)\frac{1+\epsilon}{1-n/(L-1)}$,
не существует $(n,\epsilon)$-датчика длины $L$.
Покажем, что, зная $L$, $n$, $\epsilon$,
множество правил с таким свойством
можно построить алгоритмически.

Действительно, по каждому множеству
неадаптивных правил $\rls_L$ и
последовательности $\vct t$ длины $L$
можно эффективно узнать, является ли
$\vct t$ $(n,\epsilon)$-датчиком
для $\rls_L$
(надо применить к $\vct t$
каждое правило из $\rls_L$
и вычислить отклонение).
Перебрав все последовательности длины $L$,
можно проверить, существуют ли
$(n,\epsilon)$-датчики для $\rls_L$.
Перебирая все множества неадаптивных правил
данного размера, мы найд\"ем нужное (если
множеств с нужным свойством несколько, мы
возьм\"ем первое в нашем перечислении).

По $L$, $n$, $\epsilon$
найденное множество правил
можно перечислить программой,
энтропия которой зависит
только от языка программирования.
Из утверждения~\ref{prop:ent}
(релятивизованного относительно
$L$, $n$, $\epsilon$)
следует, что условная энтропия каждого
из этих правил не превосходит
сложности множества плюс некоторая константа.
При добавлении правил (всех остальных с энтропией меньше
$d(n,\epsilon)\frac{1+\epsilon}{1-n/(L-1)}+C$)
требуемое свойство
(отсутствие $(n,\epsilon)$-датчика)
не может нарушиться.
Оста\"ется отметить, что разность
$\left(d(n,\epsilon)\frac{1+\epsilon}{1-n/(L-1)}-
d(n,\epsilon)\frac{1+\epsilon}{1-n/L}\right)$
меньше $1$.
\end{proof}


\section{Сравнение универсальной и частотной случайности}

\subsection{Философская мотивировка}

Для уточнения представлений о случайности
в математической статистике
традиционно используются тесты.
Пусть перед нами конечная последовательность карт
(см.~абзац перед определением~\ref{def:rule}),
пов\"ернутых лицевой стороной вниз.
На лицевой стороне каждой карты нарисована
двоичная цифра.
Последовательности карт в этой формулировке
соответствует (неизвестная нам)
последовательность нулей и единиц.
Неслучайность (относительно равномерного
распределения) этой последовательности
неформально означает возможность
сделать нетривиальное предсказание
о е\"е поведении.
Если кто-нибудь назов\"ет последовательность,
и после переворачивания карт нарисованная
на них последовательность
совпад\"ет с названной,
то такую последовательность можно считать
максимально неслучайной.
Если кто-нибудь назов\"ет множество,
содержащее сравнительно мало
последовательностей,
и после переворачивания карт нарисованная
на них последовательность
попад\"ет в названное множество,
то и такую последовательность можно считать
неслучайной
(прич\"ем мера е\"е неслучайности
будет тем меньше, чем больше будет
мощность названного множества).
Такие множества принято называть тестами.

На практике бывает удобно
рассматривать тесты какого-то
специального вида.
Особенно важными являются частотные тесты.
Каждому правилу $r$, выбирающему из
последовательностей длины $L$
подпоследовательности длины $n$,
и отклонению $\epsilon$
сопоставляется множество\footnote{
В определении~\ref{def:right_set} такие множества
названы правильными.
}
(частотный тест),
содержащее те последовательности $\vct t$,
для которых $\ell(\vct t)=L$,
$\ell(r[\vct t])=n$ и доля нулей
в $r[\vct t]$ отстоит от $\half$
по крайней мере на $\epsilon$.
Можно было бы сказать, что общее
представление о случайности сводится к частотному,
если бы любой тест $U$ можно было покрыть
небольшим набором частотных тестов
$F_1,\ldots,F_m$. При этом важно,
чтобы $m$ было очень мало по сравнению
с мощностью $U$ и чтобы
мощность каждого $F_i$ не была гораздо
больше мощности $U$.
В теореме~\ref{thm:cover} даются конкретные
оценки такого типа.
В теореме~\ref{thm:no_cover} доказывается, что
оценки из теоремы~\ref{thm:cover} нельзя
существенно улучшить.
Из теоремы~\ref{thm:no_adapt} следует,
что частотные тесты $F_i$, вообще говоря,
невозможно задать с помощью
правил выбора более узкого
(чем в теореме~\ref{thm:cover}) класса.

Стоит отметить, что комбинаторные результаты
первой части статьи тоже можно
интерпретировать как исследование вопроса
о возможности покрытия множества $U$
частотными тестами $F_1,\ldots,F_m$.
Только там в качестве $U$ бер\"ется
множество всех последовательностей.

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

Как и в первой части статьи, теоремы алгоритмического
подхода имеют номера параллельных теорем
комбинаторного подхода с добавленным штрихом.



\subsection{Комбинаторный подход}

\begin{defn}\label{def:set_defect}
\emph{Дефектом} $\Dv(S)$ множества $S$
двоичных последовательностей
некоторой длины $L$
называется разность между $L$ и сложностью множества
$S$, т.~е., $\Dv(S)=L-\lb|S|$.
\emph{Удельным дефектом} $\dv(S)$ называется величина
$\dv(S)=\Dv(S)/L$.
\end{defn}

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


\begin{thm}\label{thm:cover}
Пусть $\delta\in(0,\Exp{-\Exp{8}})$
и фиксировано натуральное
$L\ge(1/\delta)^5$.
Будем рассматривать множества
двоичных последовательностей длины $L$.
Для произвольного множества $S$
с удельным дефектом $\ge\delta$
существует семейство правильных множеств
с удельным дефектом больше
$$
\delta'=\frac{\delta}{\ln(1/\delta)}(1-\beta)\,,
$$
которое покрывает $S$ и содержит не более
$L\Exp{1/\delta'}$ множеств
(а в качестве $\beta$ можно взять
$\frac{2\ln\ln(1/\delta)}{\ln(1/\delta)}$).
\end{thm}
\begin{proof}
Для произвольного множества $S$
последовательностей длины $L$
рассмотрим следующую игру.
Математик и Природа по очереди
делают $L$ ходов: на $i$-ом ходу
Математик указывает ставку
$x_i\in[0,1]$ на цифру $0$ или $1$,
а Природа указывает элемент $t_i\in\{0,1\}$,
прич\"ем так, чтобы после
$L$-ого хода построенная
последовательность $\vct t$
принадлежала $S$.
В начале капитал Математика
равен нулю, затем на каждом ходу он
возрастает на величину ставки,
если Математик угадал следующую цифру $t_i$,
и уменьшается на ту же
величину в противоположном случае.
Капитал может быть отрицательным,
поэтому такая игра называется
игрой \glqq в кредит\grqq.
Покажем, что для любого множества $S$
существует стратегия Математика,
позволяющая выиграть не менее $\Dv(S)\ln 2$.

Введ\"ем сначала несколько обозначений.
Если $\vct s$~--- продолжение
последовательности $\vct t$,
будем писать $\vct s\sqsupset\vct t$
(при этом возможно $\vct s=\vct t$).
$S_{\vct t}=\{\vct s\mid
\vct s\sqsupset\vct t, \vct s\in S\}$~---
множество продолжений $\vct t$,
принадлежащих множеству $S$.
Пусть $\vct t_{1:i}$~---
часть последовательности $\vct t$,
полученная перед $(i+1)$-м ходом.

Стратегия Математика заключается в следующем.
Если $|S_{\vct t_{1:i}0}|\ge |S_{\vct t_{1:i}1}|$
(то есть, если большинство
лежащих в $S$ продолжений $\vct t_{1:i}$ начинается на $0$),
то Математик ставит на $0$,
а в противном случае~--- на $1$;
величина ставки $x$
определяется соотношением
$\frac{1+x}{2}=\frac{|S_{\vct t_{1:i}0}|}{|S_{\vct t_{1:i}}|}$
или, соответственно,
$\frac{1+x}{2}=\frac{|S_{\vct t_{1:i}1}|}{|S_{\vct t_{1:i}}|}$.

Покажем, что для этой стратегии не убывает величина
$K_i+\Delta_i\ln 2$, где $K_i$~--- капитал Математика после
$i$-го хода, а $\Delta_i=\Dv(S_{\vct t_{1:i}})-i$
является дефектом множества возможных
концовок игры.
Поскольку в начальный момент $K_0=0$,
$\Delta_0=\Delta(S)$, а после последнего хода
$\Dv(S_{\vct t_{1:L}})-L=L-\lb 1-L=0$, отсюда будет
следовать, что выигрыш Математика $K_L$
не меньше $\Dv(S)\ln 2$.
Мы хотим доказать, что сумма
$(K_{i+1}-K_i)+(\Delta_{i+1}-\Delta_i)\ln 2$
всегда неотрицательна.
Второе слагаемое равно
$-\ln 2-\ln\frac{|S_{\vct t_{1:(i+1)}}|}
               {|S_{\vct t_{1:i}}|}$.
Первое слагаемое равно ставке $x$ или $(-x)$.
В первом случае получается
$x-\ln 2-\ln\frac{1+x}{2}=x-\ln(1+x)\ge 0$
(в силу известного неравенства для логарифма).
Во втором случае получается
$-x-\ln 2-\ln\frac{1-x}{2}=-x-\ln(1-x)\ge 0$.
Таким образом, мы доказали, что выигрыш составит не меньше
$\delta L\ln2$, где $\delta=\dv(S)$.

Описанную стратегию мы используем
для построения множества правил,
которые дадут покрытие $S$ правильными множествами.
В общих чертах конструкция выглядит так:
по $S$  мы строим правильные множества большого дефекта,
покрывающие \glqq{}почти вс\"е\grqq{} $S$,
а для оставшейся части мы повторяем
ту же конструкцию;
оценка количества покрытых последовательностей
проводится с помощью нашей выигрышной стратегии
(которая будет слегка модифицирована,
чтобы уменьшить количество возможных размеров ставок).

Прежде всего модифицируем стратегию.
Для этого возьм\"ем ближайшее сверху
к $\ln(1/\delta)$ такое число $B$,
что $M=\frac{B}{\delta\ln 2}$~---
натуральное число, и округлим с уменьшением
все ставки до ближайшего
числа вида $k/M$ (где $k\in\mathbb N$).
Заметим, что уменьшение выигрыша на каждом ходу
меньше $\frac{1}{M}$,
и стратегия теперь выигрывает больше
$\delta L\ln2(1-\frac{1}{B})$.
При этом ненулевые ставки могут принимать
только $M$ различных значений.

Двоичной цифре ($0$ или $1$) и
множеству допустимых размеров ставок~---
подмножеству $\{1/M,2/M,\ldots,1\}$~---
сопоставляем следующее правило.
Оно читает последовательность
по порядку и применяет к прочитанному
отрезку выигрышную стратегию;
очередная цифра выбирается
в подпоследовательность,
если стратегия предписывает
поставить ставку допустимого размера
на заданную цифру.
Общее количество правил выбора
такого вида не превышает  $2\cdot2^M$.
К каждому правилу применим
$n$-нормализацию для всех $n$,
после этого количество нормальных
правил не превышает
$2L\cdot2^{B/(\delta\ln2)} <
 2L\cdot2^{1+\lb(1/\delta)/\delta}=
4L(1/\delta)^{1/\delta}$.

Для почти каждой последовательности из $S$
найд\"ем нормальное правило $r$ описанного вида
и число $\epsilon$, такие что соответствующее правильное
множество $A_{r,\epsilon}$ содержит эту последовательность
и имеет достаточно большой дефект.
Из $\epsilon_1>\epsilon_2$ следует
$A_{r,\epsilon_1}\subseteq A_{r,\epsilon_2}$,
поэтому
для каждого $r$ можно брать наименьшее $\epsilon$,
при котором дефект $A_{r,\epsilon}$
достаточно велик.
Б\'ольшая часть $S$ окажется покрытой
не более чем
$4L(1/\delta)^{1/\delta}$ множествами.
А для малого исключительного
множества $\widetilde S\subset S$
повторим всю конструкцию;
рекурсивный подсч\"ет покажет,
что суммарное количество множеств в покрытии
будет невелико.

Зафиксируем последовательность $\vct t_0\in S$.
Наша стратегия выигрывает на ней
более $\delta L\ln2(1-\frac{1}{B})$,
ставя как на нуль, так и на единицу.
При ставках только на $0$ или только на
$1$ выигрыш хотя бы в одном случае составит более
$\half\delta L\ln2(1-\frac{1}{B})$.
Выберем соответствующую цифру
(будем считать, что это $0$) и далее
будем рассматривать ставки только на $0$
(а ставки на $1$ игнорируем).

Для произвольного начала $\vct t$
последовательности из $S$
обозначим через $d_i(\vct t)$
разность количества выигрышей и проигрышей на
ставках размера $i/M$ (ставки только на $0$), а через
$n_i(\vct t)$~--- общее количество таких ставок
(в ситуации, когда Природа ходила в соответствии с $\vct t$).

Выигрыш на $\vct t_0$ равен
$$
\sum_{i=1}^M \frac{i}{M}d_i(\vct t_0)\,.
$$
Исключим те ставки,
для которых $n_i(\vct t_0)\le\frac{L}{M^2}$.
Выигрыш на одном ходу не превышает размера ставки,
то есть $1$, поэтому общий выигрыш
уменьшится самое большее на
$1\cdot\frac{L}{M^2}\cdot M = L/M=\delta L\ln 2/B$.
Таким образом,
\begin{equation}
\sum_{i\colon n_i(\vct t_0) > \frac{L}{M^2}}
   \frac{i}{M}d_i(\vct t_0)
   \quad>\quad
   \half\delta L\ln2\left(1-\frac{3}{B}\right)\,.
  \label{eq:2}
\end{equation}


Для каждого $\vct t_1\in S$
рассмотрим множество
$$
 S(\vct t_1,i)=
 \left\{\vct t\in S
      \left|
 n_i(\vct t)=n_i(\vct t_1),\,
  d_i(\vct t)\le
   \frac{i}{M}n_i(\vct t_1)\left(1-\frac{1}{B}\right)
      \right.
 \right\}\,.
$$

\begin{claim}\label{claim:size}
 Если $n_i(\vct t_1)>L/M^2$, то
 $|S(\vct t_1,i)| < |S|\Exp{-L/2B^2 M^4}$.
\end{claim}
Докажем это предложение позже,
а сейчас продолжим доказательство теоремы.

%Понятно, что $\vct t_0$ может принадлежать или не принадлежать
%$S(\vct t_0, i)$, то есть быть
%исключительным или типичным соответственно.
%Уточним эту идею.
Положим
{%
\newlength{\tempdima}
\settowidth{\tempdima}{$i\colon n_i(\vct t_1)\ge L/M^2$}
\newlength{\tempdimb}
\settowidth{\tempdimb}{$\vct t_1\in S$}
$$
 \widetilde S\quad =\text{\hbox to \tempdimb {\hss$
      \bigcup_
  {\parbox{1.01\tempdima}{\hfil$\vct t_1\in S$\hfil\\
     $i\colon n_i(\vct t_1) > L/M^2$}}
                   $\hss}}
           S(\vct t_1,i)\,.
$$%
}
Заметим, что множество $S(\vct t_1,i)$ полностью определяется двумя
параметрами~--- $i$ и $n_i(\vct t_1)$, которые могут принимать
соответственно $M$ и $L$ различных значений.
Поэтому
$$
|\widetilde S| < LM|S|\Exp{-L/2B^2 M^4}\,.
$$

Рассмотрим два возможных случая:
\begin{enumerate}
\item $\vct t_0\in\widetilde S$;
\item $\vct t_0\notin\widetilde S$.
\end{enumerate}

В первом случае $\vct t_0$ попало
в исключительное множество, которое мы не
пытаемся покрыть правильными множествами
ранее описанного типа.
Вместо этого мы повторяем всю описываемую конструкцию для множества
$\widetilde S$ с одним и тем же $\delta$ (дефект $\widetilde S$
больше дефекта $S$).
В результате получаем цепочку
уменьшающихся множеств
$S^{(0)}=S$, $S^{(1)}=\widetilde{S^{(0)}}$,
$S^{(2)}=\widetilde{S^{(1)}}$,\,\ldots\:.
Эта цепочка оборв\"ется,
поскольку мощность множества~---
целое число~--- на каждом шаге
уменьшается более чем
в $\Exp{L/2B^2 M^4}/LM$ раз.
Длина цепочки не превышает
$$
1+\frac{\ln|S|}{\ln(\Exp{L/2B^2 M^4}/LM)} <
1+\frac{L\ln 2}{L/2B^2 M^4-\ln L-\ln M}\,.
$$
Учитывая границы,
наложенные в условии теоремы на $L$ и $\delta$,
длину цепочки можно оценить сверху как
$\frac{25\ln^6 (1/\delta)}{\delta^4}$.
Так как количество правил
для одного члена цепочки
не больше $4L(1/\delta)^{1/\delta}$,
то всего их получается меньше
$L\Exp{1/\delta'}$.

Разбер\"ем теперь второй случай.
Построим для $\vct t_0$ покрывающее
правильное множество,
то есть, укажем правило
(совокупность размеров ставок)
и отклонение.

Для краткости обозначим
$n_i=n_i(\vct t_0)$, $d_i=d_i(\vct t_0)$.
Из $\vct t_0\notin\widetilde S$,
в частности, следует, что при
$n_i > L/M^2$ имеет место
$\vct t_0\notin S(\vct t_0,i)$, то есть,
$d_i > \frac{i}{M}n_i(1-\frac{1}{B})$.
Отсюда и из~(\ref{eq:2})
$$
\sum_{i\colon n_i > \frac{L}{M^2}}
     \frac{d_i^2}{n_i} \:\:>
\sum_{i\colon n_i > \frac{L}{M^2}}
     d_i\frac{i}{M}\left(1-\frac{1}{B}\right) >
     \half\delta L\ln2\left(1-\frac{4}{B}\right)\,.
$$

Рассмотрим правильное множество,
которое зада\"ется совокупностью ставок
$J\subseteq\{i\mid n_i > \frac{L}{M^2}\}$,
длиной выбираемой подпоследовательности
$n=\sum_{i\in J}n_i$ и отклонением
$\epsilon=\frac{1}{2n}\sum_{i\in J} d_i$.
Это множество содержит $\vct t_0$
(напомним, что $d_i$~---
разность количества выигрышей и проигрышей).
По оценке Чернова
удельный дефект такого множества не меньше
$2n\epsilon^2\lb\Exp{}/L$.
Теорема будет доказана,
если мы покажем, что для некоторого $J$
эта величина больше
$\frac{\delta}{\ln(1/\delta)}(1-\beta)$.

Предположим противное, то есть, для каждого
$J\subseteq\{i\mid n_i > \frac{L}{M^2}\}$
$$
\frac{\left(\sum_{i\in J} d_i\right)^2}
     {\left(\sum_{i\in J} n_i\right)\cdot 2L\ln2}
  \le \frac{\delta}{\ln(1/\delta)}(1-\beta)\,.
$$
Перепишем это в виде
$$
\left(\sum_{i\in J} \frac{d_i}{n_i}n_i\right)^2 \le
Z\cdot\left(\sum_{i\in J} n_i\right)\,,
$$
где $Z=\frac{\delta}{\ln(1/\delta)}(1-\beta)\cdot 2L\ln2$.

\begin{claim}\label{claim:calc}
 Если $\sum_{i\in J} \frac{d_i}{n_i}n_i
     \le \sqrt{Z\sum_{i\in J} n_i}$
для всех $J$, то
$$
 \sum \frac{d_i^2}{n_i}\le Z+\frac{Z}{4}(\ln\sum n_i-\ln Z)\,,
$$
где суммирование ид\"ет по всем $i$ таким,
что $n_i > \frac{L}{M^2}$.
\end{claim}
Доказательство этого предложения
помещено чуть ниже.

Вспоминая полученную ранее оценку на $\sum d_i^2/n_i$,
имеем
$$
\half\delta L\ln2\left(1-\frac{4}{B}\right) <
               Z+\frac{Z}{4}(\ln L-\ln Z)\,
$$
(здесь учтено $\sum n_i\le L$).
После простых преобразований получим
$$
\left(1-\frac{4}{\ln(1/\delta)}\right) <
(1-\beta)\left(1+
 \frac{\ln\ln(1/\delta)+4-\ln\ln4-\ln(1-\beta)}
      {\ln(1/\delta)}\right)\,,
$$
что неверно при $\beta=\frac{2\ln\ln(1/\delta)}{\ln(1/\delta)}$ и
$\delta<\Exp{-\Exp{8}}$.
\end{proof}

Осталось доказать два использованных предложения.

\begin{proof}[Доказательство предложения~\ref{claim:calc}]
Мы хотим из оценки сумм
$\sum\frac{d_i}{n_i}n_i$
получить оценку суммы
$\sum\frac{d_i^2}{n_i}=
\sum\left(\frac{d_i}{n_i}\right)^2\!n_i$.
Заменим эти суммы интегралами от
кусочно-постоянных функций.
Поскольку упорядочение индексов $i$ несущественно,
будем считать, что $i=1,\ldots,I$,
а $\frac{d_i}{n_i}$ монотонно невозрастают.
На полуинтервале $[0,\sum_{i=1}^I n_i)$ рассмотрим
невозрастающую функцию $f$,
определ\"енную равенством:
$$
 f(x)=\frac{d_k}{n_k}\,,\text{ если } N_{k-1}\le x<N_k\,,
$$
где $N_k=\sum_{i=1}^k n_i$.
Очевидно, что рассматриваемые
суммы по $i$ от $1$ до $k$
равны соответственно
интегралам $f$ и $f^2$ от $0$ до $N_k$.
По условию, для любого $k$
$$
 \int_0^{N_k}f(x)\,dx\le\sqrt{Z\cdot N_k}\,.
$$
Пользуясь выпуклостью корня,
продолжим это неравенство на произвольные
значения верхнего предела интегрирования.
Действительно, для $N_k\le u \le N_{k+1}$
$$
\int_0^{u}f(x)\,dx=\int_0^{N_k}f(x)\,dx
    +\frac{d_{k+1}}{n_{k+1}}(u-N_k)\,.
$$
Из неравенства при $u=N_{k+1}$ получаем
для всех $u$
$$
\frac{d_{k+1}}{n_{k+1}}(u-N_k)
\le\left(
     \sqrt{ZN_{k+1}}-\int_0^{N_k}f(x)\,dx
   \right)
    \frac{u-N_k}{N_{k+1}-N_k}\,.
$$
Отсюда
$$
\int_0^{u}f(x)\,dx\le
 \sqrt{ZN_{k+1}}\frac{u-N_k}{N_{k+1}-N_k}+
       \sqrt{ZN_k}\left(1-\frac{u-N_k}{N_{k+1}-N_k}\right)\le
  \sqrt{Zu}\,.
$$

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

Заметим, что $f(x)\le 1$, так как $d_k\le n_k$.
Положим
$$
 g(x)=
 \begin{cases}
  1,                           & \text{если }x<Z,\\
  \frac{\sqrt{Z}}{2\sqrt{x}},  & \text{если }x\ge Z.
 \end{cases}
$$
Отметим, что если
$u\ge Z$, то $\int_0^{u}g(x)\,dx=\sqrt{Zu}$.
Тогда
$$
\int_0^{u}(g(x)-f(x))\,dx\ge 0
$$
при всех $u\in[0,N_I]$.
Выведем отсюда, что
$\int_0^{u}(g^2(x)-f^2(x))\,dx\ge 0$.

Вторая теорема о среднем для интегралов утверждает, что
для любой интегрируемой функции $\psi(x)$
и любой неотрицательной невозрастающей функции $\phi(x)$
найд\"ется точка $\xi\in[a,b]$ такая, что
$$
 \int_a^b\phi(x)\psi(x)\,dx=\phi(a)\int_a^\xi \psi(x)\,dx\,.
$$
Для $\psi(x)=g(x)-f(x)$ и
$\phi(x)=g(x)+f(x)$ условия теоремы
выполнены, откуда
$$
\int_0^{u}(g^2(x)-f^2(x))\,dx=
     (g(0)+f(0))\int_0^\xi (g(x)-f(x))\,dx\ge 0\,.
$$

Проверим, что $Z < N_I$. В самом деле,
$\sum n_i=\sum\frac{n_i^2}{n_i}\ge
\sum\frac{d_i^2}{n_i} >
\half\delta L\ln 2(1-\frac{4}{B}) >
\frac{\delta}{\ln(1/\delta)}
(1-\beta)\cdot 2L\ln 2=Z$
(использовано, что $\delta$ мало).

Таким образом,
$$
\sum_i\frac{d_i^2}{n_i}=\int_0^{N_I}f^2(x)\,dx\le
   \int_0^{N_I}g^2(x)\,dx = Z+\frac{Z}{4}(\ln N_I-\ln Z)\,.
$$
\end{proof}

\begin{proof}[Доказательство
              предложения~\ref{claim:size}]
Рассмотрим множество $S(\vct t_1,i)$.
Заметим, что условие
$$
d_i(\vct t) \le
 \frac{i}{M}n_i(\vct t_1)
   \left(1-\frac{1}{B}\right)
$$
можно переписать в виде
$$
 \left(\half+\frac{i}{2M}\right)n_i
                    -\frac{in_i}{2BM}
   \ge \frac{n_i+d_i}{2}\,.
$$
%
%то есть, словами, количество нулей ($\frac{n_i+d_i}{2}$) отличается от
%среднего $\left(\half+\frac{i}{2M}\right)n_i$ более чем на
%$\frac{in_i}{2BM}$.
%

Чтобы оценить размер $S(\vct t_1,i)$, введ\"ем
две вспомогательные вероятностные меры,
$\Pr_S$ и $\Pr$.
Мера $\Pr_S$ равномерно распределена на $S$,
то есть $\Pr_S(X)=|X\cap S|/|S|$.
В качестве меры $\Pr$ возьм\"ем
бернуллиевскую меру с вероятностью
нуля $\half+\frac{i}{2M}$.

Пусть $X_{\nu,\sigma}$~--- множество
последовательностей длины $\nu$,
в которых не более $\sigma$ нулей.
Пусть $\vct t\in\{0,1\}^{\le L}$,
$z_i(\vct t)$~--- количество выигрышей
на ставках размера $i/M$,
сделанных на цифру $0$,
когда Природа играет в соответствии
с  последовательностью $\vct t$,
а Математик играет
в соответствии со своей
(модифицированной) стратегией.
Отметим, что
$z_i(\vct t)=(n_i(\vct t)+d_i(\vct t))/2$.
Предполагая, что $S_{\vct s}\ne\varnothing$,
докажем индукцией по длине
$\vct s$ (спуском от $L$ к $0$)
следующее соотношение\footnote{
$\Pr_S\{U\mid V\}$ обозначает вероятность
выполнения $U$ при условии выполнения $V$,
то есть
$\Pr_S(\{\vct t\mid U,V\})/\Pr_S(\{\vct t\mid V\})$.
}:
$$
 \forall\nu\forall\sigma\quad
  \Pr\nolimits_S
   \{n_i(\vct t)=\nu+n_i(\vct s), z_i(\vct t)\le\sigma+z_i(\vct s)
   \mid \vct t\sqsupset\vct s\}\le \Pr(X_{\nu,\sigma})\,.
$$

Если $\nu<0$ или $\sigma<0$,
то вероятность слева равна $0$.
Далее считаем, что $\nu\ge 0$,
$\sigma\ge 0$.

Предположим $\ell(\vct s)=L$, тогда
\begin{itemize}
\item[\qquad] если $\nu=0$,
      то вероятность справа равна $1$;\\
 если $\nu\ne 0$, то вероятность слева равна $0$.
\end{itemize}

Базис индукции доказан.

Делая индуктивный переход, разбер\"ем два случая.
Для краткости обозначим
$P(\vct s,\nu,\sigma)=\Pr\nolimits_S
 \{n_i(\vct t)=\nu+n_i(\vct s), z_i(\vct t)\le\sigma+z_i(\vct s)
 \mid \vct t\sqsupset\vct s\}$,
$\Pr\nolimits_S\{\vct t\sqsupset\vct s0\mid \vct t\sqsupset\vct s\}=
\frac{|S_{\vct s0}|}{|S_{\vct s}|}=\frac{1+x}{2}$.
\begin{enumerate}
\item В позиции $\vct s$ стратегия не делает
      на нуль ставку размера $i/M$. Тогда
\begin{multline*}
 P(\vct s,\nu,\sigma)=\frac{1+x}{2}P(\vct s0,\nu,\sigma)+
                      \frac{1-x}{2}P(\vct s1,\nu,\sigma)\le\\
  \left(\frac{1+x}{2}+\frac{1-x}{2}\right)
    \Pr(X_{\nu,\sigma})=\Pr(X_{\nu,\sigma})\,.
\end{multline*}

\item В позиции $\vct s$ стратегия делает
      на нуль ставку размера $i/M$.
      Напомним, что в этом случае $i/M\le x$.
      Тогда
\begin{multline*}
 P(\vct s,\nu,\sigma)=\frac{1+x}{2}P(\vct s0,\nu-1,\sigma-1)+
                      \frac{1-x}{2}P(\vct s1,\nu-1,\sigma)\le\\
                      \frac{1+x}{2}\Pr(X_{\nu-1,\sigma-1})+
                      \frac{1-x}{2}\Pr(X_{\nu-1,\sigma})\,.
\end{multline*}
С другой стороны,
$$
 \Pr(X_{\nu,\sigma})=\frac{1+i/M}{2}\Pr(X_{\nu-1,\sigma-1})+
                     \frac{1-i/M}{2}\Pr(X_{\nu-1,\sigma})\,.
$$
Очевидно, что $\Pr(X_{\nu-1,\sigma})\ge\Pr(X_{\nu-1,\sigma-1})$.
Поэтому, уменьшая вес меньшего слагаемого
(с $(1+x)/2$ до $(1+i/M)/2$) и
соответственно увеличивая вес большего,
мы только увеличим сумму.
Отсюда получаем требуемое неравенство
$P(\vct s,\nu,\sigma)\le\Pr(X_{\nu,\sigma})$.
\end{enumerate}

Таким образом,
$|S(\vct t_1,i)|/|S|=
\Pr_S\{n_i(\vct t)=\nu,\: z_i(\vct t)\le \sigma\}\le
\Pr(X_{\nu,\sigma})$,
где
$\nu=n_i(\vct t_1)$,
$\sigma=(\half+i/2M)\nu - i \nu/2BM$.

Из оценки Чернова имеем
$$
\Pr(X_{\nu,\sigma})\le \Exp{-2(\frac{i}{2BM})^2\nu}\,,
$$
и используя то, что $i\ge 1$, а
$n_i(\vct t_1) > \frac{L}{M^2}$,
получаем окончательную оценку
$$
|S(\vct t_1,i)| < |S|\Exp{-\frac{L}{2B^2 M^4}}\,.
$$
\end{proof}

\begin{note}
 Можно доказать, что в теореме~\ref{thm:cover}
(в отличие от теоремы~\ref{thm:MS})
недостаточно рассматривать только семейства
правильных множеств с одним и тем же отклонением $\epsilon$.
\end{note}

\begin{note}
В доказательстве теоремы~\ref{thm:cover} были использованы
правильные множества, порожд\"енные
только монотонными правилами.
В теореме~\ref{thm:no_adapt} будет показано, что нельзя ограничиться
правильными множествами, по\-рож\-д\"ен\-ными неадаптивными правилами.
\end{note}

Следующая теорема показывает,
что оценка теоремы~\ref{thm:cover}
на удельный дефект правильных множеств
точна.

\begin{thm}\label{thm:no_cover}
Пусть $\delta\in(0,\Exp{-\Exp{8}})$
и фиксировано натуральное $L\ge (1/\delta)^5$.
Будем рассматривать множества
двоичных последовательностей длины $L$.
Существует множество $S$ с удельным дефектом
больше $\delta$, которое нельзя покрыть менее
чем $\Exp{L\delta^4/70}$ правильными множествами
с удельным дефектом не меньше
$$
\frac{2\delta}{\ln(1/\delta)}\,.
$$
\end{thm}
\begin{proof}
Положим
\begin{gather*}
m=\left\lfloor\left.\left(2-4\sqrt{\delta\ln(1/\delta)}\right)
   \right/
           \delta\ln 2\right\rfloor\,,\\
k=\lfloor L/2m \rfloor\,.
\end{gather*}

Каждую последовательность длины $L$ мы будем представлять в виде
конкатенации $m$ пар последовательностей длины $k$
и \glqq{}остатка\grqq{} длины $L-2km<2m$.
В каждой паре одна последовательность сопоставлена
(в уточняемом далее смысле) цифре $0$,
другая~--- цифре $1$; мы будем называть эти последовательности
$i$-ым $0$- и $1$-отрезками исходной
последовательности $\vct t$ длины $L$
и обозначать $\vct t_{i,0}$ и $\vct t_{i,1}$ соответственно.

Определим сначала для каждого $i$ от 1 до $m$ множества $S_{i,0}$ и
$S_{i,1}$ последовательностей длины $k$.
Пусть $p_i=\half+\frac{1}{\sqrt{i\ln m}}$. Тогда
$S_{i,0}$ состоит из последовательностей, в которых не менее
$k(p_i-\frac{1}{m})$ нулей, а
$S_{i,1}$ состоит из последовательностей, в которых не менее
$k(p_i-\frac{1}{m})$ единиц.
К множеству $S$ отнес\"ем все последовательности $\vct t$, у которых
$\vct t_{i,0}\in S_{i,0}$ и $\vct t_{i,1}\in S_{i,1}$
для каждого $i$.

Оценим сначала удельный дефект $S$.
Мощность $S$ равна произведению
$|S_{i,0}|\cdot|S_{i,1}|$ по всем $i$,
умноженному на $2^{L-2km}$~---
количество возможных \glqq остатков\grqq,
поэтому из оценки Чернова (для равномерного
распределения на всех двоичных последовательностях)
получаем:
$$
|S|\le 2^{L-2km}\prod_{i=1}^m
\left(2^k\Exp{-2k\left(\frac{1}{\sqrt{i\ln m}}
         -\frac{1}{m}\right)^2}\right)^2=
2^{L-2km}\cdot2^{2km}\Exp{-4k\sum\limits_{i=1}^m
    \left(\frac{1}{\sqrt{i\ln m}}
          -\frac{1}{m}\right)^2}\,.
$$
Поскольку $1-\frac{\sqrt{i\ln m}}{m}\ge
           1-\sqrt{\frac{\ln m}{m}}$\:
и\: $\sum\limits_{i=1}^m\frac{1}{i}>\ln m$,
имеем
$$
\sum_{i=1}^m \left(\frac{1}{\sqrt{i\ln m}}
                   -\frac{1}{m}\right)^2=
\sum_{i=1}^m \frac{1}{i\ln m}
        \left(1-\frac{\sqrt{i\ln m}}{m}\right)^2 >
\frac{\ln m}{\ln m}
    \left(1-\sqrt{\frac{\ln m}{m}}\right)^2.
$$
Откуда
$|S| < 2^L\Exp{-4k\left(1-2\sqrt{\frac{\ln m}{m}}\right)}$,
и таким образом удельный дефект $S$ больше
$\frac{4k}{L\ln 2}\left(1-2\sqrt{\frac{\ln m}{m}}\right)
> \left(\frac{2}{m\ln 2}-\frac{4}{L\ln 2}\right)
   \left(1-2\sqrt{\frac{\ln m}{m}}\right)>
\delta$.


Возьм\"ем какое-нибудь покрытие $S$ правильными множествами,
в котором меньше $\Exp{L\delta^4/70}$ элементов.
Докажем, что хотя бы одно множество в этом покрытии
имеет удельный дефект меньше
$\frac{2\delta}{\ln(1/\delta)}$.

Схема доказательства следующая. Рассмотрим множество правил,
соответствующих участвующим в покрытии правильным множествам.
Для каждого правила $r$ назов\"ем
последовательность $r$-типичной, если
в выбранной подпоследовательности
отклонение частоты от $\half$
невелико по отношению к длине выборки.
Затем мы докажем, что во множестве $S$
найд\"ется последовательность, типичная
для всех рассматриваемых правил
(показав, что вероятность противоположного события
относительно некоторого распределения вероятностей
строго меньше единицы).
Поэтому одно из множеств покрытия
имеет малый дефект.


Пусть $\vct t$~--- последовательность длины $L$,
а $r$~--- нормальное правило выбора.
Мы дадим определение $r$-типичности в
предположении, что в выборке $r[\vct t]$
количество единиц больше количества нулей;
если это не так, всюду в определении
надо заменить $0$ на $1$ и наоборот.
Обозначим через $n$ длину выбираемой подпоследовательности
$r[\vct t]$, через $n_i$~--- количество цифр, выбранных правилом $r$
из $i$-ого $1$-отрезка последовательности, а через $n'$~--- общее
количество цифр, выбранных правилом $r$ из $0$-отрезков
последовательности (и таким образом
$n\ge\sum_{i=1}^m n_i+n'$ и $n_i\le k$).
Последовательность $\vct t$ назов\"ем
$r$-типичной, если выполнены следующие условия:
\begin{itemize}
 \item количество единиц, выбранных из $i$-го $1$-отрезка,
       меньше\\
       $n_i p_i+\sqrt{\frac{kn_i}{m^3}}$;
 \item либо $n'<k/m$, либо среди цифр,
       выбранных из $0$-отрезков,
       количество единиц меньше количества нулей.
\end{itemize}


Определим вспомогательную меру на
последовательностях длины $L$:
цифры появляются независимо,
цифры из $i$-го $0$-отрезка ($1$-отрезка)
с вероятностью $p_i$ равны нулю
(соответственно, единице),
цифры из \glqq{}остатка\grqq{} равны нулю
с вероятностью $\half$.

Оценим вероятность (по введ\"енной мере) того, что наугад выбранная
последовательность $\vct t$ длины $L$ не принадлежит множеству $S$:
\begin{multline*}
\Pr\{\vct t \notin S\}\le
\sum_{i=1}^m (\Pr\{\vct t_{i,0}\notin S_{i,0}\}
            +\Pr\{\vct t_{i,1}\notin S_{i,1}\})\le\\
2m\cdot\Exp{-2k\left(\frac{1}{m}\right)^2}=
\Exp{-\frac{2k}{m^2}\left(1-\frac{m^2\ln 2m}{2k}\right)}\,.
\end{multline*}

Теперь зафиксируем какое-нибудь правило выбора и
оценим вероятность того, что наугад выбранная
последовательность $\vct t$ длины $L$ не $r$-типична
(как и в определении типичности,
мы считаем, что в выборке $r[\vct t]$ количество единиц больше
количества нулей; противоположный случай аналогичен).

Сначала оценим вероятность того, что хотя бы для одного
$i$ из $i$-ого $1$-отрезка выбрано
по крайней мере $n_i p_i+\sqrt{\frac{kn_i}{m^3}}$ единиц.
Она не превышает суммы вероятностей
соответствующих событий для каждого $i$.
При фиксированном $n_i>0$,
пользуясь оценкой Чернова, получаем
$$
\Exp{-2\frac{1}{n_i}\left(\sqrt{\frac{kn_i}{m^3}}\right)^2}\,.
$$
Поскольку $n_i$ нам неизвестно,
мы просуммируем вероятности по всем
возможным значениям $n_i\le k$.
Окончательная верхняя оценка:
$$
m\cdot k\cdot
 \Exp{-\frac{2k}{m^3}}\,.
$$

Оценим теперь вероятность того, что
из $0$-отрезков выбрано
$n'\ge\frac{k}{m}$ цифр и
среди этих цифр количество единиц
не меньше количества нулей.
При заданном $n'$ она не превышает
$$
\Exp{-2n'\left(p_m-\half\right)^2}\le
\Exp{-2\frac{k}{m}\frac{1}{m\ln m}}\,.
$$
Суммируя по всем возможным значениям
$n'\le mk$, окончательно получаем оценку
$$
mk\,\Exp{-\frac{2k}{m^2\ln m}}\,.
$$

Мы видим, что оценка вероятности нарушения первого
условия $r$-ти\-пич\-нос\-ти гораздо больше
оценки вероятности нарушения второго условия.
Учитывая симметричный случай (замена $0$ на $1$),
получим, что вероятность не $r$-типичности
наугад взятой последовательности меньше
$2mk\,\Exp{-\frac{L}{m^4}+1}\le
\Exp{-\frac{L}{m^4}+\ln L+1}$.
Умножая на количество правильных множеств,
покрывающих $S$, найд\"ем, что вероятность
\glqq не быть типичной последовательностью
хотя бы для одного правила\grqq{}
значительно меньше $1$
при $\delta < \Exp{-\Exp{8}}$, $L\ge (1/\delta)^5$.
После добавления малой вероятности
не принадлежать $S$ эта оценка по-прежнему
будет меньше единицы, поэтому существует
последовательность $\vct t\in S$,
которая типична для всех правил из покрытия.

Рассмотрим то множество $A$ из покрытия $S$,
которое содержит $\vct t$,
и соответствующее правило $r$.
Оценим сверху возможную величину
удельного дефекта $A$,
используя $r$-типичность $\vct t$.
Мы рассмотрим отдельно два случая.

\begin{enumerate}
 \item $n\le 8k/(\ln m \ln 2)$.
    Дефект $A$ не больше $n$,
    поэтому удельный дефект не больше
         $$
    \frac{n}{L}\le\frac{4}{m\ln m\ln 2}\,.
         $$

 \item $n > 8k/(\ln m \ln 2)$.
    Оценим сверху разность между количеством единиц
    в $r[\vct t]$ и половиной длины выборки
    (для нулей рассуждение симметрично).
    Она складывается из соответствующих разностей
    для $1$-отрезков, для $0$-отрезков
    и для \glqq остатка\grqq.
    Для \glqq{}остатка\grqq{} разность оценим просто
    половиной его длины, которая меньше $m$.
    В силу типичности на $0$-отрезках
    либо общая длина выборки
    (а значит и удвоенная разность)
    меньше $k/m$, либо в ней нулей больше чем единиц.
    На $1$-отрезках также в силу типичности
    разность меньше
     $$
      \sum_{i=1}^m \left(\frac{n_i}{\sqrt{i\ln m}}
                    +\sqrt{\frac{kn_i}{m^3}}\right)=
            \frac{1}{\sqrt{\ln m}}
         \sum_{i=1}^m\left(\frac{n_i}{\sqrt{i}}\right)
            +\sqrt{\frac{k}{m^3}}
         \sum_{i=1}^m \sqrt{n_i}\,.
     $$
 Так как корень~--- выпуклая функция,
 $$
 \sum\limits_{i=1}^m \sqrt{n_i}\le
   m\sqrt{\sum\limits_{i=1}^m n_i/m}\le\sqrt{nm}\,.
 $$

 С одной стороны,
 $\sum\limits_{i=1}^m \left(n_i/\sqrt{i}\right)\le n$.
 С другой стороны, чтобы оценить
 $\sum\limits_{i=1}^m \left(n_i/\sqrt{i}\right)$
 при $n > 4k$,
 заметим, что если $n_i$ увеличить на единицу,
 а $n_{i+1}$ уменьшить на единицу,
 то сумма увеличится. Мы знаем,
 что $n_i\le k$, $\sum n_i\le n$,
 поэтому увеличивая первые $n_i$ до $k$, получаем:
    $$
  \sum_{i=1}^m \left(\frac{n_i}{\sqrt{i}}\right)\le
   \sum_{i=1}^{\ulcorner n/k\urcorner}
         \left(\frac{k}{\sqrt{i}}\right) <
   k\cdot 2\sqrt{n/k}=2\sqrt{nk}\,.
    $$


 Окончательно получаем, что разность
 между количеством единиц в $r[\vct t]$ и $n/2$
 меньше
\begin{align*}
m+\frac{k}{2m}+\frac{\sqrt{nk}}{m}+
             \frac{n}{\sqrt{\ln m}} &<
\frac{n}{\sqrt{\ln m}}\left(1+\frac{\sqrt{\ln^3 m}}{m}\right)&&
\text{при $n\le 4k$}\,;\\
m+\frac{k}{2m}+\frac{\sqrt{nk}}{m}+
\frac{2\sqrt{nk}}{\sqrt{\ln m}}     &<
\frac{2\sqrt{nk}}{\sqrt{\ln m}}
 \left(1+\frac{\sqrt{\ln m}}{m}\right)&&
\text{при $n > 4k$}\,.
\end{align*}

 Поскольку правильное множество $A$
 содержит последовательность $\vct t$,
 его удельный дефект не больше
\begin{align*}
\frac{1}{L}\cdot\frac{2}{n\ln 2}\cdot
\frac{n^2}{\ln m}(1+o(1)) &\le
\frac{4}{m\ln m\ln 2}(1+o(1))&&
\text{при $n\le 4k$}\,;\\[5pt]
\frac{1}{L}\cdot\frac{2}{n\ln 2}\cdot
   \frac{4nk}{\ln m}(1+o(1))&\le
\frac{4}{m\ln m\ln 2}(1+o(1))&&
\text{при $n > 4k$}\,.
\end{align*}
Нижние оценки на биномиальный
коэффициент
$$
\binom{n}{j} \ge
\frac{\Exp{n\cdot h(j/n)}}{\sqrt{8 j(n-j)/n}}
$$
и на шенноновскую функцию энтропии
(при $\epsilon\le\frac{1}{\sqrt{12}}$)
$$
h\left(\half+\epsilon\right)\ge
  \ln 2 - 2\epsilon^2(1+\epsilon^2)
$$
показывают, что величины $o(1)$,
входящие в предыдущие выражения,
меньше $1/\ln(1/\delta)$. С другой стороны,
$\ln m > \ln(1/\delta)(1+1.05/\ln(1/\delta))$.
\end{enumerate}

Во всех случаях хотя бы у одного
правильного множества из покрытия $S$
удельный дефект меньше
$$
 \frac{2\delta}{\ln(1/\delta)}\,.
$$
\end{proof}

%\begin{note}
% Множество $S$ эффективно строится по $\delta$ и $L$.
%\end{note}


\begin{thm}\label{thm:no_adapt}
Для любого $\sigma > 0$ и для любого
$L \ge 12+6\lb(1/\sigma)$
существует множество двоичных
последовательностей длины $L$
с удельным дефектом $\ge 1/3$, которое нельзя покрыть
менее чем $2^{\sigma L/2}$
неадаптивными правильными множествами
с удельным дефектом $\ge\sigma$.
\end{thm}
\begin{proof}
Рассмотрим упорядоченный набор из $2^{\lfloor 2L/3\rfloor}$
последовательностей длины $L$ (возможно, с повторениями).
Множество входящих в него последовательностей имеет
удельный дефект не меньше $1/3$.
Поэтому для доказательства теоремы достаточно найти такой
набор, который нельзя покрыть никаким семейством,
состоящим из менее чем $2^{\sigma L/2}$ неадаптивных
правильных множеств с удельным дефектом не меньше $\sigma$
(можно считать, что $\sigma\le 1$).

Количество наборов из $2^{\lfloor 2L/3\rfloor}$
последовательностей равно
$$
\left(2^L\right)^{2^{\lfloor 2L/3\rfloor}}\,.
$$
Оценим количество наборов,
которые можно покрыть семействами указанного типа.

Зафиксируем какое-нибудь такое семейство $\als_L$.
Количество покрываемых им наборов равно
$$
|\cup\als_L|^{2^{\lfloor 2L/3\rfloor}}\,.
$$
Из условия на $\als_L$ имеем:
$$
|\cup\als_L|\le|\als_L|\max\{|A|\colon A\in\als_L\} <
   2^{\sigma L/2}\cdot 2^{L-\sigma L} =
  2^{L-\sigma L/2}\,.
$$
Таким образом, количество наборов, покрываемых одним семейством правильных
множеств, меньше
$$
  2^{(L-\sigma L/2)\cdot 2^{\lfloor 2L/3\rfloor}}\,.
$$

Семейству $\als_L$ соответствует некоторое семейство
неадаптивных правил $\rls_L$.
Выбирая различные отклонения,
мы получаем, вообще говоря,
различные семейства правильных множеств
(большого дефекта),
соответствующие одному и тому же
множеству правил. Однако с ростом отклонения
класс покрываемых наборов
может только уменьшаться,
поэтому одно семейство правил мощности
$< 2^{\sigma L/2}$
обеспечивает покрытие также менее
$$
  2^{(L-\sigma L/2)\cdot 2^{\lfloor 2L/3\rfloor}}
$$
наборов.

Заметим, что неадаптивное правило по сути является подмножеством
$\{1,\ldots,L\}$, поэтому количество неадаптивных правил равно $2^L$.
Количество семейств, состоящих из менее чем
$2^{\sigma L/2}$ неадаптивных правил,
меньше
$$
 2^{L\cdot 2^{\sigma L/2}}\,.
$$
Поэтому с помощью таких семейств
можно покрыть менее
$$
 2^{L\cdot 2^{\sigma L/2}}\cdot
   2^{(L-\sigma L/2)\cdot 2^{\lfloor 2L/3\rfloor}}=
  \left(2^L\right)^{2^{\sigma L/2}+
     \left(1-\frac{\sigma}{2}\right)2^{\lfloor 2L/3\rfloor}}
$$
наборов.
Чтобы убедиться в существовании
не покрытых наборов,
достаточно проверить, что
$$
  \left(2^L\right)^{2^{\sigma L/2}+
     \left(1-\frac{\sigma}{2}\right)2^{\lfloor 2L/3\rfloor}}
  \le \left(2^L\right)^{2^{\lfloor 2L/3\rfloor}}\,.
$$
Последнее следует из
$L(2/3-\sigma/2) \ge 2-\lb\sigma$.
Это неравенство вытекает из
$L \ge 12+6\lb(1/\sigma)$ и $\sigma\le 1$.
\end{proof}


\subsection{Алгоритмический подход}

\begin{defn}\label{def:alg_defect}
\emph{Дефектом\/} непустой
двоичной последовательности $\vct t$
длины $L$ называется величина
$L-K(\vct t|L)$,
где $K(\vct t|L)$~--- энтропия $\vct t$ при известном $L$.
\emph{Удельным дефектом\/} называется дефект, дел\"енный
на длину. (Аддитивная константа из определения энтропии,
дел\"енная на
длину последовательности, стремится к нулю,
когда длина стремится к
бесконечности.
Так что в пределе понятие удельного дефекта инвариантно.)
\end{defn}

Так как в доказательствах для оценки
дефекта последовательностей мы будем
использовать дефект
вспомогательных правильных множеств,
введ\"ем следующее обозначение.
Если нормальное правило $r$ выбирает
подпоследовательности длины $n$,
то дефект правильного множества $A_{r,\epsilon}$
будет обозначаться через $D(n,\epsilon)$.
Важным свойством дефекта правильного множества
является то, что он не зависит от $L$
(длины последовательностей, к которым
применяется правило выбора).
Если $n$ фиксировано, то $D$ становится
монотонно возрастающей
ступенчатой функцией от $\epsilon\in[0,\half]$.
При этом границы между ступенями~---
рациональные числа со знаменателем $2n$,
значения функции~--- это двоичные логарифмы
рациональных чисел, и все эти рациональные числа
вычислимо зависят от $n$.

Когда $\epsilon$ достаточно мало, а $n$ достаточно
велико по сравнению с $1/\epsilon$, то
$D(n,\epsilon)\sim d(n,\epsilon)$.

На первый взгляд естественным аналогом
теоремы~\ref{thm:cover} была бы такая

\begin{statement}\label{stat:cover}
Пусть $\delta>0$ достаточно мало и
натуральное $L$ достаточно велико.
Если $\vct t$~--- двоичная
последовательность длины $L$
с удельным дефектом $\ge\delta$, то
существует правило $r$,
для которого
$$
K(r|L)\le\alpha(\delta)\quad\text{и}\quad
D(n,\epsilon)/L \ge \delta'(\delta)\,,
$$
где $n$~--- длина $r[\vct t]$,
$\epsilon$~--- отклонение доли нулей
в $r[\vct t]$ от $\half$,
а $\alpha$ и $\delta'$~---
некоторые положительные функции.
\end{statement}

Однако следующая теорема очевидно влеч\"ет
отрицание формулировки~\ref{stat:cover}.
\renewcommand{\thmprimname}{Теорема~\ref{thm:cover}$''$}
\begin{thm_prim}
Пусть $\alpha$ и $\delta'$~---
положительные числа.
Для любого достаточно большого
натурального $L$ найд\"ется такая
двоичная последовательность $\vct t$ длины $L$
с удельным дефектом больше $\half$, что
для каждого правила $r$
$$
K(r|L)\le\alpha
\quad\Rightarrow\quad
D(n,\epsilon)/L < \delta'\:
\lor\: n=0\,,
$$
где $n$~--- длина $r[\vct t]$,
$\epsilon$~--- отклонение доли нулей
в $r[\vct t]$ от $\half$.
\end{thm_prim}
\begin{proof}
Обозначим через $\rls_L$ семейство всех правил $r$,
для которых $K(r|L)\le\alpha$.
Зная числа $\left\lfloor\alpha\right\rfloor$,
$L$ и $|\rls_L|$,
можно эффективно найти список элементов $\rls_L$.
Обозначим $n$-нормализацию правила $r$
через $r_n$.

Рассмотрим на двоичных последовательностях
длины $L$ равномерное распределение.
Из определения функции $D$ следует, что
для каждого правила $r$
вероятность множества $A_{r_n,\epsilon}$
равна $2^{-D(n,\epsilon)}$.

Для каждого $n$ возьм\"ем наименьшую
границу ступени
$\epsilon$, для которой
$D(n,\epsilon) \ge \delta'L$.
Если такое $\epsilon$ существует, оно будет
рациональным числом из $[0,\half]$
со знаменателем $2n$.
Полученный набор пар $\pair{n,\epsilon}$
обозначим через $E$.
Поскольку $|\rls_L| < 2^{\alpha+1}$,
а $|E|\le L$,
то вероятность объединения
множеств $A_{r_n,\epsilon}$
для $r\in\rls_L$ и
$\pair{n,\epsilon}\in E$
не превышает
$$
\sum\limits_{\pair{n,\epsilon}\in E}
2^{-D(n,\epsilon)+\alpha+1}\le
2^{-\delta'L+\alpha+1+\lb L}\,.
$$
При достаточно больших $L$ последнее выражение
строго меньше $1$.
Зная списки элементов $\rls_L$ и $E$,
можно перебором найти
последовательность $\vct t$ длины $L$,
которая не принадлежит $A_{r_n,\epsilon}$
при всех $r\in\rls_L$ и
$\pair{n,\epsilon}\in E$.

Теперь постараемся экономно закодировать
информацию, достаточную для построения списка
элементов $E$.
Понятно, что набор $E$ можно построить, если
известно $L$ и та пара,
на которой функция $D$ достигает своего
минимума на $E$.
Таким образом, энтропия списка элементов $E$
при известном $L$
не превышает $2\lb L+O(1)$.

Так как последовательность $\vct t$
построена по числам $L$,
$\left\lfloor\alpha\right\rfloor$,
$|\rls_L|$ и набору $E$,
то $K(\vct t|L)\le 2\lb L+C(\alpha)$.
Удельный дефект $\vct t$ равен
${1-K(\vct t|L)/L}$, что больше $\half$
при достаточно больших $L$.

Пусть $r\in\rls_L$, $n=\ell(r[\vct t])$
и $\epsilon$~--- отклонение в $r[\vct t]$.
Предположим, что
$D(n,\epsilon)/L \ge \delta'$.
Тогда по построению $\vct t$
не принадлежит $A_{r_n,\epsilon}$,
и поэтому отклонение в $r[\vct t]$
должно быть строго меньше $\epsilon$.
Противоречие, теорема доказана.
\end{proof}

Для восстановления аналогии с комбинаторным подходом
при алгоритмическом подходе правила выбора надо понимать не как явно
заданные функции, а как
программы, которые, получив в качестве дополнительного
входа длину последовательности $L$, вычисляют функцию $r$
из определения~\ref{def:rule}, прич\"ем теперь функция $r$
может быть \emph{не всюду определ\"енной}.

\begin{defn}\label{def:fre_defect}
\emph{Частотным $\alpha$-дефектом\/}
двоичной последовательности $\vct t$
длины $L$ называется максимум величины
$D(n,\epsilon)/L$ по правилам $r$,
заданным такими программами, что
$r[\vct t]$ определено и энтропия программы
при известном $L$ меньше $\alpha$
(где $n$~--- длина $r[\vct t]$,
а $\epsilon$~--- отклонение доли нулей
в $r[\vct t]$ от $\half$).
\end{defn}

Отметим, что с ростом $\alpha$ частотный
$\alpha$-дефект может только увеличиваться.

\renewcommand{\thmprimname}{Теорема~\ref{thm:cover}$'$}
\begin{thm_prim}
Пусть $\delta_1 > 0$ достаточно мало.
Тогда по каждому
рациональному $\delta_0 > 0$
можно эффективно указать
такое $L_0$, что
для любых $\delta \in[\delta_0,\delta_1]$
и натурального $L \ge L_0$
выполнено следующее.
Если $\vct t$~--- двоичная
последовательность длины $L$
с удельным дефектом $\delta$, то
частотный $\alpha$-дефект $\vct t$
больше
$$
\delta'=\frac{\delta}{\ln(1/\delta)}(1-B(\delta))\,,
$$
где $\alpha=\frac{4\ln(1/\delta)}{\delta}$
и $B(\delta)=O(\frac{\ln\ln(1/\delta)}{\ln(1/\delta)})$.
\end{thm_prim}
\begin{note}
  Мы видим, что данная теорема соответствует
  формулировке~\ref{stat:cover}.
\end{note}
\begin{proof}
Строим правило, выбирающее из $\vct t$
подпоследовательность с большим отклонением.
Разделим последовательность $\vct t$
на две части примерно равной длины
(то есть их длины равны $\lfloor L/2\rfloor$ и
$\lceil L/2\rceil$).
Каждую часть снова разделим на две части
примерно равной длины и так далее.
Перед $(i+1)$-м этапом рекурсивного построения
нашего правила будет указана одна из частей
$\vct t$, получившаяся после $i$ делений
(перед первым этапом указанная часть~---
это сама последовательность $\vct t$).
Обозначим эту часть через $\vct u_i$,
а е\"е дополнение\footnote{
Под дополнением мы понимаем двоичный код
результата замены в последовательности
$\vct t$ цифр из $\vct u_i$
на некоторый специальный знак.}
через $\vct v_i$.
Предполагается, что перед $(i+1)$-м этапом
перев\"ернуты были в точности карты из $\vct v_i$,
прич\"ем ни одна не была включена
в подпоследовательность.
Предполагается также, что
условный удельный дефект $\vct u_i$
при известном $\vct v_i$ больше
$\delta+\lambda(i-1)$,
где $\lambda$~---
такое число из интервала
$(\frac{\delta}{\ln (1/\delta)},
\frac{2\delta}{\ln (1/\delta)})$,
что число $1-\delta+3\lambda$ рационально.
При больших $L$ последнее предположение,
очевидно, выполнено для $i=0$.


Теперь опишем $(i+1)$-ый этап.
Разобь\"ем последовательность $\vct u_i$
на две примерно равные по длине части,
обозначим их $\vct w_1$ и $\vct w_2$.
Пусть $\gamma=
\left\lfloor
(1-\delta+3\lambda)\ell(\vct w_1)
\right\rfloor$.
Рассмотрим два возможных случая.

\begin{enumerate}
\item \label{en:4_1}
      Пусть
      $K(\vct w_1|\vct v_i) < \gamma$ и
      $K(\vct w_2|\vct v_i) < \gamma$.

      Поскольку функция энтропии перечислима
      сверху, при известных $\vct v_i$ и $\gamma$
      эти факты можно обнаружить, скажем,
      за $T_1$ и $T_2$ шагов перечисления.
      Числа $T_1$ и $T_2$ нам неизвестны.
      Наша цель~--- узнать большее из них.
      Пусть, например, $T_1\le T_2$.
      Тогда правило должно перевернуть
      все карты из $\vct w_2$,
      ничего не включая в подпоследовательность.
      Зная $\vct w_2$, можно дождаться его появления
      в упомянутом перечислении и тем самым узнать $T_2$.
      Теперь рассмотрим $S$~--- множество
      последовательностей $\vct s$ длины
      $\ell(\vct w_1)$,
      для которых выполнение неравенства
      $K(\vct s|\vct v_i) < \gamma$
      обнаруживается не более чем за $T_2$ шагов.
      Очевидно, что $\vct w_1\in S$.
      Множество $S$ содержит менее
      $2^{\gamma}$ элементов,
      поэтому его удельный дефект больше
      $1 - \gamma/\ell(\vct w_1)\ge
      \delta-3\lambda$.
      (Если бы оказалось, что
      $T_1\ge T_2$, то получилось бы
      аналогичное неравенство, поскольку
      $\ell(\vct w_1)\le\ell(\vct w_2)$.)

      Теперь применим теорему~\ref{thm:cover}
      к множеству $S$ с указанной оценкой
      на удельный дефект.
      Из доказательства теоремы~\ref{thm:cover}
      вытекает существование
      такого семейства $\rls$ правил,
      что
      $$
      |\rls| \le
       \left(\frac{1}{\delta-3\lambda}\right)^
                             {1/(\delta-3\lambda)+O(1)}
      $$
      и  правильные множества, задаваемые
      нормализациями правил из $\rls$,
      покрывают $S$.
      Одно из этих правильных множеств
      (назов\"ем его $A$)
      содержит $\vct w_1$ и имеет удельный дефект
      $\ge\frac{\delta-3\lambda}
        {\ln(1/(\delta-3\lambda))}(1-\beta)$,
      где $\beta=O\left(\frac{\ln\ln(1/(\delta-3\lambda))}
                 {\ln(1/(\delta-3\lambda))}\right)
      =O\left(\frac{\ln\ln(1/\delta)}
                 {\ln(1/\delta)}\right)$.
      Пусть нормальное правило, задающее множество $A$,
      выбирает из $\vct w_1$ подпоследовательность
      длины $n$ с отклонением $\epsilon$.
      Поскольку дефект $A$ не больше
       $D(n,\epsilon)$, то
      \begin{multline*}
      \frac{D(n,\epsilon)}{L}\ge
        \frac{\delta-3\lambda}
             {\ln(1/(\delta-3\lambda))}(1-\beta)=\\
        \frac{\delta}{\ln(1/\delta)}
            \left(1-O\left(\frac{1}{\ln(1/\delta)}\right)\right)
              (1-\beta)=\\
         \frac{\delta}{\ln(1/\delta)}
            \left(1-O\left(\frac{\ln\ln(1/\delta)}
                        {\ln(1/\delta)}\right)\right)\,.
      \end{multline*}

      После реализации случая $\ref{en:4_1})$ правило выбора
      завершает работу.

\item Пусть
      $K(\vct w_1|\vct v_i) \ge \gamma$ или
      $K(\vct w_2|\vct v_i) \ge \gamma$.

      Пусть для определ\"енности
      $K(\vct w_1|\vct v_i) \ge \gamma$.
      По теореме об энтропии  пары
      $K(\vct u_i|\vct v_i)=K(\vct w_1|\vct v_i)+
        K(\vct w_2|\vct w_1,\vct v_i)-
        O(\log K(\vct u_i|\vct v_i))$
      (понятно, что можно отождествлять пару
      $\pair{\vct w_1,\vct v_i}$ с дополнением до
      $\vct w_2$).
      Следовательно,
      $K(\vct w_2|\vct w_1,\vct v_i)=
       K(\vct u_i|\vct v_i) - K(\vct w_1|\vct v_i)+
        O(\log K(\vct u_i|\vct v_i))\le
       (1-\delta-\lambda(i-1))\ell(\vct u_i)-
       (1-\delta+3\lambda)\ell(\vct w_1)+
       O(\log \ell(\vct u_i))\le
       (1-\delta-2\lambda i-\lambda)\ell(\vct w_2)+
       O(\log \ell(\vct u_i))$.
      Отсюда при большом $\ell(\vct u_i)$
      просто вывести следующее неравенство на
      условный удельный дефект $\vct w_2$ при известных
      $\vct w_1$ и $\vct v_i$:
         $$
       1 - \frac{K(\vct w_2|\vct w_1,\vct v_i)}
            {\ell(\vct w_2)} >
           \delta + \lambda i\,.
         $$

      После этого правило выбора переходит к $(i+2)$-ому
      этапу с $\vct u_{i+1}=\vct w_2$.
\end{enumerate}

Так как удельный дефект не бывает больше $1$,
то второй случай реализуется менее
$(1 - \delta)/\lambda$ раз.
Поэтому количество этапов в построенном правиле
выбора не превышает некоторого числа,
не зависящего от $L$.
Отсюда следует, что при достаточно большом $L$
предположение о том, что $\ell(\vct u_i)$
велико, выполнено для всех $i$.


Осталось оценить энтропию (при известном $L$)
построенного правила.
При его построении мы пользовались
следующей информацией:
\begin{itemize}
 \item чему равно $1-\delta+3\lambda$;
 \item для каждого этапа~--- выполнен первый
       или второй случай;
 \item для второго случая (на каждом этапе):
       какое из неравенств верно:
       $K(\vct w_1|\vct v_i) \ge \left\lfloor
        (1-\delta+3\lambda)\ell(\vct w_1)
           \right\rfloor$
       или
       $K(\vct w_2|\vct v_i) \ge \left\lfloor
        (1-\delta+3\lambda)\ell(\vct w_1)
           \right\rfloor$;
 \item для первого случая (на одном этапе~--- последнем):
       какое из неравенств верно~---
       $T_1 \le T_2$ или  $T_1 \ge T_2$,
       а также
       номер множества $A$ в
       семействе $\rls$.
\end{itemize}

Для нахождения рационального
числа $1-\delta+3\lambda$
достаточно найти число $\delta-3\lambda$,
а для этого достаточно найти натуральное число
из интервала
$((\delta-\frac{3\delta}{\ln (1/\delta)})^{-1},
(\delta-\frac{6\delta}{\ln (1/\delta)})^{-1})$.
Поскольку длина указанного интервала больше $1$,
в н\"ем есть натуральное число, и
энтропия этого числа не больше $\lb(1/\delta)+O(1)$.

Итак, верхняя оценка на энтропию нашего правила
получится, если к следующей сумме добавить
несколько е\"е логарифмов
(нужных для кодирования кортежа):
$$
 \lb\frac{1}{\delta}+O(1)+
 2\cdot\left(\frac{1 - \delta}{\lambda}+O(1)\right)+
 \lb |\rls|+O(1)\,.
$$

При малых $\delta$ найденная оценка
меньше
$\frac{4\ln(1/\delta)}{\delta}$.

Заметим наконец, что когда мы говорили
\glqq $L$ достаточно велико\grqq,
соответствующая нижняя оценка на $L$
могла быть эффективно указана по $\delta_0$.
Значение $L_0$ есть максимум этих оценок.
\end{proof}

\begin{note}
Если в теореме~\ref{thm:cover}
достаточно ограничиться правильными множествами, порожд\"енными
монотонными правилами (а неадаптивных правил не хватает),
то для теоремы~\ref{thm:cover}$'$ необходимы немонотонные правила, как
показывает теорема~\ref{thm:no_adapt}$'$.
\end{note}

\renewcommand{\thmprimname}{Теорема~\ref{thm:no_cover}$'$}
\begin{thm_prim}
Пусть $\delta_0>0$ достаточно мало
и натуральное $L \ge (1/\delta_0)^5$.
Существует двоичная
последовательность
$\vct t$ длины $L$ с удельным дефектом
больше $\delta_0$, у которой частотный
$\alpha$-дефект меньше
$$
\frac{2\delta_0}{\ln(1/\delta_0)}(1+3\delta_0)
$$
при $\alpha=L\delta_0^4/70$.
\end{thm_prim}
\begin{proof}
Возьм\"ем множество правил,
у которых энтропия при известном $L$ меньше $\alpha$.
Некоторые из этих правил не всюду определены.
Доопределим их произвольным образом и
произвед\"ем $n$-нормализацию для всех $n=1,\ldots,L$.
Получившихся нормальных правил меньше
$L\cdot 2^{\alpha} < \Exp{L\delta_0^4/70}$.
Рассмотрим множество последовательностей $S$,
построенное (эффективно) в теореме~\ref{thm:no_cover}
по числам $\delta=\frac{1}{\lfloor 1/\delta_0\rfloor-1}$
и $L$. Поскольку $\delta > \delta_0$, то
$L>(1/\delta)^5$,
$\Exp{L\delta^4/70} > \Exp{L\delta_0^4/70}$
и по теореме~\ref{thm:no_cover} найд\"ется
$\vct t\in S$, для которого
$$
\max\left\{D(n,\epsilon)/L\mid
    n=\ell(r[\vct t]), K(r|L)< \alpha\right\} <
  \frac{2\delta}{\ln(1/\delta)} <
  \frac{2\delta_0}{\ln(1/\delta_0)}(1+3\delta_0)\,.
$$
Энтропия любого $\vct t\in S$ при известном $L$
не превышает $2\lb(1/\delta)+\lb|S|$.
Поэтому удельный дефект $\vct t$ не меньше
$1-\frac{\lb|S|+2\lb(1/\delta)}{L}$.
По теореме~\ref{thm:no_cover} удельный дефекет $S$
(равный $1-\lb|S|/L$) больше $\delta$.
Следовательно, удельный дефект $\vct t$ больше
$\delta-2\lb(1/\delta)/L > \delta_0$.
\end{proof}

\begin{defn}
  Назов\"ем \emph{монотонным
$\alpha$-частотным дефектом} двоичной
последовательности $\vct t$ длины $L$
максимум величины $D(n,\epsilon)/L$ по
монотонным правилам $r$,
заданным программами энтропии
меньше $\alpha$,
где $n$~--- длина $r[\vct t]$,
$\epsilon$~--- отклонение в $r[\vct t]$,
в энтропии предполагается условие $L$.
\end{defn}

\renewcommand{\thmprimname}{Теорема~\ref{thm:no_adapt}$'$}
\begin{thm_prim}
Пусть $\delta>0$ достаточно мало и натуральное
$L\ge (1/\delta)^2$.
Существует двоичная последовательность
$\vct t$ длины $L$ с удельным дефектом
больше $\half$,
для которой монотонный
$(\delta L/4)$-частотный дефект
меньше $\delta$.
\end{thm_prim}
\begin{proof}
 Для построения последовательности $\vct t$ мы рассмотрим игру, похожую
на ту, которая была использована в доказательстве теоремы~\ref{thm:cover}.
Отличие заключается в том, что величина ставки может
принимать любые значения, не превышающие текущего капитала
(поэтому игра называется \glqq игрой на наличные\grqq).
Начальный капитал равен $1$.
Удобно называть ставкой долю $\sigma$ текущего капитала;
тогда текущий капитал умножается на $(1+\sigma)$ при выигрыше
(если следующая цифра угадана) и на $(1-\sigma)$ при проигрыше.

Каждому монотонному правилу $r$, двоичной цифре $b$
и числу $\sigma\in[0,1]$
сопоставим следующую стратегию в игре:
на шаге $i$ правило $r$ применяется к отрезку
$\vct t_{1:i-1}$;
если следующая цифра выбрана
в подпоследовательность, делается ставка
$\sigma$ на цифру $b$,
если же следующая цифра не выбрана,
ставка не делается.
Если $r$ на некотором $\vct t_{1:i-1}$ не определено
(программа не останавливается),
то на всех последующих шагах стратегия не определена
и текущий капитал тоже становится неопредел\"енным.
Очевидно, что если в выбранной
подпоследовательности $r[\vct t]$ длины
$n$ цифра $b$ встречается $n_b$ раз,
то конечный капитал стратегии равен
$(1+\sigma)^{n_b}(1-\sigma)^{n-n_b}$
(а отклонение равно $\left|\half-\frac{n_b}{n}\right|$,
поэтому из оценки на капитал
можно получить оценку на отклонение).

Сначала предположим, что $1/\delta$~---
натуральное число. В конце объясним,
как перейти к произвольному $\delta$.
Пусть $\rls_L$~--- множество всех
монотонно выбирающих программ энтропии
меньше $\delta L/4$, а $R$~---
их количество.
Без ограничения общности можно считать,
что каждому кодовому слову
сопоставлена
монотонно выбирающая программа
(возможно, нигде не определ\"енная)
и различным кодовым словам сопоставлены
различные программы. Так что
$R=2^{\left\lceil\delta L/4\right\rceil}-1$.
Для
$n=\left\lceil\frac{\ln(4LR)}{\delta}\right\rceil,\ldots,L$
определим ставки $\sigma_n=\sqrt{\frac{\ln(4LR)}{n}}$.
Будем рассматривать множество стратегий, сопоставленных всем
возможным $\sigma_n$, $r\in\rls_L$ и $b\in\{0,1\}$.

Для построения последовательности $\vct t$ нам понадобятся
некоторые вспомогательные величины, зависящие от $\vct t$.
Пусть $S_i$~--- суммарный капитал всех ещ\"е определ\"енных
стратегий на шаге $i$ (он зависит только от $\vct t_{1:i-1}$).
Начальный капитал $S_0$ равен количеству стратегий,
то есть меньше $2LR$.

Идея построения $\vct t$ следующая:
на каждом шаге выбираем $t_i$ так, чтобы суммарный капитал
не возрастал; тогда конечный капитал любой стратегии не превышает
суммарного начального капитала $S_0$, что да\"ет оценку на
отклонение в подпоследовательности.
Однако непосредственно этот подход неосуществим, поскольку
мы не можем алгоритмически проверить, какие правила определены на
данном начале, а какие~--- нет, а значит, не можем вычислить
$S_{i+1}$ при каждом из двух возможных значений $t_i$.
Поэтому на каждом шаге алгоритма необходима некоторая
дополнительная информация.


Пусть $Q_i$~--- суммарный капитал на шаге $i$ тех стратегий,
которые будут также определены и на шаге $i+1$ (то есть
на начале $\vct t_{1:i}$). Очевидно, что $Q_i\le S_i$.

Определим последовательности $P_i$ и $m_i$ следующими
соотношениями:
\begin{gather*}
P_0=S_0\,,\\
m_i=\left\lfloor\frac{P_i-Q_i}{2R}\sqrt{\delta}\right\rfloor\,,\\
P_{i+1}=P_i+2R-\frac{2Rm_i}{\sqrt{\delta}}\,.
\end{gather*}
Из определения ясно, что
$$
P_i-\frac{2Rm_i}{\sqrt{\delta}}-\frac{2R}{\sqrt{\delta}}
      < Q_i \le P_i-\frac{2Rm_i}{\sqrt{\delta}}\,.
$$

Опишем теперь, как по началу $\vct t_{1:i}$ и заданным $P_i$
и $m_i$ строится следующая цифра $t_{i+1}$.
Построение состоит из двух этапов:
\begin{enumerate}
\item \label{alg:enum}
К началу $\vct t_{1:i}$ параллельно применяются все стратегии;
вычисляется текущий капитал тех, которые уже определились,
до тех пор, пока их суммарный капитал не превысит
$(P_i-\frac{2Rm_i}{\sqrt{\delta}}-\frac{2R}{\sqrt{\delta}})$.
\item \label{alg:choose}
Выбирается то значение $t_{i+1}$, при котором суммарный
выигрыш стратегий, определившихся к концу этапа~\ref{alg:enum},
неположителен.
\end{enumerate}

Сначала докажем осуществимость алгоритма.
Если начало $\vct t_{1:i}$ построено, то значения
$S_i$, $Q_i$, $P_i$ и $m_i$ определены. Пусть алгоритм
получил на вход корректные $P_i$ и $m_i$.
В процессе выполнения этапа~\ref{alg:enum} наступит момент,
когда уже определились все стратегии, которые вообще определены
на данном начале. Тогда их суммарный капитал равен
$Q_i > P_i-\frac{2Rm_i}{\sqrt{\delta}}-
        \frac{2R}{\sqrt{\delta}}$,
поэтому в некоторый момент этап~\ref{alg:enum} завершится.
Теперь заметим, что для каждой (определ\"енной)
стратегии сумма выигрышей при
$t_{i+1}=0$ и $t_{i+1}=1$ равна нулю.
Равна нулю и сумма при $t_{i+1}=0$ и $t_{i+1}=1$
суммарных выигрышей любого множества
(определ\"енных) стратегий, поэтому
суммарный выигрыш на этапе~\ref{alg:choose} не может быть
положительным для обоих значений $t_{i+1}$.

Нам понадобятся следующие три свойства введ\"енных величин:
\begin{enumerate}
\item $S_i\le P_i$.

      $S_0=P_0$ по определению.
      Оценим $S_{i+1}$.
      Для тех стратегий, которые определились в
      течение этапа~\ref{alg:enum}, суммарный капитал
      (обозначим его $Q'_i$) не возрос.
      Капитал остальных стратегий равен $Q_i-Q'_i$,
      он увеличился не более чем в
      $(1+\sqrt{\delta})$ раз, поскольку все ставки не
      превышают $\sqrt{\delta}$. Очевидно, что
      $Q_i-Q'_i <
      Q_i-(P_i-\frac{2Rm_i}{\sqrt{\delta}}
           -\frac{2R}{\sqrt{\delta}})\le
      \frac{2R}{\sqrt{\delta}}$.
      Таким образом,
      \begin{multline*}
       S_{i+1}\le Q'_i+(Q_i-Q'_i)(1+\sqrt{\delta})=
       Q_i+(Q_i-Q'_i)\sqrt{\delta} < \\
       (P_i-\frac{2Rm_i}{\sqrt{\delta}})+
         \frac{2R}{\sqrt{\delta}}\sqrt{\delta}=P_{i+1}\,.
      \end{multline*}

\item $m_i\ge 0$.

      Неравенство следует из того, что $Q_i\le S_i\le P_i$.

\item $\sum m_i < 2L\sqrt{\delta}$.

      Просуммируем равенства
      $P_{i+1}=P_i+2R-\frac{2Rm_i}{\sqrt{\delta}}$
      по всем $i$. Получим
      $P_L=P_0+2RL-2R\sum m_i/\sqrt{\delta}$, откуда
      с уч\"етом того, что $P_0 < 2RL$ и
      $P_L > S_L\ge 0$,
      имеем
      $$
       \sum m_i=(2RL+P_0-P_L)\frac{\sqrt{\delta}}{2R}
        < 2L\sqrt{\delta}\,.
      $$
\end{enumerate}


Теперь мы можем оценить
энтропию построенной последовательности $\vct t$.
Алгоритм построения $\vct t$ использовал знание множества
стратегий и последовательностей $P_i$, $m_i$. Множество
стратегий строится по $L$ и $\delta$.
$P_i$ строится по $m_i$, $L$ и $\delta$.
Поэтому
$K(\vct t)\le
K(\langle m_0,\ldots,m_{L-1}\rangle|L,1/\delta)+
2\lb L + 2\lb(1/\delta)
= K(\langle m_0,\ldots,m_{L-1}\rangle|L,1/\delta) + o(L)$.

Энтропию $\langle m_0,\ldots,m_{L-1}\rangle$
при известных $L$, $1/\delta$
оценим через двоичный логарифм количества таких
последовательностей из $L$ натуральных чисел,
что сумма этих чисел
меньше $N=\left\lceil 2L\sqrt{\delta}\right\rceil$.
Легко показать, что последовательность
$\langle m_0,\ldots,m_{L-1}\rangle$
однозначно определяется мультимножеством
(с уч\"етом кратностей)
своих частичных сумм
$\{m_0, m_0+m_1,\ldots, m_0+\ldots+m_{L-1}\}$.
Частичные суммы могут принимать только
значения $\{0,\ldots,N-1\}$.
Таким образом, количество возможных
последовательностей $m_i$ не превосходит количества
неупорядоченных выборок с повторениями из $N$ по $L$,
которое равно
$\binom{N+L}{L} < \frac{(N+L)^N}{N!} <
  \left(\frac{(N+L)\Exp{}}{N}\right)^N$.
В результате,
\begin{multline*}
K(\langle m_0,\ldots,m_{L-1}\rangle|L,1/\delta)\le\\
\lb \binom{N+L}{L} + O(1)\le
N \lb \frac{(N+L)\Exp{}}{N}+ O(1)\le\\
\left\lceil 2L\sqrt{\delta}\right\rceil\cdot
\lb\left(1+\frac{1}{2\sqrt{\delta}}\right)\Exp{} + O(1)
< L/3\,.
\end{multline*}
Из того, что $K(\vct t) < L/2$,
следует, что удельный дефект $\vct t$
больше $\half$.

Осталось оценить монотонный частотный дефект построенной
последовательности $\vct t$.
Для этого зафиксируем правило $r$ и рассмотрим
выборку $r[\vct t]$ длины $n$ с отклонением $\epsilon$.
Оценим сверху $D(n,\epsilon)$.
Рассмотрим два возможных случая.
\begin{enumerate}
\item $n \le 7\delta L/8$.
      Так как $D(n,\epsilon)\le n$, то
      $D(n,\epsilon)/L \le \frac{7}{8}\delta$.
\item $n > 7\delta L/8$.
      Пусть отклонение в $r[\vct t]$ в сторону нулей.
      Возьм\"ем стратегию, соответствующую правилу $r$,
      ставящую долю капитала $\sigma_n$ на $0$.
      Конечный капитал этой стратегии не превышает
      суммарного капитала
      $S_L < P_L\le P_0+2RL < 4RL$
      (мы воспользовались уже упомянутым равенством
       $P_L=P_0+2RL-2R\sum m_i/\sqrt{\delta}$).
      С другой стороны, капитал стратегии равен
      $(1+\sigma_n)^{n\left(\half+\epsilon\right)}
      (1-\sigma_n)^{n\left(\half-\epsilon\right)}$.
      Получаем неравенство
      $$
       \frac{n}{2}\left((1+2\epsilon)\ln(1+\sigma_n)
         +(1-2\epsilon)\ln(1-\sigma_n)\right) < \ln(4RL)\,,
      $$
      откуда
      $$
       2\epsilon\ln\frac{1+\sigma_n}{1-\sigma_n}+
         \ln(1-\sigma_n^2) < \frac{2}{n}\ln(4RL)\,.
      $$
      Используя то, что $\ln\frac{1+x}{1-x}\ge 2x$
      при $0\le x < 1$,
      а также то, что $\ln(1-x)\ge -2x$
      при $0\le x \le \half$,  найд\"ем, что
      $$
       \epsilon <
        \frac{\frac{2}{n}\ln(4LR)+2\sigma_n^2}{4\sigma_n}=
        \frac{\ln(4LR)}{2n\sigma_n}+\frac{\sigma_n}{2}=
        \sqrt{\frac{\ln(4LR)}{n}}\,.
      $$
      Ниже мы используем оценку
      $$
      \binom{n}{j} \ge
      \frac{\Exp{n\cdot h(j/n)}}{\sqrt{8 j(n-j)/n}}\,,
      $$
      вытекающую из формулы Стирлинга,
      и оценку (при $\epsilon\le\frac{1}{\sqrt{5}}$)
      $$
      h\left(\half+\epsilon\right)\ge
        \ln 2 - 2\epsilon^2(1+10\epsilon^2/3)\,,
      $$
      получающуюся двукратным дифференцированием.
      Так как
      \begin{multline*}
      D(n,\epsilon) <
       2n\epsilon^2\lb\Exp{}(1+10\epsilon^2/3)+\ln n<\\
       2\ln(4LR)\lb\Exp{}\left(1+\frac{10\ln(4LR)}{3n}\right)
            +\ln n <\\
       2\lb(4LR)\left(1+\frac{10\ln(4LR)}{3(7\delta L/8)}\right)
            + \ln n \le
       \frac{5}{6}\delta L+O(\ln L)\,,
      \end{multline*}
      то  $D(n,\epsilon)/L<\frac{7}{8}\delta$
       (мы учли, что $\delta$ мало,
       $L\ge (1/\delta)^2$ и
       $\epsilon\le\frac{1}{\sqrt{5}}$).
\end{enumerate}

Наконец, если число $1/\delta$ не было натуральным,
то можно провести вс\"е рассуждение для числа
$\delta_0=\frac{1}{\lfloor 1/\delta\rfloor}\ge\delta$.
При этом $\frac{7}{8}\delta_0 < \delta$.

\end{proof}


\subsection{Об оптимальности оценок}

Все оценки, доказанные в настоящей работе,
представляются близкими к оптимальным,
за исключением одного места,
которое мы сейчас обсудим.
Пусть $\delta$ и $\delta'$ пробегают
действительные числа из $(0,1)$,
$L$ пробегает натуральные числа,
и $S$ пробегает множества двоичных
последовательностей длины $L$.
Обозначим через $\Phi_{L,\delta}(\delta')$
максимум по множествам $S$ дефекта $\ge\delta$
наименьшего количества правильных множеств
дефекта $\ge\delta'$,
объединение которых покрывает $S$.
По существу, в теоремах~\ref{thm:cover},
\ref{thm:no_cover} оценивается
эта функция $\Phi$.
А именно, для некоторых функций $\rho_1$, $\rho_2$
$$
\begin{aligned}
\delta' \le с_1\cdot\frac{\delta}{\ln(1/\delta)}
\quad&\Rightarrow&\mspace{9mu}
&\Phi_{L,\delta}(\delta') < L\cdot\rho_1(1/\delta)\,,\\
\delta' \ge с_2\cdot\frac{\delta}{\ln(1/\delta)}
\quad&\Rightarrow&\mspace{9mu}
&\Phi_{L,\delta}(\delta') > \Exp{L/\rho_2(1/\delta)}\,,
\end{aligned}
$$
где $c_1\approx 1$, $c_2 = 2$ и $L \ge (1/\delta)^5$.
То есть, когда $\delta'$ меняется
от $с_1\cdot\frac{\delta}{\ln(1/\delta)}$
до $с_2\cdot\frac{\delta}{\ln(1/\delta)}$,
функция $\Phi$ делает скачок
от линейного по $L$ выражения
до экспоненциального по $L$ выражения.
Если нас интересует поведение $\Phi$
при фиксированном $\delta$ и $L\to\infty$,
то оценка выглядит оптимальной
(разве что можно сближать константы
$c_1$ и $c_2$).
Теперь рассмотрим поведение $\Phi$
при $\delta\to 0$.
Тогда в полученных оценках $\rho_2$
раст\"ет полиномиально, а $\rho_1$
раст\"ет экспоненциально.

{\bf Открытая проблема:}
нельзя ли усилить верхнюю оценку на $\Phi$,
сделав $\rho_1$ полиномиальным?

Ан.~Мучник доказал (см.~\cite{3avt}),
что если уменьшить верхнюю оценку на $\delta'$,
то в качестве $\rho_1$ годится
линейная функция\footnote{
Алгоритмический аналог этого результата
недавно получили Н.~Верещагин и Б.~Дюран,
см.~\cite{ver}. Некоторые элементы их
рассуждения мы использовали
в доказательстве теоремы~\ref{thm:cover}$'$.}.
Более точно,
$$
\delta' \le с_3\cdot\delta^2
\quad\Rightarrow\quad
\Phi_{L,\delta}(\delta') < L\cdot(c_4/\delta)\,.
$$
Поэтому положительное решение
сформулированной проблемы
кажется достаточно вероятным.

\section*{Благодарности}
Авторы признательны
Николаю Константиновичу Верещагину
за интересные обсуждения
вопросов колмогоровской теории,
которые
послужили для нас одним из стимулов
начать настоящую работу.
Большую помощь оказал
Алексей Вячеславович Чернов
при подготовке текста к публикации,
за что авторы ему очень благодарны.
Основное содержание статьи
было доложено
на Колмогоровском семинаре
Московского государственного университета
весной 2002 года.
Мы признательны его участникам за внимание.

%\newpage

\begin{thebibliography}{9}

\bibitem{kolm} A.~N.~Kolmogorov.
On tables of random numbers.
{\it Sankhy\~a: The Indian Journal of Statistics},
Series~A, v.~25, part~4 (1963).
(Reprinted in {\it Theoretical Computer Science},
v.~207 (1998), pp.~387\nddash395).

\bibitem{3appr} А.~Н.~Колмогоров.
Три подхода к определению
понятия \glqq количество информации\grqq.
{\it Проблемы передачи информации},
т.~1 (1965), N~1, с.~3\nddash11.

\bibitem{trans_kolm} А.~Н.~Колмогоров.
О таблицах случайных чисел.
{\it Семиотика и информатика},
вып.~18 (1982), М.:~ВИНИТИ, с.~3\nddash13.
(Перепечатано в сборнике:
А.~Н.~Колмогоров. Теория информации
и теория алгоритмов.
М.:~Наука, 1987, с.~204\nddash213.)

\bibitem{yaglom} А.~М.~Яглом, И.~М.~Яглом.
Вероятность и информация.
2-е издание. М.:~Физматгиз, 1960.

\bibitem{lambalg} M.~van Lambalgen.
Von Mises' definition of random sequences reconsidered.
{\it Journal of Symbolic Logic},
v.~52 (1987), pp.~725\nddash755.

\bibitem{UspSh} V.~A.~Uspensky, A.~Kh.~Shen.
Relations between varieties
of Kolmogorov complexities.
{\it Math. Systems Theory}, 29(1996),
pp.~271\nddash292.

\bibitem{3avt} An.~A.~Muchnik, A.~L.~Semenov,
V.~A.~Uspensky.
Mathematical me\-ta\-phy\-sics of randomness.
{\it Theoretical Computer Science},
v.~207 (1998), pp.~263\nddash317.

\bibitem{ver} B.~Durand, N.~Vereshchagin.
Kolmogorov--Loveland stochasticity
for finite strings.
\verb"http://markov.math.msu.ru/~ver/papers/kolm-love.ps"
2002.

\end{thebibliography}

\end{document}



