\input style
\chapnotrue\chapno=3\subchno=4\subsubchno=1
\subsubchap{��ǰ���� �˱���� � ������ȸ�����\note{1}%
{� ��������� shuffling---°�������.---{\sl ����. �����.\/}}} % 3.4.2
��� ������º� ������ ǰ�¾ �˲��� ����ž���� ���ǰ��˼ ������� �
�����������½� �˱���� $n$~������� �� İ���, � ��¾��� ����������
$N$~�������. ⰺ�� ����ǰ ���������, ��������, ��� �������� ��ǵ�²� ��� �
��ó�� �°¸�¸ǵ���� ��Ǹ�������, ��� ��������� �˱����. ޱ�ǽ� $N$ �ǵ��
������, °� �¾ ������������ ������� ��� ����˵ � ����¸ ����������,
���¾�� �ö�� ���¸ °��� ��ĵ�¸���� ���Ƶ���� �˱��� $n$~�������,
��¾��� ��������� �� ����� ��Ȱ��, ������� ��� �º������ ������
���ž����� ������.

Ի� ��ȵ��� �¾� ����Ǹ �˻� ���������� ������̺� ��¾���. ݰ������
�ǵ����� °��� ���ž�, ����� �α�� ������ �˱������� � ����� � ¾� ��
�����½�����~$n/N$. ؽ���� �¾� ������ ����˲����� ô���˼, �� ��� ���
�����̷������ � �˱���� ����ǰ���� $n$~������� ¾�̺� � \emph{�������,}
���ǵ� �°����½�� �º������� �����~$\sqrt{n(1-(n/N))}$: �˱���� �����
��������� ��� ���Ⱥ�� ����Ⱦ�, ��� ���Ⱥ�� ����� ��� ���¸����� ��������
���û�°¾�.

�������� ������� ����ĸ��Ƹ� �¾�� "�ǵ�������" ��¾��, ��ȵ���� °����
�����°º�. ���� $m$~������� ö� �˻� �¾�����, �� ������ ����Ǹ��
$(t+1)\hbox{-�}$~������ � �˱���� � �����½�����~$(n-m)/(N-t)$. �°
�����½���� ���������� ������ °��� ����Ǹ���, ������̺� �� ���� ���������
�������� �˱��� $n$~������� ��~$N$ °��� �������, �¾ $m$~�� ���
�±������� �� �����~$t$,  � ¾ǽ��¸
$$
\perm{N-t-1}{n-m-1}\bigg/\perm{N-t}{n-m}={n-m\over N-t}
\eqno(1)
$$
���� �������� �˱����� $(t+1)\hbox{-�}$~ͻ�����.

����������� ���� ����� �ľ����� � ���� ������ɵ�� ������¼�:
\alg S.(ܵ¾� �˱����.) �˱���� ���ǰ��˼ ������� $n$~������� ��~$N$,
���~$0<n\le N$.

\st[ݰǰ�̽�� ��°�����.] ��°������~$t\asg 0$, $m\asg 0$.

\st[������°��~$U$.] ������°�� ���ǰ���� Ǹ���~$U$,
���������� �������������� ����� �û�� � �����Ƶ�.

\st[���������.] ����~$(N-t)U \ge n-m$, �����¸ �~\stp{5}.

%% 152

\st[�¾�����.] Һ��Ǹ�� ������ � �˱���� � ò���Ǹ��~$m$ �~$t$ ��~$1$.
����~$m<n$, �����¸ �~\stp{2}, � ���¸���� ���ǰ� �˱���� ������� �
������¼ �����ǵ�.

\st[������¸��.] ������¸�� ��������� ������ (�� ����ǰ�� �� � �˱����),
ò���Ǹ��~$t$ ��~$1$ � �����¸ �~\stp{2}.
\algend

ݰ ����˹ ����ϴ �¾� ������¼ ����� ���������� ��������˼ � ����
��������̽˼, �� �����µ�̽˹ ������ (��. ÿ��������, ����ɵ��˵ ����)
�����˲���, �¾ �� ������½� �����. ݵ��ô�� ñ�������, �¾
\medskip
\item{(a)}~�±������� \emph{�����} $n$~ͻ����¾�,
\item{(b)}~�˱���� �����ȵ��� ���ǰ���: � ǰ�½��¸, �����½���� �˱���
�α��� ��������� ͻ����°, �������� ���������� ͻ����° İ���, �����~$n/N$.
\medskip

�²��������~(b) ����������� �������� �� ¾, �¾ �� \emph{��} �˱�����
$(t+1)\hbox{-�}$~ͻ����� � �����½�����~$n/N$---�� �˱����� ��� �
���²���²�� � ľ��û��~(1)! �¾ ������� � ����¾��� ��°��Ƶ �
�ñ����Ƹ��. ܾ��� �� Ǹ°µ�� ��������� �¾ ����ɵ��� ���¸����Ǹ�?

