\input style
ВЫБИРАЛ БЫ $j\hbox{-Е}$~ВЫЧИСЛИМОЕ ПРАВИЛО ПОСТРОЕНИЯ 
ПОДПОСЛЕДОВАТЕЛЬНОСТИ~$\cR_j$, НЕ МОЖЕТ СУЩЕСТВОВАТЬ; ЭТО СЛЕДУЕТ ИЗ 
ТОГО, ЧТО НЕ МОЖЕТ СУЩЕСТВОВАТЬ ЭФФЕКТИВНЫЙ АЛГОРИТМ, КОТОРЫЙ ОПРЕДЕЛЯЛ 
БЫ, СОСТОИТ ЛИ ДАННЫЙ ВЫЧИСЛИТЕЛЬНЫЙ МЕТОД ИЗ КОНЕЧНОГО ЧИСЛА ШАГОВ. (мЫ 
ВЕРНЕМСЯ К ЭТОМУ ВОПРОСУ В ГЛ.~11.) оДНАКО ВАЖНЫЕ БОЛЬШИЕ КЛАССЫ 
АЛГОРИТМОВ \emph{МОГУТ} БЫТЬ СИСТЕМАТИЧЕСКИ ПЕРЕЧИСЛЕНЫ. нАПРИМЕР, ИЗ 
ПОСТРОЕНИЯ АЛГОРИТМА~W ВИДНО, ЧТО С ПОМОЩЬЮ ЭФФЕКТИВНОГО АЛГОРИТМА МОЖНО 
ПОСТРОИТЬ ПОСЛЕДОВАТЕЛЬНОСТЬ, УДОВЛЕТВОРЯЮЩУЮ ОПРЕДЕЛЕНИЮ~R5, ЕСЛИ МЫ 
ОГРАНИЧИМСЯ "ПРИМИТИВНО РЕКУРСИВНЫМИ" ПРАВИЛАМИ ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ.

еСЛИ ВИДОИЗМЕНИТЬ ШАГ~W6 АЛГОРИТМА~W ТАК, ЧТОБЫ ТАМ ПРОИСХОДИЛА 
УСТАНОВКА~$U_n\asg V_{k+t}$ (А НЕ~$V_k$), ГДЕ~$t$---ЛЮБОЕ НЕОТРИЦАТЕЛЬНОЕ 
ЦЕЛОЕ ЧИСЛО, ЗАВИСЯЩЕЕ ОТ~$a_1$,~\dots, $a_r$, ТО МОЖНО ПОКАЗАТЬ, ЧТО 
СУЩЕСТВУЕТ \emph{НЕСЧЕТНОЕ} МНОЖЕСТВО ПОСЛЕДОВАТЕЛЬНОСТЕЙ НА~$[0, 1)$, 
УДОВЛЕТВОРЯЮЩИХ ОПРЕДЕЛЕНИЮ~R5.

дРУГОЙ, МЕНЕЕ ПРЯМОЙ, ПУТЬ ДОКАЗАТЕЛЬСТВА СУЩЕСТВОВАНИЯ НЕСЧЕТНОГО 
МНОЖЕСТВА СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, ОСНОВАННЫЙ НА ТЕОРИИ МЕРЫ, ДЛЯ 
ПОСЛЕДОВАТЕЛЬНОСТЕЙ, УДОВЛЕТВОРЯЮЩИХ ДАЖЕ СИЛЬНОМУ ОПРЕДЕЛЕНИЮ~R6, ДАЕТ

\proclaim тЕОРЕМА~M. пУСТЬ ДЕЙСТВИТЕЛЬНОЕ ЧИСЛО~$x$, $0\le x < 1$, 
ПОСТАВЛЕНО В СООТВЕТСТВИЕ ДВОИЧНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ~$\<X_n>$ ТАКИМ 
ОБРАЗОМ, ЧТО ДВОИЧНОЕ ПРЕДСТАВЛЕНИЕ~$x$ ЕСТЬ~$0.X_0X_1\ldots\,$. иМЕЯ В 
ВИДУ ЭТО СООТВЕТСТВИЕ, МОЖНО УТВЕРЖДАТЬ, ЧТО ПОЧТИ ВСЕ $x$~СООТВЕТСТВУЮТ 
ДВОИЧНЫМ ПОСЛЕДОВАТЕЛЬНОСТЯМ, КОТОРЫЕ ЯВЛЯЮТСЯ СЛУЧАЙНЫМИ В СМЫСЛЕ 
ОПРЕДЕЛЕНИЯ~R6. (дРУГИМИ СЛОВАМИ, МНОЖЕСТВО ТЕХ ДЕЙСТВИТЕЛЬНЫХ~$x$, 
КОТОРЫЕ СООТВЕТСТВУЮТ НЕСЛУЧАЙНЫМ В СМЫСЛЕ ОПРЕДЕЛЕНИЯ~R6 
ПОСЛЕДОВАТЕЛЬНОСТЯМ, ИМЕЕТ МЕРУ НУЛЬ.)

\proof пУСТЬ~$\cS$---ЭФФЕКТИВНЫЙ АЛГОРИТМ, ОПРЕДЕЛЯЮЩИЙ БЕСКОНЕЧНУЮ 
ПОСЛЕДОВАТЕЛЬНОСТЬ РАЗЛИЧНЫХ НЕОТРИЦАТЕЛЬНЫХ ЦЕЛЫХ ЧИСЕЛ~$\<s_n>$, ТАКОЙ,
 ЧТО $s_n$~ЗАВИСИТ ТОЛЬКО ОТ~$n$ И~$X_{s_k}$, ГДЕ~$0\le k < n$, 
И~$\cR$---ВЫЧИСЛИМОЕ ПРАВИЛО ПОСТРОЕНИЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ. тОГДА ИЗ 
ЛЮБОЙ ДВОИЧНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ~$\<X_n>$ МОЖНО ПОЛУЧИТЬ 
ПОДПОСЛЕДОВАТЕЛЬНОСТЬ~$\<X_{s_n}>\cR$, И ОПРЕДЕЛЕНИЕ~R6 УТВЕРЖДАЕТ, ЧТО 
ЭТА ПОДПОСЛЕДОВАТЕЛЬНОСТЬ ДОЛЖНА БЫТЬ ИЛИ КОНЕЧНОЙ, ИЛИ 
$1\hbox{-РАСПРЕДЕЛЕННОЙ}$. дОСТАТОЧНО ДОКАЗАТЬ, ЧТО \emph{ПРИ 
ЗАДАННЫХ~$\cR$ И~$\cS$ МНОЖЕСТВО~$N(\cR, \cS)$ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ~$x$, 
СООТВЕТСТВУЮЩИХ~$\<X_n>$ И ТАКИХ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<X_{s_n}>\cR$ 
БЕСКОНЕЧНА И НЕ ЯВЛЯЕТСЯ $1\hbox{-РАСПРЕДЕЛЕННОЙ}$, ИМЕЕТ МЕРУ НУЛЬ.} в 
САМОМ ДЕЛЕ, $x$~ИМЕЕТ НЕСЛУЧАЙНОЕ ДВОИЧНОЕ ПРЕДСТАВЛЕНИЕ В ТОМ И ТОЛЬКО 
ТОМ СЛУЧАЕ, КОГДА $x$~ПРИНАДЛЕЖИТ ОБ®ЕДИНЕНИЮ~$\cup N(\cR, \cS)$, 
ПРОСУММИРОВАННОМУ ПО СЧЕТНОМУ МНОЖЕСТВУ~$\cR$ И~$\cS$.
%% 182

пУСТЬ, ТАКИМ ОБРАЗОМ, $\cR$ И~$\cS$ ЗАДАНЫ. рАССМОТРИМ 
МНОЖЕСТВО~$T(a_1a_2\ldots{}a_r)$, КОТОРОЕ ОПРЕДЕЛЯЕТСЯ ДЛЯ ЛЮБЫХ ДВОИЧНЫХ 
ЧИСЕЛ~$a_1a_2\ldots{}a_r$ КАК МНОЖЕСТВО ВСЕХ ТЕХ~$x$, 
СООТВЕТСТВУЮЩИХ~$\<X_n>$, ЧТО~$\<X_{s_n}>\cR$ ИМЕЕТ ${}\ge r$~ЭЛЕМЕНТОВ, 
ПРИЧЕМ ПЕРВЫЕ $r$~ЭЛЕМЕНТОВ РАВНЫ СООТВЕТСТВЕННО~$a_1$, $a_2$,~\dots, 
$a_r$. сНАЧАЛА МЫ ДОКАЖЕМ, ЧТО
\EQ[32]{
\hbox{МЕРА МНОЖЕСТВА~}T(a_1a_2\ldots{}a_r)\le 2^{-r}.
}
зАМЕТИМ ВНАЧАЛЕ, ЧТО МНОЖЕСТВО~$T(a_1a_2\ldots{}a_r)$  ИЗМЕРИМО:
КАЖДЫЙ ЭЛЕМЕНТ ИЗ~$T(a_1a_2\ldots{}a_r)$ ЕСТЬ ДЕЙСТВИТЕЛЬНОЕ 
ЧИСЛО~$x=0.X_0X_1\ldots$, ДЛЯ КОТОРОГО СУЩЕСТВУЕТ ЦЕЛОЕ ЧИСЛО~$m$, ТАКОЕ,
 ЧТО АЛГОРИТМ~$\cS$ ОПРЕДЕЛЯЕТ РАЗЛИЧНЫЕ ЗНАЧЕНИЯ~$s_0$, $s_1$,~\dots, 
