\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