\newcommand{\thmprimword}{Theorem}
\newtheorem*{thmprim}{}{\bfseries}{\itshape}
\newtheorem{assertion}{Assertion}{\bfseries}{\itshape}

\newcommand*{\vct}[1]{\mathbfit{#1}}
\newcommand*{\pair}[1]{\langle #1\rangle}
\newcommand*{\Exp}[1]{\mathrm e^{#1}}
\newcommand{\lb}{\mathop{\rm lb}} %\DeclareMathOperator{\lb}{lb}


\OrigPages{134--165}

\OrigCopyrightedAuthors{Muchnik, Semenov}

\title{On the Role of the Law of Large Numbers\\
in Theory of Randomness\thanks{
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.}
}

\titlerunning{On the Role of the Law of Large Numbers
in Theory of Randomness}
\authorrunning{Muchnik, Semenov}

\received{Received December 22, 2002}

\author{ Andrej Muchnik\and
         Alexei Semenov
       }

\institute{Institute of New Technologies,\\
      10, Nizhnyaya Radishevskaya, Moscow, 109004, Russia}

\maketitle
\setcounter{footnote}{1}

\begin{abstract}
In the first part of this article
we answer Kolmogorov's question
(stated in 1963 in~\cite{kolm})
about exact conditions
for the existence of random generators.
Kolmogorov theory of complexity
permit of a precise definition of
the notion of randomness for
an individual sequence.
For infinite sequences,
the property of randomness is a binary property,
a sequence can be random or not.
For finite sequences, we can solely speak about
a continuous property, a measure of randomness.
Is it possible to measure randomness of
a sequence $\vct t$ by the extent
to which the law of large numbers
is satisfied in all subsequences of $\vct t$
obtained in an ``admissible way''?
As a measure of randomness
(or, more exactly, of nonrandomness)
of a finite sequence, we consider
the specific deficiency of randomness $\delta$
(Definition~\ref{def:alg_defect}).
In the second part of this paper,
we prove that the function
$\delta/\ln(1/\delta)$
characterizes the connections between randomness
of a finite sequence and the extent to which
the law of large numbers is satisfied.
\end{abstract}

%\begin{keywords}
%descriptive complexity,
%Kolmogorov entropy,
%random generator,
%admissible place-selection rule,
%stability of frequencies,
%deficiency of randomness.
%\end{keywords}


\section*{Introduction}

In 1930-s Andrei Kolmogorov founded
probability theory on the base of
measure theory.
In~\cite{kolm} he writes:
``The set-theoretic axioms of
the calculus of probability \ldots
had solved the majority of formal difficulties
in the construction of a mathematical apparatus
which is useful for a very large number of
applications of probabilistic methods,
so successfully that the problem of finding
the basis of real applications of the results
of the mathematical theory of probability
became rather secondary to many investigators.''
However Kolmogorov himself regarded
the question about the basis as a principal one.
In 1962, during his visit to India,
he began to develop a new
approach to it\footnote{
The first publication appeared
in 1963, see~\cite{kolm}.
},
the so-called theory of descriptive complexity.
Now the research area initiated by Kolmogorov
has grown into a rich theory,
which has important connections
not only with probability theory but also
with theory of algorithms, theory of coding,
theory of matroids, and other fields
of mathematics.

As for practical applications,
the main results are to appear in future.
To get them, it is required
to take into account not only
the descriptive complexity of a program
but also an amount of resources used by it.
In many cases this task is connected with
unsolved problems of computational complexity theory.

Consider a sequence of independent trials
with two equiprobable outcomes, $0$ and $1$.
The simplest and at the same time
the most significant condition of
randomness for a sequence of outcomes
is an approximate equality of the number
of zeros and the number of ones.
Obviously, this requirement alone is not
sufficient
(for instance, the sequence $0101010101\ldots$
does not seem to be random).
But if \emph{this condition holds
for all subsequences obtained from
the original one with help of ``admissible''
place-selection rules},
then such a sequence can be considered as
a random generator.
Surely, the notion of an admissible rule
should be made mathematically precise\footnote{
An example of an admissible rule is
``to select all digits at even places.''
An example of a nonadmissible rule is
``to select the digits at places such
that the original sequence contains zeros at them.''}.

Is the mentioned frequency criterion
universal?
A number of known facts about
infinite sequences would rather
be an evidence of the opposite.
For example (see~\cite{lambalg}),
\begin{itemize}\label{utv:1}
\item[(i)]
there exists a set $S$
of measure $0$ that
consists of infinite binary sequences,
and for any countable family $R$
of admissible place-selection rules
there exists $s\in S$ such that
the law of large numbers is
satisfied in all infinite subsequences
selected from $s$ by rules belonging to $R$.
\end{itemize}
The construction of the set $S$
and its property to be of measure $0$
are effective,
hence all its elements are intuitively
nonrandom.

Kolmogorov stressed importance of the
analysis not only of limit regularities
of infinite sequences
but of finite sequences too.
All results of our paper lie
in the finite field.
An analog of~(i) for finite sequences
would be the following:
\begin{itemize}
\item[(ii)]\label{utv:2}
Assume that $L$ is a natural number.
There exists a set $S$
of finite sequences of length $L$
such that the cardinality of $S$
is small enough compared with $2^L$
and, for any not too large family $R$
of admissible place-selection rules,
there exists $s\in S$ such that
the law of large numbers is
satisfied precisely enough
in all not too short subsequences
selected from $s$ by rules
belonging to $R$.
\end{itemize}
Surely, the last statement
should be made more precise.
What is ``small enough,''
``not too large,''
``precisely enough,''
``not too short''?
Remarkably,
there is a natural precise meaning
of these expressions
such that the negation of~(ii) is true.
Thus, it is possible
to establish a positive connection
between the notions of \emph{frequency} and
\emph{universal} randomness
(Theorem~\ref{thm:cover}).


\section{Analysis of Kolmogorov's article
``On tables of random numbers''}

\subsection{Philosophical Motivation}

As Kolmogorov wrote in~\cite{kolm},
for a long time he thought that:
\begin{enumerate}
\item
``The frequency concept
based on the notion of limiting frequency
as the number of trials increases to infinity,
does not contribute anything to substantiate
the applicability of the results of probability theory
to real practical problems
where we have always to deal with
a finite number of trials'';
\item
``The frequency concept applied to a large
but finite number of trials
does not admit a rigorous formal exposition
within the framework of pure mathematics.''
\end{enumerate}
Kolmogorov's opinion on the first statement
had not changed\footnote{Though,
in other papers Kolmogorov, emphasized that
researches on infinite sequences
are of great heuristic significance.}
(as he said in~\cite{kolm}).
As for the second statement,
Kolmogorov came to the conclusion that,
using the frequency conception of randomness
and the refined notion of the complexity of a program,
it is possible to formulate purely mathematical
conditions under that probability theory
can be applied to practice.
He wrote that
an exact definition of the complexity
of a program would be given in another paper,
but in~\cite{kolm} the fact
that the number of simple objects
cannot be very large was only used.
Later, Kolmogorov referred to this approach
as the combinatorial one (see~\cite{3appr}).
Definitions that correspond
to another approach, the algorithmical one,
were given by Kolmogorov in 1965 (see~\cite{3appr}).
The results of~\cite{kolm} have natural
algorithmical analogs,
and we formulate and prove them.
This parallel between the two approaches
can be extended widely.
Therefore in our paper most of the theorems
are formulated in two variants,
combinatorial and algorithmical,
and are numbered in parallel
(numbers of algorithmical theorems have the prime).

Kolmogorov considered a finite binary sequence
to be a table of random numbers (a random generator)
if the frequencies of zeros and ones
are close to $\frac{1}{2}$
in all long enough subsequences obtained
by not too complex place-selection rules.

The mathematical purpose of the paper~\cite{kolm}
was to estimate
how large the complexity of
place-selection rules can be to still ensure that
at least one random generator exists.

\subsection{Definitions}

In~\cite{kolm}, Kolmogorov defined the notion of
a (nonmonotonic) place-selection rule
on a finite binary sequence $\vct t$.

An informal description is as follows.
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 selected digits are arranged in subsequence
according to the order of the selecting,
not the order of the original sequence.
Here is the formal definition.


\begin{definition}\label{def:rule}
\emph{A (place-selection) rule on sequences of length $L$}
is a function $r$ that maps binary sequences
of lengths from $0$ to $L-1$
to pairs from the set
$\{1,\ldots,L\}\times\{\text{``select''},\text{``do not select''}\}$,
where the first components of values of the function
are always different on any sequence and
on any of its proper extensions.
Assume that $\vct t$ is a sequence of length $L$.
For each $i$ from $0$ to $L$,
by induction on $i$ we construct
a binary sequence $\vct s_i$ of length $i$.
Put $\vct s_0=\Lambda$.
To obtain $\vct s_{i+1}$, we write
the $\pi_1(r(\vct s_i))$th digit of the sequence $\vct t$
at the end of $\vct s_i$.
\emph{The sequence selected from $\vct t$ by the rule $r$}
is obtained from $\vct s_L$ by eventual deleting
all digits with numbers $i$ such that
$\pi_2(r(\vct s_{i-1}))=\text{``do not select''}$.
(Here $\pi_1$ and $\pi_2$ denote the first and the second
elements of a pair.)

The selected sequence is denoted by $r[\vct t]$.
\end{definition}

Sometimes, it is useful to consider more restricted
classes of rules.
\emph{Monotonic rules} turn over the cards
sequentially in the original order.\footnote{
Monotonic rules were first
considered by Church in 1940.}
\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{definition}\label{def:gen}
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 every 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 $\frac{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{definition}

Let us remark that for each $p\in[0,1]$
we can consider $(n,\epsilon,p)$-random generator,
where the fraction of zeros
in the selected subsequences
are close not to $\frac{1}{2}$,
but to $p$.

How can we translate words about
not too complex place-selection rules
into a formal language?

Under the combinatorial approach,
the \emph{complexity} of a finite set
is the binary logarithm of its cardinality.

Under the algorithmical approach we use
the \emph{plain entropy} of a constructive object.
The notion of entropy\footnote{
A comparison of different versions of the notion
of entropy can be found in~\cite{UspSh}.}
was defined by Kolmogorov in 1965.
Actually, a class of functions was defined such that
any two of them differ by a constant.
Kolmogorov hoped that it would be achievable
to suggest a certain ``natural'' programming language
such that the corresponding entropy function
is less than the entropy function of any other
``natural'' programming language plus $100$.
Since our results are equally applicable
to any entropy function,
formulations of these results may contain
a constant $C$ depending on the choice
of a programming language only.
We also use the notion of
\emph{conditional} entropy,
which also was introduced by Kolmogorov.

The analogy between the combinatorial and
algorithmical approaches is based on
the following two propositions proved by Kolmogorov.

\begin{proposition}\label{prop:num}
The set of objects
such that their entropy
conditional to a fixed object is less than $m$
cannot contain more than ${2^m-1}$ elements.
\end{proposition}

\begin{proposition}\label{prop:ent}
Assume that a set is enumerated by a program
of entropy less than $\alpha$ and
the cardinality of this set is less than $2^m$.
Then the entropy of its elements
is less than
$m+\alpha+2\lb\alpha+C$.
(Here and in the sequel, we denote by $\lb(x)$
the binary logarithm of $x$.)
\end{proposition}

Consider
the set of all sequences such that
the subsequence selected by a fixed rule
has length and deviation greater then given values.
The law of large numbers implies that,
if these values are large enough
(in other words, if we speak about
long subsequences of large deviation),
then the cardinality of this set is small.
However, even if we do not require that
the deviation is small,
the cardinality can be small anyway.
As an example, consider the following
monotonic rule:
if the digits already selected
form the beginning of the sequence $0101010101\ldots$,
then the next digit have to be selected.
If the length of selection is equal to
the length of the original sequence
(for an arbitrary deviation),
the corresponding set
contains only two elements.

To overcome this difficulty,
we introduce the notion of a normal rule,
and we will consider sets
generated by normal rules only.

\begin{definition}\label{def:right_set}
A rule $r$ on sequences of length $L$
is called \emph{normal} if
$r$ selects subsequences
of the same positive length
from all sequences of length $L$.

For a normal rule $r$ that
selects subsequences of length $n$
and for a number $\epsilon\in[0,\frac{1}{2}]$,
we denote by $A_{r,\epsilon}$ the set of all
sequences such that $r$
selects a subsequence of them with deviation
not less than $\epsilon$.
Such sets are called \emph{regular}.
\end{definition}

Let us introduce the notation,
which we will often use:
$$
d(n,\epsilon)\rightleftharpoons 2n\epsilon^2\lb\mathrm e\,.
$$
The following facts (later they will be discussed in details)
give reasons for this notation.
If a normal rule $r$ selects subsequences
of length $n$, then the cardinality
of the regular set $A_{r,\epsilon}$
depends on $L$, $n$, and $\epsilon$ only.
If $\epsilon$ is small enough and
$n$ is large enough compared with $1/\epsilon$,
then
$|A_{r,\epsilon}|\approx 2^{L-d(n,\epsilon)}$.

There exists an effective operation
(we will call it \emph{$n$-normalization})
that transforms each rule into
a normal one,
the length of selection become equal to $n$,
and selections
that had the length exactly $n$
do not change.

Let us describe the procedure of
$n$-normalization of a rule.
The new rule operates as the old one,
but with two exceptions.
If the old rule has already selected $n$ digits,
then the new rule stops selecting at this moment.
If the old rule has already selected $k<n$ digits
and only $n-k$ digits are not selected,
then the new rule selects all of them.


\subsection{Sufficient Conditions and
Necessary Conditions for Existence of a Random Generator}

\begin{theorem}[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{theorem}
\begin{proof}
In~\cite{kolm}, Kolmogorov just outlined
the proof of this theorem;
for this reason, we give a complete proof here.

Obviously, we can assume without loss
of generality that $\epsilon\le\frac{1}{2}$.
Consider the uniform distribution on
sequences of length $L$
(all digits are independent and
are equal to $0$ and $1$ with probability $\frac{1}{2}$).
The probability of each sequence
is equal to $2^{-L}$.

Take a place-selection rule $r$,
by $r_k$ denote the result of
$k$-normalization of $r$.
Since digits keep to be independent
when their order changes,
for $r_k$ the probability of
selecting a given subsequence of length $k$
is equal to $2^{-k}$.

Let us estimate the probability that
a sequence $\vct t$ is not
an $(n,\epsilon)$-random generator for the rule $r$
(i.\,e., the length of selection is greater than
or equal to $n$, and the deviation is
$\epsilon$ or greater).
Consider the least $k\ge n$ such that
the deviation in the beginning of $r[\vct t]$
of length $k$ is not less than $\epsilon$.
It is clear that
\begin{multline*}
\Pr\{\vct t\text{ is not
           an $(n,\epsilon)$-random generator for } r\}\\
  \le\Pr\{\text{the deviation in $r_n[\vct t]$ }\ge\epsilon\} +
  2\cdot\sum_{k=n}^L
   \Pr\left\{\text{the number of zeros in $r_k[\vct t]$ }
      =\left\lceil k\left(\frac{1}{2}+\epsilon\right)
       \right\rceil\right\}\\
= 2\cdot\sum_{j=\lceil n(\frac{1}{2}+\epsilon)\rceil}^n
  \binom{n}{j}\cdot 2^{-n} +
2\cdot\sum_{k=n}^L
  \binom{k}{\lceil k(\frac{1}{2}+\epsilon)\rceil}\cdot 2^{-k}\,.
\end{multline*}

For $j\ne k$, we use the following inequality
arising from the Stirling formula:
$$
\binom{k}{j}\le\frac{\Exp{k\cdot h(j/k)}}{\sqrt{2\pi j(k-j)/k}}\,,
$$
where $h(x)=-x\ln x-(1-x)\ln(1-x)$ is
the Shannon entropy function.
The denominator of the bound is not less than
$\sqrt{2\pi\cdot (1-1/k)}\ge \sqrt{2\pi\cdot 15/16}$,
since $k\ge n\ge\epsilon^{-4}\ge 16$.
The sign of the derivative of $h(x)$ shows that,
for $x\ge\frac{1}{2}$, the function $h$ decreases;
therefore, $h(j/k)\le h(\frac{1}{2}+\epsilon)$.
Differentiating twice, we can easily show that
$h(\frac{1}{2}+\epsilon)\le \ln 2 - 2\epsilon^2$.

Thus, the upper bound on the probability
for the rule $r$ is less than
$$
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}}\,.
$$

Simple calculations show that
the last bound is strictly less than
$\Exp{-2n\epsilon^2(1-\epsilon)}$
for $\epsilon\le\frac{1}{2}$ and $n\ge\epsilon^{-4}$
(the inequality
$1-\Exp{-x}\ge x/\sqrt{\Exp{}}$ for $0\le x\le\frac{1}{2}$
is used).

To estimate the probability that
a sequence is not an $(n,\epsilon)$-random generator
for at least one rule from $\mathcal{R}_L$,
we multiply by the number of rules.
So the probability that
a sequence is not an $(n,\epsilon)$-random generator
with respect to $\mathcal{R}_L$ is strictly less than $1$;
therefore, there exists
at least one $(n,\epsilon)$-random generator.\qed
\end{proof}


\begin{remark}
Kolmogorov's theorem, as well as our results below,
can be generalized to the case where
$0$ and $1$ have frequencies close to $p$ and $1-p$
respectively
in all long subsequences selected by
simple rules.
\end{remark}

Under the algorithmical approach,
we get the following statement.

\renewcommand{\thmprimname}{\thmprimword~\ref{thm:kolm}$'$}
\begin{thmprim}
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{thmprim}
\begin{proof}
 Proposition~\ref{prop:num} implies that
the set of rules with the entropy less than
$d(n,\epsilon)(1-\epsilon)$
has the complexity less than
$d(n,\epsilon)(1-\epsilon)$,
so the algorithmical theorem
trivially follows from
the combinatorial result.\qed
\end{proof}

\begin{theorem}[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{theorem}
\begin{proof}
We should construct a set of
nonadaptive place-selection rules
such that, for each sequence $\vct t$,
there is a rule $r$ in this set
that selects a long subsequence
$r[\vct t]$ of large deviation.

Let
$$
 m=\left\lfloor\frac{1}{4\epsilon}+\frac{1}{2}\right\rfloor\,,\quad
L'=2m\cdot\left\lceil\frac{n}{2m-1}\right\rceil\,.
$$
It can easily be checked that $L'<L$
under conditions on $\epsilon$ and $n$
from the theorem assumption.

Our rules will select subsequences just from the first
$L'$ digits of a sequence.
Namely, we split the beginning of the length $L'$
into $m$ segments of the equal length $L'/m$.
A rule selects exactly one-half of digits
from one of these segments
and all digits from the others.
Thus, a rule is determined by
the number of a segment and
a subset of $\{1,\ldots,L'/m\}$
consisting of $\frac{L'}{2m}$ elements.

Each rule selects a subsequence of length
$$
n'=(2m-1)\cdot\left\lceil\frac{n}{2m-1}\right\rceil\ge n\,.
$$

Take a sequence $\vct t$.
We prove that there is a rule $r$
such that the deviation in $r[\vct t]$
is greater than $\epsilon$.
Denote the beginning of the sequence $\vct t$
of length $L'$ by $\vct t'$.
Let us consider three cases.
\begin{enumerate}
\item Assume that there are two segments of $\vct t'$
      such that
      at least one-half of digits in the first one
      are zeros
      and at least one-half of digits in the second one
      are ones.

      Consider two rules, $r_1$ and $r_2$.
      To define them, we point out which digits
      they do \emph{not} select.
  \begin{itemize}
   \item For $r_1$, all such digits are zeros
         and lie in the first segment.
   \item For $r_2$, all such digits are ones
         and lie in the second segment.
  \end{itemize}
      The number of zeros in $r_1[\vct t]$ is equal to
      the number of zeros in $\vct t'$ minus $L'/2m$,
      and the number of zero in $r_2[\vct t]$ is equal to
      the number of zeros in  $\vct t'$.
      Thus, the numbers of zeros in these selections
      differ by $L'/2m$,
      hence the difference between one of them
      and $n'/2$ is not less than $L'/4m$.
      The deviation in either
      $r_1[\vct t]$ or $r_2[\vct t]$
      is not less than
      $$
       \frac{L'/4m}{n'}=
       \frac{1}{2(2m-1)}\ge \epsilon\,.
      $$

\item Assume that, in all segments of $\vct t'$,
      at least one-half of all digits are zeros.

      Then consider a rule that selects only zeros
      from (for instance) the first segment and
      all digits from the others.
      The number of zeros in the selection is not less than
      $$
       \frac{L'}{2m}+(m-1)\frac{L'/m}{2}=\frac{L'}{2}\,.
      $$
      The deviation is not less than
      $$
       \frac{L'/2-n'/2}{n'}=\frac{2m-(2m-1)}{2(2m-1)}\ge\epsilon\,.
      $$

\item Finally, assume that,
      in all segments of $\vct t'$,
      at least one-half of digits are zeros.

      This case is entirely similar
      to the previous one
      (with changing zeros to ones).
\end{enumerate}

Thus, we have proved that there are no
$(n,\epsilon)$-random generators with respect to
the constructed set of rules.
Now we should estimate the number of rules.
It is equal to
$$
 m\cdot \binom{\scriptstyle L'/m}{\scriptstyle L'/2m}\le
  m\cdot\sqrt{\frac{2}{\pi L'/m}}\cdot 2^{L'/m}\,.
$$
It remains to note that
$m\cdot\sqrt{2m/\pi L'}<1/4$
for $n\ge \epsilon^{-3}$ and $\epsilon<1/20$,
and $\frac{L'}{m}< 2+ 4n\epsilon(1+5\epsilon)$
for $\epsilon<1/20$.\qed
\end{proof}

Theorem~\ref{thm:kolm} gives us a lower bound and
Theorem~\ref{thm:rev_kolm} gives 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.
As is noted in~\cite{kolm}, he had not succeeded.
In the preface to the translation of~\cite{kolm}
into Russian (see~\cite{trans_kolm})
Kolmogorov reminded the reader that the problem was
waiting to be solved.

The lower bound obtained by Kolmogorov
turns out to be practically sharp
(even for nonadaptive rules).

\begin{theorem}\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{theorem}
\begin{proof}
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$.\footnote{
There are many examples in mathematics
where an implicit construction gives better estimation
than all known explicit constructions.
The book~\cite{yaglom}, pp.~257\nobreakdash--261
and~273\nobreakdash--280, contains a detailed discussion
Kolmogorov's proof of a special case of
Shannon's theorem about noise-resistant coding,
and the significance of
``noneffectiveness'' in reasoning is stressed.
}


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 define 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)}$\nobreakdash-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).

At first, we assume that the numbers
$L/2$ and $n(\frac{1}{2}+\epsilon)$ are integers;
in the end of the proof, we explain
what should be done in other cases.
Since we need a lower bound,
it is sufficient 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.
Moreover, it is sufficient to estimate
the probability of the deviation
that exactly equals $\epsilon$.
Thus, we estimate the probability of
selecting a subsequence of length $n$
containing exactly $(\frac{1}{2}+\epsilon)n$ zeros
from a sequence of $L/2$ zeros and $L/2$ ones.
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}\,,
$$
(we assume that $\epsilon<\frac{1}{2}$ and $n\le L/2$).

As in Theorem~\ref{thm:kolm},
we use the following inequality
arising from the Stirling formula:
$$
\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}}\,.
$$
We get that the probability is not less than
$$
\Exp{L\left(\frac{1}{2} h((1-2\epsilon)\gamma)+
                   \frac{1}{2} 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}}\,,
$$
where $\gamma=n/L$.

It can easily be checked that the second factor
in this bound is greater than $1/\sqrt{\Exp{}n}$.

Differentiating twice, we can verify that,
for $\epsilon\le\frac{1}{\sqrt{8}}$
%%
%%(in particular, if $\epsilon<\frac{19}{54}$)
%%
and $\gamma\le\frac{1}{2}$,
we have
\begin{equation}\label{eq:hless}
{\frac{1}{2} h((1-2\epsilon)\gamma)+
  \frac{1}{2} h((1+2\epsilon)\gamma)-h(\gamma)
\ge -\frac{2\gamma\epsilon^2}{1-\gamma}(1+4\epsilon^2/3)}\,.
\end{equation}


Finally, we get that the required probability
is greater than $\Exp{-K}$, where
$$
K=\frac{2n\epsilon^2}{1-\gamma}(1+4\epsilon^2/3)
  +\frac{1}{2}(1+\ln n)\,.
$$

Thus, the probability that
one rule does not select a subsequence
from a given sequence
such that the deviation
is not less than $\epsilon$
turns out to be less than $(1-\Exp{-K})$.
Now let us independently take
$N$ random rules\footnote{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 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
is not greater than
$$
\frac{2n\epsilon^2}{1-n/L}
   (1+4\epsilon^2/3)\lb\Exp{}+2\lb L\,.
$$
It can easily be checked that
\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}
for $\epsilon<1/3$ and $n\ge 2\epsilon^{-3}\lb L$.

Now let us return to our assumption that
the numbers $L/2$ and $n(\frac{1}{2}+\epsilon)$
are integers.
If the number $L$ is odd,
we can make the same reasoning
for the beginnings of original sequences
of length $L-1$,
and in the final formula $n/L$ is replaced by $n/(L-1)$.
The number $n(\frac{1}{2}+\epsilon)$
can always be converted into an integer by
changing $\epsilon$ to $\epsilon'\ge\epsilon$
such that $\epsilon'-\epsilon<\frac{1}{n}$.
The theorem assumption easily implies that,
if $\epsilon < \frac{1}{3}$,
then $\epsilon'<\frac{1}{\sqrt{8}}$.
Thus, the inequality~(\ref{eq:hless}) holds
if we replace $\epsilon$ by $\epsilon'$,
and the inequality~(\ref{eq:1}) holds
if we do not change its left-hand side
and in the right-hand side
we replace $\epsilon$ by $\epsilon'$.\qed
\end{proof}

\begin{remark}
In the proof of Theorem~\ref{thm:rev_kolm},
the set $\mathcal{R}_L$ is polynomially computable,
i.\,e.,
an algorithm have been constructed
that, given the number of a rule from $\mathcal{R}_L$
and an argument of the rule,
computes (within polynomial time)
the result of applying the rule to the argument.
As for the set $\mathcal{R}_L$ from the theorem~\ref{thm:MS},
this is likely to be false
since the proof is probabilistic.

{\bf Open problem.}
Is it possible to improve Theorem~\ref{thm:MS}
in order to make the set $\mathcal{R}_L$
polynomially computable
(informally speaking, so that
$\mathcal{R}_L$ would become an explicitly defined set)?
\end{remark}

\renewcommand{\thmprimname}{\thmprimword~\ref{thm:MS}$'$}
\begin{thmprim}
Consider a natural $L \ge 2$
(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
conditional entropy under known $L$
is less than
$$
d(n,\epsilon)\frac{1+\epsilon}{1-n/L}+C\,.
$$
\end{thmprim}
\begin{proof}
By the previous theorem,
there is no $(n,\epsilon)$-random
generator of length $L$ with respect to
a certain 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 verify 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).

Given $L$, $n$, and $\epsilon$,
this set can be enumerated
by a program of entropy
depending on the programming language only.
Proposition~\ref{prop:ent}
(relativized with respect to $L$, $n$, $\epsilon$)
implies that
the conditional entropy of each of these rules
does not exceed the complexity of the set
plus a constant.
If we add rules (all remaining
with entropy less than
$d(n,\epsilon)\frac{1+\epsilon}{1-n/(L-1)}+C$),
the property
(nonexistence of an $(n,\epsilon)$-random generator)
cannot be violated.
Finally, note that the difference
$$
\left(d(n,\epsilon)\frac{1+\epsilon}{1-n/(L-1)}-
d(n,\epsilon)\frac{1+\epsilon}{1-n/L}\right)
$$
is less than $1$.\qed
\end{proof}


\section{Comparison of universal and
frequency randomness}

\subsection{Philosophical Motivation}

It is traditional for mathematical statistics
to use tests in order to clarify
our idea of randomness.
Assume that we have a finite sequence of cards
(see the paragraph before Definition~\ref{def:rule}),
their faces down, each containing a binary digit.
In this formulation,
to each sequence of cards
we assign a certain (unknown to us)
sequence of zeros and ones.
Informally,
nonrandomness (with respect to the uniform distribution)
of this sequence  means that
it is possible to make
a nontrivial prediction about its behavior.
If one offers a sequence and, after
the cards are opened the sequence, on them coincides
with the offered one,
then this sequence should be considered as
maximally nonrandom.
If one offers a set containing
a relatively small number of elements
and, after the cards are opened,
the sequence on them belongs to the offered set,
then this sequence should be considered as
nonrandom too
(having a bigger measure of nonrandomness
for the smaller cardinality of the set).
Such sets are usually called tests.

Practically,
sometimes it is convenient to consider
tests of a certain special kind.
Frequency tests are especially important.
Let $r$ be a rule selecting a subsequence
of length $n$ from any sequence of length $L$,
and let $\epsilon$ be a deviation.
We assign to $r$ and $\epsilon$ a set\footnote{
In Definition~\ref{def:right_set}, such sets
are referred to as regular.}
(a frequency test) containing
sequences $\vct t$ such that
$\ell(\vct t)=L$, $\ell(r[\vct t])=n$,
and the fraction of zeros in $r[\vct t]$
differs from $\frac{1}{2}$ by at least $\epsilon$.
We could say that
the universal concept of randomness
is reduced to the frequency one
if any test $U$ could be covered by
a small collection of frequency tests
$F_1,\ldots,F_m$.
In this case, it is important
that $m$ is very small compared with
the cardinality of $U$,
and the cardinality of each $F_i$ is not
much greater than the cardinality of $U$.
Theorem~\ref{thm:cover} gives
particular estimations of this kind.
Theorem~\ref{thm:no_cover} shows that
the estimations from Theorem~\ref{thm:cover}
cannot be improved substantially.
Theorem~\ref{thm:no_adapt} implies that
frequency tests $F_i$ cannot be defined with help of
more restricted (than in Theorem~\ref{thm:cover})
class.

It is worth saying that
the combinatorial results from the first part
of this article can also be interpreted as
an analysis of the possibility to cover
a set $U$ by frequency tests $F_1,\ldots,F_m$.
But in this case, as $U$, we consider
the set of all sequences.

Under the combinatorial approach,
as in classical probability theory,
we cannot precisely define what is
``one (who does not know a sequence)
offers a set of small cardinality
that contains this sequence.''
Under the algorithmical approach,
in place of such a set we take the set
of all sequences of small
(compared with their length) entropy.
In other words, one (``universal'') test
is studied.
An advantage is that we can speak about
a complexity measure of an individual sequence.
A disadvantage is that the universal test
does not defined explicitly
(it is enumerable but not decidable).

As in the first part of the article,
algorithmical theorems have the numbers
of parallel combinatorial theorems
with the prime.



\subsection{The Combinatorial Approach}

\begin{definition}\label{def:set_defect}
The \emph{deficiency} $\Delta(S)$ of a set $S$
consisting of binary sequences of a certain length $L$
is the difference between $L$ and
the complexity of the set $S$,
i.\,e., $\Delta(S)=L-\lb|S|$.
The \emph{specific deficiency} $\delta(S)$
is the value $\delta(S)=\Delta(S)/L$.
\end{definition}

The specific deficiency characterizes
a measure of nontriviality of a set
if it is used as a test.

\begin{theorem}\label{thm:cover}
Let $\delta\in(0,\Exp{-\Exp{8}})$
and consider a natural $L\ge(1/\delta)^5$.
Let us consider sets of
binary sequences of length $L$.
For an arbitrary set $S$ of
specific deficiency $\ge\delta$,
there is a family of regular sets
of specific deficiency greater than
$$
\delta'=\frac{\delta}{\ln(1/\delta)}(1-\beta)
$$
that covers $S$ and contains at most
$L\Exp{1/\delta'}$ sets
(as $\beta$, we can take
$\frac{2\ln\ln(1/\delta)}{\ln(1/\delta)}$).
\end{theorem}
\begin{proof}
For a set $S$ of sequences of length $L$,
let us consider the following game.
Mathematician and Nature  make
$L$ moves in turn. At the $i$th move
Mathematician places an $x_i\in[0,1]$ bet
on a digit $0$ or $1$,
and Nature chooses an element $t_i\in\{0,1\}$
so that after $L$ moves
the sequence $\vct t$ would belong to $S$.
At first, the capital of Mathematician
is equal to zero; then, at each move,
it increases by the value of the bet if
Mathematician have guessed the next digit $t_i$,
and it decreases by the same value otherwise.
The capital may be negative, and for this reason
the game is called the \emph{game ``on credit.''}
Let us show that for any set $S$,
there is a strategy of Mathematician
that allows him to win not less than $\Delta(S)\ln 2$.

Let us introduce some notation.
If $\vct s$ is an extension of a sequence $\vct t$
(in other words, $\vct t$ is a prefix of $\vct s$),
we write $\vct s\sqsupset\vct t$
(it is possible that $\vct s=\vct t$).
The set $S_{\vct t}=\{\vct s\mid
\vct s\sqsupset\vct t, \vct s\in S\}$ is the
set of all extensions of $\vct t$
belonging to $S$.
Let $\vct t_{1:i}$ be the beginning of
a sequence $\vct t$
obtained before the $(i+1)$st move.

Mathematician's strategy is as follows.
If $|S_{\vct t_{1:i}0}|\ge |S_{\vct t_{1:i}1}|$
(i.\,e., if most of the extensions of $\vct t_{1:i}$
belonging to $S$ begin with $0$),
then Mathematician bets on $0$;
otherwise, he bets on $1$;
the value $x$ of the bet
is determined by the equation
$\frac{1+x}{2}=\frac{|S_{\vct t_{1:i}0}|}{|S_{\vct t_{1:i}}|}$
or
$\frac{1+x}{2}=\frac{|S_{\vct t_{1:i}1}|}{|S_{\vct t_{1:i}}|}$
respectively.

Let us show that the value
$K_i+\Delta_i\ln 2$
does not decrease for this strategy,
where $K_i$ is Mathematician's capital
after the $i$th move and
$\Delta_i=\Delta(S_{\vct t_{1:i}})-i$
is the deficiency of the set of all possible
finishes of the game.
This implies that Mathematician's gain $K_L$
is not less than $\Delta(S)\ln 2$,
since at the beginning $K_0=0$,
$\Delta_0=\Delta(S)$,
and after the last move
$\Delta(S_{\vct t_{1:L}})-L=L-\lb 1-L=0$.

We should prove that the sum
$(K_{i+1}-K_i)+(\Delta_{i+1}-\Delta_i)\ln 2$
is always nonnegative.
The second term is equal to
$-\ln 2-\ln\frac{|S_{\vct t_{1:(i+1)}}|}
               {|S_{\vct t_{1:i}}|}$.
The first term is equal to the bet $x$ or $(-x)$.
In the first case, we have
$x-\ln 2-\ln\frac{1+x}{2}=x-\ln(1+x)\ge 0$
(by the well-known inequality for the logarithm).
In the second case, we have
$-x-\ln 2-\ln\frac{1-x}{2}=-x-\ln(1-x)\ge 0$.
Thus, we obtain that the gain is not less than
$\delta L\ln2$, where $\delta=\delta(S)$.

We will use this strategy
for constructing a set of rules
that give a cover of $S$ by regular sets.
The idea is the following:
given $S$, we construct regular sets of large deficiency
that cover ``almost all'' of $S$;
for the rest of $S$, we repeat the same construction.
We estimate the number of covered sequences
using our winning strategy
(it will be slightly modified in order to decrease
the number of possible bet values).

First of all, we modify the strategy.
To this end, let us take the nearest
to $\ln(1/\delta)$ from above number $B$ such that
$M=\frac{B}{\delta\ln 2}$ is natural,
and round off all bet values to
the nearest number of the form
$k/M$ (where $k\in\mathbb N$).
Note that the decreasing of the gain
at each move is less than
$\frac{1}{M}$,
and the modified strategy wins more than
$\delta L\ln2(1-\frac{1}{B})$.
Now nonzero bets can run over
$M$ different values only.

To each set of admissible values of bets
(subset of $\{1/M,2/M,\ldots,1\}$) and
to each binary digit ($0$ or $1$),
assign the following rule.
It reads a sequence digit by digit and
applies the winning strategy
to the part read previously;
the next digit is selected to
the subsequence if
the strategy prescibes to bet this value
on this digit.
The number of rules of this form
is not greater than $2\cdot2^M$.
For each $n$, apply $n$-normalization
to each rule.
After that, the number of normal rules
is not greater than
$2L\cdot2^{B/(\delta\ln2)} <
 2L\cdot2^{1+\lb(1/\delta)/\delta}=
4L(1/\delta)^{1/\delta}$.

For almost all sequences $\vct t\in S$,
we will find a normal rule $r$
of the form described above
and a number $\epsilon$ such that
the regular set $A_{r,\epsilon}$ contains
$\vct t$ and the deficiency of $A_{r,\epsilon}$
is large enough.
The inequality
$\epsilon_1>\epsilon_2$
implies that
$A_{r,\epsilon_1}\subseteq A_{r,\epsilon_2}$;
therefore,
for each $r$, we can take the least $\epsilon$
such that the deficiency of $A_{r,\epsilon}$
is large enough.
Most part of $S$ turns out to be covered
by not more than
$4L(1/\delta)^{1/\delta}$ sets,
and for a small exceptional set
$\widetilde S\subset S$
we repeat the whole construction;
a recursive calculation shows that
the total number of sets in the cover
is not too large.

Let us take a sequence $\vct t_0\in S$.
The strategy wins more than
$\delta L\ln2(1-\frac{1}{B})$
on it, betting on zero and on one.
If we allow betting on $0$ or on $1$ only,
then at least in one case the gain is greater than
$\frac{1}{2}\delta L\ln2(1-\frac{1}{B})$.
Let us choose the corresponding digit
(assume that it is $0$) and in the sequel
consider bets on $0$ only
(we will ignore bets on $1$).

For any beginning $\vct t$
of a sequence from $S$,
denote by $d_i(\vct t)$
the difference between
the numbers of wins and losses
on bets of value $i/M$ (bets on $0$ only)
and denote by $n_i(\vct t)$
the total number of such bets
(when Nature moves in accordance with $\vct t$).

The gain on $\vct t_0$ is equal to
$$
\sum_{i=1}^M \frac{i}{M}d_i(\vct t_0)\,.
$$

Let us exclude all bets (of value $i/M$) such that
$n_i(\vct t_0)\le\frac{L}{M^2}$.
The gain on one move is not greater than the value
of the bet, that is, $1$; hence,
after the bets are excluded,
the total gain decreases by at most
$1\cdot\frac{L}{M^2}\cdot M = L/M=\delta L\ln 2/B$.
Thus,
\begin{equation}
\sum_{i\colon n_i(\vct t_0) > \frac{L}{M^2}}
   \frac{i}{M}d_i(\vct t_0)
   \quad>\quad
   \frac{1}{2}\delta L\ln2\left(1-\frac{3}{B}\right)\,.
  \label{eq:2}
\end{equation}


For each $\vct t_1\in S$,
consider the set
$$
 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}
 If $n_i(\vct t_1)>L/M^2$, then
 $|S(\vct t_1,i)| < |S|\Exp{-L/2B^2 M^4}$.
\end{claim}
We will prove this claim later,
and now we continue the proof of the theorem.

Put
{%
\newlength{\tempdima}
\settowidth{\tempdima}
       {$\scriptstyle  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$\scriptstyle\vct t_1\in S$\hfil\\[-1ex]
     $\scriptstyle i\colon n_i(\vct t_1) > L/M^2$}}
                   $\hss}}
           S(\vct t_1,i)\,.
$$
}%
Let us note that a set $S(\vct t_1,i)$ is uniquely determined
by two parameters, $i$ and $n_i(\vct t_1)$,
which can range over
$M$ and $L$ different value respectively.
Therefore,
$$
|\widetilde S| < LM|S|\Exp{-L/2B^2 M^4}\,.
$$

Let us consider two cases:
\begin{enumerate}
\item $\vct t_0\in\widetilde S$;
\item $\vct t_0\notin\widetilde S$.
\end{enumerate}

In the first case, $\vct t_0$ belongs to
the exceptional set, and we do not try
to cover this set by regular sets of the form
described above.
Instead, we repeat our construction for the set
$\widetilde S$ with the same bound on $\delta$
(the deficiency of $\widetilde S$ is greater
than the deficiency of $S$).
As a result, we obtain the following chain of
decreasing sets:
$S^{(0)}=S$, $S^{(1)}=\widetilde{S^{(0)}}$,
$S^{(2)}=\widetilde{S^{(1)}}$,\,\ldots\:.
This chain is finite since,
at each step,
the cardinality (a natural number)
of the corresponding set
becomes at least
$\Exp{L/2B^2 M^4}/LM$
times as small.
The length of the chain is not greater than
$$
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}\,.
$$
Using bounds for $L$ and $\delta$ from
the theorem assumption,
we obtain that the chain length is less than
$\frac{25\ln^6 (1/\delta)}{\delta^4}$.
For each element of the chain
the number of rules is not greater than
$4L(1/\delta)^{1/\delta}$,
therefore, the total number of rules is less than
$L\Exp{1/\delta'}$.

Consider the second case now.
Let us construct a regular set
covering $\vct t_0$,
that is, point out a rule
(a collection of bets values)
and a deviation.

For brevity, put
$n_i=n_i(\vct t_0)$ and $d_i=d_i(\vct t_0)$.
The condition
$\vct t_0\notin\widetilde S$
implies in particular that,
if $n_i > L/M^2$, then
$\vct t_0\notin S(\vct t_0,i)$,
or, equivalently,
$d_i > \frac{i}{M}n_i(1-\frac{1}{B})$.
From this and by~(\ref{eq:2}),
we get
$$
\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) >
     \frac{1}{2}\delta L\ln2\left(1-\frac{4}{B}\right)\,.
$$

Consider a regular set that is determined by
a collection of bets
$J\subseteq\{i\mid n_i > \frac{L}{M^2}\}$,
the length of a selected subsequence
$n=\sum_{i\in J}n_i$, and the deviation
$\epsilon=\frac{1}{2n}\sum_{i\in J} d_i$.
This set contains $\vct t_0$
(recall that $d_i$ is the difference
between numbers of wins and losses).
By Chernoff bound, we have that
the specific deficiency of the set
in not less than
$2n\epsilon^2\lb\Exp{}/L$.
The proof will be completed
if we show that
this value is greater than
$\frac{\delta}{\ln(1/\delta)}(1-\beta)$
for some $J$.

Assume the contrary, i.\,e.,
for any
$J\subseteq\{i\mid n_i > \frac{L}{M^2}\}$,
we have
$$
\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)\,.
$$
In other notation,
$$
\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)\,,
$$
where $Z=\frac{\delta}{\ln(1/\delta)}(1-\beta)\cdot 2L\ln2$.

\begin{claim}\label{claim:calc}
 If $\sum_{i\in J} \frac{d_i}{n_i}n_i
     \le \sqrt{Z\sum_{i\in J} n_i}$
for all $J$, then
$$
 \sum \frac{d_i^2}{n_i}\le Z+\frac{Z}{4}(\ln\sum n_i-\ln Z)\,,
$$
where the sum is taken over all $i$ such that
$n_i > \frac{L}{M^2}$.
\end{claim}

This claim will be proved later too.

Now, if we recall the bound for $\sum d_i^2/n_i$
obtained previously, we get
$$
\frac{1}{2}\delta L\ln2\left(1-\frac{4}{B}\right) <
               Z+\frac{Z}{4}(\ln L-\ln Z)\,
$$
(here we take into account that $\sum n_i\le L$).
After simple transformations, we get
$$
\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)\,,
$$
which is wrong for
$\beta=\frac{2\ln\ln(1/\delta)}{\ln(1/\delta)}$
and
$\delta<\Exp{-\Exp{8}}$.\qed
\end{proof}

It remains to prove two claims used.

%%\begin{proof}
\proofof{Claim~\ref{claim:calc}}
We should obtain an estimation of the sum
$\sum\frac{d_i^2}{n_i}=
\sum\left(\frac{d_i}{n_i}\right)^2\!n_i$
from a given estimation of the sum
$\sum\frac{d_i}{n_i}n_i$.
Let us change these sums to integrals of
step functions.
Since the order of indices $i$ is not important,
assume that $i=1,\ldots,I$
and $\frac{d_i}{n_i}$ monotonically nonincreases.
Consider nonincreasing function $f$
on the half-open interval $[0,\sum_{i=1}^I n_i)$
that defined by the equality
$$
 f(x)=\frac{d_k}{n_k}\:\text{ if } N_{k-1}\le x<N_k\,,
$$
where $N_k=\sum_{i=1}^k n_i$.
Obviously, these sums over $i=1,\ldots,k$
are equal to integrals from $0$ to $N_k$
of $f$ and $f^2$ respectively.
By the claim condition,
for every $k$ we have
$$
 \int_0^{N_k}f(x)\,dx\le\sqrt{Z\cdot N_k}\,.
$$
Using convexity of the square root,
we can extend this inequality on
arbitrary values of the upper limit
of the integral.
Indeed, for $N_k\le u \le N_{k+1}$,
we get
$$
\int_0^{u}f(x)\,dx=\int_0^{N_k}f(x)\,dx
    +\frac{d_{k+1}}{n_{k+1}}(u-N_k)\,.
$$
For $u=N_{k+1}$,
the inequality implies that for all $u$ we have
$$
\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}\,.
$$
Therefore,
$$
\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}\,.
$$