({\sl װ��ǰ���.\/} Ի� ¾�� �¾�� �������� �������Ƹ� ����� �˱������,
����ǵ��˼� ��� �����ǽ�� ����ǵ°� �� ������¼�~S, ����õ� �����
�����ǽ˵ ��¾ǽ��� ���ǰ���� Ǹ���~$U$. Ի� �¾��, ��������, ����� �����
�����ǽ˵~$X_0$ � �������� ������ͽ½�� ��¾��. ׽�ǵ���~$X_0$ �����
���� ��Ϸ��� � ����������� ��¾�, ��� � ��������� ���ǵ����~$X$,
����ǵ��˼ � ����˴�ɵ� ����ǵµ.)

ޱ�ǽ� ��� �� �ö�� �ô�� ������������� ��� $N$~�������;
����²�µ�̽�, ������̺� �~(b) ú�����, �¾ ��������� ������ �˱������� �
�����½�����~$n/N$, � $(1-n/N)$~���� ���� ���ǰ��  ������¼ �����Ǹ� ����
������ \emph{������,} ǵ� ������ �� ��������� ������. ������� Ǹ���
������������� ������� ���~$n=2$ ���°��ϵ� �����~$(2/3)N$; ��ɸ� ľ��û�
���� � ÿ�.~5 �~6.

л����¼~S �������� ���� � ¾� ���ǰ�, ����� ����Ǹ��~$N$ ������� �����½�.
����������� µ����, �¾ �� ž¸� ���ǰ��˼ ������� �˱����
$n$~ͻ����¾� �� İ���, �� �� �����, �� ����̺�� ͻ����¾� �� ���¾��.
ܾ��� ���ǰ�� �����Ǹ°�� ��� ͻ������, � ��¾�, �¾�� ������� �˱����,
��������� �� �¾��ǽ�. ޴����, ����ɵ ������, ���ȵ ����� ��� �����ǵµ
�¾����� $m\ge n$~ͻ����¾�, ��� $m$~������� ����ȵ~$N$, � µ�, �¾��
�¾��� ��� ���������� ¾�̺� $m$~ͻ����¾�. ҵ�� ľ���, ���ü�����,
�����ǰ���� � ¾�, �¾�� � ���û�°µ ����Ǹ�� ��¸��� ���ǰ���� �˱����
�� �������ǰ�̽��� İ���.

ᵹǰ� �� ���ȵ� �����ü�˹ �����, ��������ɸ� ��� �����̽�
���������������� ����. Ծ���¸�, ������� ���Ǹ� ���ǰ���� Ǹ���,
�������˹ �������� �� ������� ���� $N$~�����ǽ��
%% 153
���ǵ���, ������ ǵ� �����-���� ���ǵ��� ���¾�����, ��������---�¾
�������� ������ͽ½�� ���������µ�̽���� � ��������, ����ȸ�~$N$. (Ի���
�������� ���ǽ� ���°����� ������̺� ����������.) Ի� ���Ǹ�� �����
������������� ������¼~3.2.2M, ����������˹ ܰ�������� � ܰ����̵�.

ش�� ���¾�� � ¾�, �¾�� ��Ǹ����� $N$~���ǰ���� ����Ǹ� � ��°������,
�����~$n$ �� ��� ϲ������ �������ȸ��. ι²���²��ɸ� �� $n$~������� �
���°��� ����ǰµ�̽�� �˱����. Ҿ ����� ������� �������� �� �������
"������ð�", � ��¾�˹ �ž��� ¾�̺� °��� $m$~�������---�������˵
��������� � �˱����, �¾ ����� ���²���²��ɸ�� �� ���ǰ��˼� ����Ǹ����
��� $n$ ����ȸ� ���ǵ��� (����˵ $n$~ͻ����¾� ������ �������� � ������ð�).

\alg R.(�˱���� � ������ð���.) Ի� ¾�� �¾�� ľ����������� �������˹
��ȵ ���Ƶ��, ������ ��������µ�̽�� °����� �� $n$~ͻ����¾� ����~$(Y, I)$,
���~$Y$---���ǰ���� ����Ǹ��, ���²���²��ɰ� $I\hbox{-�}$~������ �
������ð��. ҽ�ǰ�� �° °���ư Ƶ����� ��������� ͻ����°��~$(0, 0)$.

\st[ݰǰ�̽�� ��°�����.] ��°������~$m\asg 0$.

\st[������°��~$U$.] �����~$U$---���ǰ���� ����Ǹ��,
���������� �������������� ����� �û�� � �����Ƶ�. (ڰ� ������ϻ��� �����,
��������������, �¾ $U$ \emph{�� �����} �������� �� ����� ����ǵ���� ��
�¾� Ȱ�� ���ǰ���� Ǹ���.)

\st[���������.] ����� �������ȵ� ���ǵ���~$Y$ �� ��������µ�̽��
°���Ƶ~$(Y, I)$ �����~$Y_0$. ����~$U<Y_0$, �����¸ �~\stp{6}.

