%%
%% codepage cp866
%% ДАН, Математика
%% А.Семенов, Ан.Мучник.
%%
%%
%% Russified LaTeX2e, based on LaTeX2e 2001/06/01
%% Document Class: article 2001/04/21 v1.4e Standard LaTeX document class
%% Package: amsmath 2000/07/18 v2.13 AMS math features
%% Package: amssymb 1995/02/01 v2.2a
%% Package: amsthm 2000/10/26 v2.08
%% Package: russcorr 1996/03/24
%%
\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{lem}{Лемма}
\theoremstyle{definition} \newtheorem{defn}{Определение}
\theoremstyle{remark} \newtheorem*{note}{Замечание}

\newcommand*{\vct}[1]{\mathbf{#1}}
\newcommand*{\Exp}[1]{\mathrm e^{#1}}

\newcommand{\rls}{\mathcal R}

\newcommand{\half}{\frac{1}{2}}
\newcommand{\lb}{\mathop{\rm lb}}

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

\hfuzz=0.5pt
\tolerance=350

\begin{document}

\centerline{УДК 519.211+510.52\hfill\underline{\sc математика}}

\begin{center}
\makeatletter
\renewcommand{\@makefnmark}{}
\makeatother
\bf\large
Об уточнении оценок Колмогорова,
относящихся к датчикам случайных чисел и
сложностному определению случайности\footnotemark[0]{}
\footnotetext[0]{
Работа выполнена при поддержке
Российского фонда фундаментальных исследований,
гранты N~01-01-00505, N~02-01-10904.}\\[5pt]
\end{center}

\centerline{\large Алексей Семенов\hfil Андрей Мучник}
\bigskip
\bigskip
\bigskip


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

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

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

\begin{defn}\label{def:right_set}
Пусть $\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}

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

Для уточнения слов о
не слишком сложных правилах выбора
\emph{cложностью} конечного множества
назов\"ем двоичный логарифм его мощности.
Введ\"ем обозначение: $
d(n,\epsilon)\rightleftharpoons 2n\epsilon^2\lb\mathrm e$.


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

 В статье~\cite{kolm} Колмогоров только наметил доказательство этой
теоремы. Полное его изложение (связанное с некоторыми тонкостями)
будет приведено в работе, которую авторы готовят к публикации
в журнале \лк Проблемы передачи информации\пк.


Следующая теорема да\"ет алгоритмический аналог
для теоремы~\ref{thm:kolm} (понятие условной энтропии
было введено Колмогоровым в~\cite{3appr}).

\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{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}

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

\begin{thm}\label{thm:MS}
  Рассмотрим произвольные числа
$L$ (длина последовательности),
$\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}
  Существование такого множества правил доказывается, как и в
теореме~\ref{thm:kolm}, вероятностно.
Однако теперь мы рассматриваем
распределение вероятностей на правилах и показываем,
что событие
\glqq для множества правил $\rls_L$ существует
$(n,\epsilon)$-датчик\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$.
Очевидно, эта вероятность равна
$$
\frac{\dbinom{L/2}{(\half-\epsilon)n}\dbinom{L/2}{(\half+\epsilon)n}}
     {\dbinom L n}\,.
$$

Используя верхнюю и нижнюю оценки на
биномиальные коэффициенты, вытекающие из формулы Стирлинга,
и оценку на функцию шенноновской энтропии,
получим, что искомая вероятность больше
$\Exp{-K}$, где
$$
K=\frac{2n\epsilon^2}{1-n/L}(1+4\epsilon^2/3)+\half(1+\ln n)\,.
$$
Вероятность того,
что из фиксированной последовательности
одно правило не выберет подпоследовательность
с отклонением не менее $\epsilon$,
оказывается меньше $1-\Exp{-K}$.
Теперь укажем независимо $N$ случайных
правил (некоторые из этих правил могут совпасть
друг с другом).
Вероятность того, что
фиксированная последовательность
$\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\,.
$$
Оста\"ется убедиться, что последняя величина
меньше $d(n,\epsilon)\frac{1+\epsilon}{1-n/L}$
при $\epsilon<1/3$ и $n\ge 2\epsilon^{-3}\lb L$.


Следующая теорема да\"ет алгоритмический аналог
для теоремы~\ref{thm:MS}.

\renewcommand{\thmprimname}{Теорема~\ref{thm:MS}$'$}
\begin{thm_prim}
  Рассмотрим произвольные числа $L$ (длина последовательности),
рациональное $\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-1)}+C\,,
$$
не существует $(n,\epsilon)$-датчика случайных чисел.
(Здесь $C$~--- константа, зависящая только от выбора
оптимального языка программирования.)
\end{thm_prim}

{
По предыдущей теореме для некоторого множества
неадаптивных правил, имеющего сложность меньше
$d(n,\epsilon)\frac{1+\epsilon}{1-n/(L-1)}$,
не существует
$(n,\epsilon)$\nobreakdash-датчика длины $L$.
Покажем, что, зная $L$, $n$, $\epsilon$,
множество правил с таким свойством
можно построить алгоритмически.
\sloppy

}

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

Условная (относительно $L$, $n$, $\epsilon$)
энтропия каждого правила
из найденного множества не превосходит
его сложности
плюс длина программы, действие которой
описано в предыдущем абзаце.
При добавлении правил (всех остальных с энтропией меньше
$d(n,\epsilon)\frac{1+\epsilon}{1-n/(L-1)}+C$)
отсутствие $(n,\epsilon)$-датчика сохранится.


Авторы признательны
Николаю Константиновичу Верещагину
за интересные обсуждения
вопросов колмогоровской теории.
Большую помощь оказал
Алексей Вячеславович Чернов
при подготовке текста к публикации,
за что авторы ему очень благодарны.
Основное содержание статьи
было доложено
на Колмогоровском семинаре
Московского государственного университета
весной 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,
1963, v.~25, part~4, pp.~369--376. (Reprinted in {\it
Theoretical Computer Science}, 1998, v.~207, pp.~387--395.)\\
Перевод с добавлением автора:
 А.~Н.~Колмогоров. О таблицах случайных чисел.
{\it Семиотика и информатика}, 1982, вып.~18, с.~3--13.
(Перепечатано в сборнике: А.~Н.~Колмогоров. Теория информации
и теория алгоритмов. М.:~\лк Наука\пк, 1987, с.~204--213.)

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

\end{thebibliography}

\end{document}