We want to represent the right-hand side as
an integral of a bounded nonincreasing function $g$.

Note that $f(x)\le 1$ since $d_k\le n_k$.
Put
$$
 g(x)=
 \begin{cases}
  1,                           & \text{if }x<Z,\\
  \frac{\sqrt{Z}}{2\sqrt{x}},  & \text{if }x\ge Z.
 \end{cases}
$$
Let us remark that,
if $u\ge Z$, then
$\int_0^{u}g(x)\,dx=\sqrt{Zu}$.
Hence,
$$
\int_0^{u}(g(x)-f(x))\,dx\ge 0
$$
for all $u\in[0,N_I]$.
It remains to show that
$\int_0^{u}(g^2(x)-f^2(x))\,dx\ge 0$.

The second mean-value theorem for integrals asserts that,
for any integrable function $\psi(x)$
and any nonnegative nonincreasing function $\phi(x)$,
there exists a point $\xi\in[a,b]$ such that
$$
 \int_a^b\phi(x)\psi(x)\,dx=\phi(a)\int_a^\xi \psi(x)\,dx\,.
$$
The functions $\psi(x)=g(x)-f(x)$ and
$\phi(x)=g(x)+f(x)$ satisfy
conditions of this theorem;
hence,
$$
\int_0^{u}(g^2(x)-f^2(x))\,dx=
     (g(0)+f(0))\int_0^\xi (g(x)-f(x))\,dx\ge 0\,.
