\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