\documentclass[12pt,draft]{article}
\usepackage{amsmath,amssymb,amsthm}

\newtheorem{thm}{Theorem}
\newcommand{\thmprimname}{Theorem}
\newtheorem*{thm_prim}{\thmprimname}
\newtheorem{lem}{Lemma}
\theoremstyle{definition} \newtheorem{defn}{Definition}
\theoremstyle{remark} \newtheorem*{note}{Remark}

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

\newcommand{\rls}{\mathcal R}

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

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

\hfuzz=0.5pt
\tolerance=300

\begin{document}

\begin{center}
\makeatletter
\renewcommand{\@makefnmark}{}
\makeatother
\bf\large
On sharpening Kolmogorov bounds
that relative to random number generators and
complexity definition of randomness\footnotemark[0]{}
\footnotetext[0]{
Supported in part by the Russian Foundation
for Basic Research, project nos. 01-01-00505,
02-01-10904, 02-01-22001
and the Council on Grants for Scientific Schools.}\\[5pt]
\end{center}

\centerline{\large Alexey Semenov\hfil Andrej Muchnik}
\bigskip
\bigskip
\bigskip


In 1930-s Andrei Kolmogorov founded
probability theory with help of
measure theory.
However, this did not solve a couple of questions
connected with foundations of probability theory.
In~\cite{kolm}, he began to develop
a new approach to the problem,
theory of descriptive complexity.
In that paper, Kolmogorov obtained
upper and lower bounds for the maximal number
of admissible place-selection rules, for which
the existence of random generator
is guaranteed, and set the problem
of obtaining a bound sharp by order.
In the present paper,
Kolmogorov's problem is solved;
his lower bound is shown to be sharp (by order).

In~\cite{kolm}, Kolmogorov
defined the notion of a place-selection rule
on a finite binary sequence~$\vct t$.
An informal description is as follows
(the reader can find the exact definition in~\cite{kolm}).
Assume that we have a sequence of cards
of the same length as a given sequence $\vct t$.
The digits of the sequence $\vct t$ are written
on the face of cards, the back is the same for all cards.
In the beginning, cards lie face down
in the order of digits in $\vct t$.
A rule decides what card should be turned over
and (before turning over) whether it should be included
in the subsequence under construction.
To make the next decision,
the rule takes into account digits on the cards that
have already been turned over.
The subsequence selected by a rule $r$
from a sequence $\vct t$ is denoted by $r[\vct t]$.

Sometimes, it is useful to consider more restricted
classes of rules.
\emph{Monotonic rules}
(first considered by Church in 1940)
turn over the cards sequentially in the original order.
\emph{Nonadaptive rules} point out
a certain set of cards at once,
and the subsequence consists of digits
written on these cards and arranged in the
original order.


\begin{defn}\label{def:right_set}
Assume that $\mathcal{R}_L$ is a set of rules
on sequences of length $L$.
A sequence $\vct t$ of length $L$ is called
an \emph{$(n,\epsilon)$-random generator
 with respect to $\mathcal{R}_L$} if,
for each rule $r\in\mathcal{R}_L$,
the selected subsequence $r[\vct t]$ has
the following property:
\begin{itemize}
\item[]
If the length of $r[\vct t]$
is greater than or equal to $n$,\\
then the difference between the fraction of zeros
and $1/2$ is less than $\epsilon$.
\end{itemize}

The absolute value of the difference between
$\frac{1}{2}$ and the fraction of zeros in the sequence
is called the \emph{deviation} (of the fraction of zeros).
\end{defn}

\begin{note}
The results below can be generalized
to the case when $0$ and $1$ appear
with frequencies close to $p$ and $1-p$
in all long subsequencies seleceted by simple rules.
\end{note}

To refine words about not too complex
place-selection rules,
we say that the \emph{complexity} of a finite set
is the binary logarithm of its cardinality.
Let us introduce the notation:
$d(n,\epsilon)\rightleftharpoons 2n\epsilon^2\lb\mathrm e$.


\begin{thm}[Kolmogorov, 1963]\label{thm:kolm}
Consider arbitrary numbers $L$ (the length of a sequence),
${\epsilon>0}$ (the deviation), and
$n\ge\epsilon^{-4}$ (the length of selected subsequences).
For any set of rules $\mathcal{R}_L$,
if its complexity is less than
$$
d(n,\epsilon)(1-\epsilon)\,,
$$
then there exists an $(n,\epsilon)$-random
generator with respect to $\mathcal{R}_L$ .
\end{thm}

Kolmogorov just outlined a proof of this theorem
in~\cite{kolm}.
A complete proof (connected with some niceties)
will be presented in the paper
which the authors are preparing to publication
in ``Problems of Information Transmission.''

The following theorem gives us
an algorithmical counterpart
for Theorem~\ref{thm:kolm}
(the notion of conditional entropy
was introduced by Kolmogorov in~\cite{3appr}).