$$

Let us verify that $Z < N_I$.
In fact,
$$
\sum n_i=\sum\frac{n_i^2}{n_i}\ge
\sum\frac{d_i^2}{n_i} >
\frac{1}{2}\delta L\ln 2(1-\frac{4}{B}) >
\frac{\delta}{\ln(1/\delta)}
(1-\beta)\cdot 2L\ln 2=Z
$$
(recall that $\delta$ is small).

Thus,
$$
\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)\,.\qed
$$
%%\end{proof}

%%\begin{proof}
\proofof{Claim~\ref{claim:size}}
Consider the set $S(\vct t_1,i)$.
Note that the condition
$$
d_i(\vct t) \le
 \frac{i}{M}n_i(\vct t_1)
   \left(1-\frac{1}{B}\right)
$$
may be rewritten in the following form:
$$
 \left(\frac{1}{2}+\frac{i}{2M}\right)n_i
                    -\frac{in_i}{2BM}
   \ge \frac{n_i+d_i}{2}\,.
$$

To estimate the cardinality of $S(\vct t_1,i)$,
we introduce two auxiliary probability measures,
$\Pr_S$ and $\Pr$.
The measure $\Pr_S$ is the uniform distribution on $S$,
that is, $\Pr_S(X)=|X\cap S|/|S|$.
The measure $\Pr$ is the Bernoulli measure
with the probability of zero
equal to $(\frac{1}{2}+\frac{i}{2M})$.