\st[Ծ������ � ������ð�.] ߵ�����¸ ��������� ������ �� İ��� � ������ð�
� ò���Ǹ��~$m$ ��~$1$.

\st[ޱ������ °�����.] װ������ ͻ����� °�����~$(Y_0, I_0)$ ��~$(U, m)$.
ߵ���¸ �~\stp{7}.

\st[������¸��.] ������¸�� ��������� ������ İ���.

\st[ھ��� İ���?] ���� � İ��� ����ȵ ��� �������, �����¸ �~\stp{8}, �
���¸���� ���ǰ�---�~\stp{2}.

\st[�¾��� �������.] �����¸������ ͻ������ °�����~$(Y, I)$ ��~$I$.
װ���� � ������ð��, ���²���²��ɸ� ���û�¸���ɸ�
���ǵ��ϼ~$I_1<I_2<\ldots<I_n$, ���°����� ����ǰµ�̽�� �˱����.
\algend

�°µ�� ������ �������°�� ������ ���������� �¾�� ������¼� � ÿ�.~9.

ⰱ����~$(Y, I)$ � ������¼�~R ����� ���°���� °��� �������, �¾
�����~$Y_0$ �� Ȱ��~R3 �ô�� �ǵ�� �����˼ � �������~$(U, m)$ �� Ȱ��~R5
°��� �ô�� ��ĵ�¸��˼. װ ����������ϼ� Ǹ°µ�� ���˻����� � ������¼��
�˱���� �����̵� � ��.~5.
%% 154

��� ���������� ������¼�~R ��������� ��µ�²���˹ ������:
ڰ��� �������˹ ������~$m$ ������ð��?" ط ÿ�.~11 ����õ�, �¾ �������
���ǵ���~$m$ �����~$n(1+H_N-H_n)$, �¾ ����������� �����~$n(1+\ln(N/n))$.
ỵ����µ�̽�, ���~$N/n=1000$ � ������ð��
�ô�� ��������µ�̽� � 125~��� ����ȵ ͻ����¾�, ǵ� � İ���.

װ��¸�, �¾ ������¼�~S �~R ����� �����̷����� ��� ¾��, �¾��
����ǰ�� �˱���� �� ������̺�� ���������˼ ��µ����ϼ ������������.
ݰ������, ���� ����Ⱦ� İ�� ���� � ������� ��µ��� ���, ����� ����Ǹ��
���ǰ��˵ �˱���� ����� �� 10~ǵ����� ������� �� 50~�°¾�, �� ���������
50~��� ���� İ�� � �� ���¸��� İ�� �� �°°�.

л����¼�~S �~R � ������̺� ��ó�� ��¾��� ����ǵ��� �˱����
���ö������ � �°�̵ �. 䰽�, �. ܰ����� � �. ൷�Ÿ
[{\sl Journal of the American Statistical Association,\/} {\bf 57} (1962), 387--402].
�¼�¸�, �¾ ������¼~S ���������� �������°� �.~Զ�ý�
[{\sl CACM,\/} {\bf 5} (1962), 343].


{\sl װ���� � �˱����,\/} ��� �� �� ����� ����˲���, ����� �������������
��� ��Ǹ������ ���ǰ����� ��ǵ°��� � ���²���²��
� ���ǽ˼ ������������ ��ǵ°��� �� $N$~ͻ����¾� ��~$n$ (��.~�.~1.2.6).
��������� µ���� ������ ��Ǹ������ ���ǰ���� \emph{�����°�����}
$t$~�����¾�. �� ������� �� \dfn{����ǵ� ������ȸ�����} (��� °�������),
������̺� °������� ������ �� 52~���� ���� ���ǰ���� �� �����°�����.

��ɵ�²��� ��� �������� ������� ������ȸ�����. � ������, ������������
�.~㻰��� � ��ǰ�� ��¸������� ����� �����̷õ���, ��������, ����
�����������, ������ �� ��¾��� ���������� ������������ �����°�����
ͻ����¾� $X_1$, $X_2$,~\dots, $X_t$. �����������, �¾ �ö�� ����Ǹ��
\emph{���������µ�̽����}  ���ǰ���� �����°�����. Ի� ����ǵ��� �ǵ������
�����°����� ��ȵ� ���������µ�̽��¸ �� ����²õ� �� ����˴���� �����
�� ��¸ �����°�����. �¸ ��� �����°����� �˱������� ���ǰ��˼ �������
� �� ��Ϸ�µ�̽� �»�ǰ���� ��ó �� ��ó�.