$s_m$, И ПРАВИЛО~$\cS$ ОПРЕДЕЛЯЕТ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ~$X_{s_0}$, 
$X_{s_1}$,~\dots, $X_{s_m}$, ТАКУЮ, ЧТО $X_{s_m}$~ЕСТЬ 
$r\hbox{-Й}$~ЭЛЕМЕНТ ЭТОЙ ПОСЛЕДОВАТЕЛЬНОСТИ. мНОЖЕСТВО ВСЕХ 
ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ~$y=0.Y_0Y_1\ldots$, ТАКИХ, ЧТО~$Y_{s_k}=X_{s_k}$ 
ПРИ~$0\le k \le m$, ТАКЖЕ ПРИНАДЛЕЖИТ МНОЖЕСТВУ~$T(a_1a_2\ldots{}a_r)$ И 
ЯВЛЯЕТСЯ ИЗМЕРИМЫМ МНОЖЕСТВОМ, СОСТОЯЩИМ ИЗ КОНЕЧНОГО ОБ®ЕДИНЕНИЯ ДВОИЧНЫХ 
ПОДЫНТЕРВАЛОВ~$I_{b_1\ldots{}b_t}$. пОСКОЛЬКУ МНОЖЕСТВО ТАКИХ ИНТЕРВАЛОВ 
СЧЕТНО, $T(a_1a_2\ldots{}a_r)$ ЯВЛЯЕТСЯ СЧЕТНЫМ ОБ®ЕДИНЕНИЕМ ДВОИЧНЫХ 
ИНТЕРВАЛОВ, И, СЛЕДОВАТЕЛЬНО, ОНО ИЗМЕРИМО. бОЛЕЕ ТОГО, ИЗ ЭТОГО 
РАССУЖДЕНИЯ СЛЕДУЕТ, ЧТО МЕРА~$T(a_1\ldots{}a_{r-1}0)$ РАВНА 
МЕРЕ~$T(a_1\ldots{}a_{r-1}1)$, ПОСКОЛЬКУ ПОСЛЕДНЕЕ МНОЖЕСТВО ЕСТЬ 
ОБ®ЕДИНЕНИЕ ДВОИЧНЫХ ИНТЕРВАЛОВ, ПОЛУЧЕННЫХ ИЗ ПРЕДШЕСТВУЮЩЕГО ПРИ 
ДОПОЛНИТЕЛЬНОМ ТРЕБОВАНИИ, ЧТО~$Y_{s_k}=X_{s_k}$ ДЛЯ~$0\le k < m$ 
И~$Y_{s_m}\ne X_{s_m}$ . пОСКОЛЬКУ
\EQ{
 T(a_1\ldots a_{r-1}0)\cup T(a_1\ldots a_{r-1}1)\subseteq 
T(a_1\ldots{}a_{r-1}),
}
МЕРА МНОЖЕСТВА~$T(a_1a_2\ldots{}a_r)$ НЕ ПРЕВОСХОДИТ ПОЛОВИНЫ 
МЕРЫ МНОЖЕСТВА~$T(a_1\ldots{}a_{r-1})$. нЕРАВЕНСТВО~\eqref[32] ПОЛУЧАЕТСЯ 
ИНДУКЦИЕЙ ПО~$r$.

тЕПЕРЬ, КОГДА СПРАВЕДЛИВОСТЬ НЕРАВЕНСТВА~\eqref[32] УСТАНОВЛЕНА, ОСТАЛОСЬ 
ДОКАЗАТЬ В ОСНОВНОМ СЛЕДУЮЩЕЕ: ДВОИЧНЫЕ ПРЕДСТАВЛЕНИЯ ПОЧТИ ВСЕХ 
ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ РАВНОМЕРНО РАСПРЕДЕЛЕНЫ. дАЛЕЕ В НЕСКОЛЬКИХ АБЗАЦАХ, 
ГДЕ ИЛЛЮСТРИРУЕТСЯ ТИПИЧНАЯ В МАТЕМАТИЧЕСКОМ АНАЛИЗЕ ТЕХНИКА ПОЛУЧЕНИЯ 
ОЦЕНОК, ПРЕДСТАВЛЕНО ДОВОЛЬНО ДЛИННОЕ, НО НЕ ТРУДНОЕ ДОКАЗАТЕЛЬСТВО ЭТОГО ФАКТА.

пУСТЬ~$0<\varepsilon<1$ И~$B(r, \varepsilon)$ ЕСТЬ~$\bigcup 
T(a_1\ldots{}a_r)$, ГДЕ ОБ®ЕДИНЕНИЕ БЕРЕТСЯ ПО ВСЕМ ДВОИЧНЫМ 
ЧИСЛАМ~$a_1\ldots{}a_r$, ТАКИМ, ЧТО КОЛИЧЕСТВО~$\nu(r)$ НУЛЕЙ 
СРЕДИ~$a_1$,~\dots, $a_r$ УДОВЛЕТВОРЯЕТ НЕРАВЕНСТВУ
\EQ{
 \abs{\nu(r)-{1\over2}r}\ge 1+\varepsilon r.
}
кОЛИЧЕСТВО ТАКИХ ДВОИЧНЫХ ЧИСЕЛ РАВНО~$C(r, \varepsilon)=\sum \perm{r}{k}$,
 ГДЕ СУММИРОВАНИЕ ВЕДЕТСЯ ПО ЗНАЧЕНИЯМ~$k$, ТАКИМ, 
ЧТО~$\abs{k-{1\over2}r}\ge 1+\varepsilon r$. %% 183
пУСТЬ~$r=2t$ ЕСТЬ ЦЕЛОЕ ЧЕТНОЕ ЧИСЛО. мЫ МОЖЕМ ДАТЬ ГРУБУЮ ОЦЕНКУ 
ВЕЛИЧИНЫ~$\sum\perm{r}{k}$. еСЛИ~$k>0$, ТО
\EQ{
\eqalign{
\perm{2t}{t+k}&=\perm{2t}{t}{t\over t+1}{t-1\over t+2}\ldots {t-k+1\over t+k}
<\perm{2t}{t}{t\over t}{t-1\over t}\ldots{t-k+1\over t}\le\cr
&\le \perm{2t}{t}e^{-0/t}e^{-1/t}\ldots e^{-(k-1)/t}=\perm{2t}{t}e^{-k(k-1)/r}.\cr
}
}
тАКИМ ОБРАЗОМ,
\EQ{
\eqalign{
C(r, \varepsilon)=2\sum_{k\ge 1+\varepsilon r} \perm{2t}{t+k}
&\le 2\perm{2t}{t}\sum_{k\ge1+\varepsilon r}e^{-k(k-1)/r}\le\cr
&\le 2\perm{2t}{t}t e^{-(1+\varepsilon r)\varepsilon)} < r\perm{r}{t}e^{-\varepsilon^2r}.\cr
}
}
аНАЛОГИЧНО, ДЛЯ~$r=2t+1$ ПОЛУЧАЕМ
\EQ{
C(r, \varepsilon)<r\perm{r}{t}e^{-\varepsilon^2r}.
}
иСПОЛЬЗУЯ ТЕПЕРЬ~\eqref[32], ВЫВОДИМ
\EQ[33]{
\hbox{МЕРА МНОЖЕСТВА } B(r, \varepsilon) \le 2^{-r} C(r, \varepsilon)< 
re^{-\varepsilon^2 r}.
}

дАЛЕЕ ОПРЕДЕЛИМ МНОЖЕСТВО
\EQ{
B^*(r, \varepsilon)=B(r, \varepsilon)\cup B(r+1,\varepsilon) \cup B(r+2,
\varepsilon)\cup \ldots \, .
}
мЕРА~$B^*(r, \varepsilon)$ НЕ ПРЕВОСХОДИТ~$\sum_{k\ge r} 
ke^{-\varepsilon^2k}$. пОСЛЕДНЯЯ ВЕЛИЧИНА ЯВЛЯЕТСЯ ОСТАТКОМ СХОДЯЩЕГОСЯ 
РЯДА, ПОЭТОМУ
\EQ[34]{
\lim_{r\to\infty} (\hbox{МЕРЫ } B^*(r, \varepsilon))=0.
}