Let $X_{\nu,\sigma}$ be the set
of all sequences of length $\nu$
that contain not more than $\sigma$ zeros.
Assume that $\vct t\in\{0,1\}^{\le L}$.
Let $z_i(\vct t)$ be the number of wins
on bets on zero of value $i/M$
when Nature moves in accordance with
the sequence $\vct t$
and Mathematician moves
in accordance with
the (modified) strategy.
Note that
$z_i(\vct t)=(n_i(\vct t)+d_i(\vct t))/2$.
Assuming that $S_{\vct s}\ne\varnothing$,
let us prove the inequality\footnote{
Here $\Pr_S\{U\mid V\}$ denotes
the probability that $U$ is true
under the condition that $V$ is true,
that is,
$\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})
$$
by descent induction on the length of
$\vct s$ from $L$ to $0$.

Assume that $\nu<0$ or $\sigma<0$;
then the probability in the left-hand side
equals $0$.
Now assume that $\nu\ge 0$,
$\sigma\ge 0$.

Let $\ell(\vct s)=L$, then
\begin{itemize}
\item[\qquad]
 if $\nu=0$,
   then the probability on the right-hand side equals $1$;\\
 if $\nu\ne 0$,
   then the probability on the left-hand side equals $0$.
\end{itemize}

The induction base is proved.

