\input style
\chapnotrue\chapno=3\subchno=4\subsubchno=1
\subsubchap{sLUCHAJNAYA VYBORKA I PEREMESHIVANIE\note{1}%
{v ORIGINALE shuffling---TASOVANIE.---{\sl pRIM. PEREV.\/}}} % 3.4.2
pRI OBRABOTKE DANNYH CHASTO BYVAET NEOBHODIMO SLUCHAJNYM OBRAZOM I
BESPRISTRASTNO VYBRATX $n$~ZAPISEJ IZ FAJLA, V KOTOROM SODERZHITSYA
$N$~ZAPISEJ. tAKAYA ZADACHA VOZNIKAET, NAPRIMER, PRI KONTROLE KACHESTVA ILI V
DRUGIH STATISTICHESKIH VYCHISLENIYAH, GDE TREBUYUTSYA VYBORKI. oBYCHNO $N$ OCHENX
VELIKO, TAK CHTO ODNOVREMENNO HRANITX VSE DANNYE V PAMYATI NEVOZMOZHNO,
PO|TOMU NUZHNO NAJTI TAKUYU |FFEKTIVNUYU PROCEDURU VYBORA $n$~ZAPISEJ,
KOTORAYA POZVOLILA BY SRAZU RESHATX, PRINYATX ILI OTKLONITX KAZHDUYU
PROHODYASHCHUYU ZAPISX.

dLYA RESHENIYA |TOJ ZADACHI BYLO PREDLOZHENO NESKOLXKO METODOV. nAIBOLEE
OCHEVIDEN TAKOJ PODHOD, KOGDA LYUBAYA ZAPISX VYBIRAETSYA S ODNOJ I TOJ ZHE
VEROYATNOSTXYU~$n/N$. iNOGDA |TOT SPOSOB OKAZYVAETSYA UDOBNYM, NO PRI EGO
ISPOLXZOVANII V VYBORKE POLUCHAETSYA $n$~ZAPISEJ TOLXKO V \emph{SREDNEM,}
PRICHEM STANDARTNOE OTKLONENIE RAVNO~$\sqrt{n(1-(n/N))}$: VYBORKA MOZHET
OKAZATXSYA ILI SLISHKOM BOLXSHOJ, ILI SLISHKOM MALOJ DLYA DOSTIZHENIYA ZHELAEMYH
REZULXTATOV.

pRIVEDEM PROSTUYU MODIFIKACIYU |TOGO "OCHEVIDNOGO" METODA, LISHENNUYU TAKOGO
NEDOSTATKA. eSLI $m$~ZAPISEJ UZHE BYLO OTOBRANO, MY DOLZHNY VKLYUCHITX
$(t+1)\hbox{-YU}$~ZAPISX V VYBORKU S VEROYATNOSTXYU~$(n-m)/(N-t)$. eTA
VEROYATNOSTX VYRAZHAETSYA IMENNO TAKOJ VELICHINOJ, POSKOLXKU IZ VSEH VOZMOZHNYH
SPOSOBOV VYBORA $n$~ZAPISEJ IZ~$N$ TAKIM OBRAZOM, CHTO $m$~IZ NIH
OTBIRAYUTSYA IZ PERVY~$t$,  V TOCHNOSTI
$$
\perm{N-t-1}{n-m-1}\bigg/\perm{N-t}{n-m}={n-m\over N-t}
\eqno(1)
$$
DOLYA SPOSOBOV VYBIRAET $(t+1)\hbox{-J}$~|LEMENT.

vYSKAZANNUYU IDEYU MOZHNO OFORMITX V VIDE SLEDUYUSHCHEGO ALGORITMA:
\alg S.(mETOD VYBORKI.) vYBRATX SLUCHAJNYM OBRAZOM $n$~ZAPISEJ IZ~$N$,
GDE~$0<n\le N$.

\st[nACHALXNAYA USTANOVKA.] uSTANOVITX~$t\asg 0$, $m\asg 0$.

\st[vYRABOTATX~$U$.] vYRABOTATX SLUCHAJNOE CHISLO~$U$,
RAVNOMERNO RASPREDELENNOE MEZHDU NULEM I EDINICEJ.

\st[pROVERITX.] eSLI~$(N-t)U \ge n-m$, PEREJTI K~\stp{5}.

%% 152

\st[oTOBRATX.] vKLYUCHITX ZAPISX V VYBORKU I UVELICHITX~$m$ I~$t$ NA~$1$.
eSLI~$m<n$, PEREJTI K~\stp{2}, V PROTIVNOM SLUCHAE VYBORKA SDELANA I
ALGORITM ZAKONCHEN.

\st[pROPUSTITX.] pROPUSTITX SLEDUYUSHCHUYU ZAPISX (NE VKLYUCHATX EE V VYBORKU),
UVELICHITX~$t$ NA~$1$ I PEREJTI K~\stp{2}.
\algend

nA PERVYJ VZGLYAD |TOT ALGORITM MOZHET POKAZATXSYA NENADEZHNYM I DAZHE
NEPRAVILXNYM, NO VNIMATELXNYJ ANALIZ (SM. UPRAZHNENIYA, POMESHCHENNYE NIZHE)
POKAZYVAET, CHTO ON ABSOLYUTNO VEREN. nETRUDNO UBEDITXSYA, CHTO
\medskip
\item{(a)}~OTBIRAETSYA \emph{ROVNO} $n$~|LEMENTOV,
\item{(b)}~VYBORKA SOVERSHENNO SLUCHAJNA: V CHASTNOSTI, VEROYATNOSTX VYBORA
LYUBOGO ZADANNOGO |LEMENTA, NAPRIMER POSLEDNEGO |LEMENTA FAJLA, RAVNA~$n/N$.
\medskip

