\documentclass[14pt,draft]{extarticle}

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


\pagestyle{empty}

\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=1pt
\tolerance=300
\renewcommand{\baselinestretch}{1.2}

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

\begin{center}
\bf\large
Об уточнении оценок Колмогорова,
относящихся к датчикам случайных чисел и
сложностному определению случайности
\end{center}

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

\section*{Примечание при корректуре}

В статье~[1] Колмогоров определил
понятие таблицы $(n,\epsilon,p)$-слу\-чай\-ных чисел
для $\rls_L$,
которое отличается от $(n,\epsilon)$-датчика
случайных чисел из нашего определения~1
тем, что в \glqq длинных\grqq{} выборках,
полученных правилами из $\rls_L$,
доля вхождений единицы
близка не к $1/2$, а к $p$.
Через $l(n,\epsilon)$ Колмогоров обозначил
максимальное число $l$, для которого всякому $p$,
всякому $L$ и всякому множеству правил,
имеющему сложность меньше $l$,
соответствует хотя бы одна таблица
$(n,\epsilon,p)$-случайных чисел длины $L$.
Из~[1] вытекает, что
при достаточно малых $\epsilon$
(например, $\epsilon < 1/20$)
и $n\ge \epsilon^{-4}$
$$
(2\lb\mathrm e)n\epsilon^2(1-\epsilon) < l(n,\epsilon) <
4n\epsilon(1+5\epsilon)\,.
$$
Колмогоров поставил проблему устранения расхождения
в степенях $\epsilon$ в
нижней и верхней оценках на
$l(n,\epsilon)$.
Из нашей теоремы~3 следует неравенство
$$
l(n,\epsilon) <
  (2\lb\mathrm e) n\epsilon^2 (1+2\epsilon)\,,
$$
выполненное при достаточно малых $\epsilon$
и $n\ge \epsilon^{-4}$.
(Для доказательства в теореме~3 мы полагаем
$L=\left\lfloor 2^{n\epsilon^3/2}\right\rfloor$.)
Таким образом, верхняя оценка на $l(n,\epsilon)$,
как и нижняя, имеет вид
$(2\lb\mathrm e) n(\epsilon^2 + o(\epsilon^2))$.
\end{document}