To prove the inductive step,
let us consider two cases.
For brevity,
here we use the following notation:
\begin{gather*}
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}\,.
\end{gather*}
\begin{enumerate}
\item In position $\vct s$,
      the strategy does not place
      a bet of value $i/M$ on zero.
      Then
\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 In position $\vct s$,
      the strategy places
      a bet of value $i/M$ on zero.
      Recall that in this case $i/M\le x$.
      Then
\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*}
On the other hand,
$$
 \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})\,.
$$
It is obvious that
$\Pr(X_{\nu-1,\sigma})\ge\Pr(X_{\nu-1,\sigma-1})$.
So, reducing the weight of the lesser term
(from $(1+x)/2$ to $(1+i/M)/2$) and
appropriately enlarging the weight of the greater one,
we enlarge the sum.
Hence we get the desired inequality
$P(\vct s,\nu,\sigma)\le\Pr(X_{\nu,\sigma})$.
\end{enumerate}

Thus,
$$
|S(\vct t_1,i)|/|S|=
\Pr_S\{n_i(\vct t)=\nu,\: z_i(\vct t)\le \sigma\}\le
\Pr(X_{\nu,\sigma}\,,
$$
where
$\sigma={(\frac{1}{2}+i/2M)\nu - i \nu/2BM}$ and
$\nu=n_i(\vct t_1)$.

It follows from the Chernoff bound that
$$
\Pr(X_{\nu,\sigma})\le \Exp{-2(\frac{i}{2BM})^2\nu}\,.
$$
Taking into account that $i\ge 1$
and
$n_i(\vct t_1) > \frac{L}{M^2}$,
we obtain the final bound
$$
|S(\vct t_1,i)| < |S|\Exp{-\frac{L}{2B^2 M^4}}\,.\qed
$$
%%\end{proof}

\begin{remark}
It can be proved that in Theorem~\ref{thm:cover}
(in contrast to Theorem~\ref{thm:MS})
we cannot restrict ourselves to
families of regular sets with the same deviation
$\epsilon$.
\end{remark}

\begin{remark}
The proof of Theorem~\ref{thm:cover}
uses regular sets generated by monotonic rules only.
Theorem~\ref{thm:no_adapt} shows that
using regular sets generated by nonadaptive rules
is not sufficient.
\end{remark}

Theorem~\ref{thm:cover} gives
a bound for the specific deficiency
of covering regular sets.
The following theorem shows that
this bound is sharp.

\begin{theorem}\label{thm:no_cover}
Let $\delta\in(0,\Exp{-\Exp{8}})$
and consider a natural $L\ge (1/\delta)^5$.
Consider sets of binary sequences of length $L$.
There exists a set $S$ of specific deficiency
greater than $\delta$
that cannot be covered by less than
$\Exp{L\delta^4/70}$
regular sets of specific deficiency
not less than
$$
\frac{2\delta}{\ln(1/\delta)}\,.
$$
\end{theorem}
\begin{proof}
Let
$$
m=\left\lfloor\left.\left(2-4\sqrt{\delta\ln(1/\delta)}\right)
   \right/
           \delta\ln 2\right\rfloor\,,\qquad
k=\lfloor L/2m \rfloor\,.
$$

A sequence of length $L$ is represented as
a concatenation of $m$ pairs of sequences having length $k$
and a ``remainder'' having length $L-2km<2m$.
In each pair, one sequence corresponds
(a more precise explanation will be given later)
to the digit $0$,
and the other corresponds to the digit $1$;
for the $i$th pair,
these sequences are called
$i$th $0$- and $1$-segments of an original
sequence $\vct t$ of length $L$
and are denoted by
$\vct t_{i,0}$ and $\vct t_{i,1}$ respectively.

For each $i$ from $1$ to $m$,
let us define sets $S_{i,0}$ and $S_{i,1}$
of sequences having length $k$.
Let $p_i=\frac{1}{2}+\frac{1}{\sqrt{i\ln m}}$.
The set $S_{i,0}$ consists of
sequences with not less than
$k(p_i-\frac{1}{m})$ zeros,
and $S_{i,1}$ consists of
sequences with not less than
$k(p_i-\frac{1}{m})$ ones.
The set $S$ contains all sequences $\vct t$ such that
$\vct t_{i,0}\in S_{i,0}$ and $\vct t_{i,1}\in S_{i,1}$
for each $i$.

First let us estimate the specific deficiency of $S$.
The cardinality of $S$ is equal to
the product of
$|S_{i,0}|\cdot|S_{i,1}|$
over all $i$
multiplied by $2^{L-2km}$,
the number of possible ``remainders.''
Therefore,
from the Chernoff bound (for the uniform distribution
on all binary sequences)
we obtain:
$$
|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}\,.
$$
Since
$1-\frac{\sqrt{i\ln m}}{m}\ge
           1-\sqrt{\frac{\ln m}{m}}$\:
and\: $\sum\limits_{i=1}^m\frac{1}{i}>\ln m$,
we have
$$
\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.
$$
Hence
we get
$|S| < 2^L\Exp{-4k\left(1-2\sqrt{\frac{\ln m}{m}}\right)}$,
and so the specific deficiency of $S$ is greater than
$$
\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\,.
$$

Take a cover of $S$ consisting of
less than $\Exp{L\delta^4/70}$ regular sets.
Let us prove that at least one set in this cover
has the specific deficiency less than
$\frac{2\delta}{\ln(1/\delta)}$.

The plan of the proof is as follows.
Consider the set of rules that generate
regular sets from the cover.
For each rule $r$,
the sequence is called $r$-typical
if the deviation in the selected subsequence
is small compared with its length.
We will prove that the set $S$ contains
a sequence that is typical for all rules
under consideration
(since the probability with respect to a certain distribution
of the opposite event is strictly less than $1$).
Therefore, one set from the cover
(namely, the set containing this typical sequence)
has small deficiency.

Let $\vct t$ be a sequence of length $L$ and
$r$ be a normal place-selection rule.
To define $r$-typicalness,
assume that the number of ones
in the subsequence $r[\vct t]$ is greater
than the number of zeros;
in the opposite case
it is necessary to change ones to zeros
and vice versa in the definition below.

Denote by $n$ the length of selected subsequence
$r[\vct t]$,
denote by $n_i$ the number of digits selected by $r$
from $i$th $1$-segment of the sequence,
and denote by $n'$ the total number of digits
selected by $r$ from $0$-segments of the sequence
(whence $n\ge\sum_{i=1}^m n_i+n'$ and $n_i\le k$).
The sequence $\vct t$ is called
\emph{$r$-typical} if the following conditions hold:
\begin{itemize}
 \item The number of ones selected from $i$th $1$-segment
       is less than
       $n_i p_i+\sqrt{\frac{kn_i}{m^3}}$.
 \item Either $n'<k/m$ or,
       among digits selected from $0$-segments,
       the number of ones is less than
       the number of zeros.
\end{itemize}

Let us introduce an auxiliary probabilistic measure
on sequences of length $L$:
digits are independent,
digits from $i$th $0$-segment ($1$-segment)
are equal to zero (or, respectively, to one)
with probability $p_i$,
digits from the ``remainder'' are equal to zero
with probability $\frac{1}{2}$.

Let us estimate the probability
(with respect to this measure) that
a sequence $\vct t$ (of length $L$) selected by guess
does not belong to the set $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*}

Now let us fix a place-selection rule $r$
and estimate the probability that
a sequence $\vct t$ (of length $L$) selected by guess
is not $r$-typical
(as in the definition of $r$-typicalness,
we assume that the number of ones in the subsequence $r[\vct t]$
is greater than the number of zeros;
the opposite case is considered similarly).

First, let us estimate the probability that,
at least for one $i$ from $i$th $1$-segment,
at least $n_i p_i+\sqrt{\frac{kn_i}{m^3}}$ ones
are selected.
It is not greater than the sum of probabilities
of corresponding events for each $i$.
For a fixed $n_i>0$,
using the Chernoff bound, we get
$$
\Exp{-2\frac{1}{n_i}\left(\sqrt{\frac{kn_i}{m^3}}\right)^2}\,.
$$
Since $n_i$ is not given,
we sum up the probabilities over all
possible values of $n_i\le k$.
The final upper bound is
$$
m\cdot k\cdot
 \Exp{-\frac{2k}{m^3}}\,.
$$

Now let us estimate the probability that,
from $0$-segments,
$n'\ge\frac{k}{m}$ digits are selected
and the number of ones among these digits
is not less than the number of zeros.
For a fixed $n'$,
the probability does not exceed
$$
\Exp{-2n'\left(p_m-\frac{1}{2}\right)^2}\le
\Exp{-2\frac{k}{m}\frac{1}{m\ln m}}\,.
$$
Summing up over all possible $n'\le mk$,
we finally get the bound
$$
mk\,\Exp{-\frac{2k}{m^2\ln m}}\,.
$$

We see that the bound on the probability of
violating the first condition of $r$-typicalness
is much greater than
the bound on the probability of violating
the second condition.
Taking into account the symmetric case
(change $0$ to $1$),
we obtain that,
for a sequence selected by guess,
the probability of being non-$r$-typical
is less than
$2mk\,\Exp{-\frac{L}{m^4}+1}\le
\Exp{-\frac{L}{m^4}+\ln L+1}$.
Multiplying by the number of regular sets
from the cover of $S$,
we find that the probability of
``being not typical for at least one rule''
is considerably less than $1$
when
$\delta < \Exp{-\Exp{8}}$ and $L\ge (1/\delta)^5$.
If we add a small probability
that a sequence does not belong to $S$,
this bound remains to be less than $1$.
Thus, there exists a sequence $\vct t\in S$
that is typical for all rules from the cover.

Take the set $A$ from the cover
that contains this $\vct t$
and let $r$ be the corresponding rule.
Let us majorize a possible value of
the specific deficiency of $A$,
using the $r$-typicalness of $\vct t$.
Consider two cases.

\begin{enumerate}
 \item $n\le 8k/(\ln m \ln 2)$.
    The deficiency of $A$ is not less than $n$;
    therefore, the specific deficiency is not less than
         $$
    \frac{n}{L}\le\frac{4}{m\ln m\ln 2}\,.
         $$

 \item $n > 8k/(\ln m \ln 2)$.
    Let us majorize the difference
    between the number of ones in the subsequence $r[\vct t]$
    and the half of the subsequence length
    (the argument for zeros is parallel).
    This difference consists of the corresponding
    differences for $1$-segments, for $0$-segments,
    and for the ``remainder.''
    We bound the difference for the ``remainder''
    by the half of its length, which is less than $m$.
    The typicalness implies that, for $0$-segments,
    either the total length of the selected subsequence
    (and hence the doubled difference)
    is less than $k/m$,
    or the number of zeros in the subsequence is greater
    than the number of ones.
    For the same reason, on $1$-segments,
    the difference is less than
     $$
      \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}\,.
     $$
 Since the square root is a convex function,
 we get
 $$
 \sum\limits_{i=1}^m \sqrt{n_i}\le
   m\sqrt{\sum\limits_{i=1}^m n_i/m}\le\sqrt{nm}\,.
 $$

 On one hand,
 $\sum\limits_{i=1}^m \left(n_i/\sqrt{i}\right)\le n$.
 On the other hand,
 to estimate the sum
 $\sum\limits_{i=1}^m \left(n_i/\sqrt{i}\right)$
 for $n > 4k$,
 note that, if $n_i$ increases by one
 and $n_{i+1}$ decreases by one,
 then the sum will increase.
 We know that $n_i\le k$ and $\sum n_i\le n$;
 therefore, increasing values of the first $n_i$
 until they attain $k$,
 we obtain
    $$
  \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}\,.
    $$

 Finally, we obtain that the difference
 between the number of ones in $r[\vct t]$
 and $n/2$ is less than