�¾� ��¾� ��ž� �� ������, ��¾�˼ �δ� ���ǽ� °���� ������ ����
(��.~ÿ�.~13). ܾ��� ����, Ǹ°µ�� �ô�� ��µ����� ÷����, �����
�����°����� ����ǰ���� � ������, ����°�������� �û����. Ի� ¾�� �¾��
�¾ ��������, ��¾� �������� �.~۾�ͽ� (���Ƹ����° �� ��Ǹ���µ�̽��
µŽ��� � °������� ����) ��ĸ��������� ���û�°�� ����
������ȸ����� ������ �� 52~����. ߾��Ǹ���� ������ɸ� �����°�����:
$$
\eqalign{
\pi_1&=(1\,23\,31)\,(2\,42\,20)\,(3\,34\,52\,48\,24\,28\,39\,50\,15\,40\,
41\,9\,17\,38\,25\,43\,47\,14\,8\,13\,35\,11\,22\,10\,12\,36\,49\,46\,44\,
4\,37)\,(5\,19\,18\,45)\,(6)\,(7\,30)\,(16\,51\,27\,32)\,(21\,29\,33\,26)\cr
\pi_2&=(1\,5\,24\,15\,36\,19)\,(2\,18\,27\,52\,37\,44\,25\,47\,50\,46\,20\,
7\,17\,10)\,(3\,28\,6\,39\,13\,23\,41\,43\,11\,38\,49\,12\,4\,34\,8\,40\,
21\,14\,30\,16\,45\,51\,22\,9\,33\,32\,35\,31\,26)\,(29\,42)\,(48)\cr
%% 154
\pi_3&=(1\,42\,19\,40\,30)\,(2\,51\,10\,34\,44\,48)\,(3\,12\,33\,49\,8\,
23\,20\,25\,14\,7\,43\,36)\, (4\,11\,26\,16\,46\,32\,24\,28\,9\,31\,29\,
52\,21\,5\,47\,13\,39\,38\,17\, 15\,37\,45\,6\,41\,50\,27)\,(18\,22\,35)\cr
}
$$
�¸ �����°����� �����°����� � ������� Ƹ���� (��.~�.~1.3.3). Ի� ¾��
�¾�� �������� ��ĵ�¸��˼ �������� ��������¸ �����°�����
���������µ�̽��¸ Ǹ���, ����õ� �����̷����� �� Ƹ���ǵ���� ���ú����.
����, ��������, �����̷����� \MIX, ������ �� ����������� ��ȵ �����°�����
����� ���� ����������������� ���
$$
\vcenter{
\mixcode
LDA & X+1
LDX & X+31
STX & X+1
LDX & X+23
STX & X+31
STA & X+23
LDA & X+2
LDX & X+20
\endmixcode
}
$$
�~�.~�.

�� ž¸� ���� ò����� � ¾�, �¾ ���� �����̷����� ��� ����� �� ��¸
�������� �����°����� � �������ɵ� ���������µ�̽��¸, ¾ ����� ����Ǹ��
��� $t!$~��������� �����°�����. ܾ��� ��������, �¾, ���� ���
�����°����� ������ɵ�� ����:
$$
\eqalignter{
\pi_1&=(1\,2) & \rem{(�α�� ������������ �����������ɸ��� Ƹ����, ����˹ �� ��� ��ǵ½�� �����),}\cr
\pi_2&=(1)& \rem{(�α�� Ƹ�� �����~$t-1$, � ��¾�˹ �� �ž��� ͻ�����~$1$),}\cr
}
\eqno(2)
$$
����ǵ�� � �����, ����� ����Ǹ�� �α�� �����°����� �� $t$~ͻ����¾� ��µ�
���������µ�̽��� ����������~$\pi_1$ �~$\pi_2$ � ����¾��� ���ϴ��
(��.~ÿ�.~12.) Զ.~Ը���� �������, �¾ ���¸~$3/4$ �� ���� ���
�����°����� �������� �¸� �����²�� ({\sl Math.~Z.,\/} {\bf 110} (1969), 199--205).

�¾��� ��¾� ������ȸ����� µ��� ��Ϸ�� � ������¼��~3.3.2P. �°µ��
������ ��������� � �¾�� ������¼�, ��¾�˹ ���� ����¾� ���²���²��
����� ������ �� $t!$~��������� �����°����� � ������� Ǹ��� $C[1]$,
$C[2]$,~\dots, $C[t]$, ���~$0\le C[j]<j$. ܾ��� ����� ����Ǹ�� ���ǰ��˹
����� Ǹ���, ����� ǵ�� � ������� ÿ��Ͻ�¾�� ���²���²�� ����Ǹ��
���ǰ���� �����°�����.

\alg P.(ߵ����ȸ�����.) ����� $X_1$, $X_2$,~\dots, $X_t$---����� $t$~Ǹ���,
��¾�˹ �ö�� ������Ȱ��.

\st[ݰǰ�̽�� ��°�����.] ��°������~$j\asg t$.

\st[������°��~$U$.] ������°�� ���ǰ���� Ǹ���~$U$,
���������� �������������� ����� �û�� � �����Ƶ�.

%% 156

