\input style
of a Random Sequence" ({\sl BIT,\/} {\bf 5} (1965), 246--250). 
������������������, ����������� � ���� ������, ������� ������� �� 
������������ �����. ������ �����~$U_n$ ����� �������� ������������� � 
�������� ������� ���������. ��������� ����� ������� ����� ������ 
���������� $\infty\hbox{-��������������}$ ������������������ ����� �������� �� 
����������� ���� �������~W.

\qsection{C. ������������ �� ������� $\infty\hbox{-����������������}$ � 
�����������}?
�� ����� ���������� ���� ��� $\infty\hbox{-��������������}$ 
������������������ �������, ��� ������� $\infty\hbox{-����������������}$ 
����� ���� �� ����. ����� ����� � ����������� ���������� �������, ��� 
��������� ����������� ������ ��������� ����������� ������� �����������.

\proclaim ����������� R1. ������������������ ��~$[0, 1)$ ���������� 
"���������", ���� ��� $\infty\hbox{-������������}$.

�� ������, ��� ����� ������������������ ������������� ���� ������ �.~3.3.2 
� ��� ������ ������.

��������� ���������� ������� � ����� �����������. ������ �����, �������� 
�� ����� "������� ���������" ������������������ 
$\infty\hbox{-��������������}$? ���������� ��������� ���������� 
�������������������~$U_0$, $U_1$,~\dots{} �������������� �����, 
����������� ����� ����� � ��������. ���� ��������~$U_0$, $U_1$,~\dots{} 
���������� � ������� ������� ������� ��������� �����, ����� �� 
������������������� ����� ������� �����������. ��� ���� ��������� �� 
���� ������������������� (� ���������������� ���������� ������� �� �����) 
�� ����� ���� ���������� ������������. � ������ �������, ��� ����� 
�������� ����������� ����������� �� ���� ������������ ���� ��������� 
������������������� �� ������ ���������, ��� ��������� ������������������ 
$\infty\hbox{-������������}$ � \emph{������������}~$1$. ����� �������, �� 
�������� � ������������ ����������� �����������, ������� ���������� 
(��.\ ������ ���������).

\proclaim ����������� R2. ������������������~$\<U_n>$ ��~$[0, 1)$ ���������� 
"���������", ���� ��� ������ ��������~$P$, ������, ���~$P(\<V_n>)$ 
����������� � ������������~1 ��� ������������������~$\<V_n>$ ����������� 
������� ��������� ������� �� ������������ �������������, �����������~$P(\<U_n>)$.

�������� ��, ��� �����������~R1 ������������ �����������~R2? ��������� 
��������� ������ �����������~R1 ��������� ����������.

������ ����� �����������~R1 ����� ���� ������ � ����������� ���������� 
������������������ ���~$n\to\infty$. ���������� $\infty\hbox{-��������������}$ 
������������������, ������������ ��������
%% 172
�� �������� �����. ������� �� ������� ����� ������������������ ���������?

��� ���������� �� ����� ��������. �����~$\varepsilon$---����� 
������������� �����, ����� ������ ��������, ��� ������ �� 
������� �������� ������ ������������������ ������~$\varepsilon$. ��� �� 
��� �������� �����, ��� �������, ������������ ������ � ���, �������� ��� 
��� �������� ������������������. ������� ��������� ������������������ � 
������������ ������� �������� ���������� ����� �������� �� �������� 
���������������� ������, ������ �� ������� ������~$\varepsilon$. ������ �� 
����� ������� �� ����� ��������� � ������ ������������������?

� ������ �������, ���������� �����������~R2, � ����� $P$---�������� 
������������������, ��������� � ���, ��� ��� �� �������� ��������. 
��������~$P$ ����������� � ������������ �������, ������� ����� 
������������������ � ��������� ����� �� \emph{�����} �������� �� �������� 
���������.