\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{if $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{if $n > 4k$}\,.
\end{align*}

 Since the regular set $A$
 contains the sequence $\vct t$,
 its specific deficiency is not greater than
\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{if $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{if $n > 4k$}\,.
\end{align*}
The lower bounds for binomial coefficients,
$$
\binom{n}{j} \ge
\frac{\Exp{n\cdot h(j/n)}}{\sqrt{8 j(n-j)/n}}\,,
$$
and for the Shannon entropy function
(if $\epsilon\le\frac{1}{\sqrt{12}}$),
$$
h\left(\frac{1}{2}+\epsilon\right)\ge
  \ln 2 - 2\epsilon^2(1+\epsilon^2)\,,
$$
show that
the terms $o(1)$
in the previous expressions
are less than $1/\ln(1/\delta)$.
On the other hand,
$\ln m > \ln(1/\delta)(1+1.05/\ln(1/\delta))$.
\end{enumerate}

Thus, in all cases,
at least one set from the cover of $S$
has the specific deficiency
that is less than
$$
 \frac{2\delta}{\ln(1/\delta)}\,.\qed
$$
\end{proof}


\begin{theorem}\label{thm:no_adapt}
For any $\sigma > 0$
and for any
$L \ge 12+6\lb(1/\sigma)$,
there exists
a set of binary sequences of length $L$
and of specific deficiency $\ge 1/3$
that cannot be covered by less than
$2^{\sigma L/2}$
nonadaptive regular sets
of specific deficiency $\ge\sigma$.
\end{theorem}
\begin{proof}
Consider an ordered collection of $2^{\lfloor 2L/3\rfloor}$
sequences of length $L$
(maybe, with repetitions).
The specific deficiency of the set of these sequences
(without repetitions) is not less than $1/3$.
Therefore, to prove the theorem,
it is sufficient to find a collection that
cannot be covered by any family consisting of
less than $2^{\sigma L/2}$ nonadaptive
regular sets of specific deficiency not less than $\sigma$
(we can assume that $\sigma\le 1$).

The number of collections consisting of
$2^{\lfloor 2L/3\rfloor}$ sequences
is equal to
$$
\left(2^L\right)^{2^{\lfloor 2L/3\rfloor}}\,.
$$
Let us estimate the number of collections
that cannot be covered by families
of the kind described.

Take any of such families, denote it by $\mathcal A_L$.
The number of collections that are covered by $\mathcal A_L$
is equal to
$$
\left|\bigcup\mathcal A_L\right|^{2^{\lfloor 2L/3\rfloor}}\,.
$$
The definition of the family $\mathcal A_L$ implies that
$$
\left|\bigcup\mathcal A_L\right|
  \le|\mathcal A_L|\max\{|A|\colon A\in\mathcal A_L\} <
   2^{\sigma L/2}\cdot 2^{L-\sigma L} =
  2^{L-\sigma L/2}\,.
$$
Thus, the number of collections covered by one family
is less than
$$
  2^{(L-\sigma L/2)\cdot 2^{\lfloor 2L/3\rfloor}}\,.
$$

The family $\mathcal A_L$ corresponds to
a family of nonadaptive rules $\mathcal{R}_L$.
Choosing various deviation,
we get different (generally speaking)
families of regular sets
corresponding to the same set of rules.
However, as the deviation increases,
the class of covered collections
can only decrease.
Thus, one family of $< 2^{\sigma L/2}$ rules
can cover less than
$$
  2^{(L-\sigma L/2)\cdot 2^{\lfloor 2L/3\rfloor}}
$$
collections.

Note that, in essence, a nonadaptive rule is
a subset of $\{1,\ldots,L\}$;
hence, the number of nonadaptive rules
is equal to $2^L$.
The number of families consisting of less than
$2^{\sigma L/2}$ nonadaptive rules
is less than
$$
 2^{L\cdot 2^{\sigma L/2}}\,.
$$
Therefore, such families
can cover less than
$$
 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}}
$$
collections.
To show that there are collections that are not covered
it is sufficient to verify that
$$
  \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}}\,.
$$
This inequality arises from the inequality
$L(2/3-\sigma/2) \ge 2-\lb\sigma$,
which is provided by
$\sigma\le 1$
and ${L \ge 12+6\lb(1/\sigma)}$.\qed
\end{proof}


\subsection{The Algorithmical Approach}

\begin{definition}\label{def:alg_defect}
\setlength{\rightskip}{0pt plus 0.1pt}
The \emph{deficiency} of a nonempty
binary sequences $\vct t$ of length $L$
is the value ${L-K(\vct t|L)}$,
where $K(\vct t|L)$ is the entropy of $\vct t$
conditional to $L$.
The \emph{specific deficiency} is the deficiency
divided by the length.
(An additive term from the definition of the entropy
divided by the length of a sequence
tends to zero as the length tends to infinity.
So, in the limit,
the notion of specific deficiency is invariant.)
\end{definition}

In the sequel,
to estimate the deficiency of sequences,
we will use the deficiency
of auxiliary regular sets.
Let us introduce the following notation.
Assume that a normal rule $r$
selects a subsequence of length $n$;
denote the deficiency of a regular set $A_{r,\epsilon}$
by $D(n,\epsilon)$.
An important property of the deficiency of a regular set
is that the deficiency does not depend on $L$
(the length of sequences to which place-selection
rules are applied).
For given $n$, $D$ is a monotone
increasing step function of $\epsilon\in[0,\frac{1}{2}]$;
boundaries of steps are rationals
with the denominator $2n$,
values of the function are binary logarithms
of rationals,
and all these rationals computably depend on $n$.

When $\epsilon$ is small enough and $n$
is large enough compared with $1/\epsilon$,
we have
$D(n,\epsilon)\sim d(n,\epsilon)$.

At first sight,
a natural analog of Theorem~\ref{thm:cover}
would be the following:

\begin{assertion}\label{stat:cover}
Assume that $\delta>0$ is small enough
and a natural $L$ is large enough.
Assume that $\vct t$ is a binary sequence
of length $L$ and
of specific deficiency $\ge\delta$.
Then there exists a rule $r$ such that
$$
K(r|L)\le\alpha(\delta)\quad\text{and}\quad
D(n,\epsilon)/L \ge \delta'(\delta)\,,
$$
where $n$ is the length of $r[\vct t]$,
$\epsilon$ is the deviation in $r[\vct t]$,
$\alpha$ and $\delta'$ are positive functions.
\end{assertion}

But the following theorem trivially implies
the negation of Assertion~\ref{stat:cover}.
\renewcommand{\thmprimname}{\thmprimword~\ref{thm:cover}$''$}
\begin{thmprim}
Let $\alpha$ and $\delta'$ be positive numbers.
For any natural $L$ large enough,
there exists a binary sequence $\vct t$
of length $L$
and of specific deficiency greater than $\frac{1}{2}$
such that
for any rule $r$,
$$
K(r|L)\le\alpha
\quad\Rightarrow\quad
D(n,\epsilon)/L < \delta'\:
\lor\: n=0\,,
$$
where $n$ is the length of $r[\vct t]$ and
$\epsilon$ is the deviation in $r[\vct t]$.
\end{thmprim}
\begin{proof}
Denote by $\mathcal{R}_L$ the family of all rules $r$
such that $K(r|L)\le\alpha$.
Given numbers  $\left\lfloor\alpha\right\rfloor$,
$L$, and $|\mathcal{R}_L|$,
one can effectively find a list of elements of $\mathcal{R}_L$.
Denote by $r_n$ the $n$-normalization of a rule $r$.

Consider the uniform distribution
on binary sequences of length $L$.
It follows from the definition of the function $D$
that, for any rule $r$,
the probability of the set $A_{r_n,\epsilon}$
is equal to $2^{-D(n,\epsilon)}$.

For each $n$,
take the least step bound
$\epsilon$ such that
$D(n,\epsilon) \ge \delta'L$.
If such $\epsilon$ exists, it is
a rational from $[0,\frac{1}{2}]$
with the denominator $2n$.
Denote by $E$
this collection of pairs $\pair{n,\epsilon}$.
Since $|\mathcal{R}_L| < 2^{\alpha+1}$
and $|E|\le L$,
the probability of the union of sets $A_{r_n,\epsilon}$
for $r\in\mathcal{R}_L$ and
$\pair{n,\epsilon}\in E$
does not exceed
$$
\sum\limits_{\pair{n,\epsilon}\in E}
2^{-D(n,\epsilon)+\alpha+1}\le
2^{-\delta'L+\alpha+1+\lb L}\,.
$$
For $L$ large enough,
the last expression is strictly less than $1$.
Given lists of elements of $\mathcal{R}_L$ and $E$,
using exhaustive search
one can find a sequence $\vct t$ of length $L$
that does not belong to $A_{r_n,\epsilon}$
for all $r\in\mathcal{R}_L$ and
$\pair{n,\epsilon}\in E$.

Now let us try to briefly encode
information sufficient for constructing
a list of elements of $E$.
Clearly, one can construct $E$
if it is known $L$ and the pair $\pair{n,\epsilon}$
such that the function $D$ achieves
its minimum on $E$ at the point $\pair{n,\epsilon}$.
Thus,
the entropy of the list
conditional to $L$
does not exceed $2\lb L+O(1)$.

The sequence $\vct t$
is constructed from numbers $L$,
$\left\lfloor\alpha\right\rfloor$,
$|\mathcal{R}_L|$ and the collection $E$;
therefore, $K(\vct t|L)\le 2\lb L+C(\alpha)$.
The specific deficiency of $\vct t$ is equal to
${1-K(\vct t|L)/L}$,
which is greater than $\frac{1}{2}$
for large enough $L$.

Assume that $r\in\mathcal{R}_L$, $n=\ell(r[\vct t])$,
and $\epsilon$ is the deviation in $r[\vct t]$.
Assume that
$D(n,\epsilon)/L \ge \delta'$.
Then, by construction,
$\vct t$ does not belong to $A_{r_n,\epsilon}$;
hence, the deviation in $r[\vct t]$
is strictly less than $\epsilon$.
This contradiction concludes the proof.\qed
\end{proof}

To repair the analogy with the combinatorial approach,
a place-selection rule under the algorithmical approach
should be interpreted as not an explicit function
but a program that
gets the length of a sequence $L$ as an addition input
and computes the function $r$ from
Definition~\ref{def:rule};
now, the function $r$ may be defined
\emph{not everywhere}.

\begin{definition}\label{def:fre_defect}
The \emph{frequency $\alpha$-deficiency\/}
of a binary sequence $\vct t$ of length $L$
is the maximum of the value
$D(n,\epsilon)/L$ over rules $r$
that are determined by programs
such that $r[\vct t]$ is defined
and the entropy of the program
conditional to $L$
is less than $\alpha$
(where $n$ is the length of $r[\vct t]$ and
$\epsilon$ is the deviation in $r[\vct t]$).
\end{definition}

Let us remark that, as $\alpha$ increases,
the frequency $\alpha$-deficiency
also increases.

\renewcommand{\thmprimname}{\thmprimword~\ref{thm:cover}$'$}
\begin{thmprim}
Assume that $\delta_1 > 0$ is small enough.
Then, for each rational $\delta_0 > 0$,
one can effectively find $L_0$ such that,
for any $\delta \in[\delta_0,\delta_1]$
and natural $L \ge L_0$,
the following condition holds:\\
If $\vct t$ is a binary sequence of length $L$
and of specific deficiency $\delta$,
then the frequency $\alpha$-deficiency of $\vct t$
is greater than
$$
\delta'=\frac{\delta}{\ln(1/\delta)}(1-B(\delta))\,,
$$
where $\alpha=\frac{4\ln(1/\delta)}{\delta}$
and $B(\delta)=O(\frac{\ln\ln(1/\delta)}{\ln(1/\delta)})$.
\end{thmprim}
\begin{remark}
We see that this theorem corresponds
to Assertion~\ref{stat:cover}.
\end{remark}
\begin{proof}
Let us construct a rule that selects
a subsequence of large deviation from $\vct t$.
Split the sequence $\vct t$
into two parts of approximately equal lengths
(i.\,e., their lengths are equal to $\lfloor L/2\rfloor$
and $\lceil L/2\rceil$).
Split each part again into two parts
of approximately equal lengths and so on.
Before the $(i+1)$st stage of the recursive construction
of our rule,
we choose one part of $\vct t$
obtained after $i$ splits
(before the first stage, this part is
the sequence $\vct t$ itself).
Denote this part by $\vct u_i$
and its complement\footnote{
Here, the complement is the binary encoding
of the sequence $\vct t$, where digits of $\vct u_i$
are replaced by a special new symbol.}
by $\vct v_i$.
We assume that, before the $(i+1)$st stage,
exactly the cards from $\vct v_i$ were turned over,
and neither of them was selected.
We assume also that the specific deficiency of
$\vct u_i$ conditional to $\vct v_i$
is greater than
$\delta+\lambda(i-1)$,
where $\lambda$ is a number
from the interval
$(\frac{\delta}{\ln (1/\delta)},
  \frac{2\delta}{\ln (1/\delta)})$
such that the number $(1-\delta+3\lambda)$ is rational.
For large $L$,
the last assumption is obviously true
for $i=0$.

Now let us describe the $(i+1)$st stage.
Split the sequence $\vct u_i$
into two parts of approximately equal lengths
and denote them by $\vct w_1$ and $\vct w_2$.
Let $\gamma=
\left\lfloor
(1-\delta+3\lambda)\ell(\vct w_1)
\right\rfloor$.
Consider two possible cases.

\begin{enumerate}
\item \label{en:4_1}
      Let
      $K(\vct w_1|\vct v_i) < \gamma$ and
      $K(\vct w_2|\vct v_i) < \gamma$.

      Since the entropy function is enumerable from above,
      given $\vct v_i$ and $\gamma$,
      these facts can be discovered within, say,
      $T_1$ and $T_2$ steps of the enumeration.
      We do not know the numbers $T_1$ and $T_2$.
      Our aim is to know the greater of them.
      Without loss of generality, assume that
      $T_1\le T_2$.
      Then the rule should turn over all cards from $\vct w_2$,
      selecting nothing.
      Knowing $\vct w_2$, we can wait its appearance
      in the enumeration, and hence we can know $T_2$.
      Now consider the set $S$ of sequences $\vct s$
      of length $\ell(\vct w_1)$ such that
      we can discover within less than $T_2$ steps
      that the inequality
      $K(\vct s|\vct v_i) < \gamma$ holds.
      Obviously, $\vct w_1\in S$.
      The set $S$ contains less than
      $2^{\gamma}$ elements;
      therefore, its specific deficiency is greater than
      $1 - \gamma/\ell(\vct w_1)\ge
      \delta-3\lambda$.
      (If $T_1\ge T_2$,
      then we obtain a similar inequality
      since
      $\ell(\vct w_1)\le\ell(\vct w_2)$.)

      Now apply Theorem~\ref{thm:cover}
      to the set  $S$ with this bound for
      the specific deficiency.
      The proof of Theorem~\ref{thm:cover}
      shows that there exists
      a family of rules $\mathcal{R}$ such that
      $$
      |\mathcal{R}| \le
       \left(\frac{1}{\delta-3\lambda}\right)^
                             {1/(\delta-3\lambda)+O(1)}
      $$
      and regular sets generated by normalizations of
      rules from $\mathcal{R}$ cover $S$.
      One of these regular sets
      (denote it by $A$)
      contains $\vct w_1$,
      and its specific deficiency is
      $\ge\frac{\delta-3\lambda}
        {\ln(1/(\delta-3\lambda))}(1-\beta)$,
      where $\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)$.
      Let the normal rule generating $A$
      selects from $\vct w_1$
      a subsequence of length $n$ and
      deviation $\epsilon$.
      Since the deficiency of $A$ is not greater than
       $D(n,\epsilon)$,
      we have
      \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*}

      The place-selection rule that we are constructing
      stops when Case \ref{en:4_1} is realized.