\renewcommand{\thmprimname}{Theorem~\ref{thm:kolm}$'$}
\begin{thm_prim}
Consider arbitrary numbers $L$ (the length of a sequence),
$\epsilon>0$ (the deviation), and
$n\ge\epsilon^{-4}$ (the length of selected subsequences).
Then there exists an $(n,\epsilon)$-random generator
with respect to
the set of rules $\mathcal{R}_L$
consisting of all rules such that their
entropy conditional to $L$
is less than
$$
d(n,\epsilon)(1-\epsilon)\,.
$$
\end{thm_prim}

\begin{thm}[Kolmogorov, 1963]\label{thm:rev_kolm}
Consider arbitrary numbers $L$ (the length of a sequence),
${\epsilon\in(0,1/20)}$ (the deviation), and
$n\in[\epsilon^{-3},L/2]$ (the length of selected subsequences).
There exists a set $\mathcal{R}_L$ of nonadaptive rules
such that its complexity is less than
$$
4n\epsilon(1+5\epsilon)\,
$$
and there is no
$(n,\epsilon)$-random generator
with respect to $\mathcal{R}_L$.
\end{thm}
Theorem~\ref{thm:kolm} gives us a lower bound and
Theorem~\ref{thm:rev_kolm} gives us an upper bound for
the maximal number $\tau$ such that,
for each $L$ and each set of rules with the complexity
less than $\tau$,
there is at least one $(n,\epsilon)$-random generator
of length $L$.
Since
$d(n,\epsilon)=2n\epsilon^2\lb\mathrm e$ is far less than
$4n\epsilon$ for small $\epsilon$,
Kolmogorov tried to remove the discrepancy
between the power of $\epsilon$ in the bounds.
The lower bound obtained by Kolmogorov
turns out to be sharp by order
(even for nonadaptive rules).

\begin{thm}\label{thm:MS}
Consider arbitrary numbers $L\ge 2$
(the length of a sequence),
$\epsilon\in(0,1/3)$ (the deviation), and
$n\in[2\epsilon^{-3}\lb L,L/2]$
(the length of selected subsequences).
There exists a set $\mathcal{R}_L$ of nonadaptive rules
such that its complexity is less than
$$
d(n,\epsilon)\frac{1+\epsilon}{1-n/(L-1)}\,
$$
and there is no
$(n,\epsilon)$-random generator
with respect to $\mathcal{R}_L$.
\end{thm}
We prove the existence of such a set of rules
using a probabilistic method,
as in Theorem~\ref{thm:kolm}.
But now we consider a probability distribution
on rules and show that
the probability of the event
``there is an $(n,\epsilon)$-random
generator with respect to a set of rules $\mathcal{R}_L$''
is less than $1$.

We will look for a required set of rules
among nonadaptive rules that select
subsequences of length exactly $n$;
i.\,e., a rule is determined by
an $n$-element subset of the set $1,\ldots,L$.
The number of such rules is $\binom{L}{n}$;
we consider the uniform distribution on them.

Take a sequence $\vct t$ of length $L$.
Let us bound from below the probability that
$\vct t$ is not an
${(n,\epsilon)}$-random generator
with respect to a randomly chosen rule $r$, i.\,e.,
the deviation in $r[\vct t]$ is not less than $\epsilon$.
We assume that the number of zeros in $\vct t$
is not less than the number of ones
(the opposite case is considered symmetrically).

Consider the case when
$L/2$ and $n(\half+\epsilon)$ are integers;
the general case is easily reduced
to this specific one.
We want to estimate the probability
of the deviation such that the fraction of zeros
in a selection exceeds $\frac{1}{2}$
by at least $\epsilon$;
obviously, this probability is minimal
if $\vct t$ contains the same number
of zeros and ones.
It is sufficient to estimate
the probability of the deviation
that exactly equals $\epsilon$.
Evidently, this probability is equal to
$$
\frac{\dbinom{L/2}{(\frac{1}{2}-\epsilon)n}
      \dbinom{L/2}{(\frac{1}{2}+\epsilon)n}}
     {\dbinom L n}\,,
$$

Using upper and lower bounds on
binomial coefficients arising from Striling formula
and a bound on Shannon entropy function,
we get that the required probability
is greater than $\Exp{-K}$, where
$$
K=\frac{2n\epsilon^2}{1-n/L}(1+4\epsilon^2/3)+\half(1+\ln n)\,.
$$
The probability that
one rule does not select a subsequence
with the deviation not less than $\epsilon$
from a given sequence
turns out to be less than $1-\Exp{-K}$.
Now let us independently take
$N$ random rules (some of them may coincide).
The probability that
a fixed sequence $\vct t$ is
an $(n,\epsilon)$-random generator
with respect to this set of rules
is less than
$$
(1-\Exp{-K})^N < \Exp{-N\Exp{-K}}
$$
(here we use the inequality
$(1-\frac{1}{x})^{x} < \Exp{-1}$,
which is true for all $x>1$).
Multiplying the value in the right-hand side
of the last inequality
by the number of sequences of length $L$,
we get a strict upper bound for the probability
that there exists at least one
$(n,\epsilon)$-random generator
with respect to this set of rules,
namely,
$$
2^L\Exp{-N\Exp{-K}}=\Exp{L\ln 2 -N\Exp{-K}}\,.
$$
The last expression is not greater than $1$
if $N = \left\lceil\Exp{K}L\ln 2\right\rceil
 < \Exp{K}L$.
And the complexity of the set of rules
is not greater than
$$
\frac{2n\epsilon^2}{1-n/L}
   (1+4\epsilon^2/3)\lb\Exp{}+2\lb L\,.
$$
It remains to check that the last value
is less than
$d(n,\epsilon)\frac{1+\epsilon}{1-n/L}$
if $\epsilon<1/3$ and $n\ge 2\epsilon^{-3}\lb L$.


The following theorem gives us
an algorithmical counterpart
for Theorem~\ref{thm:MS}.

\renewcommand{\thmprimname}{Theorem~\ref{thm:MS}$'$}
\begin{thm_prim}
Consider a natural $L$ (the length of a sequence),
a rational $\epsilon\in(0,1/3)$ (the deviation),
and a natural $n\in[2\epsilon^{-3}\lb L,L/2]$
(the length of selected subsequences).
There is no
$(n,\epsilon)$-random generator with respect to
the set $\mathcal{R}_L$ consisting of
all nonadaptive rules such that their
entropy conditional to $L$, $n$, and $\epsilon$
is less than
$$
d(n,\epsilon)\frac{1+\epsilon}{1-n/(L-1)}+C\,.
$$
(Here $C$ is a constant depending on
the choice of optimal programming language only.)
\end{thm_prim}

By Theorem~\ref{thm:MS},
there is no $(n,\epsilon)$-random
generator of length $L$ with respect to
a set of nonadaptive rules
of complexity less than
$d(n,\epsilon)\frac{1+\epsilon}{1-n/(L-1)}$.
Let us show that, given $L$, $n$, and $\epsilon$,
a set of rules with this property
can be constructed algorithmically.

Indeed, given a set $\mathcal{R}_L$ of nonadaptive rules
and a sequence $\vct t$ of length $L$,
we can effectively determine
whether $\vct t$ is an $(n,\epsilon)$-random
generator with respect to $\mathcal{R}_L$
(it is sufficient to apply
each rule from $\mathcal{R}_L$ to $\vct t$
and to calculate the deviation).
Examining each sequence of length $L$,
we can check whether
there exists an $(n,\epsilon)$-random
generator with respect to $\mathcal{R}_L$.
Examining all sets of nonadaptive rules
with a given cardinality,
we find the required set (if
there are several sets with this property,
we take the first set in our enumeration).


The conditional (to $L$, $n$, and $\epsilon$)
entropy of each rule from the set found
does not exceed the complexity of the set
plus the length of the program described
in the previous paragraph.
When we add rules (all remaining
with entropy less than
$d(n,\epsilon)\frac{1+\epsilon}{1-n/(L-1)}+C$),
the property of nonexistence
of an $(n,\epsilon)$-random generator is kept.


The authors are grateful to
Nikolai Vereshchagin
for interesting discussions about
the problems of Kolmogorov theory.
The authors are also grateful to
Alexey Chernov for a great help
in preparing the text for publication.
The main contents of the paper
was reported at Kolmogorov seminar
of Moscow State University
in the spring of 2002,
and we thank its participants for attention.

\newpage

\begin{thebibliography}{9}

\bibitem{kolm} A.~N.~Kolmogorov. On tables of random numbers.
\emph{Sankhy\~a: The Indian Journal of Statistics}, Series~A,
1963, v.~25, part~4, pp.~369--376.
(Reprinted in \emph{Theoretical Computer Science},
1998, v.~207, pp.~387--395.)\\
Russian translation with author's addition:
A.~N.~Kolmogorov. On tables of random numbers.
\emph{Semiotika i informatika}, 1982, v.~18, p.~3--13.
(Rerprinted in A.~N.~Kolmogorov. Information theory
and theory of algorithms. M.:~Nauka, 1987, p.~204--213.)

\bibitem{3appr} A.~N.~Kolmogorov.
Three Approaches to the Quantitative
Definition of Information.
\emph{Problemy peredachi informatsii},
1965, vol.~1, no~1, pp.~3--11
[\emph{Problems of Information Transmission}
(English Translation), 1965, vol.~1, no.~1,
pp.~1--7].

\end{thebibliography}
\end{document}