еСЛИ ТЕПЕРЬ~$x$---ДЕЙСТВИТЕЛЬНОЕ ЧИСЛО, ТАКОЕ, ЧТО ЕГО ДВОИЧНОЕ 
ПРЕДСТАВЛЕНИЕ~$0.X_0X_1\ldots$ ПРИВОДИТ К БЕСКОНЕЧНОЙ 
ПОСЛЕДОВАТЕЛЬНОСТИ~$\<X_{s_n}>\cR$, КОТОРАЯ НЕ ЯВЛЯЕТСЯ 
$1\hbox{-РАСПРЕДЕЛЕННОЙ}$, a $\nu(r)$~ОБОЗНАЧАЕТ ЧИСЛО НУЛЕЙ В ПЕРВЫХ~$r$  
ЕЕ ЭЛЕМЕНТАХ, ТО
\EQ{
 \abs{\nu(r)/r-{1\over 2}}\ge 2\varepsilon
}
ДЛЯ НЕКОТОРОГО~$\varepsilon>0$ И БЕСКОНЕЧНО МНОГИХ~$r$. эТО ЗНАЧИТ, 
ЧТО~$x$ ПРИ ВСЕХ~$r$ СОДЕРЖИТСЯ В~$B^*(r, \varepsilon)$. тАКИМ ОБРАЗОМ, 
ОКОНЧАТЕЛЬНО НАХОДИМ, ЧТО
\EQ{
 N(\cR, \cS)=\bigcup_{t\ge 2} \bigcap_{r\ge1} B^*(r, 1/t).
}
иЗ ФОРМУЛЫ~\eqref[34] СЛЕДУЕТ, ЧТО~$\bigcap_{r\ge1} B^*(r, 1/t)$ ПРИ 
ВСЕХ~$t$  ИМЕЕТ МЕРУ НУЛЬ; СЛЕДОВАТЕЛЬНО, $N(\cR, \cS)$ ТАКЖЕ ИМЕЕТ МЕРУ НУЛЬ.
\proofend

%% 184

иЗ СУЩЕСТВОВАНИЯ \emph{ДВОИЧНЫХ} ПОСЛЕДОВАТЕЛЬНОСТЕЙ, УДОВЛЕТВОРЯЮЩИХ 
ОПРЕДЕЛЕНИЮ~R6, СЛЕДУЕТ СУЩЕСТВОВАНИЕ ПОСЛЕДОВАТЕЛЬНОСТЕЙ НА~$[0, 1)$, 
СЛУЧАЙНЫХ В СМЫСЛЕ ЭТОГО ОПРЕДЕЛЕНИЯ. сМ.\ ПО ЭТОМУ ПОВОДУ УПР.~36. тЕМ 
САМЫМ МЫ УСТАНОВИЛИ СОСТОЯТЕЛЬНОСТЬ ОПРЕДЕЛЕНИЯ~R6.

\section{е.~сЛУЧАЙНЫЕ КОНЕЧНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ}. вЫШЕ ПРИВОДИЛОСЬ 
СООБРАЖЕНИЕ О ТОМ, ЧТО ПОНЯТИЕ СЛУЧАЙНОСТИ ДЛЯ КОНЕЧНЫХ 
ПОСЛЕДОВАТЕЛЬНОСТЕЙ ВВЕСТИ НЕВОЗМОЖНО, ПОСКОЛЬКУ ВСЯКАЯ ЗАДАННАЯ 
КОНЕЧНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ НИЧУТЬ НЕ ХУЖЕ ЛЮБОЙ ДРУГОЙ. нЕСМОТРЯ НА ЭТО, 
ПОЧТИ КАЖДЫЙ СОГЛАСИТСЯ С ТЕМ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ~$011101001$ "БОЛЕЕ 
СЛУЧАЙНА", ЧЕМ ПОСЛЕДОВАТЕЛЬНОСТЬ~$101010101$, А ПОСЛЕДНЯЯ "БОЛЕЕ 
СЛУЧАЙНА", ЧЕМ~$000000000$. хОТЯ СПРАВЕДЛИВО УТВЕРЖДЕНИЕ, ЧТО ИСТИННО 
СЛУЧАЙНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ ЛОКАЛЬНО МОЖЕТ БЫТЬ НЕСЛУЧАЙНОЙ, МЫ БЫ 
ПРЕДПОЧЛИ ОБНАРУЖИТЬ ТАКУЮ НЕСЛУЧАЙНОСТЬ ТОЛЬКО В ДЛИННОЙ, А НЕ В 
КОРОТКОЙ КОНЕЧНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ.

сУЩЕСТВУЕТ НЕСКОЛЬКО ПОДХОДОВ К ОПРЕДЕЛЕНИЮ СЛУЧАЙНОСТИ КОНЕЧНОЙ 
ПОСЛЕДОВАТЕЛЬНОСТИ, И МЫ НАМЕТИМ ЛИШЬ НЕСКОЛЬКО ОТНОСЯЩИХСЯ СЮДА ИДЕЙ. 
бУДЕМ РАССМАТРИВАТЬ ТОЛЬКО $b\hbox{-ИЧНЫЕ}$ ПОСЛЕДОВАТЕЛЬНОСТИ.

еСЛИ ЗАДАНА $b\hbox{-ИЧНАЯ}$ ПОСЛЕДОВАТЕЛЬНОСТЬ~$X_1$, $X_2$,~\dots, $X_N$,
 ТО МОЖНО СКАЗАТЬ, ЧТО
\EQ{
\Pr(S(n))\approx p, \rem{ЕСЛИ~$\abs{\nu(N)/N-p}\le 1/\sqrt{N}$,}
}
ГДЕ~$\nu(n)$---ВЕЛИЧИНА, ВВЕДЕННАЯ В ОПРЕДЕЛЕНИИ~A В НАЧАЛЕ НАСТОЯЩЕГО 
ПАРАГРАФА. пРИВЕДЕННУЮ ВЫШЕ ПОСЛЕДОВАТЕЛЬНОСТЬ МОЖНО НАЗВАТЬ 
"$k\hbox{-РАСПРЕДЕЛЕННОЙ}$", ЕСЛИ
\EQ{
\Pr(X_nX_{n+1}\ldots{}X_{n+k-1}=x_1x_2\ldots x_k)\approx 1/b^k
}
ДЛЯ ВСЕХ $b\hbox{-ИЧНЫХ}$ ЧИСЕЛ~$x_1 x_2 \ldots x_k$. (сР.\ С 
ОПРЕДЕЛЕНИЕМ~D. к СОЖАЛЕНИЮ, ПО ЭТОМУ НОВОМУ ОПРЕДЕЛЕНИЮ 
ПОСЛЕДОВАТЕЛЬНОСТЬ МОЖЕТ БЫТЬ $k\hbox{-РАСПРЕДЕЛЕНА}$, ДАЖЕ ЕСЛИ ОНА НЕ 
ЯВЛЯЕТСЯ $(k-1)\hbox{-РАСПРЕДЕЛЕННОЙ}$.)

тЕПЕРЬ МОЖНО ВВЕСТИ ПОНЯТИЕ СЛУЧАЙНОСТИ АНАЛОГИЧНО ТОМУ, КАК ЭТО БЫЛО 
СДЕЛАНО В ОПРЕДЕЛЕНИИ~R1.

\proclaim оПРЕДЕЛЕНИЕ~Q1. $b\hbox{-ИЧНАЯ}$ ПОСЛЕДОВАТЕЛЬНОСТЬ ДЛИНЫ~$N$ 
НАЗЫВАЕТСЯ "СЛУЧАЙНОЙ", ЕСЛИ ОНА $k\hbox{-РАСПРЕДЕЛЕНА}$ (В УКАЗАННОМ ВЫШЕ 
СМЫСЛЕ) ПРИ ВСЕХ ПОЛОЖИТЕЛЬНЫХ ЦЕЛЫХ~$k$, ТАКИХ, ЧТО~$k\le \log_b N$.

в СООТВЕТСТВИИ С ЭТИМ ОПРЕДЕЛЕНИЕМ, ИМЕЮТСЯ, НАПРИМЕР 170~НЕСЛУЧАЙНЫХ 
ДВОИЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДЛИНЫ~11:
\EQ{
\matrix{
00000001111 & 10000000111 & 11000000011 & 11100000001\cr
00000001110 & 10000000110 & 11000000010 & 11100000000\cr
00000001101 & 10000000101 & 11000000001 & 10100000001\cr
00000001011 & 10000000011 & 01000000011 & 01100000001\cr
00000000111\cr
}
}
%% 185
ПЛЮС~$01010101010$ И ВСЕ ПОСЛЕДОВАТЕЛЬНОСТИ, В КОТОРЫХ ИМЕЕТСЯ НЕ МЕНЕЕ 
ДЕВЯТИ НУЛЕЙ, ПЛЮС ВСЕ ПОСЛЕДОВАТЕЛЬНОСТИ, ПОЛУЧЕННЫЕ ИЗ ПРЕДШЕСТВУЮЩИХ 
ВЗАИМНОЙ ЗАМЕНОЙ НУЛЕЙ И ЕДИНИЦ.

пОДОБНЫМ ЖЕ ОБРАЗОМ МОЖНО ВВЕСТИ ОПРЕДЕЛЕНИЕ, АНАЛОГИЧНОЕ ОПРЕДЕЛЕНИЮ~R6, 
ДЛЯ КОНЕЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ. пУСТЬ~$A$ ЕСТЬ МНОЖЕСТВО АЛГОРИТМОВ, 
КАЖДЫЙ ИЗ КОТОРЫХ ПРЕДСТАВЛЯЕТ СОБОЙ ПРОЦЕДУРУ ПОЛУЧЕНИЯ 
ПОДПОСЛЕДОВАТЕЛЬНОСТИ~$\<X_{s_n}>\cR$, АНАЛОГИЧНО ТОМУ, КАК ЭТО СДЕЛАНО 
ПРИ ДОКАЗАТЕЛЬСТВЕ ТЕОРЕМЫ~M.