\item Let
      $K(\vct w_1|\vct v_i) \ge \gamma$ or
      $K(\vct w_2|\vct v_i) \ge \gamma$.

      To be definite, assume that
      $K(\vct w_1|\vct v_i) \ge \gamma$.
      By the theorem about the entropy of a pair,
      we have
      $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))$
      (clearly, the pair $\pair{\vct w_1,\vct v_i}$
      can be identified with the complement of $\vct w_2$).
      Hence it follows that
     \begin{equation*}
     \begin{split}
      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))\,.
     \end{split}
     \end{equation*}
      For large $\ell(\vct u_i)$,
      it is easy to deduce the following inequality
      for the specific deficiency of $\vct w_2$
      conditional to $\vct w_1$ and  $\vct v_i$:
         $$
       1 - \frac{K(\vct w_2|\vct w_1,\vct v_i)}
            {\ell(\vct w_2)} >
           \delta + \lambda i\,.
         $$

      After that, the place-selection rule we are constructing
      passes to the $(i+2)$nd stage
      with ${\vct u_{i+1}=\vct w_2}$.
\end{enumerate}

The specific deficiency is always not greater than $1$;
hence, the second case can be realized less than
$(1 - \delta)/\lambda$ times.
Therefore, the number of stages in the rule constructed
does not exceed a number independent of $L$.
This yields that, for large enough $L$,
the assumption that $\ell(\vct u_i)$ is large
holds for all $i$.

It remains to estimate the entropy (conditional to $L$)
of the rule constructed.
To construct it,
we used the following information:
\begin{itemize}
 \item the value of $1-\delta+3\lambda$;
 \item for each stage: whether the first or the second case holds;
 \item for the second case at each stage:
       which inequality holds,
       $K(\vct w_1|\vct v_i) \ge \left\lfloor
        (1-\delta+3\lambda)\ell(\vct w_1)
           \right\rfloor$
       or
       $K(\vct w_2|\vct v_i) \ge \left\lfloor
        (1-\delta+3\lambda)\ell(\vct w_1)
           \right\rfloor$;
 \item for the first case at the last stage:
       which inequality holds,
       $T_1 \le T_2$ or $T_1 \ge T_2$,
       and also the number of the set $A$
       in the family $\mathcal{R}$.
\end{itemize}

To find the rational $(1-\delta+3\lambda)$
it is sufficient to find $(\delta-3\lambda)$;
for this,
it is sufficient to find a natural from the interval
$((\delta-\frac{3\delta}{\ln (1/\delta)})^{-1},
(\delta-\frac{6\delta}{\ln (1/\delta)})^{-1})$.
Since the length of the interval is greater than $1$,
it contains a natural,
and the entropy of this natural is not greater than
$\lb(1/\delta)+O(1)$.

Thus,
an upper bound for the entropy of the rule
can be obtained from the following sum
by adding several logarithms of this sum
(logarithms appear because of encoding tuples):
$$
 \lb\frac{1}{\delta}+O(1)+
 2\cdot\left(\frac{1 - \delta}{\lambda}+O(1)\right)+
 \lb |\mathcal{R}|+O(1)\,.
$$

For small $\delta$,
this bound is less than
$\frac{4\ln(1/\delta)}{\delta}$.

Finally, let us remark that
every time we wrote ``$L$ is large enough,''
the corresponding lower bound for $L$
could be effectively derived from $\delta_0$.
The value $L_0$ is the maximum of these bounds.\qed
\end{proof}

\begin{remark}
In Theorem~\ref{thm:cover},
we could restrict ourselves to regular sets generated
by monotonic rules (however, using only
nonadaptive rules was not sufficient).
Conversely, in Theorem~\ref{thm:cover}$'$
nonmonotonic rules are necessary,
as Theorem~\ref{thm:no_adapt}$'$ shows.
\end{remark}

\renewcommand{\thmprimname}{\thmprimword~\ref{thm:no_cover}$'$}
\begin{thmprim}
Assume that $\delta_0>0$ is small enough
and consider a natural $L > (1/\delta_0)^5$.
There exists a binary sequence
$\vct t$ of length $L$
and of specific deficiency greater than $\delta_0$
such that its frequency $\alpha$-deficiency is less than
$$
\frac{2\delta_0}{\ln(1/\delta_0)}(1+3\delta_0)
$$
for $\alpha=L\delta_0^4/70$.
\end{thmprim}
\begin{proof}
Take the set of rules such that
their entropy conditional to $L$
is less than $\alpha$.
Some of these rules are defined not everywhere;
let us extend them to all sequences (of length $L$)
in an arbitrary way.
Take $n$-normalizations of these rules
for all $n=1,\ldots,L$.
The number of rules obtained is less than
$L\cdot 2^{\alpha} < \Exp{L\delta_0^4/70}$.
Consider the set of sequences $S$
that was (effectively) constructed in Theorem~\ref{thm:no_cover}
for the numbers $\delta=\frac{1}{\lfloor 1/\delta_0\rfloor-1}$
and $L$.
Since $\delta > \delta_0$,
we have
$L>(1/\delta)^5$,
$\Exp{L\delta^4/70} > \Exp{L\delta_0^4/70}$,
and by Theorem~\ref{thm:no_cover}
there exists
$\vct t\in S$ such that
$$
\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)\,.
$$
The entropy of any $\vct t\in S$ conditional to $L$
does not exceed $2\lb(1/\delta)+\lb|S|$.
Therefore,
the specific deficiency of $\vct t$
is not less than
$1-\frac{\lb|S|+2\lb(1/\delta)}{L}$.
By Theorem~\ref{thm:no_cover}, the specific deficiency of $S$
(which equals $1-\lb|S|/L$) is greater than $\delta$.
Hence, the specific deficiency of $\vct t$ is greater than
$\delta-2\lb(1/\delta)/L > \delta_0$.\qed
\end{proof}

\begin{definition}
The \emph{monotonic
$\alpha$-frequency deficiency} of a binary
sequence $\vct t$ of length $L$
is the maximum of the value
$D(n,\epsilon)/L$
over monotonic rules $r$
generated by programs
of entropy less than $\alpha$,
where $n$ is the length of $r[\vct t]$,
$\epsilon$ is the deviation in $r[\vct t]$, and
the entropy is conditional to $L$.
\end{definition}

\renewcommand{\thmprimname}{\thmprimword~\ref{thm:no_adapt}$'$}
\begin{thmprim}
Assume that $\delta>0$ is small enough
and consider a natural $L\ge (1/\delta)^2$.
Then there exists a binary sequence
$\vct t$ of length $L$
and of specific deficiency
greater than $\frac{1}{2}$
such that
its monotonic $(\delta L/4)$-frequency deficiency
is less than $\delta$.
\end{thmprim}
\begin{proof}
To construct the sequence $\vct t$,
we will consider a game similar to that used
in the proof of Theorem~\ref{thm:cover}.
But in this case the value of a bet can be any number less
than the current capital
(and the game is called the \emph{game ``on cash''}).
The initial capital is equal to $1$.
It is convenient to say that
a bet is a fraction $\sigma$ of the current capital;
then the current capital is multiplied by $(1+\sigma)$
in the case of winning (if the next digit has been guessed right),
and by $(1-\sigma)$ in the other case.

To each monotonic rule $r$,
binary digit $b$
and number $\sigma\in[0,1]$,
assign the following strategy in the game:
at step $i$, the rule $r$
is applied to the segment
$\vct t_{1:i-1}$;
if the rule prescribes to select the next digit,
the bet $\sigma$ is placed on $b$;
otherwise, the bet is not placed.
If $r$ is undefined on a segment $\vct t_{1:i-1}$
(the program does not halt),
then the strategy is undefined at all subsequent steps
and the current capital becomes undefined too.
Clearly, if the digit $b$ occurs $n_b$ times in
the subsequence $r[\vct t]$ of length $n$,
than the final capital of the strategy is equal to
$(1+\sigma)^{n_b}(1-\sigma)^{n-n_b}$
(and the deviation is equal to
$\left|\frac{1}{2}-\frac{n_b}{n}\right|$,
hence an estimation of the deviation
can be obtained from an estimation of the capital).

Assume that $1/\delta$ is natural;
in the end of the proof, we explain
what should be done with an arbitrary $\delta$.

Let $\mathcal{R}_L$ be the set of all
monotonically selecting programs of entropy
less than $\delta L/4$,
and $R$ be the number of them.
Without loss of generality,
we can assume that
a monotonically selecting program
(possibly, undefined everywhere)
is assigned to each codeword,
and if codewords are different, then
the assigned programs are different too.
Therefore
$R=2^{\left\lceil\delta L/4\right\rceil}-1$.
For
$n=\left\lceil\frac{\ln(4LR)}{\delta}\right\rceil,\ldots,L$,
define the bet $\sigma_n=\sqrt{\frac{\ln(4LR)}{n}}$.
We will consider the set of strategies assigned
to all possible
$\sigma_n$, $r\in\mathcal{R}_L$, and $b\in\{0,1\}$.

Let us introduce several auxiliary values,
which will be useful in the construction of $\vct t$.
Let $S_i$ be the total capital of all strategies
that are defined at step $i$
(this capital depends on $\vct t_{1:i-1}$ only).
The initial capital $S_0$
is equal to the number of strategies
and hence is less than $2LR$.

The idea of the construction is as follows:
at each step we choose $t_i$ so that
the total capital does not increase;
then the final capital of a strategy is not greater than
the total initial capital $S_0$,
and we obtain an estimation of the deviation in the sequence.
However, we cannot perform this directly
since we cannot verify algorithmically
whether a rule is defined on a given segment;
therefore, we cannot compute $S_{i+1}$
for both possible values of $t_i$.
Thus, at each step of our algorithm,
we need additional information.

Let $Q_i$ be the total capital at step $i$
of strategies that will be defined
at the next step, $i+1$, too
(i.\,e., defined on the segment $\vct t_{1:i}$).
It is obvious that $Q_i\le S_i$.

Define sequences $P_i$ and $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*}
It follows easily that
$$
P_i-\frac{2Rm_i}{\sqrt{\delta}}-\frac{2R}{\sqrt{\delta}}
      < Q_i \le P_i-\frac{2Rm_i}{\sqrt{\delta}}\,.
$$