uTVERZHDENIE~(b) SPRAVEDLIVO NESMOTRYA NA TO, CHTO MY \emph{NE} VYBIRAEM
$(t+1)\hbox{-J}$~|LEMENT S VEROYATNOSTXYU~$n/N$---MY VYBIRAEM EGO V
SOOTVETSTVII S FORMULOJ~(1)! eTO PRIVELO K NEKOTOROJ PUTANICE V
PUBLIKACIYAH. mOZHET LI CHITATELX OB®YASNITX |TO KAZHUSHCHEESYA PROTIVORECHIE?

({\sl zAMECHANIE.\/} dLYA TOGO CHTOBY IZBEZHATX KORRELYACIJ MEZHDU VYBORKAMI,
POLUCHENNYMI PRI RAZLICHNYH PROSCHETAH PO ALGORITMU~S, SLEDUET BRATX
RAZLICHNYE ISTOCHNIKI SLUCHAJNYH CHISEL~$U$. dLYA |TOGO, NAPRIMER, MOZHNO BRATX
RAZLICHNYE~$X_0$ V LINEJNOM KONGRU|NTNOM METODE. zNACHENIE~$X_0$ MOZHET
BYTX SVYAZANO S KALENDARNOJ DATOJ, ILI S POSLEDNIM ZNACHENIEM~$X$,
POLUCHENNYM V PREDYDUSHCHEM PROSCHETE.)

oBYCHNO NAM NE NUZHNO BUDET PROSMATRIVATX VSE $N$~ZAPISEJ;
DEJSTVITELXNO, POSKOLXKU V~(b) UKAZANO, CHTO POSLEDNYAYA ZAPISX VYBIRAETSYA S
VEROYATNOSTXYU~$n/N$, V $(1-n/N)$~DOLE VSEH SLUCHAEV  ALGORITM ZAKONCHIT SVOYU
RABOTU \emph{PREZHDE,} CHEM DOJDET DO POSLEDNEJ ZAPISI. sREDNEE CHISLO
RASSMOTRENNYH ZAPISEJ DLYA~$n=2$ SOSTAVLYAET OKOLO~$(2/3)N$; OBSHCHIE FORMULY
DANY V UPR.~5 I~6.

aLGORITM~S PRIMENIM LISHX V TOM SLUCHAE, KOGDA VELICHINA~$N$ ZARANEE IZVESTNA.
pREDPOLOZHIM TEPERX, CHTO MY HOTIM SLUCHAJNYM OBRAZOM VYBRATX
$n$~|LEMENTOV IZ FAJLA, NO NE ZNAEM, IZ SKOLXKIH |LEMENTOV ON SOSTOIT.
mOZHNO SNACHALA PERESCHITATX VSE |LEMENTY, A POTOM, CHTOBY SDELATX VYBORKU,
PEREBRATX IH VTORICHNO. oDNAKO, VOOBSHCHE GOVORYA, LUCHSHE SRAZU PRI PERESCHETE
OTOBRATX $m\ge n$~|LEMENTOV, GDE $m$~GORAZDO MENXSHE~$N$, S TEM, CHTOBY
VTOROJ RAZ PEREBIRATX TOLXKO $m$~|LEMENTOV. vESX FOKUS, RAZUMEETSYA,
ZAKLYUCHAETSYA V TOM, CHTOBY V REZULXTATE POLUCHITX ISTINNO SLUCHAJNUYU VYBORKU
IZ PERVONACHALXNOGO FAJLA.

sEJCHAS MY OPISHEM OSTROUMNYJ PRIEM, REALIZUYUSHCHIJ |TU DOVOLXNO
NEPRAVDOPODOBNUYU IDEYU. dOPUSTIM, IMEETSYA DATCHIK SLUCHAJNYH CHISEL,
SPOSOBNYJ PORODITX PO KRAJNEJ MERE $N$~RAZLICHNYH
%% 153
ZNACHENIJ, PREZHDE CHEM KAKOE-LIBO ZNACHENIE POVTORITSYA, NAPRIMER---|TO
LINEJNAYA KONGRU|NTNAYA POSLEDOVATELXNOSTX S PERIODOM, BOLXSHIM~$N$. (dLINY
PERIODOV OBYCHNO SOSTAVLYAYUT NESKOLXKO MILLIARDOV.) dLYA DATCHIKA MOZHNO
REKOMENDOVATX ALGORITM~3.2.2M, PREDLOZHENNYJ mAKLARENOM I mARSALXEJ.

iDEYA SOSTOIT V TOM, CHTOBY VYCHISLITX $N$~SLUCHAJNYH VELICHIN I USTANOVITX,
KAKIE~$n$ IZ NIH YAVLYAYUTSYA NAIBOLXSHIMI. sOOTVETSTVUYUSHCHIE IM $n$~ZAPISEJ I
SOSTAVYAT OKONCHATELXNUYU VYBORKU. vO VREMYA PERVOGO PEREBORA MY SOZDAEM
"REZERVUAR", V KOTORYJ VHODYAT TOLXKO TAKIE $m$~ZAPISEJ---VOZMOZHNYE
KANDIDATY V VYBORKU, CHTO PERED SOOTVETSTVUYUSHCHIMI IM SLUCHAJNYMI VELICHINAMI
NET $n$ BOLXSHIH ZNACHENIJ (PERVYE $n$~|LEMENTOV VSEGDA POPADAYUT V REZERVUAR).

\alg R.(vYBORKA S REZERVUAROM.) dLYA TOGO CHTOBY FORMALIZOVATX OPISANNYJ
VYSHE PROCESS, VVEDEM VSPOMOGATELXNUYU TABLICU IZ $n$~|LEMENTOV VIDA~$(Y, I)$,
GDE~$Y$---SLUCHAJNAYA VELICHINA, SOOTVETSTVUYUSHCHAYA $I\hbox{-J}$~ZAPISI V
REZERVUARE. vNACHALE |TA TABLICA CELIKOM ZAPOLNENA |LEMENTAMI~$(0, 0)$.