\proclaim оПРЕДЕЛЕНИЕ~Q2. $b\hbox{-ИЧНАЯ}$ ПОСЛЕДОВАТЕЛЬНОСТЬ~$X_1$,  
$X_2$,~\dots, $X_N$ НАЗЫВАЕТСЯ $(n, \varepsilon)\hbox{-СЛУЧАЙНОЙ}$ ПО 
ОТНОШЕНИЮ К МНОЖЕСТВУ~$A$ АЛГОРИТМОВ, ЕСЛИ ДЛЯ КАЖДОЙ 
ПОДПОСЛЕДОВАТЕЛЬНОСТИ~$X_{t_1}$, $X_{t_2}$,~\dots, $X_{t_m}$, 
ОПРЕДЕЛЕННОЙ С ПОМОЩЬЮ АЛГОРИТМА, ПРИНАДЛЕЖАЩЕГО МНОЖЕСТВУ~$A$,
СПРАВЕДЛИВО ЛИБО НЕРАВЕНСТВО~$m<n$, ЛИБО НЕРАВЕНСТВО
\EQ{
 \abs{{1\over m}\nu_a (X_{t_1}, \ldots, X_{t_m})-{1\over b}}\le \varepsilon
 \rem{ПРИ~$0\le a < b$.}
}

\noindent зДЕСЬ~$\nu_a(x_1, \ldots, x_m)$ ОБОЗНАЧАЕТ ЧИСЛО ПОЯВЛЕНИЙ~$a$ В 
ПОСЛЕДОВАТЕЛЬНОСТИ~$x_1$,~\dots, $x_m$.

(дРУГИМИ СЛОВАМИ, КАЖДАЯ ДОСТАТОЧНО ДЛИННАЯ ПОДПОСЛЕДОВАТЕЛЬНОСТЬ, 
ОПРЕДЕЛЕННАЯ С ПОМОЩЬЮ АЛГОРИТМА, ПРИНАДЛЕЖАЩЕГО МНОЖЕСТВУ~$A$, ДОЛЖНА 
БЫТЬ ПРИБЛИЖЕННО РАВНОМЕРНО РАСПРЕДЕЛЕНА.) оСНОВНАЯ ИДЕЯ СОСТОИТ В ТОМ, 
ЧТОБЫ СОСТАВИТЬ МНОЖЕСТВО~$A$ ИЗ "ПРОСТЫХ" АЛГОРИТМОВ, ЧИСЛО ЖЕ ИХ (И 
СЛОЖНОСТЬ) МОЖЕТ ВОЗРАСТАТЬ С РОСТОМ~$N$.

в КАЧЕСТВЕ ПРИМЕРА РАССМОТРИМ ДВОИЧНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ, И 
ПУСТЬ$A$~СОСТОИТ ИЗ ЧЕТЫРЕХ АЛГОРИТМОВ.
\medskip
\item{(a)}~вЗЯТЬ ВСЮ ПОСЛЕДОВАТЕЛЬНОСТЬ.

\item{(b)}~вЗЯТЬ ЧЛЕНЫ ПОСЛЕДОВАТЕЛЬНОСТИ ЧЕРЕЗ ОДИН, НАЧИНАЯ С ПЕРВОГО.

\item{(c)}~вЗЯТЬ ЧЛЕНЫ ПОСЛЕДОВАТЕЛЬНОСТИ, СТОЯЩИЕ ПОСЛЕ НУЛЯ.

\item{(d)}~вЗЯТЬ ЧЛЕНЫ ПОСЛЕДОВАТЕЛЬНОСТИ, СТОЯЩИЕ ПОСЛЕ ЕДИНИЦЫ.

\medskip

тАК, ПОСЛЕДОВАТЕЛЬНОСТЬ~$X_1$,~\dots, $X_8$ ЯВЛЯЕТСЯ 
$(4, 1/8)\hbox{-СЛУЧАЙНОЙ}$, ЕСЛИ
\descrtable{
ПО АЛГОРИТМУ~(a):& 
  $\abs{{1\over8}(X_1+\cdots+X_8)-{1\over2}}\le{1\over8}$, 
  Т.~Е.\ ЕСЛИ В НЕЙ ИМЕЕТСЯ 3,4 ИЛИ 5 ЕДИНИЦ;\cr
ПО АЛГОРИТМУ~(b): & 
  $\abs{{1\over 4}(X_1+X_3+X_5+X_7)-{1\over 2}}\le {1\over 8}$,  
  Т.~Е.\ ЕСЛИ В НЕЙ ИМЕЮТСЯ ДВЕ ЕДИНИЦЫ НА МЕСТАХ С НЕЧЕТНЫМИ НОМЕРАМИ;\cr
ПО АЛГОРИТМУ~(c): & 
  НУЖНО РАССМОТРЕТЬ ТРИ ВОЗМОЖНОСТИ В ЗАВИСИМОСТИ ОТ ТОГО, СКОЛЬКО НУЛЕЙ СТОЯТ 
  НА МЕСТАХ~$X_1$,~\dots, $X_7$: ЕСЛИ ТАМ СТОЯТ~2 ИЛИ 3~НУЛЯ,
%% 186
  ТО ПРОВЕРЯТЬ НИЧЕГО НЕ НУЖНО (ПОСКОЛЬКУ~$n=4$), ЕСЛИ ТАМ 4~НУЛЯ, 
  ЗА НИМИ ДОЛЖНЫ СТОЯТЬ ДВА НУЛЯ И ДВЕ ЕДИНИЦЫ, И, НАКОНЕЦ, ЕСЛИ ТАМ 5~НУЛЕЙ,
  ЗА НИМИ ДОЛЖНЫ СТОЯТЬ ДВА ИЛИ ТРИ НУЛЯ.\cr
ПО АЛГОРИТМУ~(d):& 
  УСЛОВИЯ, АНАЛОГИЧНЫЕ ПОЛУЧЕННЫМ ПО АЛГОРИТМУ~(c).\cr
}

иТАК, ТОЛЬКО СЛЕДУЮЩИЕ ДВОИЧНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ ДЛИНЫ~$8$ ЯВЛЯЮТСЯ ПО 
ЭТИМ ПРАВИЛАМ $\left(4, {1\over 8}\right)\hbox{-СЛУЧАЙНЫМИ}$:
\EQ{
 \matrix{
  00001011 & 00101001 & 01001110 & 01101000\cr
  00011010 & 00101100 & 01011011 & 01101100\cr
  00011011 & 00110010 & 01011110 & 01101101\cr
  00100011 & 00110011 & 01100010 & 01110010\cr
  00100110 & 00110110 & 01100011 & 01110110\cr
  00100111 & 00111001 & 01100110\cr
 }
}
ПЛЮС ПОСЛЕДОВАТЕЛЬНОСТИ, ПОЛУЧЕННЫЕ ИЗ НИХ ВЗАИМНОЙ ЗАМЕНОЙ~$0$ И~$1$.

яСНО, ЧТО МНОЖЕСТВО АЛГОРИТМОВ МОЖНО ВЗЯТЬ НАСТОЛЬКО БОЛЬШИМ, ЧТО НИ ОДНА 
ПОСЛЕДОВАТЕЛЬНОСТЬ НЕ БУДЕТ УДОВЛЕТВОРЯТЬ ОПРЕДЕЛЕНИЮ В СЛУЧАЕ, КОГДА~$n$ 
И~$\varepsilon$ РАЗУМНЫМ ОБРАЗОМ МАЛЫ. а.~н.~кОЛМОГОРОВ ДОКАЗАЛ, ЧТО~$(n, 
e)$-СЛУЧАЙНАЯ ДВОИЧНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ \emph{ВСЕГДА СУЩЕСТВУЕТ} ПРИ 
ЛЮБОМ ЗАДАННОМ~$N$, ЕСЛИ ЧИСЛО АЛГОРИТМОВ В~$A$ НЕ ПРЕВОСХОДИТ
\EQ[35]{
 {1\over 2} e^{2n\varepsilon^2(1-\varepsilon)}.
}
эТОТ РЕЗУЛЬТАТ НЕДОСТАТОЧНО СИЛЕН ДЛЯ ТОГО, ЧТОБЫ ПОКАЗАТЬ, ЧТО СУЩЕСТВУЮТ 
ПОСЛЕДОВАТЕЛЬНОСТИ, УДОВЛЕТВОРЯЮЩИЕ ОПРЕДЕЛЕНИЮ~Q1, ОДНАКО ТАКИЕ 
ПОСЛЕДОВАТЕЛЬНОСТИ МОГУТ БЫТЬ ЭФФЕКТИВНО ПОСТРОЕНЫ С ПОМОЩЬЮ ПРОЦЕДУРЫ 
рИСА В УПР.~3.2.2-21.