Now let us describe the procedure of constructing
the next digit $t_{i+1}$
given a segment $\vct t_{1:i}$
and the values of $P_i$ and $m_i$.
The procedure consists of two stages:
\begin{enumerate}
\item \label{alg:enum}
All strategies are applied to the segment $\vct t_{1:i}$
in parallel;
the current capital of strategies
already defined on this segment is computed
until their total capital exceeds
$(P_i-\frac{2Rm_i}{\sqrt{\delta}}-\frac{2R}{\sqrt{\delta}})$.
\item \label{alg:choose}
Then the value of $t_{i+1}$ is chosen
so that the total gain of strategies that
were defined at the stage~\ref{alg:enum}
is nonpositive.
\end{enumerate}

First, let us prove that the algorithm is well defined,
that is, both stages are feasible.
If the segment $\vct t_{1:i}$ has already been constructed,
then the values $S_i$, $Q_i$, $P_i$, and $m_i$ are defined.
Assume that the algorithm was given correct $P_i$ and $m_i$.
During Stage~\ref{alg:enum},
there will be a moment
when every strategy that is defined on this segment
has already been defined.
Their total capital is equal to
$Q_i > P_i-\frac{2Rm_i}{\sqrt{\delta}}-
        \frac{2R}{\sqrt{\delta}}$;
hence, at a certain moment,
Stage~\ref{alg:enum} will stop.
Let us note that, for each (defined) strategy,
the sum of the gains for
$t_{i+1}=0$ and $t_{i+1}=1$
is zero.
The same is true for any set of (defined) strategies;
therefore,
the total gain at Stage~\ref{alg:choose}
cannot be positive for both values of $t_{i+1}$.

In the sequel, we need several properties of
the values used.
\begin{enumerate}
\item $S_i\le P_i$.

      By definition, $S_0=P_0$.
      Let us estimate $S_{i+1}$.
      The total capital of the strategies
      that were defined during Stage~\ref{alg:enum}
      (denote it by $Q'_i$)
      does not decrease.
      The capital of other strategies is equal to $Q_i-Q'_i$,
      and it becomes not more than
      $(1+\sqrt{\delta})$ times as large
      since the values of bets do not exceed $\sqrt{\delta}$.
      It is obvious that
      $Q_i-Q'_i <
      Q_i-(P_i-\frac{2Rm_i}{\sqrt{\delta}}
           -\frac{2R}{\sqrt{\delta}})\le
      \frac{2R}{\sqrt{\delta}}$.
      Consequently,
      $$
       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}\,.
      $$

\item $m_i\ge 0$.

      The equality follows from the fact that
      $Q_i\le S_i\le P_i$.

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

      Let us sum up the equalities
      $P_{i+1}=P_i+2R-\frac{2Rm_i}{\sqrt{\delta}}$
      over all $i$.
      We get
      $P_L=P_0+2RL-2R\sum m_i/\sqrt{\delta}$,
      and, taking into account that
      $P_0 < 2RL$ and $P_L > S_L\ge 0$,
      we have
      $$
       \sum m_i=(2RL+P_0-P_L)\frac{\sqrt{\delta}}{2R}
        < 2L\sqrt{\delta}\,.
      $$
\end{enumerate}


Now we can estimate the entropy of
the constructed sequence $\vct t$.
The algorithm should know
the set of strategies
and the sequences $P_i$ and $m_i$.
The set of strategies can be generated
from $L$ and $\delta$,
and $P_i$ can be generated from $m_i$, $L$, and $\delta$.
Thus,
$$
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)\,.
$$

The entropy of $\langle m_0,\ldots,m_{L-1}\rangle$
conditional to $L$ and $1/\delta$
can be majorized
by the binary logarithm of the number of
tuples such that
a tuple consists of $L$ naturals
and the sum of these naturals is less than
$N=\left\lceil 2L\sqrt{\delta}\right\rceil$.
It can easily be shown that
the tuple
$\langle m_0,\ldots,m_{L-1}\rangle$
is uniquely determined by
the multiset of its partial sums
$\{m_0, m_0+m_1,\ldots, m_0+\ldots+m_{L-1}\}$
(repetitions are allowed).
The partial sums range over the set $\{0,\ldots,N-1\}$.
Thus, the number of possible sequences $\{m_i\}$
does not exceed the number of
unordered samples with replacement
of $N$ things $L$ at a time,
which is equal to
$$
\binom{N+L}{L} < \frac{(N+L)^N}{N!} <
  \left(\frac{(N+L)\Exp{}}{N}\right)^N\,.
$$
As a result, we have
\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*}
Since $K(\vct t) < L/2$,
we get that the specific deficiency of $\vct t$
is greater than $\frac{1}{2}$.

It remains to estimate the monotonic frequency deficiency
of the sequence $\vct t$.
To this end,
let us fix a rule $r$
and consider the subsequence $r[\vct t]$
of length $n$ with deviation $\epsilon$.
Let us majorize $D(n,\epsilon)$.
Consider two possible cases.
\begin{enumerate}
\item $n \le 7\delta L/8$.
      Since $D(n,\epsilon)\le n$,
      we obtain
      $D(n,\epsilon)/L \le \frac{7}{8}\delta$.
\item $n > 7\delta L/8$.
      Assume that the number of zeros in $r[\vct t]$
      is greater than the number of ones.
      Take the strategy assigned to the rule $r$
      that places a bet $\sigma_n$ on $0$.
      The final capital of this strategy does not exceed
      the total capital
      $S_L < P_L\le P_0+2RL < 4RL$
      (it follows from the equality
       $P_L=P_0+2RL-2R\sum m_i/\sqrt{\delta}$).
      On the other hand, the capital of the strategy
      is equal to
      $(1+\sigma_n)^{n\left(\frac{1}{2}+\epsilon\right)}
      (1-\sigma_n)^{n\left(\frac{1}{2}-\epsilon\right)}$.
      We have the inequality
      $$
       \frac{n}{2}\left((1+2\epsilon)\ln(1+\sigma_n)
         +(1-2\epsilon)\ln(1-\sigma_n)\right) < \ln(4RL)\,;
      $$
      hence,
      $$
       2\epsilon\ln\frac{1+\sigma_n}{1-\sigma_n}+
         \ln(1-\sigma_n^2) < \frac{2}{n}\ln(4RL)\,.
      $$
      Using the fact that $\ln\frac{1+x}{1-x}\ge 2x$
      if $0\le x < 1$,
      and $\ln(1-x)\ge -2x$ if $0\le x \le \frac{1}{2}$,
      we obtain
      $$
       \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}}\,.
      $$
      The Stirling formula implies that
      $$
      \binom{n}{j} \ge
      \frac{\Exp{n\cdot h(j/n)}}{\sqrt{8 j(n-j)/n}}\,.
      $$
      Differentiating twice,
      we get (if $\epsilon\le\frac{1}{\sqrt{5}}$)
      $$
      h\left(\frac{1}{2}+\epsilon\right)\ge
        \ln 2 - 2\epsilon^2(1+10\epsilon^2/3)\,.
      $$
      Using these inequalities,
      we can easily check that
      \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*}
      and therefore
      $D(n,\epsilon)/L<\frac{7}{8}\delta$
       (recall that $\delta$ is small,
       $L\ge (1/\delta)^2$, and
       $\epsilon\le\frac{1}{\sqrt{5}}$).
\end{enumerate}

Finally,
if the number $1/\delta$ is not a natural,
then we can carry out the same reasoning
for the number
$\delta_0=\frac{1}{\lfloor 1/\delta\rfloor}\ge\delta$,
and obviously $\frac{7}{8}\delta_0 < \delta$.\qed
\end{proof}


\subsection{On Optimality of Bounds}

All bounds that are proved in this paper
seem to be close to optimal ones,
with the only exception, and now we discuss it.
Let $\delta$ and $\delta'$ range over
reals from $(0,1)$, $L$ range over naturals,
and $S$ range over the set of
binary sequences of length $L$.
Denote by $\Phi_{L,\delta}(\delta')$
the maximum (over sets $S$ with deficiency $\ge\delta$)
of the least number of regular sets
with deficiency $\ge\delta'$
such that their union covers $S$.
In essence, Theorems~\ref{thm:cover} and~\ref{thm:no_cover}
give an estimation of this function $\Phi$.
Namely, for some functions $\rho_1$, $\rho_2$,
we have
$$
\begin{aligned}
\delta' \le c_1\cdot\frac{\delta}{\ln(1/\delta)}
\quad&\Rightarrow&\mspace{9mu}
&\Phi_{L,\delta}(\delta') < L\cdot\rho_1(1/\delta)\,,\\
\delta' \ge c_2\cdot\frac{\delta}{\ln(1/\delta)}
\quad&\Rightarrow&\mspace{9mu}
&\Phi_{L,\delta}(\delta') > \Exp{L/\rho_2(1/\delta)}\,,
\end{aligned}
$$
where $c_1\approx 1$, $c_2 = 2$, and $L \ge (1/\delta)^5$.
In other words, when $\delta'$ changes
from $c_1\cdot\frac{\delta}{\ln(1/\delta)}$
to $c_2\cdot\frac{\delta}{\ln(1/\delta)}$,
the function $\Phi$ makes a jump
from an expression linear in $L$
to an expression exponential in $L$.
If we are interested in the behavior of $\Phi$
for $\delta$ fixed and $L\to\infty$,
then the bound looks optimal
(though it is possible to sharpen
the constants $c_1$ and $c_2$).
But now consider the behavior of $\Phi$
as $\delta\to 0$.
Then, in the obtained bounds,
the function $\rho_2$ increases polynomially,
and the function $\rho_1$ increases exponentially.

{\bf Open problem:}
Is it possible to strengthen the upper bound on $\Phi$
so that $\rho_1$ will become polynomial?

An.\,Muchnik proved (see~\cite{3avt})
that, for a smaller upper bound on $\delta'$,
a linear function can be taken as $\rho_1$.\footnote{
An algorithmical analog of this result
was recently obtained by N.\,Vereshchagin and B.\,Durand,
see~\cite{ver}.
We used some elements of their argument
in the proof of Theorem~\ref{thm:cover}$'$.}
More exactly, we have
$$
\delta' \le c_3\cdot\delta^2
\quad\Rightarrow\quad
\Phi_{L,\delta}(\delta') < L\cdot(c_4/\delta)\,.
$$
Thus, a positive decision of the problem
seems to be likely enough.

\acknowledgments

The authors are grateful to
Nikolai Vereshchagin
for interesting discussions
about Kolmogorov theory,
which were one of the incentives
to begin the present work.
The authors are 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} Kolmogorov, A.\,N.,
On Tables of Random Numbers,
\emph{Sankhy\~a: The Indian Journal of Statistics,
Series~A}, 1963, vol.~25, part~4, pp.~369\nobreakdash--376.
Reprinted in \emph{Theoretical Computer Science},
1998, vol.~207, pp.~387\nobreakdash--395.

\bibitem{3avt} Muchnik, An.\,A., Semenov, A.\,L.,
Uspensky, V.\,A.,
Mathematical Metaphysics of Randomness,
\emph{Theoretical Computer Science}, 1998,
vol.~207, pp.~263\nobreakdash--317.

\bibitem{lambalg} van Lambalgen, M.,
Von Mises's Definition of Random Sequences Reconsidered,
\emph{Journal of Symbolic Logic}, 1987,
vol.~52, pp.~725\nobreakdash--755.

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

\bibitem{UspSh} Uspensky, V.\,A. and Shen, A.\,Kh.,
Relations between Varieties
of Kolmogorov Complexities,
{\it Mathematical Systems Theory}, 1996, vol.~29,
pp.~271\nobreakdash--292.

\bibitem{trans_kolm} Kolmogorov, A.\,N.,
On Tables of Random Numbers.
\emph{Semiotika i informatika},
Moscow:~VINITI, 1982, vol.~18,
pp.~3\nobreakdash--13.
Reprinted in Kolmogorov, A.\,N.,
\emph{Teoriya informatsii i teoriya algoritmov}
(Information Theory and Theory of Algorithms),
Moscow:~Nauka, 1987, pp.~204\nobreakdash--213.

\bibitem{yaglom} Yaglom, A.\,M. and Yaglom, I.\,M.,
\emph{Veroyatnost' i informatsiya},
Moscow:~Fizmatgiz, 1960, 2nd ed.
Translated under the title
\emph{Probability and Information},
Boston: Reidel, 1983.

\bibitem{ver} Durand, B. and Vereshchagin, N.,
Kolmogorov--Loveland Stochasticity
for Finite Strings, 2002.
Available from
\verb"http://markov.math.msu.ru/~ver/papers/kolm-love.ps".

\end{thebibliography}