\st[ޱ���.] ��°������~$k\asg \floor{jU}+1$. (⵿��� $k$~���� ���ǰ����
Ƶ��� Ǹ���, ������������� � �������º� �����~$1$ �~$j$.)
ҷ������������~$X_k\xchg X_j$.

\st[㼵��ȸ��~$j$.] 㼵��ȸ��~$j$ ��~$1$. ����~$j>1$, ������¸���� � Ȱ��~\stp{2}.
\algend

�¾� ������¼ �����˵ ��ñ�������� �.~ܾ��� � �.~�úľ�� (Tables of Random
Permutations (Stanford University Press, 1963)) � �.~����µ�ĵ��
({\sl CACM,\/} {\bf 7} (1964), 420). л����¼ ���ȵ, ǵ� ��¾� 㻰��, ��¾��
�¾ ��, � ����� ����, �������˲��� "����²�µ�̽� ���ǰ��˵" �����°����� �
�����̷õ� ������� ������.

\excercises
\ex[M12] ޱ�����µ ľ��û�~(1).

\ex[20] Ծ����µ, �¾ ��� �����̷������ ������¼�~S �±������� ¾ǽ�
$n$~������� ��� �������, �¾~$0<n \le N$.

\rex[22] � ������¼�~S $(t+1)\hbox{-�}$~ͻ����� �˱������� �
�����½�����~$(n-m)/(N-t)$, � \emph{��} $n/N$. � µ��µ, ������, ��������,
�¾ �˱�� ���������� �����������½�, °� �¾ ����˹ ͻ����� ������
�˱������� � \emph{������} �����½�����! ڰ��� ������� ����� ����
������������ ����������� ��� �¸ �²��������?

\ex[�23] ����� $p(m, t)$~���� �����½���� ¾��, �¾ �� ������
$t$~ͻ����¾� �˱������� �����~$m$. ߾�̷���� ���������²���� ������¼��~S,
������µ, �¾
$$
p(m, t)=\perm{t}{m}\perm{N-t}{n-m}\bigg/\perm{N}{n} \rem{��� $0\le t \le N$.}
$$

\ex[�24] 絼� ����� ������� ���ǵ���~$t$ � ������ �����ȵ���
������ ������¼�~S? (��ó��� �������, ����̺� ������� �� ��ɵ�� Ǹ���~$N$
�� ���������, ������ ǵ� �˱���� �ô�� �����ǵ��?)

\ex[M24] 絼� ����� �°����½�� �º������� ����Ǹ��, ��Ǹ�������
� ����˴�ɵ� ÿ��������?

\rex[�25] Ծ����µ, �¾ ��� �����̷������ ������¼�~S �α�� \emph{������˹}
����� �� $n$~������� �� ��ɵ�� Ǹ���~$N$ ����ǰ���� �
�����½�����~$1/\perm{N}{n}$. ⵼ ���˼ �ô�� ��������, �¾ �˱����
������������ �����ȵ��� �����������½�.

\rex[18] �¾ ���������� ��� ����µ ������¼�~R, ���� � İ���
���������� ����ȵ $n$~�������? ��������µ ��������� ����ĸ��Ƹ� ������¼�
��� �����ö���� °���� ���ǰ�.

\ex[22] �����������, �¾ �� �����̷õ� ������¼~R ���~$n=3$, �
İ�� ���¾�� �� 20~�������, � �� Ȱ��~R2 �˻� ����ǵ�� ������ɸ� ���ǰ��˵ ���ǵ���~$U$:
\ctable{
$#$,\bskip&&\bskip$#$,\bskip\cr
0.53 & 0.97 & 0.66 & 0.30 & 0.81 & 0.19 & 0.09 & 0.31 & 0.67 &  0.62 \cr
0.04 & 0.05 & 0.73 & 0.54 & 0.42 & 0.99 & 0.40 & 0.78 & 0.69 & 0.80;\cr
}
20~������� ���ü������� ��~$1$ ��~$20$. ڰ��� ������ ������� �
������ð�? ڰ��� ������ ������� � ����ǰµ�̽�� �˱����?

\ex[30] ڰ��� ������� �ö�� ������������ °�����~$(Y, I)$ �
������¼�~R (�� �¾� ÿ��������� � µ��µ), �¾�� ��ĵ�¸��� �˿���ϻ���
����� � ������� �� Ȱ���~R3 �~R5?

\rex[�25] �����������, �¾ $p_m$~���� �����½���� ¾��, �¾ ���
������ �������� �� ������¼�~R � ������ð� ������� ����� $m$~ͻ����¾�. ޿������µ
%% 157
������������ �ý�Ƹ�~$G(z)=\sum_m p_m z^m$ � ��Ǹ���µ ������� �
�°����½�� �º������� (�����̷ùµ ��µ���� �.~1.2.10).