дРУГОЙ ИНТЕРЕСНЫЙ ПОДХОД К ОПРЕДЕЛЕНИЮ СЛУЧАЙНОСТИ УКАЗАЛ п.~мАРТИН-лёФ 
({\sl Information and Control,\/} {\bf 9} (1966), 602--619). пУСТЬ ЗАДАНЫ 
КОНЕЧНАЯ $b\hbox{-ИЧНАЯ}$ ПОСЛЕДОВАТЕЛЬНОСТЬ~$X_1$,~\dots, $X_N$ И~$l(X_1,
~\ldots, X_N)$---ДЛИНА КРАТЧАЙШЕЙ ПРОГРАММЫ, КОТОРАЯ ПОЛУЧАЕТ ЭТУ 
ПОСЛЕДОВАТЕЛЬНОСТЬ НА МАШИНЕ тЬЮРИНГА. (оПРЕДЕЛЕНИЕ ПОНЯТИЯ МАШИНЫ 
тЬЮРИНГА СМ.\ В ГЛ.~11; ВМЕСТО ЭТОГО ПОНЯТИЯ МЫ МОГЛИ БЫ ИСПОЛЬЗОВАТЬ 
НЕКОТОРЫЕ КЛАССЫ ЭФФЕКТИВНЫХ АЛГОРИТМОВ НАПОДОБИЕ ОПРЕДЕЛЕННЫХ В 
УПР.~1.1-8.) тОГДА $l(X_1,~\ldots, X_N)$ СЛУЖИТ МЕРОЙ "НЕРЕГУЛЯРНОСТИ" 
ПОСЛЕДОВАТЕЛЬНОСТИ, И МЫ МОЖЕМ ОТОЖДЕСТВИТЬ ЭТО ПОНЯТИЕ СО СЛУЧАЙНОСТЬЮ. 
пОСЛЕДОВАТЕЛЬНОСТИ ДЛИНЫ~$N$, МАКСИМИЗИРУЮЩИЕ~$l(X_1,~\ldots, X_N)$, МОЖНО 
НАЗВАТЬ СЛУЧАЙНЫМИ. (с ТОЧКИ ЗРЕНИЯ ПРАКТИЧЕСКОГО ПОЛУЧЕНИЯ 
СЛУЧАЙНЫХ ЧИСЕЛ НА МАШИНЕ ЭТО ОПРЕДЕЛЕНИЕ СЛУЧАЙНОСТИ КОНЕЧНО НАИХУДШЕЕ, 
КАКОЕ ТОЛЬКО МОЖНО ВООБРАЗИТЬ!)

%% 187


в ОСНОВНЫХ ЧЕРТАХ ТАКОЕ ЖЕ ОПРЕДЕЛЕНИЕ СЛУЧАЙНОСТИ НЕЗАВИСИМО И ПОЧТИ 
ОДНОВРЕМЕННО ПРЕДЛОЖИЛ г.~чЬЯТИН ({\sl JACM,\/} {\bf 16} (1969), 145--159).
 иНТЕРЕСНО ЗАМЕТИТЬ, ЧТО, ХОТЯ ЭТО ОПРЕДЕЛЕНИЕ В ОТЛИЧИЕ ОТ ДРУГИХ НИКАК 
НЕ ИСПОЛЬЗУЕТ СВОЙСТВО РАВНОМЕРНОЙ РАСПРЕДЕЛЕННОСТИ, мАРТИН-лёФ И чЬЯТИН 
ДОКАЗАЛИ, ЧТО СЛУЧАЙНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ ЭТОГО ТИПА ТАКЖЕ ИМЕЮТ 
ОЖИДАЕМЫЕ СВОЙСТВА РАВНОМЕРНОЙ РАСПРЕДЕЛЕННОСТИ. мАРТИН-лёФ ПОКАЗАЛ, ЧТО 
ТАКИЕ ПОСЛЕДОВАТЕЛЬНОСТИ В НЕКОТОРОМ СМЫСЛЕ УДОВЛЕТВОРЯЮТ \emph{ВСЕМ} 
ВЫЧИСЛИМЫМ СТАТИСТИЧЕСКИМ ПРОВЕРКАМ СЛУЧАЙНОСТИ.

\section {F.~вЫВОДЫ, ИСТОРИЯ ВОПРОСА И БИБЛИОГРАФИЯ}. мЫ ИМЕЕМ 
ТЕПЕРЬ НЕСКОЛЬКО ОПРЕДЕЛЕНИЙ РАЗНОЙ СТЕПЕНИ СЛУЧАЙНОСТИ 
ПОСЛЕДОВАТЕЛЬНОСТИ.

бЕСКОНЕЧНЫЕ $\infty\hbox{-РАСПРЕДЕЛЕННЫЕ}$ ПОСЛЕДОВАТЕЛЬНОСТИ ОБЛАДАЮТ 
МНОГИМИ ПОЛЕЗНЫМИ СВОЙСТВАМИ, КОТОРЫМИ ДОЛЖНЫ ОБЛАДАТЬ СЛУЧАЙНЫЕ 
ПОСЛЕДОВАТЕЛЬНОСТИ, И, КРОМЕ ТОГО, ДЛЯ НИХ СУЩЕСТВУЕТ РАЗВИТАЯ ТЕОРИЯ. (в 
УПРАЖНЕНИЯХ, ПОМЕЩЕННЫХ НИЖЕ, ВВОДЯТСЯ НЕСКОЛЬКО ВАЖНЫХ СВОЙСТВ 
$\infty\hbox{-РАСПРЕДЕЛЕННЫХ}$ ПОСЛЕДОВАТЕЛЬНОСТЕЙ, КОТОРЫЕ НЕ 
УПОМИНАЛИСЬ В ТЕКСТЕ.) тАКИМ ОБРАЗОМ, ОПРЕДЕЛЕНИЕ~R1 ПОДХОДИТ ДЛЯ 
ТЕОРЕТИЧЕСКИХ ИССЛЕДОВАНИЙ СЛУЧАЙНОСТИ.

пОНЯТИЕ $\infty\hbox{-РАСПРЕДЕЛЕННОЙ}$ $b\hbox{-ИЧНОЙ}$ ПОСЛЕДОВАТЕЛЬНОСТИ 
ВВЕЛ В 1909~Г.\ эМИЛЬ бОРЕЛЬ. оН ПРЕДЛОЖИЛ ТАКЖЕ ПОНЯТИЕ $(m, 
k)\hbox{-РАСПРЕДЕЛЕННОЙ}$ ПОСЛЕДОВАТЕЛЬНОСТИ И ПОКАЗАЛ, ЧТО 
$b\hbox{-ИЧНЫЕ}$ ПРЕДСТАВЛЕНИЯ ПОЧТИ ВСЕХ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ $(m, 
k)\hbox{-РАСПРЕДЕЛЕНЫ}$ ПРИ ВСЕХ ЗНАЧЕНИЯХ~$m$ И~$k$. оН НАЗВАЛ ТАКИЕ 
ЧИСЛА \dfn{НОРМАЛЬНЫМИ} ПО ОТНОШЕНИЮ К ОСНОВАНИЮ~$b$. пРЕВОСХОДНОЕ 
ОБСУЖДЕНИЕ ЭТОГО ВОПРОСА ЕСТЬ В ЕГО ХОРОШО ИЗВЕСТНОЙ КНИГЕ "Le\c{c}ons sur 
la th\'eorie des fonctions" (2-Е ИЗД.~1914), 182--216. бОЛЕЕ 
ПОЗДНИЕ РЕЗУЛЬТАТЫ И СООТВЕТСТВУЮЩАЯ БИБЛИОГРАФИЯ, КАСАЮЩИЕСЯ НОРМАЛЬНЫХ 
ЧИСЕЛ, ЕСТЬ В СТАТЬЕ в.~шМИДТА ({\sl Pacific Journal of Math.,\/} {\bf 10} 
(1960), 661--672).

пОНЯТИЕ $\infty\hbox{-РАСПРЕДЕЛЕННОЙ}$ ПОСЛЕДОВАТЕЛЬНОСТИ 
\emph{ДЕЙСТВИТЕЛЬНЫХ} ЧИСЕЛ, КОТОРУЮ НАЗЫВАЮТ ТАКЖЕ \emph{СОВЕРШЕННО 
РАВНОМЕРНО РАСПРЕДЕЛЕННОЙ ПОСЛЕДОВАТЕЛЬНОСТЬЮ,} ВВЕЛ дЖ.~фРЭНКЛИН В СТАТЬЕ 
"Deterministic Simulation of Random Processes" [{\sl Math. Comp.,\/} {\bf 
17} (1963), 28--59)]. в ЭТОЙ ВАЖНОЙ РАБОТЕ РЕШЕНО НЕСКОЛЬКО ОЧЕНЬ 
ИНТЕРЕСНЫХ ЗАДАЧ, СВЯЗАННЫХ С $k\hbox{-РАСПРЕДЕЛЕННЫМИ}$ 
ПОСЛЕДОВАТЕЛЬНОСТЯМИ, И ИССЛЕДОВАНЫ СВОЙСТВА РАСПРЕДЕЛЕННОСТИ 
МНОГИХ СПЕЦИАЛЬНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ.