\st[nACHALXNAYA USTANOVKA.] uSTANOVITX~$m\asg 0$.

\st[vYRABOTATX~$U$.] pUSTX~$U$---SLUCHAJNAYA VELICHINA,
RAVNOMERNO RASPREDELENNAYA MEZHDU NULEM I EDINICEJ. (kAK OB®YASNYALOSX RANEE,
PREDPOLAGAETSYA, CHTO $U$ \emph{NE RAVNO} NIKAKOMU IZ RANEE POLUCHENNYH NA
|TOM SHAGE SLUCHAJNYH CHISEL.)

\st[pROVERITX.] pUSTX NAIMENXSHEE ZNACHENIE~$Y$ VO VSPOMOGATELXNOJ
TABLICE~$(Y, I)$ RAVNO~$Y_0$. eSLI~$U<Y_0$, PEREJTI K~\stp{6}.

\st[dOBAVITX V REZERVUAR.] pERENESTI SLEDUYUSHCHUYU ZAPISX IZ FAJLA V REZERVUAR
I UVELICHITX~$m$ NA~$1$.

\st[oBNOVITX TABLICU.] zAMENITX |LEMENT TABLICY~$(Y_0, I_0)$ NA~$(U, m)$.
pEREJTI K~\stp{7}.

\st[pROPUSTITX.] pROPUSTITX SLEDUYUSHCHUYU ZAPISX FAJLA.

\st[kONEC FAJLA?] eSLI V FAJLE BOLXSHE NET ZAPISEJ, PEREJTI K~\stp{8}, V
PROTIVNOM SLUCHAE---K~\stp{2}.

\st[vTOROJ PEREBOR.] oTSORTIROVATX |LEMENTY TABLICY~$(Y, I)$ PO~$I$.
zAPISI V REZERVUARE, SOOTVETSTVUYUSHCHIE REZULXTIRUYUSHCHIM
ZNACHENIYAM~$I_1<I_2<\ldots<I_n$, SOSTAVLYAYUT OKONCHATELXNUYU VYBORKU.
\algend

chITATELX DOLZHEN PRORABOTATX PRIMER PRIMENENIYA |TOGO ALGORITMA V UPR.~9.

tABLICU~$(Y, I)$ V ALGORITME~R MOZHNO SOSTAVITX TAKIM OBRAZOM, CHTO
POISK~$Y_0$ NA SHAGE~R3 BUDET OCHENX BYSTRYM I PERENOS~$(U, m)$ NA SHAGE~R5
TAKZHE BUDET |FFEKTIVNYM. zA PODROBNOSTYAMI CHITATELX OTSYLAETSYA K ALGORITMAM
VYBORKI DEREVXEV V GL.~5.
%% 154

pRI PRIMENENII ALGORITMA~R VOZNIKAET ESTESTVENNYJ VOPROS:
kAKOV OZHIDAEMYJ RAZMER~$m$ REZERVUARA?" iZ UPR.~11 SLEDUET, CHTO SREDNEE
ZNACHENIE~$m$ RAVNO~$n(1+H_N-H_n)$, CHTO PRIBLIZHENNO RAVNO~$n(1+\ln(N/n))$.
sLEDOVATELXNO, PRI~$N/n=1000$ V REZERVUARE
BUDET PRIBLIZITELXNO V 125~RAZ MENXSHE |LEMENTOV, CHEM V FAJLE.

zAMETIM, CHTO ALGORITMY~S I~R MOZHNO ISPOLXZOVATX DLYA TOGO, CHTOBY
POLUCHATX VYBORKI PO NESKOLXKIM NEZAVISIMYM KATEGORIYAM ODNOVREMENNO.
nAPRIMER, IMEYA BOLXSHOJ FAJL IMEN I ADRESOV ZHITELEJ ssha, MOZHNO POLUCHITX
SLUCHAJNYE VYBORKI ROVNO PO 10~CHELOVEK KAZHDOGO IZ 50~SHTATOV, NE PEREBIRAYA
50~RAZ VESX FAJL I NE SORTIRUYA FAJL PO SHTATAM.

aLGORITMY~S I~R I NESKOLXKO DRUGIH METODOV POLUCHENIYA VYBOROK
OBSUZHDAYUTSYA V STATXE ch. fANYA, m. mALLERA I i. rEZUHI
[{\sl Journal of the American Statistical Association,\/} {\bf 57} (1962), 387--402].
oTMETIM, CHTO ALGORITM~S NEZAVISIMO RAZRABOTAL t.~dZHOUNS
[{\sl CACM,\/} {\bf 5} (1962), 343].


{\sl zADACHU O VYBORKE,\/} KAK MY EE ZDESX OPISYVAEM, MOZHNO RASSMATRIVATX
KAK VYCHISLENIE SLUCHAJNOGO SOCHETANIYA V SOOTVETSTVII
S OBYCHNYM OPREDELENIEM SOCHETANIYA IZ $N$~|LEMENTOV PO~$n$ (SM.~P.~1.2.6).
rASSMOTRIM TEPERX ZADACHU VYCHISLENIYA SLUCHAJNOJ \emph{PERESTANOVKI}
$t$~OB®EKTOV. mY NAZOVEM EE \dfn{ZADACHEJ PEREMESHIVANIYA} (ILI TASOVANIYA),
POSKOLXKU TASOVANIE KOLODY IZ 52~KART ESTX SLUCHAJNAYA IH PERESTANOVKA.

