\documentclass[11pt,draft]{article}

\begin{document}

\subsection*{Frequency and universal approaches to randomness of finite
sequences}

 Kolmogorov in~\cite{kolm} formalized von Mises's
frequency approach to randomness
of finite sequences. A sequence is called random if the frequency of
ones is almost the same in all subsequences chosen by simple rules of
choice. More formally, a sequence of length $L$ is called
$(n,\epsilon,p)$-\emph{random} with respect to the set of
rules $\mathcal R_L$ if the difference between the frequency of ones
and $p$ is $<\epsilon$ in any subsequence of length $>n$ chosen by
a rule belonging to $\mathcal R_L$. Kolmogorov showed that
\begin{enumerate}
\item
for any $L$, $\epsilon>0$, $p$, and
$n>O(\epsilon^{-4})$
if cardinality of $\mathcal R_L$ is
$<\mathrm e^{2n\epsilon^2(1-\epsilon)}$, then there exists
$(n,\epsilon,p)$-random sequence;
\item
there exists $\mathcal R_L$
of cardinality $<2^{4n\epsilon(1+3\epsilon)}$ such that there
are no $(n,\epsilon,0.5)$-random sequences.
\end{enumerate}
We remove the difference between these bounds (this problem was stated
in~\cite{kolm}):
there exists a set $\mathcal R_L$ of cardinality
$<\mathrm e^{\frac{2n\epsilon^2(1+\epsilon)}{1-n/L}}$
such that any sequence is non-random with respect to $\mathcal R_L$.

Another problem under consideration is a correlation between
universal (belonging to small simple set) and frequency
randomness.
\emph{A specific deficiency} of a set $S\subseteq\{0,1\}^L$ is
$(1-\log_2 |S|/L)$. A set of great deficiency is small (and consists of
``universally non-random'' sequences).
A rule $r$ is \emph{normal} if $r$ chooses subsequences of the same
length from all sequences of length $L$; a set is \emph{regular} if
for some $\epsilon$ and a normal rule $r$ it consists of all sequences
such that $r$ chooses subsequences with deviation of
frequency from $1/2$ greater than $\epsilon$ (elements of regular sets
are ``frequency non-random''). We prove that if $\delta$
is small enough, then
every set of specific deficiency $>\delta$ can be covered by
$L(1/\delta)^{1/\delta}$ regular sets of specific deficiency
$>\frac{\delta}{\ln(1/\delta)}
 (1-\frac{2\ln\ln(1/\delta)}{\ln(1/\delta)})$.
This bound for possible deficiency of covering regular sets is sharp,
since there exists a set of specific deficiency $>\delta$ that cannot
be covered by $2^{L\delta^5}$ regular sets of specific deficiency
$>\frac{\delta}{\ln(1/\delta)}
 (2+\frac{\ln\ln(1/\delta)}{\ln(1/\delta)})$.

Also we formulate and prove algorithmic analogues of all previous
results in terms of Kolmogorov complexity.

\begin{thebibliography}{9}
\bibitem{kolm} A.~N.~Kolmogorov. On tables of random numbers.
Sankhy\~a: The Indian Journal of Statistics, Series~A, vol.~25, part~4
(1963). (Reprinted in Theoretical Computer Science,
207(1998), pp. 387--395).
\end{thebibliography}

\end{document}