����� ������ ��������~$P$ ����������� � ���, ��� \emph{�� ����} ������� 
������������������ �� ����� ����. ��� ����������� � ������������ �������, 
������� �� �����������~R2 ����� ������������������, � ������� ���� 
������� �������, �� �������� ���������. ���������� ����� ����� ������: 
�����~$x_0$---����� �������� �����, ����������� ����� ����� � ��������, 
�~$P$---��������, ��������� � ���, ��� �� ���� ������� ������������������ 
�� �����~$x_0$. �� �����������~R2 �������, ��� ������� ��������� 
������������������ �� ����� ��������� �������, ������~$x_0$! ������ ����� 
��������, ��� \emph{�� ���� ������������������ �� ����� ������������� 
��������, ���������������� � �����������}~R2. (� ����� ����, ����~$U_0$, 
$U_1$,~\dots{} ���� ������������������, ��������������� ���� ��������, 
�� �������~$x_0=U_0$.)

����� �������, ����~R1---������� ������ �����������, �� R2---������� �������. 
"����������" ����������� ������ ���� ����� ���������������, ���~R2. ������ 
��, ������ ������, ��� �� ��������, ��� R1 ������� �����, ������� 
��������� ��� ��������. ���� ���������� � ���, ��� ����� 
��������� $\infty\hbox{-��������������}$ ������������������ 
\emph{������������} �����. (����������, � ���� ��� ������ �������� 
�������������: ��.\ ���.~1.8.) ����� ��� �������������� ����� 
�������������, ������� ����� �����������, ����� ��� ��������� 
������������������ ����� ����� ���������
\EQ{
 \Pr(U_n \hbox{ �����������})=0.
}

�������, ��� ����������� ����������������, �� ����������� ��������, 
���~$\Pr(u\le U_n<v)=v-u$. ��������� ������ ����, ����� �������� ��� 
�����������: "���� ���� ���������~$S\subseteq [0,1)$
%% 173
�����~$\mu$, ��
\EQ[27]{
 \Pr(U_n \in S)=\mu
}
��� ���� ��������� �������������������~$\<U_n>$". � ���������, ���� 
���������~$S$ ���������� �� ������������ �����, ��� ����� ���� ����, �, 
����� �������, ������� ������������������ ������������ ����� �� �������� 
���������� �������������� � ���� ���������� ������. ����� �������, ��� 
�������~B ���������� �� ������ �������������� � ������ ������, ���� 
����������� ���������� ��������~\eqref[27]. ������ �� ����� �������� � 
������, ��� �����������~\eqref[27] �������� ������� �������, ��������� �� 
���� ������������������ \emph{��} �������� ���� ���������! ���� $U_0$,  
$U_1$,~\dots---��������� ������������������, �� ���� 
���������~$S=\set{U_0, U_1,~\ldots}$ ����� ����, ������~$\Pr(U_n\in S)=1$.
����� �������, ����� ��� �� �����������, � ������� ������� �� ��������� �� 
��������� ������������������� ������������ �����, ����� ��������� ��� 
��������� ������������������.

���� ��� ��� �� ��������, ��� �����������~R1 ����������. ������ ����, 
������, ���������� ������ ����������. ����, ��������, ������� ��������� � 
����������� ������ ������������������, ����������� �� ���������������������
\EQ[28]{
 U_0, U_1, U_4, U_9,~\ldots, U_{n^2},~\ldots
}
������ ����� ���� ���������. ��� $\infty\hbox{-��������������}$ 
������������������ ��� �� ������ �����������. (�������������, ���� ����� 
����� $\infty\hbox{-��������������}$ ������������������ � 
��������~$U_{n^2}\leftarrow 0$ ��� ����~$n$, ��������~$\nu_k(n)$, ������� 
���������� ��� �������� $k\hbox{-����������������}$, ��������� �� ������, 
��� �� �������� �������~$\sqrt{n}$, ��� ��� ������� ���������~$\nu_k(n)/n$ 
�� ���������.) ������ �������, ���~R1 �� �������� ���� ��������� �����������.

��������� �������~R1 ��������� �������.

\proclaim �����������~R3. ������������������ ��~$[0, 1)$ ���������� 
"���������", ���� ������ �� ����������� ��������������������� 
$\infty\hbox{-������������}$.

������ � ��� ����������� ����������� ������� ���������������, ��������� 
�� ����� ���������� �������������� ������������������~$\<U_n>$ ����� 
�������� ���������� ���������������������~$U_{s_0}<U_{s_1}<U_{s_2}<\ldots\,$.