sUSHCHESTVUYUT DVA OSNOVNYH SPOSOBA PEREMESHIVANIYA. v PERVOM, PREDLOZHENNOM
s.~uLAMOM V NACHALE PYATIDESYATYH GODOV ISPOLXZUETSYA, NAPRIMER, PYATX
PODPROGRAMM, KAZHDAYA IZ KOTORYH PROIZVODIT OPREDELENNUYU PERESTANOVKU
|LEMENTOV $X_1$, $X_2$,~\dots, $X_t$. pREDPOLOZHIM, CHTO NUZHNO POLUCHITX
\emph{POSLEDOVATELXNOSTX}  SLUCHAJNYH PERESTANOVOK. dLYA POLUCHENIYA OCHEREDNOJ
PERESTANOVKI NASHEJ POSLEDOVATELXNOSTI MY DEJSTVUEM NA PREDYDUSHCHUYU TREMYA
IZ PYATI PERESTANOVOK. eTI TRI PERESTANOVKI VYBIRAYUTSYA SLUCHAJNYM OBRAZOM
I NE OBYAZATELXNO OTLICHAYUTSYA DRUG OT DRUGA.

eTOT METOD POHOZH NA SPOSOB, KOTORYM LYUDI OBYCHNO TASUYUT KOLODU KART
(SM.~UPR.~13). mOZHET BYTX, CHITATELYU BUDET INTERESNO UZNATX, KAKIE
PERESTANOVKI POLUCHAYUTSYA V KOLODE, PERETASOVANNOJ SHULEROM. dLYA TOGO CHTOBY
|TO VYYASNITX, AVTOR POPROSIL u.~lOG|NA (SPECIALISTA PO VYCHISLITELXNOJ
TEHNIKE I TASOVANIYU KART) ZAFIKSIROVATX REZULXTATY TREH
PEREMESHIVANIJ KOLODY IZ 52~KART. pOLUCHILISX SLEDUYUSHCHIE PERESTANOVKI:
$$
\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
}
$$
eTI PERESTANOVKI PREDSTAVLENY S POMOSHCHXYU CIKLOV (SR.~P.~1.3.3). dLYA TOGO
CHTOBY NAIBOLEE |FFEKTIVNYM SPOSOBOM PROIZVESTI PERESTANOVKU
POSLEDOVATELXNOSTI CHISEL, SLEDUET ISPOLXZOVATX EE CIKLICHESKUYU STRUKTURU.
eSLI, NAPRIMER, ISPOLXZOVATX \MIX, PERVAYA IZ PRIVEDENNYH VYSHE PERESTANOVOK
MOZHET BYTX ZAPROGRAMMIROVANA KAK
$$
\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
}
$$
I~T.~D.

mY HOTIM BYTX UVERENY V TOM, CHTO ESLI ISPOLXZOVATX NASH NABOR IZ PYATI
ZADANNYH PERESTANOVOK V NADLEZHASHCHEJ POSLEDOVATELXNOSTI, TO MOZHNO POLUCHITX
VSE $t!$~VOZMOZHNYH PERESTANOVOK. mOZHNO POKAZATX, CHTO, ESLI DVE
PERESTANOVKI SLEDUYUSHCHEGO VIDA:
$$
\eqalignter{
\pi_1&=(1\,2) & \rem{(LYUBOE PROIZVEDENIE NEPERESEKAYUSHCHIHSYA CIKLOV, KAZHDYJ IZ NIH NECHETNOJ DLINY),}\cr
\pi_2&=(1)& \rem{(LYUBOJ CIKL DLINY~$t-1$, V KOTORYJ NE VHODIT |LEMENT~$1$),}\cr
}
\eqno(2)
$$
VKLYUCHENY V NABOR, MOZHNO POLUCHITX LYUBUYU PERESTANOVKU IZ $t$~|LEMENTOV PUTEM
POSLEDOVATELXNOGO PRIMENENIYA~$\pi_1$ I~$\pi_2$ V NEKOTOROM PORYADKE
(SM.~UPR.~12.) dZH.~dIKSON POKAZAL, CHTO POCHTI~$3/4$ IZ VSEH PAR
PERESTANOVOK OBLADAYUT |TIM SVOJSTVOM ({\sl Math.~Z.,\/} {\bf 110} (1969), 199--205).

vTOROJ METOD PEREMESHIVANIYA TESNO SVYAZAN S ALGORITMOM~3.3.2P. chITATELX
DOLZHEN VERNUTXSYA K |TOMU ALGORITMU, KOTORYJ DAET PROSTOE SOOTVETSTVIE
MEZHDU KAZHDOJ IZ $t!$~VOZMOZHNYH PERESTANOVOK I NABOROM CHISEL $C[1]$,
$C[2]$,~\dots, $C[t]$, GDE~$0\le C[j]<j$. mOZHNO LEGKO POLUCHITX SLUCHAJNYJ
NABOR CHISEL, POSLE CHEGO S POMOSHCHXYU UPOMYANUTOGO SOOTVETSTVIYA POLUCHITX
SLUCHAJNUYU PERESTANOVKU.

\alg P.(pEREMESHIVANIE.) pUSTX $X_1$, $X_2$,~\dots, $X_t$---NABOR $t$~CHISEL,
KOTORYJ NUZHNO PEREMESHATX.

\st[nACHALXNAYA USTANOVKA.] uSTANOVITX~$j\asg t$.

\st[vYRABOTATX~$U$.] vYRABOTATX SLUCHAJNOE CHISLO~$U$,
RAVNOMERNO RASPREDELENNOE MEZHDU NULEM I EDINICEJ.

%% 156

\st[oBMEN.] uSTANOVITX~$k\asg \floor{jU}+1$. (tEPERX $k$~ESTX SLUCHAJNOE
CELOE CHISLO, RASPOLOZHENNOE V PROMEZHUTKE MEZHDU~$1$ I~$j$.)
vZAIMOZAMENITX~$X_k\xchg X_j$.