мЫ ВИДЕЛИ, ОДНАКО, ЧТО $\infty\hbox{-РАСПРЕДЕЛЕННЫЕ}$ ПОСЛЕДОВАТЕЛЬНОСТИ 
НЕ ОБЯЗАНЫ БЫТЬ НАСТОЛЬКО БЕСПОРЯДОЧНЫМИ, ЧТОБЫ ИХ НУЖНО БЫЛО СЧИТАТЬ 
СОВЕРШЕННО "СЛУЧАЙНЫМИ". вЫШЕ БЫЛИ СФОРМУЛИРОВАНЫ ТРИ ОПРЕДЕЛЕНИЯ~R4, R5 
И~R6 ДЛЯ ТОГО, ЧТОБЫ НАЛОЖИТЬ НА ПОСЛЕДОВАТЕЛЬНОСТИ ДОБАВОЧНЫЕ УСЛОВИЯ. 
оСОБЕННО ПОДХОДЯЩИМ ОПРЕДЕЛЕНИЕМ БЕСКОНЕЧНОЙ СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ 
ПРЕДСТАВЛЯЕТСЯ~R6. оНО ДАЕТ ТОЧНУЮ КОЛИЧЕСТВЕННУЮ ФОРМУЛИРОВКУ,
%% 188
КОТОРАЯ, ПО-ВИДИМОМУ, СОВПАДАЕТ С ИНТУИТИВНЫМ ПОНЯТИЕМ ИСТИННОЙ СЛУЧАЙНОСТИ.

еСЛИ ГОВОРИТЬ ОБ ИСТОРИИ ВОПРОСА, РАЗВИТИЕ ЭТИХ ОПРЕДЕЛЕНИЙ ВО МНОГОМ 
ОБЯЗАНО р.~ФОН~мИЗЕСУ И ЕГО ПОИСКАМ ХОРОШЕГО ОПРЕДЕЛЕНИЯ "ВЕРОЯТНОСТИ". 
оН ({\sl Math. Zeitschrift,\/} {\bf 5} (1919), 52--99) ПРЕДЛОЖИЛ 
ОПРЕДЕЛЕНИЕ, ПО ДУХУ БЛИЗКОЕ ОПРЕДЕЛЕНИЮ~R5, ХОТЯ ПО ФОРМЕ НАСТОЛЬКО 
СИЛЬНОЕ (НАПОДОБИЕ НАШЕГО ОПРЕДЕЛЕНИЯ~R3), ЧТО ПОСЛЕДОВАТЕЛЬНОСТИ, 
УДОВЛЕТВОРЯЮЩИЕ НАЛОЖЕННЫМ УСЛОВИЯМ, НЕ МОГУТ СУЩЕСТВОВАТЬ. мНОГИЕ 
ЗАМЕТИЛИ ЭТО ОБСТОЯТЕЛЬСТВО, И а.~кОУПЛЭНД ({\sl Amer.~J.~Math.,\/} {\bf 
50} (1928), 535--552) ПРЕДЛОЖИЛ ОСЛАБИТЬ ОПРЕДЕЛЕНИЕ ФОН~мИЗЕСА, ВВОДЯ ТАК 
НАЗЫВАЕМЫЕ "ДОПУСТИМЫЕ ЧИСЛА" (ИЛИ ПОСЛЕДОВАТЕЛЬНОСТИ бЕРНУЛЛИ). оНИ 
ЭКВИВАЛЕНТНЫ $\infty\hbox{-РАСПРЕДЕЛЕННЫМ}$ НА~$[0, 1)$ 
ПОСЛЕДОВАТЕЛЬНОСТЯМ, В КОТОРЫХ ВСЕ~$U_n$ ЗАМЕНЯЮТСЯ НА~$1$, ЕСЛИ~$U_n<p$, 
ИЛИ НА~$0$, ЕСЛИ~$U_n\ge p$, ПРИЧЕМ ВЕРОЯТНОСТЬ~$p$ ЗАДАНА. тАКИМ ОБРАЗОМ, 
кОУПЛЭНД ПО СУЩЕСТВУ ПРЕДЛАГАЛ ВОЗВРАТИТЬСЯ К ОПРЕДЕЛЕНИЮ~R1. 
а.~вАЛЬД ПОКАЗАЛ, ЧТО СТОЛЬ РАДИКАЛЬНО ОСЛАБЛЯТЬ ОПРЕДЕЛЕНИЕ ФОН~мИЗЕСА НЕ 
НУЖНО, А ДОСТАТОЧНО ВВЕСТИ СЧЕТНОЕ МНОЖЕСТВО ПРАВИЛ ПОСТРОЕНИЯ 
ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ. в ВАЖНОЙ СТАТЬЕ [{\sl Ergebnisse eines math. 
Kolloquiums,\/} {\bf 8} (Vienna, 1937), 38--72] вАЛЬД ПО СУЩЕСТВУ ДОКАЗАЛ 
ТЕОРЕМУ~W, ХОТЯ И СДЕЛАЛ ОШИБОЧНОЕ УТВЕРЖДЕНИЕ, СОСТОЯЩЕЕ В ТОМ, ЧТО 
ПОСЛЕДОВАТЕЛЬНОСТЬ, ПОСТРОЕННАЯ С ПОМОЩЬЮ АЛГОРИТМА~W, УДОВЛЕТВОРЯЕТ ТАКЖЕ 
БОЛЕЕ СИЛЬНОМУ ТРЕБОВАНИЮ "МЕРА~$A=\Pr(U_n\in A)$" ДЛЯ ВСЕХ ИЗМЕРИМЫХ ПО 
лЕБЕГУ $A\subseteq [0, 1)$. мЫ ВИДЕЛИ, ЧТО НИ ОДНА ПОСЛЕДОВАТЕЛЬНОСТЬ НЕ 
МОЖЕТ УДОВЛЕТВОРИТЬ ЭТОМУ ТРЕБОВАНИЮ.

оПРЕДЕЛЕНИЕ~R4 ВПЕРВЫЕ БЫЛО СФОРМУЛИРОВАНО д.~лАВЛЭНДОМ ({\sl Zeit.\ fur 
Math.\ Logik und Grundlagen d.~Math.,\/} {\bf 12} (1966), 279--294), 
КОТОРЫЙ ОБНАРУЖИЛ, ЧТО ПРИ ПОМОЩИ АЛГОРИТМА~W МОЖНО ДОКАЗАТЬ СУЩЕСТВОВАНИЕ 
ДВОИЧНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ, УДОВЛЕТВОРЯЮЩЕЙ ОПРЕДЕЛЕНИЮ~R5, НО НЕ~R4.

кОГДА вАЛЬД ПИСАЛ СВОЮ СТАТЬЮ, ПОНЯТИЕ "ВЫЧИСЛИМОСТИ" БЫЛО ЛИШЬ НЕДАВНО 
СОЗДАНО, И а.~чёРЧ [{\sl Bulletin AMS,\/}, {\bf 47} (1940), 130--135] 
ПОКАЗАЛ, КАК В ТЕОРИЮ вАЛЬДА МОЖНО ВВЕСТИ СТРОГОЕ ПОНЯТИЕ "ЭФФЕКТИВНОГО 
АЛГОРИТМА" ДЛЯ ТОГО, ЧТОБЫ СДЕЛАТЬ ЕГО ОПРЕДЕЛЕНИЯ СОВЕРШЕННО ТОЧНЫМИ. 
сУЩЕСТВЕННОЕ ПРОДВИЖЕНИЕ К ОПРЕДЕЛЕНИЮ~R6 СДЕЛАЛ а.~н.~кОЛМОГОРОВ [{\sl 
Sankhy\=a,\/} series~A, {\bf 25} (1963), 369--376], КОТОРЫЙ В ТОЙ ЖЕ 
СТАТЬЕ ПРЕДЛОЖИЛ ОПРЕДЕЛЕНИЕ~Q2 ДЛЯ КОНЕЧНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ.

дАЛЬНЕЙШИЕ СВЯЗИ МЕЖДУ СЛУЧАЙНЫМИ ПОСЛЕДОВАТЕЛЬНОСТЯМИ И ТЕОРИЕЙ 
РЕКУРСИВНЫХ ФУНКЦИЙ БЫЛИ ВЫЯВЛЕНЫ д.~лАВЛЭНДОМ [{\sl Trans. AMS,\/} {\bf 
125} (1966), 497--510]. сМ. ТАКЖЕ РАБОТУ к.-п.~шНОРРА [{\sl Z.\ Wahr.\ 
verw.\ Geb.,\/} {\bf 14} (1969), 27--35], ГДЕ ПРИВЕДЕНЫ СИЛЬНЫЕ 
ЗАВИСИМОСТИ МЕЖДУ СЛУЧАЙНЫМИ ПОСЛЕДОВАТЕЛЬНОСТЯМИ И "КАТЕГОРИЯМИ МЕРЫ 
НУЛЬ", ОПРЕДЕЛЕННЫМИ бРОУЭРОМ В 1919~Г. 