������� ��� ���������� ����� ��������������� ����������������������, 
����� ������ ���� ������������������, ������� �����������, ����� ���� �� 
�������� �� ���������� �������. ����� �������, ��������

%% 174

\proclaim �����������~R4. ������������������~$\<U_n>$ ��~$[0, 1)$ 
���������� "���������", ���� ����� �� �� ��� ����������� ��������, 
� ������� �������� ���������� ����������� ������������������ ��������� 
��������������� ����� �����~$s_n$, ���~$n\ge0$, 
���������������������~$U_{s_0}$, $U_{s_1}$,~\dots,  ��������������� 
����� ���������, �������� $\infty\hbox{-��������������}$.

���������, � ������� ���� ����,---��� ���������, �����������~$s_n$ �� 
���������~$n$. � ���� ����������� ��������� ��� ���� ����������� 
"���������� ������������" ���������������������� � ������������ � ������� 
������������ ����������� �������������� (��.~��.~11).

������������ ������� ����������� ������� ������� ��������� ���������. 
������������������~$\<\pi^n\bmod 1>$ ��������� \emph{��} ����� 
������������� �����������~R4, ��������� ��� ��� �� �������� ���������� 
��������������, ��� ���������� ����������� ��������, ������������ 
����������� ������������������~$s_n$, �����, 
���~$(\pi^{s_0}\bmod 1) < (\pi^{s_1}\bmod 1) < \ldots\,$. ����� ������� 
����������, ��� \emph{�� ���� ����� ������� ������������ ������������������ 
�� ����� ������������� �����������}~R4. � ���� ������� �����������, ���� 
�������, ��� ����� ������� ������������ ������������������ �� ����� ���� 
������������� ���������. ������ ��������, ������, ��� 
������������������~$\<\theta^n\bmod 1>$ ����� ������������� �����������~R4 
��� ����� ���� �������������� �����~$\theta>1$. ����� ��� ������������, 
��������� ����� ���~$\theta$ ���������� ��������� � ������� ���������. 
��������, ��������, ��������� �����. 
(i)~������������������~$\<\theta^m\bmod 1>$ ������������� �����������~R4 
��� ����� ���� ��������������~$\theta>1$, ���� ������� 
$\infty\hbox{-����������������}$ �������� �� 
������� $1\hbox{-����������������}$. ��� ������� ���� �������� �.~������� 
({\sl Compositio Mathematica,\/} {\bf 2} (1935), 250--258). 
(ii)~������������������~$\<\theta^{s(n)}\bmod 1>$ 
$\infty\hbox{-������������}$ ��� ����� ���� ��������������~$\theta>1$, 
����~$\<s(n)>$ ���� ������������������ ����� �����, �����, 
���~$s(n+1)-s(n)\to\infty$ ���~$n\to\infty$. �����, ��������, 
��������~$s(n)=n^2$, ���~$s(n)=\floor{n\log n}$.

�����������~R4 ������� ������� �����������~R1, ������ � ��� ��� ��� 
������� �����. �����, ��������, ������� ������� ��������� 
������������������~$\<U_n>$. ��������� 
���������������������~$\<U_{s_n}>$ ��������� �������: $s_0=0$, � 
���~$n>0$ �����~$s_n$---���������� ������������� �����, �����, ��� ��� 
�����~$U_{s_n-1}$, $U_{s_n-2}$,~\dots, $U_{s_n-n}$ ������ ��������. ��� 
����� �� ������������� ��������������������� �������, ��������� ����� �� 
�� ������ �� $n$~������, ������ �� ������� ������~$1/2$. �����������, 
��� "$U_n<1/2$" ������������� ��������� "�������" ��� �������� ������. 
������ ������ �������, ��� ���� ������ ��������� ������, �� ������� 
����� ��������� "�������" �����������
%% 175
����������� ������������ ��������� "����", � ������������ ���� 
���������������������~$\<U_{s_n}>$ ������������� ��������� ������, ��� 
������� �� ������ $n\hbox{-�}$~������ ��� �������� ������, ��������� 
����� �� ������ ���������������� ���������� $n$~"�������". ����� ����� 
�������, ���~$\Pr(U_{s_n}\ge 1/2)$ ����������� ��������, ��, ����������, � 
������� ��������� ������������������ ��������~$\<U_{s_n}>$ ����� 
���������� ����������. ��� ����� ���������, ������� ������������ �� 
������������ � ����. � �����������~R4 ������ �� ��������� � 
����������������������, ������������ �������� ����� ���������, ������� 
����� ���������� ����� �������.