\st[uMENXSHITX~$j$.] uMENXSHITX~$j$ NA~$1$. eSLI~$j>1$, VOZVRATITXSYA K SHAGU~\stp{2}.
\algend

eTOT ALGORITM VPERVYE OPUBLIKOVALI l.~mOZES I r.~oUKFORD (Tables of Random
Permutations (Stanford University Press, 1963)) I r.~dURSTENFELD
({\sl CACM,\/} {\bf 7} (1964), 420). aLGORITM LUCHSHE, CHEM METOD uLAMA, POTOMU
CHTO ON, V SAMOM DELE, VYRABATYVAET "DEJSTVITELXNO SLUCHAJNYE" PERESTANOVKI I
ISPOLXZUET MENXSHUYU PAMYATX.

\excercises
\ex[M12] oB®YASNITE FORMULU~(1).

\ex[20] dOKAZHITE, CHTO PRI ISPOLXZOVANII ALGORITMA~S OTBIRAYUTSYA TOCHNO
$n$~ZAPISEJ PRI USLOVII, CHTO~$0<n \le N$.

\rex[22] v ALGORITME~S $(t+1)\hbox{-J}$~|LEMENT VYBIRAETSYA S
VEROYATNOSTXYU~$(n-m)/(N-t)$, A \emph{NE} $n/N$. v TEKSTE, ODNAKO, NAPISANO,
CHTO VYBOR PROVODITSYA BESPRISTRASTNO, TAK CHTO KAZHDYJ |LEMENT DOLZHEN
VYBIRATXSYA S \emph{RAVNOJ} VEROYATNOSTXYU! kAKIM OBRAZOM MOGUT BYTX
ODNOVREMENNO SPRAVEDLIVY OBA |TI UTVERZHDENIYA?

\ex[m23] pUSTX $p(m, t)$~ESTX VEROYATNOSTX TOGO, CHTO IZ PERVYH
$t$~|LEMENTOV VYBIRAETSYA ROVNO~$m$. pOLXZUYASX NEPOSREDSTVENNO ALGORITMOM~S,
POKAZHITE, CHTO
$$
p(m, t)=\perm{t}{m}\perm{N-t}{n-m}\bigg/\perm{N}{n} \rem{DLYA $0\le t \le N$.}
$$

\ex[m24] chEMU RAVNO SREDNEE ZNACHENIE~$t$ V MOMENT ZAVERSHENIYA
RABOTY ALGORITMA~S? (dRUGIMI SLOVAMI, SKOLXKO ZAPISEJ IZ OBSHCHEGO CHISLA~$N$
MY PEREBEREM, PREZHDE CHEM VYBORKA BUDET ZAKONCHENA?)

\ex[M24] chEMU RAVNO STANDARTNOE OTKLONENIE VELICHINY, VYCHISLENNOJ
V PREDYDUSHCHEM UPRAZHNENII?

\rex[m25] dOKAZHITE, CHTO PRI ISPOLXZOVANII ALGORITMA~S LYUBOJ \emph{ZADANNYJ}
NABOR IZ $n$~ZAPISEJ IZ OBSHCHEGO CHISLA~$N$ POLUCHAETSYA S
VEROYATNOSTXYU~$1/\perm{N}{n}$. tEM SAMYM BUDET POKAZANO, CHTO VYBORKA
PROIZVODITSYA SOVERSHENNO BESPRISTRASTNO.

\rex[18] chTO PROIZOJDET PRI RABOTE ALGORITMA~R, ESLI V FAJLE
SODERZHITSYA MENXSHE $n$~ZAPISEJ? pREDLOZHITE NEBOLXSHUYU MODIFIKACIYU ALGORITMA
DLYA OBNARUZHENIYA TAKOGO SLUCHAYA.

\ex[22] pREDPOLOZHIM, CHTO MY ISPOLXZUEM ALGORITM~R DLYA~$n=3$, A
FAJL SOSTOIT IZ 20~ZAPISEJ, I NA SHAGE~R2 BYLI POLUCHENY SLEDUYUSHCHIE SLUCHAJNYE ZNACHENIYA~$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~ZAPISEJ ZANUMEROVANY OT~$1$ DO~$20$. kAKIE ZAPISI POPADUT V
REZERVUAR? kAKIE ZAPISI POPADUT V OKONCHATELXNUYU VYBORKU?

\ex[30] kAKIM OBRAZOM NUZHNO SKOMPONOVATX TABLICU~$(Y, I)$ V
ALGORITME~R (OB |TOM UPOMINALOSX V TEKSTE), CHTOBY |FFEKTIVNO VYPOLNYALISX
POISK I PERENOS NA SHAGAH~R3 I~R5?

\rex[m25] pREDPOLOZHIM, CHTO $p_m$~ESTX VEROYATNOSTX TOGO, CHTO PRI
PERVOM PEREBORE PO ALGORITMU~R V REZERVUAR POPADUT ROVNO $m$~|LEMENTOV. oPREDELITE
%% 157
PROIZVODYASHCHUYU FUNKCIYU~$G(z)=\sum_m p_m z^m$ I VYCHISLITE SREDNEE I
STANDARTNOE OTKLONENIE (ISPOLXZUJTE MATERIAL P.~1.2.10).

\ex[m23] pUSTX~$\pi_1$, $\pi_2$---PERESTANOVKI, OPREDELYAEMYE
SOOTNOSHENIYAMI~(2). dOKAZHITE SPRAVEDLIVOSTX SLEDUYUSHCHIH UTVERZHDENIJ,
(a)~nEKOTORAYA STEPENX~$\pi_1$ RAVNA CIKLU~$(1\,2)$. (b)~nEKOTOROE
PROIZVEDENIE $\pi_1$ I~$\pi_2$ RAVNO CIKLU~$(1\,k)$ DLYA LYUBOGO~$k$, $2\le k \le t$.
(c)~lYUBOJ CIKL~$(j\,k)$, $j\ne k$, MOZHET BYTX POLUCHEN KAK
PROIZVEDENIE $\pi_1$ I~$\pi_2$. (d)~vSE PERESTANOVKI IZ $t$~|LEMENTOV
MOGUT BYTX POLUCHENY KAK PROIZVEDENIE $\pi_1$ I~$\pi_2$.