\ex[�23] �����~$\pi_1$, $\pi_2$---�����°�����, �������ϵ�˵
���½�ȵ��ϼ�~(2). Ծ����µ �������������� ������ɸ� �²��������,
(a)~ݵ��¾��� �µ����~$\pi_1$ ����� Ƹ���~$(1\,2)$. (b)~ݵ��¾���
������������ $\pi_1$ �~$\pi_2$ ����� Ƹ���~$(1\,k)$ ��� �α���~$k$, $2\le k \le t$.
(c)~�α�� Ƹ��~$(j\,k)$, $j\ne k$, ����� ���� ����ǵ� ���
������������ $\pi_1$ �~$\pi_2$. (d)~��� �����°����� �� $t$~ͻ����¾�
����� ���� ����ǵ�� ��� ������������ $\pi_1$ �~$\pi_2$.

\ex[M23] (�.~Ӿ����.) ޱ�ǽ˹ ������ °������� ���� ���¾�� � ������ɵ�:
������ �������'�� ��� �� ���������¸ ����˵ ǰ�¸, ��¾�˵ ��°�������
���� � ��ó��. (� �������� ���¾ǽ�� ���, ��ñ���������� 徹���, Ǹ°��:
"Ի� ¾�� �¾�� ž��Ⱦ ������Ȱ�� ����� °��� ��������, �ö�� ����°������
�� ����� ���� ���".) ��������� ������ �� $2n-1$~���� $X_1$, $X_2$,~\dots,
$X_{2n-1}$. ޿���Ƹ� "�����̽��� °�������"~$s$ ������ϵ� ������ �� ���
ǰ�¸ $X_1$, $X_2$,~\dots{}, $X_n$ �~$X_{n+1}$,~\dots, $X_{2n-1}$ �
�����̽� ���ȸ���� �� °�, �¾ ����ǰ���� ���������µ�̽���� $X_1$,
$X_{n+1}$, $X_2$, $X_{n+2}$,~\dots, $X_{2n-1}$, $X_n$. ޿���Ƹ�
"���¸�"~$c^j$ ��������� ���������µ�̽���� $X_1$, $X_2$,~\dots,
$X_{2n-1}$ � ���������µ�̽����  $X_{j+1}$,~\dots, $X_{2n-1}$, $X_1$,~\dots,
$X_j$. ߾����µ, �¾ ��� �������������� "�����̽�� °�������" �
"���¸�" ����� ����Ǹ�� �� ����� ǵ� $(2n-1)(2n-2)$~�����ǽ��
���������µ�̽��µ� ���� ��� �������, �¾~$n>1$.

%% 158
\subchap{* ��� ����� ��������� ������������������?} % 3.5*

\section{A. Ҳ���˵ ����ǰ���}. � �¾� ����� ö� ���������� � ¾�, ���
����ǰ�� ���������µ�̽��¸
$$
\<U_n>=U_0, U_1, U_2, \ldots
\eqno(1)
$$
����²�µ�̽�� Ǹ���, �����ǵ���� ����� �û�� � �����Ƶ�, �.~�.\ °���,
�¾~$0\le U_n<1$. �¸ ���������µ�̽��¸ ���˲����� "���ǰ��˼�", ž�� ��
������� ����ǵ��� ��� �˻� �����ȵ��� ��µ�����������˼�. Ի� ¾�� �¾��
��������� �¾ ��������, �� ������, �¾ Ǹ��� "����� ���� °�, ��� ���� ��
��� �˻� ����²�µ�̽� ���ǰ��˼�". Ի� ����¸ǵ���� Ƶ��� (� ���¾�ɵ�
�����) °���� ��ϲ����� ����� ���� � ���°¾ǽ�, ������ ���
��ž��� ���� �ǵ�� ����˹ ĸ��������� � µ���¸ǵ���� ������: ��� ¾ǽ�
�ľ��û�������, �¾ ������ �� ������ü����� ���
"���ǰ��˼ ����������"? �ö�� ���������� ����ǵ�²����� �����������
���ǰ����� ���������. ݵ ����õ� ���̷������� ����¸ϼ�, ��¾���
��-���¾�ɵ�� �� ���������, µ� ����� �¾ � ���ǰ���� Ǹ���� �����
��������� ����� �� ����˹ ����ϴ ����������̽�� �²��������.

ܰµ��¸ǵ���� �°¸�¸�� � µ���� �����½��µ� �ɰµ�̽� �������� �²�°
�� ��� ������, ������̺� �¸ ��ú� �������������� �� ������½��
�²��������. Ҽ��¾ �¾�� ��������������� ������ � ¾�, �����
\emph{�����½����}  ����õ� ��������� ������˲���ϼ, ��Ϸ���˼ ��
���ǰ��˼� ���������µ�̽���ϼ� ����������� ����¸�. к����� µ����
�����½��µ� ��������� ��� ��ô�
��Ǹ����� �������½˵ �����½��¸, ������ ��� �¾� ��°���� �����˼, �¾
�� � ����²�µ�̽��¸ ����ǰ�� ����¸� �����½��¸, ��� ��� �¾ ����¸�
����� ���������� ��������� � ϲ����ϼ ���ö��ɵ�� ����. �.~ľ�~ܸ��� �
����� "ҵ���½����, �°¸�¸�� � ��¸��" (Probability, Statistics, and
Truth, Macmillan, 1957) �������� ���ö���� �¾ ��������� � ������˲��� °���
¾Ǻ� ������, �¾ ����������� �����½��¸ ������� �� ¾�� ��� ����������
���ǰ���� ���������µ�̽����.