в СТАТЬЯХ чёРЧА  И кОЛМОГОРОВА РАССМАТРИВАЛИСЬ ТОЛЬКО
%% 189
ДВОИЧНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ, ДЛЯ КОТОРЫХ~$\Pr(X_1=1)=p$ ПРИ ЗАДАННОЙ 
ВЕРОЯТНОСТИ~$p$. тЕМ САМЫМ РАССУЖДЕНИЯ, ПРОВЕДЕННЫЕ В ЭТОЙ ГЛАВЕ, ЯВЛЯЮТСЯ 
НЕСКОЛЬКО БОЛЕЕ ОБЩИМИ, ПОСКОЛЬКУ ПОСЛЕДОВАТЕЛЬНОСТЬ НА~$[0, 1)$ 
ПРЕДСТАВЛЯЕТ ОДНОВРЕМЕННО ВСЕ~$p$.

в ДРУГОЙ СТАТЬЕ [{\sl пРОБЛЕМЫ ПЕРЕДАЧИ ИНФОРМАЦИИ,\/} {\bf 1}, (1965),
 3--11] кОЛМОГОРОВ РАССМОТРЕЛ ЗАДАЧУ ОБ ОПРЕДЕЛЕНИИ "КОЛИЧЕСТВА 
ИНФОРМАЦИИ" ПОСЛЕДОВАТЕЛЬНОСТИ, И ЭТА РАБОТА ПРИВЕЛА мАРТИН-лёФА К 
ИНТЕРЕСНОМУ ОПРЕДЕЛЕНИЮ КОНЕЧНЫХ СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ЧЕРЕЗ 
"НЕРЕГУЛЯРНОСТЬ" [{\sl IEEE Trans.,\/} {\bf IT-14} (1968), 662--664]. еЩЕ 
ОДНО ОПРЕДЕЛЕНИЕ СЛУЧАЙНОСТИ, КОТОРОЕ МОЖНО БЫЛО БЫ ПОМЕСТИТЬ МЕЖДУ 
ОПРЕДЕЛЕНИЯМИ~Q1 И~Q2, БЫЛО СФОРМУЛИРОВАНО ДОВОЛЬНО ДАВНО 
а.~с.~бЕЗИКОВИЧЕМ [{\sl Math.\ Zeitschrift,\/}  {\bf 39} (1934), 146--156].

дАЛЬНЕЙШЕЕ ОБСУЖДЕНИЕ СВОЙСТВ СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ МОЖНО НАЙТИ 
В КНИГЕ к.~пОППЕРА "The Logic of Scientific Discovery" (London, 1959). 
оСОБЕННО ИНТЕРЕСНЫ РЕЗУЛЬТАТЫ, ПРИВЕДЕННЫЕ НА СТР.~162--163, КОТОРЫЕ ОН 
ВПЕРВЫЕ ОПУБЛИКОВАЛ В 1934~Г.

иНТЕРЕСНЫЕ УПРАЖНЕНИЯ, СВЯЗАННЫЕ С ПОСЛЕДОВАТЕЛЬНОСТЯМИ НА~$[0, 1)$, ЕСТЬ 
В КНИГЕ д.~пОЛИА, г.~сЕГё, "зАДАЧИ И ТЕОРЕМЫ ИЗ АНАЛИЗА", ЧАСТЬ~1 ({\sl 
гиттл,\/} мОСКВА, 1956~Г.); О РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ $b\hbox{-ИЧНЫХ}$ 
ПОСЛЕДОВАТЕЛЬНОСТЯХ НАПИСАНО В РАБОТАХ а.~нИВЕНА ({\sl Trans.\ Amer.\ 
Math.\ Soc.,\/} {\bf 98} (1961); 52--61) И б.~зЭЙНА ({\sl AMM,\/} {\bf 71} 
(1964), 162--164).

\excercises
\ex[10]мОЖЕТ ЛИ ПЕРИОДИЧЕСКАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ БЫТЬ РАВНОМЕРНО РАСПРЕДЕЛЕННОЙ?

\ex[10] рАССМОТРИТЕ ПЕРИОДИЧЕСКУЮ ДВОИЧНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ~$0$, $0$, 
$1$, $1$, $0$, $0$, $1$, $1$,~$\ldots\,$. яВЛЯЕТСЯ ЛИ ОНА 
$1\hbox{-РАСПРЕДЕЛЕННОЙ}$? $2\hbox{-РАСПРЕДЕЛЕИНОЙ}$? $3\hbox{-РАСПРЕДЕЛЕННОЙ}$?

\ex[M22] пОСТРОЙТЕ $3\hbox{-РАСПРЕДЕЛЕННУЮ}$ ПЕРИОДИЧЕСКУЮ ТРОИЧНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ.

\rex[вм22] рАССМОТРИТЕ 
ПОСЛЕДОВАТЕЛЬНОСТЬ~$U_n=(2^{\floor{\log_2(n+1)}}/3)\bmod 1$, ЧЕМУ РАВНА~$\Pr(U_n<1/2)$?

\ex[вм14] дОКАЖИТЕ, ЧТО ДЛЯ ЛЮБЫХ ДВУХ УТВЕРЖДЕНИЙ~$S(n)$, $T(n)$ 
СПРАВЕДЛИВО РАВЕНСТВО~$\Pr(S(n) \rand T(n))+\Pr(S(n)\ror 
T(n))=\Pr(S(n))+\Pr(T(n))$  ПРИ УСЛОВИИ, ЧТО ПО КРАЙНЕЙ МЕРЕ ТРИ ИЗ ЭТИХ 
ПРЕДЕЛОВ СУЩЕСТВУЮТ. [еСЛИ, НАПРИМЕР, ПОСЛЕДОВАТЕЛЬНОСТЬ 
$2\hbox{-РАСПРЕДЕЛЕНА}$, МЫ НАХОДИМ, ЧТО
\EQ{
 \Pr(u_1\le U_n < v_1 \ror u_2 \le U_{n+1} < v_2)=v_1-u_1+v_2-u_2-(v_1-u_1)(v_2-u_2).]
}

\ex[вм23] пУСТЬ~$S_1(n)$, $S_2(n)$,~\dots---БЕСКОНЕЧНАЯ 
ПОСЛЕДОВАТЕЛЬНОСТЬ УТВЕРЖДЕНИЙ, КАСАЮЩИХСЯ ВЗАИМНО ИСКЛЮЧАЮЩИХ СОБЫТИЙ, 
Т.~Е.\ УТВЕРЖДЕНИЯ~$S_i(n)$ И~$S_j(n)$ ПРИ~$i\ne j$ НЕ МОГУТ БЫТЬ 
ИСТИННЫМИ ОДНОВРЕМЕННО. пРЕДПОЛОЖИМ, ЧТО $\Pr(S_j(n))$ СУЩЕСТВУЕТ ДЛЯ 
КАЖДОГО~$j\ge 1$. пОКАЖИТЕ, ЧТО~$\Prsub(S_j(n) \hbox{ ИСТИННО ДЛЯ 
НЕКОТОРОГО } j\ge 1)\ge \sum_{j\ge1} \Pr(S_j(n))$, И ПРИВЕДИТЕ ПРИМЕР, 
ПОКАЗЫВАЮЩИЙ, ЧТО РАВЕНСТВО НЕ ОБЯЗАТЕЛЬНО ИМЕЕТ МЕСТО.

\ex[вм27] пУСТЬ, КАК И В ПРЕДЫДУЩЕМ УПРАЖНЕНИИ, ЗАДАНО БЕСКОНЕЧНО БОЛЬШОЕ 
ЧИСЛО ВЗАИМНО ИСКЛЮЧАЮЩИХ СОБЫТИЙ~$S_{ij}(n)$, $i\ge 1$, $j\ge 1$, ТАКИХ, 
ЧТО 
%% 190
$\Pr(S_{ij}(n))$~СУЩЕСТВУЕТ. пРЕДПОЛОЖИМ, ЧТО~$S_{ij}(n)$ ПРИ ВСЕХ~$n>0$ 
ИСТИННО ДЛЯ ТОЧНО ОДНОЙ ПАРЫ ЦЕЛЫХ ЧИСЕЛ~$i$, $j$. еСЛИ~$\sum_{i,j\ge 
1}\Pr(S_{ij}(n))=1$, ТО МОЖНО ЛИ ОТСЮДА ЗАКЛЮЧИТЬ, ЧТО ДЛЯ ВСЕХ~$i\ge 1$ 
ВЕЛИЧИНА~$\Pr(S_{ij}(n))$ ИСТИННО ДЛЯ НЕКОТОРОГО~$j\ge 1$) СУЩЕСТВУЕТ И 
РАВНА~$\sum_{j\ge 1}\Pr(S_{ij}(n))$?

\ex[M15] дОКАЖИТЕ УТВЕРЖДЕНИЕ~\eqref[13].

\ex[вм20] дОКАЖИТЕ ЛЕММУ~E. [\emph{уКАЗАНИЕ:} РАССМОТРЕТЬ 
ВЫРАЖЕНИЕ~$\sum_{1\le j \le m} (y_{jn}-\alpha)^2$.]