\ex[M23] (s.~gOLOMB.) oBYCHNYJ SPOSOB TASOVANIYA KART SOSTOIT V SLEDUYUSHCHEM:
KOLODA DELITSYA'NA DVE PO VOZMOZHNOSTI RAVNYE CHASTI, KOTORYE VSTAVLYAYUTSYA
ODNA V DRUGUYU. (v PRAVILAH KARTOCHNYH IGR, OPUBLIKOVANNYH hOJLOM, CHITAEM:
"dLYA TOGO CHTOBY HOROSHO PEREMESHATX KARTY TAKIM SPOSOBOM, NUZHNO PERETASOVATX
IH OKOLO TREH RAZ".) rASSMOTRIM KOLODU IZ $2n-1$~KART $X_1$, $X_2$,~\dots,
$X_{2n-1}$. oPERACIYA "IDEALXNOGO TASOVANIYA"~$s$ RAZDELYAET KOLODU NA DVE
CHASTI $X_1$, $X_2$,~\dots{}, $X_n$ I~$X_{n+1}$,~\dots, $X_{2n-1}$ I
IDEALXNO SMESHIVAET IH TAK, CHTO POLUCHAETSYA POSLEDOVATELXNOSTX $X_1$,
$X_{n+1}$, $X_2$, $X_{n+2}$,~\dots, $X_{2n-1}$, $X_n$. oPERACIYA
"SNYATIYA"~$c^j$ PEREVODIT POSLEDOVATELXNOSTX $X_1$, $X_2$,~\dots,
$X_{2n-1}$ V POSLEDOVATELXNOSTX  $X_{j+1}$,~\dots, $X_{2n-1}$, $X_1$,~\dots,
$X_j$. pOKAZHITE, CHTO PRI KOMBINIROVANII "IDEALXNYH TASOVANIJ" I
"SNYATIJ" MOZHNO POLUCHITX NE BOLEE CHEM $(2n-1)(2n-2)$~RAZLICHNYH
POSLEDOVATELXNOSTEJ KART PRI USLOVII, CHTO~$n>1$.

%% 158
\subchap{* chto takoe sluchajnaya posledovatel'nost'?} % 3.5*

\section{A. vVODNYE ZAMECHANIYA}. v |TOJ GLAVE UZHE GOVORILOSX O TOM, KAK
POLUCHATX POSLEDOVATELXNOSTI
$$
\<U_n>=U_0, U_1, U_2, \ldots
\eqno(1)
$$
DEJSTVITELXNYH CHISEL, ZAKLYUCHENNYH MEZHDU NULEM I EDINICEJ, T.~E.\ TAKIH,
CHTO~$0\le U_n<1$. eTI POSLEDOVATELXNOSTI NAZYVALISX "SLUCHAJNYMI", HOTYA PO
SPOSOBU POLUCHENIYA ONI BYLI SOVERSHENNO DETERMINIROVANNYMI. dLYA TOGO CHTOBY
OPRAVDATX |TO NAZVANIE, MY PISALI, CHTO CHISLA "VEDUT SEBYA TAK, KAK ESLI BY
ONI BYLI DEJSTVITELXNO SLUCHAJNYMI". dLYA PRAKTICHESKIH CELEJ (V NASTOYASHCHEE
VREMYA) TAKOGO ZAYAVLENIYA MOZHET BYTX I DOSTATOCHNO, ODNAKO ONO
OBHODIT ODIN OCHENX VAZHNYJ FILOSOFSKIJ I TEORETICHESKIJ VOPROS: KAK TOCHNO
SFORMULIROVATX, CHTO IMENNO MY PODRAZUMEVAEM POD
"SLUCHAJNYM POVEDENIEM"? nUZHNO PREDLOZHITX KOLICHESTVENNOE OPREDELENIE
SLUCHAJNOGO POVEDENIYA. nE SLEDUET POLXZOVATXSYA PONYATIYAMI, KOTORYH
PO-NASTOYASHCHEMU NE PONIMAESHX, TEM BOLEE CHTO O SLUCHAJNYH CHISLAH MOZHNO
VYSKAZATX MNOGO NA PERVYJ VZGLYAD PARADOKSALXNYH UTVERZHDENIJ.

mATEMATICHESKAYA STATISTIKA I TEORIYA VEROYATNOSTEJ TSHCHATELXNO IZBEGAYUT OTVETA
NA NASH VOPROS, POSKOLXKU |TI NAUKI VOZDERZHIVAYUTSYA OT ABSOLYUTNYH
UTVERZHDENIJ. vMESTO |TOGO RASSMATRIVAETSYA VOPROS O TOM, KAKUYU
\emph{VEROYATNOSTX}  SLEDUET PRIPISATX VYSKAZYVANIYAM, SVYAZANNYM SO
SLUCHAJNYMI POSLEDOVATELXNOSTYAMI NEZAVISIMYH SOBYTIJ. aKSIOMY TEORII
VEROYATNOSTEJ POZVOLYAYUT BEZ TRUDA
VYCHISLYATX ABSTRAKTNYE VEROYATNOSTI, ODNAKO PRI |TOM OSTAETSYA NEYASNYM, CHTO
ZHE V DEJSTVITELXNOSTI OZNACHAET PONYATIE VEROYATNOSTI, ILI KAK |TO PONYATIE
MOZHNO OSMYSLENNO PRILOZHITX K YAVLENIYAM OKRUZHAYUSHCHEGO MIRA. r.~FON~mIZES V
KNIGE "vEROYATNOSTX, STATISTIKA I ISTINA" (Probability, Statistics, and
Truth, Macmillan, 1957) PODROBNO OBSUZHDAET |TO POLOZHENIE I VYSKAZYVAET TAKUYU
TOCHKU ZRENIYA, CHTO OPREDELENIE VEROYATNOSTI ZAVISIT OT TOGO KAK OPREDELITX
SLUCHAJNUYU POSLEDOVATELXNOSTX.