��������� "������� ���������� ���������������������"~$\cR$ ��� ����������� 
������������������ �������~$\<f_n(x_1,~\ldots, x_n)>$, ���~$n\ge0$, 
$f_n$---������� $n$~����������, �~$f_n(x_1,~\ldots, x_n)$ ����� ��������� 
��������~$0$ ���~$1$. ����� $x_1$,~\dots, $x_n$ �������� ���������� 
���������� ���������~$S$. (����� �������, $f_0$~���� ���������� �������, 
������~$0$ ���~$1$.) �������~$\cR$ ���������� ��������������������� 
���������� ��������������������� ����� ����������� 
������������������~$\<X_n>$ ���������~$S$ ��������� �������: 
\dfn{$n\hbox{-�}$ ����~$X_n$ ���������� � 
���������������������~$\<X_n>\cR$ � ��� � ������ ��� ������, 
�����~$f_n(X_0, X_1,~\dots, X_{n-1})=1$.} �������, ��� ������������ ����� 
������� ���������������������~$\<X_n>\cR$ �� ����������� �������� 
����������� � ����� ���� ���� ������.

"��������������������� ������", ��������� ����, ������������� ���������� 
������� ���������� ���������������������: "$f_0=1$; 
$f_n(x_1,~\ldots, x_n)=1$ ���~$n>0$ � ��� � ������ ��� ������, 
����� ���������� ���������~$k$, $0<k\le n$,  �����,   ���~$x_m<1/2$, 
$x_{m-1}<1/2$,~\dots, $x_{m-k+1}<1/2$,~\dots, $x_{m-k+1}<1/2$ ���~$m=n$, 
�� �� � ������, �����~$k\le m < n$".

������� ���������� ���������������������~$\cR$ 
���������� \emph{"����������",} ���� ���������� ����������� ��������, 
����������� ���������� ��������~$f_n(x_1,~\ldots, x_n)$ �� ������� 
������~$n$, $x_1$,~\dots, $x_n$. �������� ���������� ������� �����������, 
����� �������������� ����������� ��������� ���������� 
����������������������, � ��������� ������ �� ������� ������� 
������� �����������, ��������~R3. ������������ �������������� ����� �� 
����� ������� �������� ������� ����������� ����������, ������ ��� ����, 
��������, �������������� �����~$x$ � ���������� ������� ��������� 
������������ ����������� ������������������� ����, �� �� ���������� 
���������, �� �������� ����� ���� �� ����������, ����������� �� 
�����������~$x<1/3$, ��������� �������� �� ����������� ��� ����� 
�����~$0,333\ldots\,$. � ����� � ���� ���������� ������� ���������� 
��������������������� �� ��������� �� ���� ������������������� "��~$[0, 1)$", 
� ���������
%% 176
����������� ����� ������ ���������� �� $b\hbox{-�����}$ �������������������.

\proclaim �����������~R5. {$b\hbox{-�����}$ ������������������ ���������� 
"���������", ���� ������ �� ����������� ���������������������, 
������������ � ������� ����������� ������� ���������� 
���������������������, 1-������������.
 \hiddenpar
������������������~$\<U_n>$ ��~$[0, 1)$ ���������� "���������", ���� 
$b\hbox{-�����}$ ������������������~$\<\floor{bU_n}>$ "��������" ��� 
���� ����� �����~$b\ge2$.
}