�������� ��� �������� ����¸� ���ǰ���� ���������µ�̽��¸, �������
����������˵ ��ü� ��¾����.
{\medskip\narrower
{\sl �.~X.~۵��� (1951 �.):\/} "��ǰ���� ���������µ�̽���� ���� �����
�����˲ǰ¾� ����¸�, �����ɰ�ɵ� ���� ���������µ�̽��¸, � ��¾���
����˹ ǻ�� ����������õ� ���
%% 159
�������ɵ����� � ͻ������ ��¾��� ô����²����� �ϴ� �����Ƹ����� �����
�°¸�¸��� ���µ����, � �����½�� �µ���� ������ɸ� �� ¾��, ��� �����
���������� ��ö�� �° ���������µ�̽����".

{\sl Զ.~�.~��ͽ���� (1962~�.):\/} "߾�������µ�̽����~(1) ���ǰ���, ����
��� �������� �α˼ �����²��, ��¾�˼ �������� ��� �������ǽ˵
���������µ�̽��¸ ����������� �˱���� ���ǰ���� ���������� ��
������������ �������������"
\medskip}

޿��������� ��ͽ����� ��ɵ�²���� ����ɰ�� ����������� ۵����, ������̺�
��� ����õ�, �¾�� ���������µ�̽���� ô����²��ϻ� \emph{����}
�°¸�¸ǵ���� ���µ��ϼ. ճ� ����������� �� ϲ�ϵ��� ������½� ¾ǽ˼, �
����� �� ñ������ � ¾�, �¾ ���ü��� ��� ��µ����°Ƹ� �������� �
����ư��� ��ɵ�²������ °���� �����°, ��� ���ǰ����
���������µ�̽����! ⰺ�� �������, ��� ���Ⱥ�� ������Ǹµ�̽�, ���¾��
����°���� �¾ǽ��� \emph{����������� ۵����.} �� ž¸� ����Ǹ��
�½���µ�̽� ����º�� ����ǵ�� ��µ��¸ǵ���� �����², ������ �� ��¾���
�� ���¸����Ǹ� ��ȵ�� ���ø¸����� �����°������ �
���ǰ���� ���������µ�̽��¸. ����� ¾��, �¾� ����ǵ�� ������ ����
���°¾ǽ� ����˼ ��� ¾��, �¾�� \emph{�α��} ���������µ�̽����,
���������� ����Ǹ�����˼� �����²���, ����� �˻� �� �½��¸ � "���ǰ��˼".
�, �¾ �� �������°�� � ���¾�ɵ� �������, �ô��, ��-��������,
ô����²���µ�̽˼, � ¾Ǻ� ������ ����������� ��ȵ �����������,
������������ ���ǰ����¸, ž�� ��� �¾� ��°����� ��� �²�° ������
��µ����˵ �������.

�����~$u$ �~$v$---����²�µ�̽˵ Ǹ���, $0\le u < v \le 1$.
����~$U$---���ǰ���� ����Ǹ��, ���������� �������������� �����~$0$ �~$1$, ¾
�����½���� ¾��, �¾~$u\le U < v$, �����~$v-u$. ݰ������, ����~$u=1/3$
�~$v=2/3$, �����½���� ¾��, �¾~$1/3\le U < 2/3$, �����~$1/3$. ڰ�
����ɸ�� �¾ �����²� �� ���ǰ� �������ǽ�� ���������µ�̽��¸~$U_0$,
$U_1$, $U_2$,~\dots? �ǵ����˹ �²�� ���¾�� � ¾�, �¾ ���� ���Ǹ°��,
����̺� ��� $U_n$~�������� � ��µ���� �����~$u$ �~$v$, ¾ ������� Ǹ���
��������� ������ ���� ����� ����Ǹ��~$v-u$. н�����ǽ˼ ������� ���������
���ø¸���� ����¸� �����½��¸: ��� �����˲����� �� ǰ�¾µ
��ϲ����� ����¸�. ���� ���� ����� ¾ǽ˼, ������Ǹ� ǵ���~$\nu(n)$
Ǹ��� ���ǵ���~$j$, $0\le j < n$, °���, �¾~$u\le U_j < v$. �� ž¸�,
�¾�� �½�ȵ���~$\nu(n)/n$ ���������� �~$v-u$ ��� ����������~$n$ � �������ǽ��¸:
$$
\lim_{n\to\infty} \nu(n)/n=v-u.
\eqno(2)
$$
���� �¾ ������� ô����²��ϵ��� ��� �α�� �˱���~$u$ �~$v$,
���������µ�̽���� �ô�� ���˲��� \dfn{���������� ��������������.}