pRIVEDEM DVA OPISANIYA PONYATIYA SLUCHAJNOJ POSLEDOVATELXNOSTI, NEDAVNO
PREDLOZHENNYE DVUMYA AVTORAMI.
{\medskip\narrower
{\sl d.~X.~lEMER (1951 G.):\/} "sLUCHAJNAYA POSLEDOVATELXNOSTX ESTX NEKOE
RASPLYVCHATOE PONYATIE, VOPLOSHCHAYUSHCHEE IDEYU POSLEDOVATELXNOSTI, V KOTOROJ
KAZHDYJ CHLEN NEPREDSKAZUEM DLYA
%% 159
NEPOSVYASHCHENNOGO I |LEMENTY KOTOROJ UDOVLETVORYAYUT RYADU TRADICIONNYH SREDI
STATISTIKOV KRITERIEV, V IZVESTNOJ STEPENI ZAVISYASHCHIH OT TOGO, DLYA KAKIH
PRIMENENIJ SLUZHIT |TA POSLEDOVATELXNOSTX".

{\sl dZH.~n.~fR|NKLIN (1962~G.):\/} "pOSLEDOVATELXNOSTX~(1) SLUCHAJNA, ESLI
ONA OBLADAET LYUBYM SVOJSTVOM, KOTORYM OBLADAYUT VSE BESKONECHNYE
POSLEDOVATELXNOSTI NEZAVISIMYH VYBOROK SLUCHAJNYH PEREMENNYH IZ
RAVNOMERNOGO RASPREDELENIYA"
\medskip}

oPREDELENIE fR|NKLINA SUSHCHESTVENNO OBOBSHCHAET OPREDELENIE lEMERA, POSKOLXKU
ONO TREBUET, CHTOBY POSLEDOVATELXNOSTX UDOVLETVORYALA \emph{VSEM}
STATISTICHESKIM KRITERIYAM. eGO OPREDELENIE NE YAVLYAETSYA ABSOLYUTNO TOCHNYM, I
SKORO MY UBEDIMSYA V TOM, CHTO RAZUMNAYA EGO INTERPRETACIYA PRIVODIT K
OTRICANIYU SUSHCHESTVOVANIYA TAKOGO OB®EKTA, KAK SLUCHAJNAYA
POSLEDOVATELXNOSTX! tAKIM OBRAZOM, ONO SLISHKOM OGRANICHITELXNO, PO|TOMU
POPYTAEMSYA UTOCHNITX \emph{OPREDELENIE lEMERA.} mY HOTIM POLUCHITX
OTNOSITELXNO KOROTKIJ PERECHENX MATEMATICHESKIH SVOJSTV, KAZHDOE IZ KOTORYH
NE PROTIVORECHIT NASHEMU INTUITIVNOMU PREDSTAVLENIYU O
SLUCHAJNOJ POSLEDOVATELXNOSTI. kROME TOGO, |TOT PERECHENX DOLZHEN BYTX
DOSTATOCHNO POLNYM DLYA TOGO, CHTOBY \emph{LYUBUYU} POSLEDOVATELXNOSTX,
OBLADAYUSHCHUYU PERECHISLENNYMI SVOJSTVAMI, MOZHNO BYLO BY OTNESTI K "SLUCHAJNYM".
tO, CHTO MY RAZRABOTAEM V NASTOYASHCHEM RAZDELE, BUDET, PO-VIDIMOMU,
UDOVLETVORITELXNYM, S TOCHKI ZRENIYA PRIVEDENNYH VYSHE SOOBRAZHENIJ,
OPREDELENIEM SLUCHAJNOSTI, HOTYA PRI |TOM OSTANUTSYA BEZ OTVETA MNOGIE
INTERESNYE VOPROSY.

pUSTX~$u$ I~$v$---DEJSTVITELXNYE CHISLA, $0\le u < v \le 1$.
eSLI~$U$---SLUCHAJNAYA VELICHINA, RAVNOMERNO RASPREDELENNAYA MEZHDU~$0$ I~$1$, TO
VEROYATNOSTX TOGO, CHTO~$u\le U < v$, RAVNA~$v-u$. nAPRIMER, ESLI~$u=1/3$
I~$v=2/3$, VEROYATNOSTX TOGO, CHTO~$1/3\le U < 2/3$, RAVNA~$1/3$. kAK
OBOBSHCHITX |TO SVOJSTVO NA SLUCHAJ BESKONECHNOJ POSLEDOVATELXNOSTI~$U_0$,
$U_1$, $U_2$,~\dots? oCHEVIDNYJ OTVET SOSTOIT V TOM, CHTO ESLI SOSCHITATX,
SKOLXKO RAZ $U_n$~POPADAET V INTERVAL MEZHDU~$u$ I~$v$, TO SREDNEE CHISLO
POPADANIJ DOLZHNO BYTX RAVNO VELICHINE~$v-u$. aNALOGICHNYM OBRAZOM VVODILOSX
INTUITIVNOE PONYATIE VEROYATNOSTI: ONO OSNOVYVALOSX NA CHASTOTE
POYAVLENIYA SOBYTIYA. eSLI BYTX BOLEE TOCHNYM, OBOZNACHIM CHEREZ~$\nu(n)$
CHISLO ZNACHENIJ~$j$, $0\le j < n$, TAKIH, CHTO~$u\le U_j < v$. mY HOTIM,
CHTOBY OTNOSHENIE~$\nu(n)/n$ STREMILOSX K~$v-u$ PRI STREMLENII~$n$ K BESKONECHNOSTI:
$$
\lim_{n\to\infty} \nu(n)/n=v-u.
\eqno(2)
$$
eSLI |TO USLOVIE UDOVLETVORYAETSYA PRI LYUBOM VYBORE~$u$ I~$v$,
POSLEDOVATELXNOSTX BUDEM NAZYVATX \dfn{RAVNOMERNO RASPREDELENNOJ.}