�������, ��� � �����������~R5 ��������������������� 
"$1\hbox{-������������}$", � �� "$\infty\hbox{-������������}$". ��������� 
��������, ��� �������� ��� ���� �� ��������. � ����� ����, ��� 
������ $b\hbox{-������}$ �����~$a_1\ldots a_k$ ����� ��� ���������� 
��������� ������� ���������� �������~$\cR(a_1{}\ldots{}a_k)$ ���������� 
���������������������. �������~$f_n(x_1,~\dots, x_n)=1$ � ��� � ������ ��� 
������ �����~$n\ge k-1$ �~$x_{n-k+1}=a_1$,~\dots, $x_{n-1}=a_{k-1}$,  
$x_n=a_k$. ���� $\<X_n>$ �������� $k\hbox{-��������������}$ 
$b\hbox{-�����}$ �������������������, �� ���������� 
�������~$\cR(a_1\ldots{}a_k)$, ������� �������� ���������������������, 
��������� �� ������, ��������� ����� �� ����������~$a_1{}\ldots{}a_k$,  
���������� ����������� ���������������������, � ���� ��� 
��������������������� $1\hbox{-������������}$, �� ������ �� �������, 
��������� �� $k+1$~��������� $a_1\ldots{}a_k{}a_{k+1}$, ��� �������, 
���~$0\le a_{k+1}<b$, ���������� �~$\<X_n>$ � ������������~$1/b^{k+1}$. 
����� �������, ��������� ��~$k$ ����� ��������, ��� ������������������, 
��������������� �����������~R5, $k\hbox{-pac���������}$ ��� ����~$k$. 
����������� �������, ������������ "����������" ������ ���������� 
���������������������� (���� $\cR_1$~���������� ����������� 
���������������������~$\<X_n>\cR_1$, ����� ����������~$\cR_1\cR_2$ ��� 
������� ���������� ���������������������, �����, 
���~$\<X_n>\cR_1\cR_2=((\<X_n>\cR_1) \cR_2)$, �� �������� � ������, ��� 
��� ���������������������, ��������� � �����������~R5, 
$\infty\hbox{-������������}$ (��.\ ���.~32).

��������� $\infty\hbox{-����������������}$ ������� �� �����������~R5 ��� 
����� ������� ������, ����� ��������� �� ��, ��� ��, �������, 
�������������� ������� ����������� �����������. ��, ���, �������� ��� ���� 
��������! ����� �� ��������, ��� ������������������, ��������������� 
�����������~R4, ������ ����� ������������� �����������~R5. "���������� 
������� ���������� ����������������������", ������� �� �����, 
������ ����������� ���������������������~$\<X_{s_n}>$, ��� 
�������~$s_0<s_1<\ldots\,$, � ��� �������� � ��� ���������� 
"����������� �������������������". ��� �� �������� � ���� ��� 
���������� ������������ ������������������, ����������� ������������~R4,
%% 177
��� ������������������~$\<s_n>$ �� ������� ���� ����������; ������ ���� 
����������� �������~$s_n\ne s_m$, ���~$n=m$.

������������ � ����� ������������, �� �������� � ���������� 
�����������~R4 �~R5.

\proclaim �����������~R6. {$b\hbox{-�����}$ ������������������~$\<X_n>$ 
���������� "���������", ���� ��� ������ ������������ ���������, 
������������� ����������� ������������������ ��������� ��������������� 
����� �����~$\<s_n>$ ��� ������� ��~$n$ � ��������~$X_{s_0}$,~\dots, 
$X_{s_{n-1}}$, ��������������� ���������������������~$\<X_{s_n}>$ 
"��������" � ������ �����������~R5.
  \hiddenpar
������������������~$\<U_n>$ ��~$[0, 1)$ ���������� "���������", ���� 
$b\hbox{-�����}$ ������������������~$\<\floor{bU_n}>$ "��������" ��� ���� 
����� ������~$b\ge 2$.
}

����� ����������, ��� ��� �����������, ����������, �������� ���� �������� 
����������� �����������, ���Į�������� � ������� �����������, �, ����� 
�������, ���� ����� �� ������� ������, ������������ �����.

\section{D.~������������� ��������� �������������������}. �� ������, ��� 
�����������~R3 ������ ��������� ������� �������, ��� �� ���� 
������������������ ��� �� �������������, � ����� �����������~R4, R5 �~R6, 
�� ��������� ��������� �������� �������� �����������~R3. ��� ���� ����� 
��������, ��� �����������~R6 �� �������� ������� ���������������, 
������� �������� ���� ������������� �������������������, 
��������������� ��������������� �����������. ������ �� ����������� 
�����������, ����� �� ����������� � �� �������������, ��������� ������ 
����� � ��, ��� ������� ��������� ������������������ ���������� � 
������������� �����������~R6. ������ ����� ��������� � ��������������� 
�����������, ���������� ��������������.

���������� ����� ���������� �������������������, ��������������� 
�����������~R5, ��������� �.~�����. ������� �������� ����� ������� 
$1\hbox{-��������������}$ ������������������.

\proclaim �����~T. ����� � �������� ������� ��������� ���������� 
������������������ �������������� �����~$\<V_n>$:
\EQ[29]{
 V_0=0, V_1=.1, V_2=.01, V_3=.11, V_4=.001,~\ldots,
 V_n=.c_r\ldots{}c_1 1, \rem{����~$n=2^r+c_12^{r-1}+\cdots+c_r$.}
}
����� $I_{b_1\ldots{}b_r}$~���������� ��������� ����� �������������� ����� 
�� �������~$[0, 1)$, �������� ������������� ������� 
���������� �~$0.b_1\ldots{}b_r$. ����� �������,
\EQ[30]{
 I_{b_1\ldots{}b_r}=[0.b_1\ldots{} b_r, 0.b_1\ldots{}b_r+2^{-r}).
}
%%178
�����, ���� $\nu(n)$~���������� ���������� �����~$V_k$, 
������������ �~$I_{b_1\ldots{}b_r}$ ���~$0\le k < n$, ����� ����� �����������
\EQ[31]{
 \abs{\nu(n)/n-2^{-r}}\le 1/n.
}

\proof ��������� $\nu(n)$~���� ����� ���~$k$, ��� 
�������~$k\bmod 2^r=b_r\ldots{}b_1$, �� �����~$\nu(n)=t$ ���~$t+1$, 
�����~$\floor{n/2^r}=t$. ����� �������, $\abs{\nu(n)-n/2^r}\le 1$.
\proofend

�� �������~\eqref[31] �������, ��� ������������������~$\<\floor{2^rV_n}>$ 
�������� ���������� �������������� $2^r\hbox{-�����}$ 
�������������������; ������ � �� �������~A ���������, 
���~$\<V_n>$---���������� �������������� ��~$[0, 1)$ ������������������. � 
����� ����, ����, ���~$\<V_n>$ ��������� ���������� ������������, 
��������� ����� ���� ���������� �������������� ������������������ 
��~$[0, 1)$! (���������� ���������� ������� ���� � ��������� � ��� 
������������������� ������� � ������� �.~���~���~������� ({\sl Proc. 
Koninklijke Nederlandse Akademie van Wetenschappen,\/} {\bf 38} (1935), 
813--821, 1058--1066) � ��.~������� ({\sl Numerische Mathematik,\/} {\bf 2} 
(1960), 84--90, 196).

����� ������~$\cR_1$, $\cR_2$,~\dots---����������� ��������� 
������ ���������� ����������������������. �� ����� ����� 
������������������~$\<U_n>$, ��� ����������� 
���������������������~$\<U_n>\cR_j$ ������� ���������� ������������.

\alg W.(������������������ ������.) ��� ��������� ���������� 
������������������~$\<U_n>$ ��~$[0, 1)$, ���� ������ ����������� ��������� 
������ ���������� ����������������������~$\cR_1$, $\cR_2$,~\dots, 
������������ ��������������������� ������������������� \emph{������������} 
����� ��~$[0, 1)$. ��� ���������� ��������� ���������� ������� ���������� 
��������������� ����������~$C[a_1,~\ldots,a_r]$, ���~$r\ge 1$ �~$a_j=0$ 
���~$1$, $1\le j \le r$. � ��������� ������ ������� ��� ��� ���������� 
����� ����.

\st[��������� ���������~$n$.] ����������~$n\asg 0$.

\st[��������� ���������~$r$.] ����������~$r\asg 1$.

\st[���������~$\cR_r$.] ���� �������~$U_n$, ������ ������� � 
���������������������, ������������~$\cR_r$, �� ��������� 
��������~$U_k$, ���~$0\le k < n$, �� ����� ���������~$a_r\asg 1$, � 
��������� ������---���������~$a_r\asg 0$. 

\st[$B[a_1,~\ldots, a_r]$ �����?] ����~$C[a_1,~\ldots, a_r]<3\cdot 4^{r-1}$, 
������� �~\stp{6}.

\st[���������~$r$.] ����������~$r\asg r+1$ � ������������ �~\stp{3}.

\st[����������~$U_n$.] ���������~$C[a_1,~\ldots, a_r]$ ��~$1$. ����� 
$k$~���� ����� ��������~$C[a_1,~\ldots, a_r]$. ����������~$U_n\asg V_k$, 
��� ��������~$V_k$ ���������� ���� � �����~T.

\st[���������~$n$.] ���������~$n$ ��~$1$ � ������������ �~\stp{2}.
\algend

%% 179

������ ������, ��� �� ���� ��������, ��������� �� �� �������. �����, 
������, �������� ��� ���, ����� �� ������������, ����� $n$~��������� 
�������� ��������. �������� ����� ����� ������������� ���� ������������ 
����������, ���� �� ��������� "����������" ��� �������, ������� ��� ���� 
�����~$3\cdot 4^{r-1}$ �� ����~W4 ��~$2^r$.

��������~W �� ������������ ��� ���������� � �������� ������� ��������� 
�����, �� ������ ���� ������������� �����.

\proclaim �������~W. �����~$U_n$---������������������ ������������ �����, 
������������ � ������� ���������~W, �~$k$---������������� ����� �����. ���� 
���������������������~$\<U_n>\cR_k$ ����������, �� ��� $1\hbox{-������������}$.

\proof ����� $A[a_1,~\ldots, a_r]$ ���������� ��������������������� 
(����� ����, ������) ������������������~$\<U_n>$, ���������� �� � ������ 
�� ��������~$U_n$, ������� ��� ����~$j$, �����, ���~$1\le j \le r$, 
����������� ���������������������~$\<U_n>\cR_j$, ����~$a_j=1$, � �� 
����������� ���������������������~$\<U_n>\cR_j$, ����~$a_j=0$.

���������� ��������, ��� ��� ����~$r\ge 1$ � ���� ��� �������� 
�����~$a_1\ldots{}a_r$ �~$b_1\ldots{}b_r$ ����� ����� 
���������~$\Pr(U_n \in I_{b_1\ldots{}b_r})=2^{-r}$ �� ��������� � 
���������������������~$A[a_1\ldots{}a_r]$ � ��� ������, ����� ��������� 
���������� [��.~\eqref[30]]. � ����� ����, ����~$r\ge k$, �� ����������� 
������������������~$\<U_n>\cR_k$ ������������ ����� �������� ����������� 
���������������� ����������������������~$A[a_1,~\ldots, a_r]$ 
���~$a_k=1$ �~$a_j=0$ ���~$1$ ���~$1\le j \le r$, $j\ne k$; �������������, 
$\Pr(U_n\in I_{b_1\ldots{}b_r})=2^{-r}$ �� ��������� �~$\<U_n>\cR_k$ 
(��.~���.~33). ���������� ��������������� ��� ��������~A, ����� ��������, 
��� ������������������ $1\hbox{-������������}$.

����� $B[a_1,~\ldots, a_r]$ ���������� ��������������������� 
���������~$\<U_n>$, ��� �������~$C[a_1,~\ldots, a_r]$ ������������� �� 
������� �� ����~W6 ���������. ��� ����� �� ���������, 
$B[a_1,~\ldots, a_r]$---�������� ������������������, ������������ ����� 
��������� ������� �����~$3\cdot4^{r-1}$. ��� �����~$A[a_1,~\ldots, a_r]$, 
����� ��������� ��  �����,  �������  ��  
����������������������~$B[a_1,~\ldots, a_r,~\ldots, a_t]$, ���~$a_j=0$ 
���~$1$ ���~$r<j\le t$.

����������� ������, ���  $A[a_1,~\ldots, a_r]$ ���������� 
�~$A[a_1,~\ldots, a_r]=\<U_{s_n}>$, ���~$s_0<s_1<s_2<\ldots{}\,$. 
����~$N$---������� ����� �����, �����, ���~$4^r\le 4^q<N\le 4^{q+1}$, 
���������� ��������~$k<N$, ��� ������� $U_{s_k}$~���������� 
�~$I_{b_1\ldots{}b_r}$, ����� (�� ����������� ��������� ����� ��������� � 
������ ���������������������)
\EQ{
 \nu(N)=\nu(N_1)+\cdots+\nu(N_m).
}
%% 180
�����~$m$---���������� ����������������������~$B[a_1,~\ldots, a_t]$, 
������������� ����, � ������� $U_s$~���������� ��� ���������~$k<N$, 
$N_j$---���������� ��������~$k$, ��� ������� $U_{s_k}$~��������� � 
��������������� ���������������������, �~$\nu(N_j)$---���������� ����� 
��������, ������� ����� ��������� �~$I_{b_1\ldots{}b_r}$. ����� �������, 
�� �����~T �������, ���
\EQ{
 \eqalign{
  \abs{\nu(N)-2^{-r}N}&=\abs{\nu(N_1)-2^{-r}N_1+\cdots+\nu(N_m)-2^{-r}N_m}\le\cr
  &\le\abs{\nu(N_1)-2^{-r}N_1}+\cdots+\abs{\nu(N_m)-2^{-r}N_m}\le\cr
  &\le m \le 1+2+4+\cdots+2^{q-r+1}<2^{q+1}.\cr
 }
}
����������� ������������~$m$ ������� �� ���� �����, ���~$U_{s_N}$ 
��� ����� ������~$N$ ��������� �~$B[a_1,~\ldots, a_t]$ ��� 
����������~$t\le q+1$. 

����� �������,
\EQ{
 \abs{\nu(N)/N-2^{-r}}\le 2^{q+1}/N<2/\sqrt{N}.
}
\proofend

��� ���� ����� ������� �������� ������������� �������������������, 
��������������� �����������~R5, ������� ������ �����, ��� 
����~$\<U_n>$---������������������ ������������ ����� ��~$[0, 1)$ � 
����~$\cR$---���������� ������� ���������� ��������������������� ������ 
$b\hbox{-�����}$ ������������������, �� ����� ����������~$\cR$ � 
���������� �������~$\cR'$ ���������� ��������������������� 
������~$\<U_n>$, �������~$f'_n(x_1,~\ldots, x_n)$ �~$\cR'$ 
������~$f_n(\floor{bx_1},~\ldots, \floor{bx_n})$ �~$\cR$. ���� 
������������������~$\<U_n>\cR'$ ���������� ������������, �� ���� �� 
��������� �������� �~$\<\floor{bU_n}>\cR$. ��������� ���� ���������� 
������ ���������� ���������������������� $b\hbox{-�����}$ 
������������������� ��� ���� ���������~$b$ ������ (��������� ���������� 
���� ������� ���������� ����������� ����������), ������� ��� �������� 
����� ����������� � ���� ��������� ������������������~$\cR_1$, 
$\cR_2$,~$\ldots\,$. ������ �������, ��� ��������~W ���������� 
������������������ ��~$[0, 1)$, ������� �������� ��������� � ������ 
�����������~R5.

������ �� ��������� � ��������� �������������� ���������. ��� ���������� 
������, ����������� ��������, ������� ��������� �� ������������������, 
��������������� �����������~R4, ������������ �� �����, � �� ��� �� 
������� �� ����� ������������ ����������� ��������, ������������ 
������������������, ��������������� �����������~R5. �������������� 
������������� ����� ��������� ������������������ �� ������������� ������ 
���� ����������������. ����� �� ������� ��� ������������������ 
���������� �� ���������~W?

������������ ����� ���. ���� � ���, ��� ���������� � ������� 
������������ ��������� ������������� ��������� ���� ����������. ������� 
�������, ����������� ��������, �������
%% 181
\bye