\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