oBOZNACHIM CHEREZ~$S(n)$ NEKOTOROE UTVERZHDENIE OTNOSITELXNO CELOGO CHISLA~$n$
I POSLEDOVATELXNOSTI~$U_1$, $U_2$,~$\ldots\,$. nAPRIMER,
%% 160
$S(n)$~MOZHET BYTX VYSKAZANNYM VYSHE UTVERZHDENIEM: "$u\le U_n < v$". mOZHNO
OBOBSHCHITX RASSUZHDENIYA, PRIVEDENNYE V PREDYDUSHCHEM ABZACE, I OPREDELITX
"VEROYATNOSTX TOGO, CHTO $S(n)$~ISTINNO" PO OTNOSHENIYU K OPREDELENNOJ
BESKONECHNOJ POSLEDOVATELXNOSTI. pUSTX~$\nu(n)$---CHISLO ZNACHENIJ~$j$, $0\le j <n$,
TAKIH, CHTO~$S(j)$~ISTINNO.

\proclaim oPREDELENIE~A. gOVORYAT, CHTO~$\Pr (S(n))=\lambda$,
ESLI~$\lim_{n\to\infty} \nu(n)/n=\lambda$. (v SLOVESNOJ FORME "VEROYATNOSTX
TOGO, CHTO $S(n)$~ISTINNO, RAVNA~$\lambda$, ESLI PREDEL~$\nu(n)/n$ PRI~$n$,
STREMYASHCHEMSYA K BESKONECHNOSTI, ESTX~$\lambda$".)

pOLXZUYASX |TIM OPREDELENIEM, MOZHNO SKAZATX, CHTO POSLEDOVATELXNOSTX~$U_0$,
$U_1$,~\dots{} RAVNOMERNO RASPREDELENA V TOM I TOLXKO TOM SLUCHAE,
ESLI~$\Pr(u\le U_n < v)=v-u$ DLYA VSEH DEJSTVITELXNYH~$u$, $v$, TAKIH,
CHTO~$0\le u < v \le 1$.

pOSLEDOVATELXNOSTX MOZHET BYTX RAVNOMERNO RASPREDELENNOJ, NO NE SLUCHAJNOJ.
eSLI, NAPRIMER, $U_0$, $U_1$,~\dots{} I~$V_0$, $V_1$,~\dots---DVE RAVNOMERNO
RASPREDELENNYE POSLEDOVATELXNOSTI, TO NETRUDNO POKAZATX, CHTO POSLEDOVATELXNOSTX
$$
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)
$$
TAKZHE RAVNOMERNO RASPREDELENA, POSKOLXKU POSLEDOVATELXNOSTX~${1\over2}U_0$,
${1\over 2}U_1$,~\dots{} RAVNOMERNO RASPREDELENA MEZHDU~$0$ I~$1/2$, A
CHEREDUYUSHCHAYASYA S NEJ POSLEDOVATELXNOSTX~${1\over 2}+{1\over 2}V_0$,
${1\over 2}+{1\over 2}V_1$,~\dots{} RAVNOMERNO RASPREDELENA MEZHDU~$1/2$ I~$1$.
v POSLEDOVATELXNOSTI~$W$ ZA VELICHINOJ, MENXSHEJ~$1/2$, VSEGDA SLEDUET
VELICHINA, BOLXSHAYA~$1/2$, I OBRATNO, TAK CHTO |TA POSLEDOVATELXNOSTX NE
YAVLYAETSYA SLUCHAJNOJ NI V KAKOM RAZUMNOM SMYSLE. nAM NUZHNO SVOJSTVO
BOLEE SILXNOE, CHEM RAVNOMERNAYA RASPREDELENNOSTX.

pRIMER, PRIVEDENNYJ V PREDYDUSHCHEM ABZACE, PRIVODIT K ESTESTVENNOMU
OBOBSHCHENIYU SVOJSTVA RAVNOMERNOJ RASPREDELENNOSTI, A IMENNO K RASSMOTRENIYU
PAR SOSEDNIH |LEMENTOV POSLEDOVATELXNOSTI. mOZHNO POTREBOVATX, CHTOBY DLYA
LYUBYH CHETYREH CHISEL~$u_1$, $v_1$, $u_2$, $v_2$, TAKIH, CHTO~$0\le u_1 < v_1 \le 1$,
$0\le u_2 < v_2 \le 1$,  POSLEDOVATELXNOSTX UDOVLETVORYALA TREBOVANIYU
$$
\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)
$$
bOLEE TOGO, DLYA LYUBOGO POLOZHITELXNOGO CELOGO CHISLA~$k$ MOZHNO
VVESTI PONYATIE \dfn{$k\hbox{-RASPREDELENNOJ}$} POSLEDOVATELXNOSTI.

\proclaim oPREDELENIE~B. gOVORYAT, CHTO POSLEDOVATELXNOSTX~(1)
$k\hbox{-pacnpeDELENA}$, ESLI
$$
\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)
$$
DLYA LYUBYH DEJSTVITELXNYH CHISEL~$u_j$, $v_j$, TAKIH, CHTO~$0\le u_j<v_j\le 1$
PRI~$1 \le j \le k$.

%% 161
\bye