\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