ޱ����Ǹ� ǵ���~$S(n)$ ����¾��� �²�������� �½���µ�̽� Ƶ���� Ǹ���~$n$
� ���������µ�̽��¸~$U_1$, $U_2$,~$\ldots\,$. ݰ������,
%% 160
$S(n)$~����� ���� ���������˼ ��ȵ �²���������: "$u\le U_n < v$". ܾ���
����ɸ�� ����ö�����, ���������˵ � ����˴�ɵ� ����Ƶ, � ����������
"�����½���� ¾��, �¾ $S(n)$~��¸���" �� �½�ȵ��� � ������������
�������ǽ�� ���������µ�̽��¸. �����~$\nu(n)$---Ǹ��� ���ǵ���~$j$, $0\le j <n$,
°���, �¾~$S(j)$~��¸���.

\proclaim ޿���������~A. Ӿ�����, �¾~$\Pr (S(n))=\lambda$,
����~$\lim_{n\to\infty} \nu(n)/n=\lambda$. (� ��������� ľ��� "�����½����
¾��, �¾ $S(n)$~��¸���, �����~$\lambda$, ���� ������~$\nu(n)/n$ ���~$n$,
������ɵ��� � �������ǽ��¸, ����~$\lambda$".)

߾�̷���� �¸� ������������, ����� �������, �¾ ���������µ�̽����~$U_0$,
$U_1$,~\dots{} ���������� ������������ � ¾� � ¾�̺� ¾� ���ǰ�,
����~$\Pr(u\le U_n < v)=v-u$ ��� ���� ����²�µ�̽��~$u$, $v$, °���,
�¾~$0\le u < v \le 1$.

߾�������µ�̽���� ����� ���� ���������� ��������������, �� �� ���ǰ����.
����, ��������, $U_0$, $U_1$,~\dots{} �~$V_0$, $V_1$,~\dots---��� ����������
������������˵ ���������µ�̽��¸, ¾ ����ô�� ��������, �¾ ���������µ�̽����
$$
W_0, W_1, W_2, W_3, \ldots = {1\over 2}U_0, {1\over 2}+{1\over 2}V_0,
{1\over2}U_1, {1\over2}+{1\over2}V_1,\ldots
\eqno(3)
$$
°��� ���������� ������������, ������̺� ���������µ�̽����~${1\over2}U_0$,
${1\over 2}U_1$,~\dots{} ���������� ������������ �����~$0$ �~$1/2$, �
ǵ�����ɰ��� � ��� ���������µ�̽����~${1\over 2}+{1\over 2}V_0$,
${1\over 2}+{1\over 2}V_1$,~\dots{} ���������� ������������ �����~$1/2$ �~$1$.
� ���������µ�̽��¸~$W$ �� ����Ǹ���, ����ȵ�~$1/2$, ������ ����õ�
����Ǹ��, ����Ȱ�~$1/2$, � ����½�, °� �¾ �° ���������µ�̽���� ��
ϲ�ϵ��� ���ǰ���� �� � ����� ���ü��� ������. ݰ� �ö�� �����²�
����� ���̽��, ǵ� ����������� ����������������.

������, ���������˹ � ����˴�ɵ� ����Ƶ, �������� � ��µ�²������
����ɵ��� �����²� ����������� ��������������¸, � ������ � ������������
��� �������� ͻ����¾� ���������µ�̽��¸. ܾ��� �����������, �¾�� ���
�α�� ǵ����� Ǹ���~$u_1$, $v_1$, $u_2$, $v_2$, °���, �¾~$0\le u_1 < v_1 \le 1$,
$0\le u_2 < v_2 \le 1$,  ���������µ�̽���� ô����²��ϻ� ����������
$$
\Pr(u_1\le U_n < v_1 \rand u_2\le U_{n+1}<v_2)=(v_1-u_1)(v_2-u_2).
\eqno(4)
$$
Ѿ��� ¾��, ��� �α��� ������µ�̽��� Ƶ���� Ǹ���~$k$ �����
����¸ ����¸� \dfn{$k\hbox{-��������������}$} ���������µ�̽��¸.

\proclaim ޿���������~B. Ӿ�����, �¾ ���������µ�̽����~(1)
$k\hbox{-pacnpe������}$, ����
$$
\Pr(u_1\le U_n < v_1, \ldots, u_k\le U_{n+k-1}<v_k)=(v_1-u_1)\ldots(v_k-u_k)
\eqno(5)
$$
��� �α�� ����²�µ�̽�� Ǹ���~$u_j$, $v_j$, °���, �¾~$0\le u_j<v_j\le 1$
���~$1 \le j \le k$.

%% 161
\bye