\rex[вм22] гДЕ ПРИ ДОКАЗАТЕЛЬСТВЕ ТЕОРЕМЫ~C ИСПОЛЬЗОВАЛСЯ ТОТ ФАКТ, ЧТО $q$~КРАТНО~$m$?

\rex[вм20] пРИМЕНИТЕ ТЕОРЕМУ~C, ЧТОБЫ ДОКАЗАТЬ, ЧТО ЕСЛИ 
ПОСЛЕДОВАТЕЛЬНОСТЬ~$\<U_n>$ $\infty\hbox{-РАСПРЕДЕЛЕНА}$, ТО ЭТИМ 
СВОЙСТВОМ ОБЛАДАЕТ И ПОДПОСЛЕДОВАТЕЛЬНОСТЬ~$\<U_{2n}>$.

\ex[вм20] пОКАЖИТЕ, ЧТО $k\hbox{-РАСПРЕДЕЛЕННАЯ}$ ПОСЛЕДОВАТЕЛЬНОСТЬ 
УДОВЛЕТВОРЯЕТ ТЕСТУ "НАИБОЛЬШЕЕ ИЗ~$k$" В СЛЕДУЮЩЕМ СМЫСЛЕ: 
$\Pr(u\le\max(U_n, U_{n+1},~\ldots, U_{n+k-1}<v)=v^k-u^k$.

\rex[вм27] пОКАЖИТЕ, ЧТО $\infty\hbox{-РАСПРЕДЕЛЕННАЯ}$ НА~$[0,1)$ 
ПОСЛЕДОВАТЕЛЬНОСТЬ УДОВЛЕТВОРЯЕТ ПРОВЕРКЕ ИНТЕРВАЛОВ В СЛЕДУЮЩЕМ СМЫСЛЕ. 
пУСТЬ~$0\le\alpha<\beta\le 1$ И~$p=\beta-\alpha$; ПОЛОЖИМ~$f(0)=0$, 
И~$f(n)$ ДЛЯ~$n\ge 1$ ЕСТЬ НАИМЕНЬШЕЕ ЦЕЛОЕ~$m>f(n-1)$, ТАКОЕ, 
ЧТО~$\alpha\le U_m<\beta$. тОГДА~$\Pr(f(n)-f(n-1)=k)=p(1-p)^{k-1}$.

\ex[вм25] пОКАЖИТЕ, ЧТО $\infty\hbox{-РАСПРЕДЕЛЕННАЯ}$ ПОСЛЕДОВАТЕЛЬНОСТЬ 
УДОВЛЕТВОРЯЕТ ПРОВЕРКЕ НА МОНОТОННОСТЬ В СЛЕДУЮЩЕМ СМЫСЛЕ. еСЛИ~$f(0)=1$ 
И~$f(n)$  ДЛЯ~$n\ge 1$ ЕСТЬ НАИМЕНЬШЕЕ ЦЕЛОЕ ЧИСЛО~$m>f(n-1)$, ТАКОЕ, 
ЧТО~$U_{m-1}>U_m$, ТО 
\EQ{
\Pr(f(n)-f(n-1)=k)=2k/(k+1)!-2(k+1)/(k+2)!.
}

\rex[вм30] пОКАЖИТЕ, ЧТО $\infty\hbox{-РАСПРЕДЕЛЕННАЯ}$ ПОСЛЕДОВАТЕЛЬНОСТЬ 
УДОВЛЕТВОРЯЕТ ТЕСТУ СОБИРАТЕЛЯ КУПОНОВ ДЛЯ СЛУЧАЯ, КОГДА ИМЕЮТСЯ ТОЛЬКО 
ДВА СОРТА КУПОНОВ, В СЛЕДУЮЩЕМ СМЫСЛЕ. пУСТЬ $X_1$, $X_2$,~\dots{} ЕСТЬ 
$\infty\hbox{-РАСПРЕДЕЛЕННАЯ}$ ДВОИЧНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ. 
пОЛОЖИМ~$f(0)=0$ И ПУСТЬ~$f(n)$ ДЛЯ~$n\ge 1$ ЕСТЬ НАИМЕНЬШЕЕ 
ЦЕЛОЕ~$m>f(n-1)$, ТАКОЕ, ЧТО~$\set{X_{f(n-1)+1},~\ldots, X_m}$ ЕСТЬ 
МНОЖЕСТВО~$\set{0, 1}$. дОКАЖИТЕ,ЧТО~$\Pr(f(n)-f(n-1)=k)=2^{1-k}$; 
$k\ge 2$. (сР.\ С УПР.~7.)

\ex[вм38] сПРАВЕДЛИВ ЛИ ТЕСТ СОБИРАТЕЛЯ КУПОНОВ ДЛЯ 
$\infty\hbox{-РАСПРЕДЕЛЕННЫХ}$ ПОСЛЕДОВАТЕЛЬНОСТЕЙ В СЛУЧАЕ, КОГДА 
ИМЕЕТСЯ БОЛЬШЕ ДВУХ СОРТОВ КУПОНОВ? (сР.\ С ПРЕДЫДУЩИМ УПРАЖНЕНИЕМ.)

\ex[вм50] фРАНКЛИН ДОКАЗАЛ, ЧТО ЕСЛИ~$r$---ЗАДАННОЕ РАЦИОНАЛЬНОЕ ЧИСЛО, ТО 
ПОСЛЕДОВАТЕЛЬНОСТЬ~$U_n=(r^n\bmod 1)$ НЕ ЯВЛЯЕТСЯ 
$2\hbox{-РАСПРЕДЕЛЕННОЙ}$. сУЩЕСТВУЕТ ЛИ РАЦИОНАЛЬНОЕ ЧИСЛО~$r$, ТАКОЕ, 
ЧТО ЭТА ПОСЛЕДОВАТЕЛЬНОСТЬ БУДЕТ РАВНОМЕРНО РАСПРЕДЕЛЕНА? в ЧАСТНОСТИ, 
БУДЕТ ЛИ ЭТА ПОСЛЕДОВАТЕЛЬНОСТЬ РАВНОМЕРНО РАСПРЕДЕЛЕННОЙ В СЛУЧАЕ, 
КОГДА~$r=3/2$? [сР. СО СТАТЬЕЙ к.~мАЛЕРА ({\sl Mathematika,\/} {\bf  4} 
(1957), 122--124).]

\rex[вм22] дОКАЖИТЕ, ЧТО ЕСЛИ~$U_0$, $U_1$,~\dots{} 
$k\hbox{-РАСПРЕДЕЛЕНА}$, ТО ЭТИМ ЖЕ СВОЙСТВОМ ОБЛАДАЕТ И 
ПОСЛЕДОВАТЕЛЬНОСТЬ~$V_0$, $V_1$,~\dots, ГДЕ~$V_n=\floor{nU_n}/n$.

\ex[вм46] рАССМОТРИТЕ ОПРЕДЕЛЕНИЕ~R4, В КОТОРОМ СЛОВО 
"$\infty\hbox{-РАСПРЕДЕЛЕННОЙ}$" ЗАМЕНЕНО НА "$1\hbox{-РАСПРЕДЕЛЕННОЙ}$". 
сУЩЕСТВУЕТ ЛИ ПОСЛЕДОВАТЕЛЬНОСТЬ, КОТОРАЯ УДОВЛЕТВОРЯЕТ ЭТОМУ БОЛЕЕ 
СЛАБОМУ ОПРЕДЕЛЕНИЮ, НО НЕ ЯВЛЯЕТСЯ $\infty\hbox{-РАСПРЕДЕЛЕННОЙ}$? (тО 
ЕСТЬ ЯВЛЯЕТСЯ ЛИ ЭТО ОПРЕДЕЛЕНИЕ ДЕЙСТВИТЕЛЬНО БОЛЕЕ СЛАБЫМ?)

\ex[BM50] уДОВЛЕТВОРЯЕТ ЛИ ПОСЛЕДОВАТЕЛЬНОСТЬ~$U_n=(\theta^n\bmod 1)$ 
ОПРЕДЕЛЕНИЮ~R4 ДЛЯ ПОЧТИ ВСЕХ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ~$\theta>1$? (оТВЕТ НА 
ЭТОТ ВОПРОС МОЖНО ПОЛУЧИТЬ ИЛИ В ТОМ СЛУЧАЕ, КОГДА НАЙДЕН ОТРИЦАТЕЛЬНЫЙ 
ОТВЕТ НА ВОПРОС УПР.~19, ИЛИ В ТОМ СЛУЧАЕ, КОГДА ПОКАЗАНО, ЧТО ДЛЯ ЛЮБОЙ 
ПОСЛЕДОВАТЕЛЬНОСТИ РАЗЛИЧНЫХ ПОЛОЖИТЕЛЬНЫХ ЦЕЛЫХ ЧИСЕЛ $s_0$,  $s_1$, 
$s_2$,~\dots{} ПОСЛЕДОВАТЕЛЬНОСТЬ~$U_n=(\theta^{s_n}\bmod 1)$ 
$\infty\hbox{-РАСПРЕДЕЛЕНА}$ ДЛЯ ПОЧТИ ВСЕХ~$\theta>1$.)

%% 191
\bye