\input style
VYBIRAL BY $j\hbox{-E}$~VYCHISLIMOE PRAVILO POSTROENIYA 
PODPOSLEDOVATELXNOSTI~$\cR_j$, NE MOZHET SUSHCHESTVOVATX; |TO SLEDUET IZ 
TOGO, CHTO NE MOZHET SUSHCHESTVOVATX |FFEKTIVNYJ ALGORITM, KOTORYJ OPREDELYAL 
BY, SOSTOIT LI DANNYJ VYCHISLITELXNYJ METOD IZ KONECHNOGO CHISLA SHAGOV. (mY 
VERNEMSYA K |TOMU VOPROSU V GL.~11.) oDNAKO VAZHNYE BOLXSHIE KLASSY 
ALGORITMOV \emph{MOGUT} BYTX SISTEMATICHESKI PERECHISLENY. nAPRIMER, IZ 
POSTROENIYA ALGORITMA~W VIDNO, CHTO S POMOSHCHXYU |FFEKTIVNOGO ALGORITMA MOZHNO 
POSTROITX POSLEDOVATELXNOSTX, UDOVLETVORYAYUSHCHUYU OPREDELENIYU~R5, ESLI MY 
OGRANICHIMSYA "PRIMITIVNO REKURSIVNYMI" PRAVILAMI POSTROENIYA PODPOSLEDOVATELXNOSTEJ.

eSLI VIDOIZMENITX SHAG~W6 ALGORITMA~W TAK, CHTOBY TAM PROISHODILA 
USTANOVKA~$U_n\asg V_{k+t}$ (A NE~$V_k$), GDE~$t$---LYUBOE NEOTRICATELXNOE 
CELOE CHISLO, ZAVISYASHCHEE OT~$a_1$,~\dots, $a_r$, TO MOZHNO POKAZATX, CHTO 
SUSHCHESTVUET \emph{NESCHETNOE} MNOZHESTVO POSLEDOVATELXNOSTEJ NA~$[0, 1)$, 
UDOVLETVORYAYUSHCHIH OPREDELENIYU~R5.

dRUGOJ, MENEE PRYAMOJ, PUTX DOKAZATELXSTVA SUSHCHESTVOVANIYA NESCHETNOGO 
MNOZHESTVA SLUCHAJNYH POSLEDOVATELXNOSTEJ, OSNOVANNYJ NA TEORII MERY, DLYA 
POSLEDOVATELXNOSTEJ, UDOVLETVORYAYUSHCHIH DAZHE SILXNOMU OPREDELENIYU~R6, DAET

\proclaim tEOREMA~M. pUSTX DEJSTVITELXNOE CHISLO~$x$, $0\le x < 1$, 
POSTAVLENO V SOOTVETSTVIE DVOICHNOJ POSLEDOVATELXNOSTI~$\<X_n>$ TAKIM 
OBRAZOM, CHTO DVOICHNOE PREDSTAVLENIE~$x$ ESTX~$0.X_0X_1\ldots\,$. iMEYA V 
VIDU |TO SOOTVETSTVIE, MOZHNO UTVERZHDATX, CHTO POCHTI VSE $x$~SOOTVETSTVUYUT 
DVOICHNYM POSLEDOVATELXNOSTYAM, KOTORYE YAVLYAYUTSYA SLUCHAJNYMI V SMYSLE 
OPREDELENIYA~R6. (dRUGIMI SLOVAMI, MNOZHESTVO TEH DEJSTVITELXNYH~$x$, 
KOTORYE SOOTVETSTVUYUT NESLUCHAJNYM V SMYSLE OPREDELENIYA~R6 
POSLEDOVATELXNOSTYAM, IMEET MERU NULX.)

\proof pUSTX~$\cS$---|FFEKTIVNYJ ALGORITM, OPREDELYAYUSHCHIJ BESKONECHNUYU 
POSLEDOVATELXNOSTX RAZLICHNYH NEOTRICATELXNYH CELYH CHISEL~$\<s_n>$, TAKOJ,
 CHTO $s_n$~ZAVISIT TOLXKO OT~$n$ I~$X_{s_k}$, GDE~$0\le k < n$, 
I~$\cR$---VYCHISLIMOE PRAVILO POSTROENIYA PODPOSLEDOVATELXNOSTEJ. tOGDA IZ 
LYUBOJ DVOICHNOJ POSLEDOVATELXNOSTI~$\<X_n>$ MOZHNO POLUCHITX 
PODPOSLEDOVATELXNOSTX~$\<X_{s_n}>\cR$, I OPREDELENIE~R6 UTVERZHDAET, CHTO 
|TA PODPOSLEDOVATELXNOSTX DOLZHNA BYTX ILI KONECHNOJ, ILI 
$1\hbox{-RASPREDELENNOJ}$. dOSTATOCHNO DOKAZATX, CHTO \emph{PRI 
ZADANNYH~$\cR$ I~$\cS$ MNOZHESTVO~$N(\cR, \cS)$ DEJSTVITELXNYH CHISEL~$x$, 
SOOTVETSTVUYUSHCHIH~$\<X_n>$ I TAKIH, CHTO POSLEDOVATELXNOSTX~$\<X_{s_n}>\cR$ 
BESKONECHNA I NE YAVLYAETSYA $1\hbox{-RASPREDELENNOJ}$, IMEET MERU NULX.} v 
SAMOM DELE, $x$~IMEET NESLUCHAJNOE DVOICHNOE PREDSTAVLENIE V TOM I TOLXKO 
TOM SLUCHAE, KOGDA $x$~PRINADLEZHIT OB®EDINENIYU~$\cup N(\cR, \cS)$, 
PROSUMMIROVANNOMU PO SCHETNOMU MNOZHESTVU~$\cR$ I~$\cS$.
%% 182

pUSTX, TAKIM OBRAZOM, $\cR$ I~$\cS$ ZADANY. rASSMOTRIM 
MNOZHESTVO~$T(a_1a_2\ldots{}a_r)$, KOTOROE OPREDELYAETSYA DLYA LYUBYH DVOICHNYH 
CHISEL~$a_1a_2\ldots{}a_r$ KAK MNOZHESTVO VSEH TEH~$x$, 
SOOTVETSTVUYUSHCHIH~$\<X_n>$, CHTO~$\<X_{s_n}>\cR$ IMEET ${}\ge r$~|LEMENTOV, 
PRICHEM PERVYE $r$~|LEMENTOV RAVNY SOOTVETSTVENNO~$a_1$, $a_2$,~\dots, 
$a_r$. sNACHALA MY DOKAZHEM, CHTO
\EQ[32]{
\hbox{MERA MNOZHESTVA~}T(a_1a_2\ldots{}a_r)\le 2^{-r}.
}
zAMETIM VNACHALE, CHTO MNOZHESTVO~$T(a_1a_2\ldots{}a_r)$  IZMERIMO:
KAZHDYJ |LEMENT IZ~$T(a_1a_2\ldots{}a_r)$ ESTX DEJSTVITELXNOE 
CHISLO~$x=0.X_0X_1\ldots$, DLYA KOTOROGO SUSHCHESTVUET CELOE CHISLO~$m$, TAKOE,
 CHTO ALGORITM~$\cS$ OPREDELYAET RAZLICHNYE ZNACHENIYA~$s_0$, $s_1$,~\dots, 
$s_m$, I PRAVILO~$\cS$ OPREDELYAET PODPOSLEDOVATELXNOSTX~$X_{s_0}$, 
$X_{s_1}$,~\dots, $X_{s_m}$, TAKUYU, CHTO $X_{s_m}$~ESTX 
$r\hbox{-J}$~|LEMENT |TOJ POSLEDOVATELXNOSTI. mNOZHESTVO VSEH 
DEJSTVITELXNYH CHISEL~$y=0.Y_0Y_1\ldots$, TAKIH, CHTO~$Y_{s_k}=X_{s_k}$ 
PRI~$0\le k \le m$, TAKZHE PRINADLEZHIT MNOZHESTVU~$T(a_1a_2\ldots{}a_r)$ I 
YAVLYAETSYA IZMERIMYM MNOZHESTVOM, SOSTOYASHCHIM IZ KONECHNOGO OB®EDINENIYA DVOICHNYH 
PODYNTERVALOV~$I_{b_1\ldots{}b_t}$. pOSKOLXKU MNOZHESTVO TAKIH INTERVALOV 
SCHETNO, $T(a_1a_2\ldots{}a_r)$ YAVLYAETSYA SCHETNYM OB®EDINENIEM DVOICHNYH 
INTERVALOV, I, SLEDOVATELXNO, ONO IZMERIMO. bOLEE TOGO, IZ |TOGO 
RASSUZHDENIYA SLEDUET, CHTO MERA~$T(a_1\ldots{}a_{r-1}0)$ RAVNA 
MERE~$T(a_1\ldots{}a_{r-1}1)$, POSKOLXKU POSLEDNEE MNOZHESTVO ESTX 
OB®EDINENIE DVOICHNYH INTERVALOV, POLUCHENNYH IZ PREDSHESTVUYUSHCHEGO PRI 
DOPOLNITELXNOM TREBOVANII, CHTO~$Y_{s_k}=X_{s_k}$ DLYA~$0\le k < m$ 
I~$Y_{s_m}\ne X_{s_m}$ . pOSKOLXKU
\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}),
}
MERA MNOZHESTVA~$T(a_1a_2\ldots{}a_r)$ NE PREVOSHODIT POLOVINY 
MERY MNOZHESTVA~$T(a_1\ldots{}a_{r-1})$. nERAVENSTVO~\eqref[32] POLUCHAETSYA 
INDUKCIEJ PO~$r$.

tEPERX, KOGDA SPRAVEDLIVOSTX NERAVENSTVA~\eqref[32] USTANOVLENA, OSTALOSX 
DOKAZATX V OSNOVNOM SLEDUYUSHCHEE: DVOICHNYE PREDSTAVLENIYA POCHTI VSEH 
DEJSTVITELXNYH CHISEL RAVNOMERNO RASPREDELENY. dALEE V NESKOLXKIH ABZACAH, 
GDE ILLYUSTRIRUETSYA TIPICHNAYA V MATEMATICHESKOM ANALIZE TEHNIKA POLUCHENIYA 
OCENOK, PREDSTAVLENO DOVOLXNO DLINNOE, NO NE TRUDNOE DOKAZATELXSTVO |TOGO FAKTA.

pUSTX~$0<\varepsilon<1$ I~$B(r, \varepsilon)$ ESTX~$\bigcup 
T(a_1\ldots{}a_r)$, GDE OB®EDINENIE BERETSYA PO VSEM DVOICHNYM 
CHISLAM~$a_1\ldots{}a_r$, TAKIM, CHTO KOLICHESTVO~$\nu(r)$ NULEJ 
SREDI~$a_1$,~\dots, $a_r$ UDOVLETVORYAET NERAVENSTVU
\EQ{
 \abs{\nu(r)-{1\over2}r}\ge 1+\varepsilon r.
}
kOLICHESTVO TAKIH DVOICHNYH CHISEL RAVNO~$C(r, \varepsilon)=\sum \perm{r}{k}$,
 GDE SUMMIROVANIE VEDETSYA PO ZNACHENIYAM~$k$, TAKIM, 
CHTO~$\abs{k-{1\over2}r}\ge 1+\varepsilon r$. %% 183
pUSTX~$r=2t$ ESTX CELOE CHETNOE CHISLO. mY MOZHEM DATX GRUBUYU OCENKU 
VELICHINY~$\sum\perm{r}{k}$. eSLI~$k>0$, TO
\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
}
}
tAKIM OBRAZOM,
\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
}
}
aNALOGICHNO, DLYA~$r=2t+1$ POLUCHAEM
\EQ{
C(r, \varepsilon)<r\perm{r}{t}e^{-\varepsilon^2r}.
}
iSPOLXZUYA TEPERX~\eqref[32], VYVODIM
\EQ[33]{
\hbox{MERA MNOZHESTVA } B(r, \varepsilon) \le 2^{-r} C(r, \varepsilon)< 
re^{-\varepsilon^2 r}.
}

dALEE OPREDELIM MNOZHESTVO
\EQ{
B^*(r, \varepsilon)=B(r, \varepsilon)\cup B(r+1,\varepsilon) \cup B(r+2,
\varepsilon)\cup \ldots \, .
}
mERA~$B^*(r, \varepsilon)$ NE PREVOSHODIT~$\sum_{k\ge r} 
ke^{-\varepsilon^2k}$. pOSLEDNYAYA VELICHINA YAVLYAETSYA OSTATKOM SHODYASHCHEGOSYA 
RYADA, PO|TOMU
\EQ[34]{
\lim_{r\to\infty} (\hbox{MERY } B^*(r, \varepsilon))=0.
}

eSLI TEPERX~$x$---DEJSTVITELXNOE CHISLO, TAKOE, CHTO EGO DVOICHNOE 
PREDSTAVLENIE~$0.X_0X_1\ldots$ PRIVODIT K BESKONECHNOJ 
POSLEDOVATELXNOSTI~$\<X_{s_n}>\cR$, KOTORAYA NE YAVLYAETSYA 
$1\hbox{-RASPREDELENNOJ}$, a $\nu(r)$~OBOZNACHAET CHISLO NULEJ V PERVYH~$r$  
EE |LEMENTAH, TO
\EQ{
 \abs{\nu(r)/r-{1\over 2}}\ge 2\varepsilon
}
DLYA NEKOTOROGO~$\varepsilon>0$ I BESKONECHNO MNOGIH~$r$. eTO ZNACHIT, 
CHTO~$x$ PRI VSEH~$r$ SODERZHITSYA V~$B^*(r, \varepsilon)$. tAKIM OBRAZOM, 
OKONCHATELXNO NAHODIM, CHTO
\EQ{
 N(\cR, \cS)=\bigcup_{t\ge 2} \bigcap_{r\ge1} B^*(r, 1/t).
}
iZ FORMULY~\eqref[34] SLEDUET, CHTO~$\bigcap_{r\ge1} B^*(r, 1/t)$ PRI 
VSEH~$t$  IMEET MERU NULX; SLEDOVATELXNO, $N(\cR, \cS)$ TAKZHE IMEET MERU NULX.
\proofend

%% 184

iZ SUSHCHESTVOVANIYA \emph{DVOICHNYH} POSLEDOVATELXNOSTEJ, UDOVLETVORYAYUSHCHIH 
OPREDELENIYU~R6, SLEDUET SUSHCHESTVOVANIE POSLEDOVATELXNOSTEJ NA~$[0, 1)$, 
SLUCHAJNYH V SMYSLE |TOGO OPREDELENIYA. sM.\ PO |TOMU POVODU UPR.~36. tEM 
SAMYM MY USTANOVILI SOSTOYATELXNOSTX OPREDELENIYA~R6.

\section{e.~sLUCHAJNYE KONECHNYE POSLEDOVATELXNOSTI}. vYSHE PRIVODILOSX 
SOOBRAZHENIE O TOM, CHTO PONYATIE SLUCHAJNOSTI DLYA KONECHNYH 
POSLEDOVATELXNOSTEJ VVESTI NEVOZMOZHNO, POSKOLXKU VSYAKAYA ZADANNAYA 
KONECHNAYA POSLEDOVATELXNOSTX NICHUTX NE HUZHE LYUBOJ DRUGOJ. nESMOTRYA NA |TO, 
POCHTI KAZHDYJ SOGLASITSYA S TEM, CHTO POSLEDOVATELXNOSTX~$011101001$ "BOLEE 
SLUCHAJNA", CHEM POSLEDOVATELXNOSTX~$101010101$, A POSLEDNYAYA "BOLEE 
SLUCHAJNA", CHEM~$000000000$. hOTYA SPRAVEDLIVO UTVERZHDENIE, CHTO ISTINNO 
SLUCHAJNAYA POSLEDOVATELXNOSTX LOKALXNO MOZHET BYTX NESLUCHAJNOJ, MY BY 
PREDPOCHLI OBNARUZHITX TAKUYU NESLUCHAJNOSTX TOLXKO V DLINNOJ, A NE V 
KOROTKOJ KONECHNOJ POSLEDOVATELXNOSTI.

sUSHCHESTVUET NESKOLXKO PODHODOV K OPREDELENIYU SLUCHAJNOSTI KONECHNOJ 
POSLEDOVATELXNOSTI, I MY NAMETIM LISHX NESKOLXKO OTNOSYASHCHIHSYA SYUDA IDEJ. 
bUDEM RASSMATRIVATX TOLXKO $b\hbox{-ICHNYE}$ POSLEDOVATELXNOSTI.

eSLI ZADANA $b\hbox{-ICHNAYA}$ POSLEDOVATELXNOSTX~$X_1$, $X_2$,~\dots, $X_N$,
 TO MOZHNO SKAZATX, CHTO
\EQ{
\Pr(S(n))\approx p, \rem{ESLI~$\abs{\nu(N)/N-p}\le 1/\sqrt{N}$,}
}
GDE~$\nu(n)$---VELICHINA, VVEDENNAYA V OPREDELENII~A V NACHALE NASTOYASHCHEGO 
PARAGRAFA. pRIVEDENNUYU VYSHE POSLEDOVATELXNOSTX MOZHNO NAZVATX 
"$k\hbox{-RASPREDELENNOJ}$", ESLI
\EQ{
\Pr(X_nX_{n+1}\ldots{}X_{n+k-1}=x_1x_2\ldots x_k)\approx 1/b^k
}
DLYA VSEH $b\hbox{-ICHNYH}$ CHISEL~$x_1 x_2 \ldots x_k$. (sR.\ S 
OPREDELENIEM~D. k SOZHALENIYU, PO |TOMU NOVOMU OPREDELENIYU 
POSLEDOVATELXNOSTX MOZHET BYTX $k\hbox{-RASPREDELENA}$, DAZHE ESLI ONA NE 
YAVLYAETSYA $(k-1)\hbox{-RASPREDELENNOJ}$.)

tEPERX MOZHNO VVESTI PONYATIE SLUCHAJNOSTI ANALOGICHNO TOMU, KAK |TO BYLO 
SDELANO V OPREDELENII~R1.

\proclaim oPREDELENIE~Q1. $b\hbox{-ICHNAYA}$ POSLEDOVATELXNOSTX DLINY~$N$ 
NAZYVAETSYA "SLUCHAJNOJ", ESLI ONA $k\hbox{-RASPREDELENA}$ (V UKAZANNOM VYSHE 
SMYSLE) PRI VSEH POLOZHITELXNYH CELYH~$k$, TAKIH, CHTO~$k\le \log_b N$.

v SOOTVETSTVII S |TIM OPREDELENIEM, IMEYUTSYA, NAPRIMER 170~NESLUCHAJNYH 
DVOICHNYH POSLEDOVATELXNOSTEJ DLINY~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
PLYUS~$01010101010$ I VSE POSLEDOVATELXNOSTI, V KOTORYH IMEETSYA NE MENEE 
DEVYATI NULEJ, PLYUS VSE POSLEDOVATELXNOSTI, POLUCHENNYE IZ PREDSHESTVUYUSHCHIH 
VZAIMNOJ ZAMENOJ NULEJ I EDINIC.

pODOBNYM ZHE OBRAZOM MOZHNO VVESTI OPREDELENIE, ANALOGICHNOE OPREDELENIYU~R6, 
DLYA KONECHNYH POSLEDOVATELXNOSTEJ. pUSTX~$A$ ESTX MNOZHESTVO ALGORITMOV, 
KAZHDYJ IZ KOTORYH PREDSTAVLYAET SOBOJ PROCEDURU POLUCHENIYA 
PODPOSLEDOVATELXNOSTI~$\<X_{s_n}>\cR$, ANALOGICHNO TOMU, KAK |TO SDELANO 
PRI DOKAZATELXSTVE TEOREMY~M.

\proclaim oPREDELENIE~Q2. $b\hbox{-ICHNAYA}$ POSLEDOVATELXNOSTX~$X_1$,  
$X_2$,~\dots, $X_N$ NAZYVAETSYA $(n, \varepsilon)\hbox{-SLUCHAJNOJ}$ PO 
OTNOSHENIYU K MNOZHESTVU~$A$ ALGORITMOV, ESLI DLYA KAZHDOJ 
PODPOSLEDOVATELXNOSTI~$X_{t_1}$, $X_{t_2}$,~\dots, $X_{t_m}$, 
OPREDELENNOJ S POMOSHCHXYU ALGORITMA, PRINADLEZHASHCHEGO MNOZHESTVU~$A$,
SPRAVEDLIVO LIBO NERAVENSTVO~$m<n$, LIBO NERAVENSTVO
\EQ{
 \abs{{1\over m}\nu_a (X_{t_1}, \ldots, X_{t_m})-{1\over b}}\le \varepsilon
 \rem{PRI~$0\le a < b$.}
}

\noindent zDESX~$\nu_a(x_1, \ldots, x_m)$ OBOZNACHAET CHISLO POYAVLENIJ~$a$ V 
POSLEDOVATELXNOSTI~$x_1$,~\dots, $x_m$.

(dRUGIMI SLOVAMI, KAZHDAYA DOSTATOCHNO DLINNAYA PODPOSLEDOVATELXNOSTX, 
OPREDELENNAYA S POMOSHCHXYU ALGORITMA, PRINADLEZHASHCHEGO MNOZHESTVU~$A$, DOLZHNA 
BYTX PRIBLIZHENNO RAVNOMERNO RASPREDELENA.) oSNOVNAYA IDEYA SOSTOIT V TOM, 
CHTOBY SOSTAVITX MNOZHESTVO~$A$ IZ "PROSTYH" ALGORITMOV, CHISLO ZHE IH (I 
SLOZHNOSTX) MOZHET VOZRASTATX S ROSTOM~$N$.

v KACHESTVE PRIMERA RASSMOTRIM DVOICHNYE POSLEDOVATELXNOSTI, I 
PUSTX$A$~SOSTOIT IZ CHETYREH ALGORITMOV.
\medskip
\item{(a)}~vZYATX VSYU POSLEDOVATELXNOSTX.

\item{(b)}~vZYATX CHLENY POSLEDOVATELXNOSTI CHEREZ ODIN, NACHINAYA S PERVOGO.

\item{(c)}~vZYATX CHLENY POSLEDOVATELXNOSTI, STOYASHCHIE POSLE NULYA.

\item{(d)}~vZYATX CHLENY POSLEDOVATELXNOSTI, STOYASHCHIE POSLE EDINICY.

\medskip

tAK, POSLEDOVATELXNOSTX~$X_1$,~\dots, $X_8$ YAVLYAETSYA 
$(4, 1/8)\hbox{-SLUCHAJNOJ}$, ESLI
\descrtable{
PO ALGORITMU~(a):& 
  $\abs{{1\over8}(X_1+\cdots+X_8)-{1\over2}}\le{1\over8}$, 
  T.~E.\ ESLI V NEJ IMEETSYA 3,4 ILI 5 EDINIC;\cr
PO ALGORITMU~(b): & 
  $\abs{{1\over 4}(X_1+X_3+X_5+X_7)-{1\over 2}}\le {1\over 8}$,  
  T.~E.\ ESLI V NEJ IMEYUTSYA DVE EDINICY NA MESTAH S NECHETNYMI NOMERAMI;\cr
PO ALGORITMU~(c): & 
  NUZHNO RASSMOTRETX TRI VOZMOZHNOSTI V ZAVISIMOSTI OT TOGO, SKOLXKO NULEJ STOYAT 
  NA MESTAH~$X_1$,~\dots, $X_7$: ESLI TAM STOYAT~2 ILI 3~NULYA,
%% 186
  TO PROVERYATX NICHEGO NE NUZHNO (POSKOLXKU~$n=4$), ESLI TAM 4~NULYA, 
  ZA NIMI DOLZHNY STOYATX DVA NULYA I DVE EDINICY, I, NAKONEC, ESLI TAM 5~NULEJ,
  ZA NIMI DOLZHNY STOYATX DVA ILI TRI NULYA.\cr
PO ALGORITMU~(d):& 
  USLOVIYA, ANALOGICHNYE POLUCHENNYM PO ALGORITMU~(c).\cr
}

iTAK, TOLXKO SLEDUYUSHCHIE DVOICHNYE POSLEDOVATELXNOSTI DLINY~$8$ YAVLYAYUTSYA PO 
|TIM PRAVILAM $\left(4, {1\over 8}\right)\hbox{-SLUCHAJNYMI}$:
\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
 }
}
PLYUS POSLEDOVATELXNOSTI, POLUCHENNYE IZ NIH VZAIMNOJ ZAMENOJ~$0$ I~$1$.

yaSNO, CHTO MNOZHESTVO ALGORITMOV MOZHNO VZYATX NASTOLXKO BOLXSHIM, CHTO NI ODNA 
POSLEDOVATELXNOSTX NE BUDET UDOVLETVORYATX OPREDELENIYU V SLUCHAE, KOGDA~$n$ 
I~$\varepsilon$ RAZUMNYM OBRAZOM MALY. a.~n.~kOLMOGOROV DOKAZAL, CHTO~$(n, 
e)$-SLUCHAJNAYA DVOICHNAYA POSLEDOVATELXNOSTX \emph{VSEGDA SUSHCHESTVUET} PRI 
LYUBOM ZADANNOM~$N$, ESLI CHISLO ALGORITMOV V~$A$ NE PREVOSHODIT
\EQ[35]{
 {1\over 2} e^{2n\varepsilon^2(1-\varepsilon)}.
}
eTOT REZULXTAT NEDOSTATOCHNO SILEN DLYA TOGO, CHTOBY POKAZATX, CHTO SUSHCHESTVUYUT 
POSLEDOVATELXNOSTI, UDOVLETVORYAYUSHCHIE OPREDELENIYU~Q1, ODNAKO TAKIE 
POSLEDOVATELXNOSTI MOGUT BYTX |FFEKTIVNO POSTROENY S POMOSHCHXYU PROCEDURY 
rISA V UPR.~3.2.2-21.

dRUGOJ INTERESNYJ PODHOD K OPREDELENIYU SLUCHAJNOSTI UKAZAL p.~mARTIN-l¸F 
({\sl Information and Control,\/} {\bf 9} (1966), 602--619). pUSTX ZADANY 
KONECHNAYA $b\hbox{-ICHNAYA}$ POSLEDOVATELXNOSTX~$X_1$,~\dots, $X_N$ I~$l(X_1,
~\ldots, X_N)$---DLINA KRATCHAJSHEJ PROGRAMMY, KOTORAYA POLUCHAET |TU 
POSLEDOVATELXNOSTX NA MASHINE tXYURINGA. (oPREDELENIE PONYATIYA MASHINY 
tXYURINGA SM.\ V GL.~11; VMESTO |TOGO PONYATIYA MY MOGLI BY ISPOLXZOVATX 
NEKOTORYE KLASSY |FFEKTIVNYH ALGORITMOV NAPODOBIE OPREDELENNYH V 
UPR.~1.1-8.) tOGDA $l(X_1,~\ldots, X_N)$ SLUZHIT MEROJ "NEREGULYARNOSTI" 
POSLEDOVATELXNOSTI, I MY MOZHEM OTOZHDESTVITX |TO PONYATIE SO SLUCHAJNOSTXYU. 
pOSLEDOVATELXNOSTI DLINY~$N$, MAKSIMIZIRUYUSHCHIE~$l(X_1,~\ldots, X_N)$, MOZHNO 
NAZVATX SLUCHAJNYMI. (s TOCHKI ZRENIYA PRAKTICHESKOGO POLUCHENIYA 
SLUCHAJNYH CHISEL NA MASHINE |TO OPREDELENIE SLUCHAJNOSTI KONECHNO NAIHUDSHEE, 
KAKOE TOLXKO MOZHNO VOOBRAZITX!)

%% 187


v OSNOVNYH CHERTAH TAKOE ZHE OPREDELENIE SLUCHAJNOSTI NEZAVISIMO I POCHTI 
ODNOVREMENNO PREDLOZHIL g.~chXYATIN ({\sl JACM,\/} {\bf 16} (1969), 145--159).
 iNTERESNO ZAMETITX, CHTO, HOTYA |TO OPREDELENIE V OTLICHIE OT DRUGIH NIKAK 
NE ISPOLXZUET SVOJSTVO RAVNOMERNOJ RASPREDELENNOSTI, mARTIN-l¸F I chXYATIN 
DOKAZALI, CHTO SLUCHAJNYE POSLEDOVATELXNOSTI |TOGO TIPA TAKZHE IMEYUT 
OZHIDAEMYE SVOJSTVA RAVNOMERNOJ RASPREDELENNOSTI. mARTIN-l¸F POKAZAL, CHTO 
TAKIE POSLEDOVATELXNOSTI V NEKOTOROM SMYSLE UDOVLETVORYAYUT \emph{VSEM} 
VYCHISLIMYM STATISTICHESKIM PROVERKAM SLUCHAJNOSTI.

\section {F.~vYVODY, ISTORIYA VOPROSA I BIBLIOGRAFIYA}. mY IMEEM 
TEPERX NESKOLXKO OPREDELENIJ RAZNOJ STEPENI SLUCHAJNOSTI 
POSLEDOVATELXNOSTI.

bESKONECHNYE $\infty\hbox{-RASPREDELENNYE}$ POSLEDOVATELXNOSTI OBLADAYUT 
MNOGIMI POLEZNYMI SVOJSTVAMI, KOTORYMI DOLZHNY OBLADATX SLUCHAJNYE 
POSLEDOVATELXNOSTI, I, KROME TOGO, DLYA NIH SUSHCHESTVUET RAZVITAYA TEORIYA. (v 
UPRAZHNENIYAH, POMESHCHENNYH NIZHE, VVODYATSYA NESKOLXKO VAZHNYH SVOJSTV 
$\infty\hbox{-RASPREDELENNYH}$ POSLEDOVATELXNOSTEJ, KOTORYE NE 
UPOMINALISX V TEKSTE.) tAKIM OBRAZOM, OPREDELENIE~R1 PODHODIT DLYA 
TEORETICHESKIH ISSLEDOVANIJ SLUCHAJNOSTI.

pONYATIE $\infty\hbox{-RASPREDELENNOJ}$ $b\hbox{-ICHNOJ}$ POSLEDOVATELXNOSTI 
VVEL V 1909~G.\ eMILX bORELX. oN PREDLOZHIL TAKZHE PONYATIE $(m, 
k)\hbox{-RASPREDELENNOJ}$ POSLEDOVATELXNOSTI I POKAZAL, CHTO 
$b\hbox{-ICHNYE}$ PREDSTAVLENIYA POCHTI VSEH DEJSTVITELXNYH CHISEL $(m, 
k)\hbox{-RASPREDELENY}$ PRI VSEH ZNACHENIYAH~$m$ I~$k$. oN NAZVAL TAKIE 
CHISLA \dfn{NORMALXNYMI} PO OTNOSHENIYU K OSNOVANIYU~$b$. pREVOSHODNOE 
OBSUZHDENIE |TOGO VOPROSA ESTX V EGO HOROSHO IZVESTNOJ KNIGE "Le\c{c}ons sur 
la th\'eorie des fonctions" (2-E IZD.~1914), 182--216. bOLEE 
POZDNIE REZULXTATY I SOOTVETSTVUYUSHCHAYA BIBLIOGRAFIYA, KASAYUSHCHIESYA NORMALXNYH 
CHISEL, ESTX V STATXE v.~shMIDTA ({\sl Pacific Journal of Math.,\/} {\bf 10} 
(1960), 661--672).

pONYATIE $\infty\hbox{-RASPREDELENNOJ}$ POSLEDOVATELXNOSTI 
\emph{DEJSTVITELXNYH} CHISEL, KOTORUYU NAZYVAYUT TAKZHE \emph{SOVERSHENNO 
RAVNOMERNO RASPREDELENNOJ POSLEDOVATELXNOSTXYU,} VVEL dZH.~fR|NKLIN V STATXE 
"Deterministic Simulation of Random Processes" [{\sl Math. Comp.,\/} {\bf 
17} (1963), 28--59)]. v |TOJ VAZHNOJ RABOTE RESHENO NESKOLXKO OCHENX 
INTERESNYH ZADACH, SVYAZANNYH S $k\hbox{-RASPREDELENNYMI}$ 
POSLEDOVATELXNOSTYAMI, I ISSLEDOVANY SVOJSTVA RASPREDELENNOSTI 
MNOGIH SPECIALXNYH POSLEDOVATELXNOSTEJ.

mY VIDELI, ODNAKO, CHTO $\infty\hbox{-RASPREDELENNYE}$ POSLEDOVATELXNOSTI 
NE OBYAZANY BYTX NASTOLXKO BESPORYADOCHNYMI, CHTOBY IH NUZHNO BYLO SCHITATX 
SOVERSHENNO "SLUCHAJNYMI". vYSHE BYLI SFORMULIROVANY TRI OPREDELENIYA~R4, R5 
I~R6 DLYA TOGO, CHTOBY NALOZHITX NA POSLEDOVATELXNOSTI DOBAVOCHNYE USLOVIYA. 
oSOBENNO PODHODYASHCHIM OPREDELENIEM BESKONECHNOJ SLUCHAJNOJ POSLEDOVATELXNOSTI 
PREDSTAVLYAETSYA~R6. oNO DAET TOCHNUYU KOLICHESTVENNUYU FORMULIROVKU,
%% 188
KOTORAYA, PO-VIDIMOMU, SOVPADAET S INTUITIVNYM PONYATIEM ISTINNOJ SLUCHAJNOSTI.

eSLI GOVORITX OB ISTORII VOPROSA, RAZVITIE |TIH OPREDELENIJ VO MNOGOM 
OBYAZANO r.~FON~mIZESU I EGO POISKAM HOROSHEGO OPREDELENIYA "VEROYATNOSTI". 
oN ({\sl Math. Zeitschrift,\/} {\bf 5} (1919), 52--99) PREDLOZHIL 
OPREDELENIE, PO DUHU BLIZKOE OPREDELENIYU~R5, HOTYA PO FORME NASTOLXKO 
SILXNOE (NAPODOBIE NASHEGO OPREDELENIYA~R3), CHTO POSLEDOVATELXNOSTI, 
UDOVLETVORYAYUSHCHIE NALOZHENNYM USLOVIYAM, NE MOGUT SUSHCHESTVOVATX. mNOGIE 
ZAMETILI |TO OBSTOYATELXSTVO, I a.~kOUPL|ND ({\sl Amer.~J.~Math.,\/} {\bf 
50} (1928), 535--552) PREDLOZHIL OSLABITX OPREDELENIE FON~mIZESA, VVODYA TAK 
NAZYVAEMYE "DOPUSTIMYE CHISLA" (ILI POSLEDOVATELXNOSTI bERNULLI). oNI 
|KVIVALENTNY $\infty\hbox{-RASPREDELENNYM}$ NA~$[0, 1)$ 
POSLEDOVATELXNOSTYAM, V KOTORYH VSE~$U_n$ ZAMENYAYUTSYA NA~$1$, ESLI~$U_n<p$, 
ILI NA~$0$, ESLI~$U_n\ge p$, PRICHEM VEROYATNOSTX~$p$ ZADANA. tAKIM OBRAZOM, 
kOUPL|ND PO SUSHCHESTVU PREDLAGAL VOZVRATITXSYA K OPREDELENIYU~R1. 
a.~vALXD POKAZAL, CHTO STOLX RADIKALXNO OSLABLYATX OPREDELENIE FON~mIZESA NE 
NUZHNO, A DOSTATOCHNO VVESTI SCHETNOE MNOZHESTVO PRAVIL POSTROENIYA 
PODPOSLEDOVATELXNOSTEJ. v VAZHNOJ STATXE [{\sl Ergebnisse eines math. 
Kolloquiums,\/} {\bf 8} (Vienna, 1937), 38--72] vALXD PO SUSHCHESTVU DOKAZAL 
TEOREMU~W, HOTYA I SDELAL OSHIBOCHNOE UTVERZHDENIE, SOSTOYASHCHEE V TOM, CHTO 
POSLEDOVATELXNOSTX, POSTROENNAYA S POMOSHCHXYU ALGORITMA~W, UDOVLETVORYAET TAKZHE 
BOLEE SILXNOMU TREBOVANIYU "MERA~$A=\Pr(U_n\in A)$" DLYA VSEH IZMERIMYH PO 
lEBEGU $A\subseteq [0, 1)$. mY VIDELI, CHTO NI ODNA POSLEDOVATELXNOSTX NE 
MOZHET UDOVLETVORITX |TOMU TREBOVANIYU.

oPREDELENIE~R4 VPERVYE BYLO SFORMULIROVANO d.~lAVL|NDOM ({\sl Zeit.\ fur 
Math.\ Logik und Grundlagen d.~Math.,\/} {\bf 12} (1966), 279--294), 
KOTORYJ OBNARUZHIL, CHTO PRI POMOSHCHI ALGORITMA~W MOZHNO DOKAZATX SUSHCHESTVOVANIE 
DVOICHNOJ POSLEDOVATELXNOSTI, UDOVLETVORYAYUSHCHEJ OPREDELENIYU~R5, NO NE~R4.

kOGDA vALXD PISAL SVOYU STATXYU, PONYATIE "VYCHISLIMOSTI" BYLO LISHX NEDAVNO 
SOZDANO, I a.~ch¸RCH [{\sl Bulletin AMS,\/}, {\bf 47} (1940), 130--135] 
POKAZAL, KAK V TEORIYU vALXDA MOZHNO VVESTI STROGOE PONYATIE "|FFEKTIVNOGO 
ALGORITMA" DLYA TOGO, CHTOBY SDELATX EGO OPREDELENIYA SOVERSHENNO TOCHNYMI. 
sUSHCHESTVENNOE PRODVIZHENIE K OPREDELENIYU~R6 SDELAL a.~n.~kOLMOGOROV [{\sl 
Sankhy\=a,\/} series~A, {\bf 25} (1963), 369--376], KOTORYJ V TOJ ZHE 
STATXE PREDLOZHIL OPREDELENIE~Q2 DLYA KONECHNYH POSLEDOVATELXNOSTEJ.

dALXNEJSHIE SVYAZI MEZHDU SLUCHAJNYMI POSLEDOVATELXNOSTYAMI I TEORIEJ 
REKURSIVNYH FUNKCIJ BYLI VYYAVLENY d.~lAVL|NDOM [{\sl Trans. AMS,\/} {\bf 
125} (1966), 497--510]. sM. TAKZHE RABOTU k.-p.~shNORRA [{\sl Z.\ Wahr.\ 
verw.\ Geb.,\/} {\bf 14} (1969), 27--35], GDE PRIVEDENY SILXNYE 
ZAVISIMOSTI MEZHDU SLUCHAJNYMI POSLEDOVATELXNOSTYAMI I "KATEGORIYAMI MERY 
NULX", OPREDELENNYMI bROU|ROM V 1919~G. 

v STATXYAH ch¸RCHA  I kOLMOGOROVA RASSMATRIVALISX TOLXKO
%% 189
DVOICHNYE POSLEDOVATELXNOSTI, DLYA KOTORYH~$\Pr(X_1=1)=p$ PRI ZADANNOJ 
VEROYATNOSTI~$p$. tEM SAMYM RASSUZHDENIYA, PROVEDENNYE V |TOJ GLAVE, YAVLYAYUTSYA 
NESKOLXKO BOLEE OBSHCHIMI, POSKOLXKU POSLEDOVATELXNOSTX NA~$[0, 1)$ 
PREDSTAVLYAET ODNOVREMENNO VSE~$p$.

v DRUGOJ STATXE [{\sl pROBLEMY PEREDACHI INFORMACII,\/} {\bf 1}, (1965),
 3--11] kOLMOGOROV RASSMOTREL ZADACHU OB OPREDELENII "KOLICHESTVA 
INFORMACII" POSLEDOVATELXNOSTI, I |TA RABOTA PRIVELA mARTIN-l¸FA K 
INTERESNOMU OPREDELENIYU KONECHNYH SLUCHAJNYH POSLEDOVATELXNOSTEJ CHEREZ 
"NEREGULYARNOSTX" [{\sl IEEE Trans.,\/} {\bf IT-14} (1968), 662--664]. eSHCHE 
ODNO OPREDELENIE SLUCHAJNOSTI, KOTOROE MOZHNO BYLO BY POMESTITX MEZHDU 
OPREDELENIYAMI~Q1 I~Q2, BYLO SFORMULIROVANO DOVOLXNO DAVNO 
a.~s.~bEZIKOVICHEM [{\sl Math.\ Zeitschrift,\/}  {\bf 39} (1934), 146--156].

dALXNEJSHEE OBSUZHDENIE SVOJSTV SLUCHAJNYH POSLEDOVATELXNOSTEJ MOZHNO NAJTI 
V KNIGE k.~pOPPERA "The Logic of Scientific Discovery" (London, 1959). 
oSOBENNO INTERESNY REZULXTATY, PRIVEDENNYE NA STR.~162--163, KOTORYE ON 
VPERVYE OPUBLIKOVAL V 1934~G.

iNTERESNYE UPRAZHNENIYA, SVYAZANNYE S POSLEDOVATELXNOSTYAMI NA~$[0, 1)$, ESTX 
V KNIGE d.~pOLIA, g.~sEG¸, "zADACHI I TEOREMY IZ ANALIZA", CHASTX~1 ({\sl 
gittl,\/} mOSKVA, 1956~G.); O RAVNOMERNO RASPREDELENNYH $b\hbox{-ICHNYH}$ 
POSLEDOVATELXNOSTYAH NAPISANO V RABOTAH a.~nIVENA ({\sl Trans.\ Amer.\ 
Math.\ Soc.,\/} {\bf 98} (1961); 52--61) I b.~z|JNA ({\sl AMM,\/} {\bf 71} 
(1964), 162--164).

\excercises
\ex[10]mOZHET LI PERIODICHESKAYA POSLEDOVATELXNOSTX BYTX RAVNOMERNO RASPREDELENNOJ?

\ex[10] rASSMOTRITE PERIODICHESKUYU DVOICHNUYU POSLEDOVATELXNOSTX~$0$, $0$, 
$1$, $1$, $0$, $0$, $1$, $1$,~$\ldots\,$. yaVLYAETSYA LI ONA 
$1\hbox{-RASPREDELENNOJ}$? $2\hbox{-RASPREDELEINOJ}$? $3\hbox{-RASPREDELENNOJ}$?

\ex[M22] pOSTROJTE $3\hbox{-RASPREDELENNUYU}$ PERIODICHESKUYU TROICHNUYU POSLEDOVATELXNOSTX.

\rex[vm22] rASSMOTRITE 
POSLEDOVATELXNOSTX~$U_n=(2^{\floor{\log_2(n+1)}}/3)\bmod 1$, CHEMU RAVNA~$\Pr(U_n<1/2)$?

\ex[vm14] dOKAZHITE, CHTO DLYA LYUBYH DVUH UTVERZHDENIJ~$S(n)$, $T(n)$ 
SPRAVEDLIVO RAVENSTVO~$\Pr(S(n) \rand T(n))+\Pr(S(n)\ror 
T(n))=\Pr(S(n))+\Pr(T(n))$  PRI USLOVII, CHTO PO KRAJNEJ MERE TRI IZ |TIH 
PREDELOV SUSHCHESTVUYUT. [eSLI, NAPRIMER, POSLEDOVATELXNOSTX 
$2\hbox{-RASPREDELENA}$, MY NAHODIM, CHTO
\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[vm23] pUSTX~$S_1(n)$, $S_2(n)$,~\dots---BESKONECHNAYA 
POSLEDOVATELXNOSTX UTVERZHDENIJ, KASAYUSHCHIHSYA VZAIMNO ISKLYUCHAYUSHCHIH SOBYTIJ, 
T.~E.\ UTVERZHDENIYA~$S_i(n)$ I~$S_j(n)$ PRI~$i\ne j$ NE MOGUT BYTX 
ISTINNYMI ODNOVREMENNO. pREDPOLOZHIM, CHTO $\Pr(S_j(n))$ SUSHCHESTVUET DLYA 
KAZHDOGO~$j\ge 1$. pOKAZHITE, CHTO~$\Prsub(S_j(n) \hbox{ ISTINNO DLYA 
NEKOTOROGO } j\ge 1)\ge \sum_{j\ge1} \Pr(S_j(n))$, I PRIVEDITE PRIMER, 
POKAZYVAYUSHCHIJ, CHTO RAVENSTVO NE OBYAZATELXNO IMEET MESTO.

\ex[vm27] pUSTX, KAK I V PREDYDUSHCHEM UPRAZHNENII, ZADANO BESKONECHNO BOLXSHOE 
CHISLO VZAIMNO ISKLYUCHAYUSHCHIH SOBYTIJ~$S_{ij}(n)$, $i\ge 1$, $j\ge 1$, TAKIH, 
CHTO 
%% 190
$\Pr(S_{ij}(n))$~SUSHCHESTVUET. pREDPOLOZHIM, CHTO~$S_{ij}(n)$ PRI VSEH~$n>0$ 
ISTINNO DLYA TOCHNO ODNOJ PARY CELYH CHISEL~$i$, $j$. eSLI~$\sum_{i,j\ge 
1}\Pr(S_{ij}(n))=1$, TO MOZHNO LI OTSYUDA ZAKLYUCHITX, CHTO DLYA VSEH~$i\ge 1$ 
VELICHINA~$\Pr(S_{ij}(n))$ ISTINNO DLYA NEKOTOROGO~$j\ge 1$) SUSHCHESTVUET I 
RAVNA~$\sum_{j\ge 1}\Pr(S_{ij}(n))$?

\ex[M15] dOKAZHITE UTVERZHDENIE~\eqref[13].

\ex[vm20] dOKAZHITE LEMMU~E. [\emph{uKAZANIE:} RASSMOTRETX 
VYRAZHENIE~$\sum_{1\le j \le m} (y_{jn}-\alpha)^2$.]

\rex[vm22] gDE PRI DOKAZATELXSTVE TEOREMY~C ISPOLXZOVALSYA TOT FAKT, CHTO $q$~KRATNO~$m$?

\rex[vm20] pRIMENITE TEOREMU~C, CHTOBY DOKAZATX, CHTO ESLI 
POSLEDOVATELXNOSTX~$\<U_n>$ $\infty\hbox{-RASPREDELENA}$, TO |TIM 
SVOJSTVOM OBLADAET I PODPOSLEDOVATELXNOSTX~$\<U_{2n}>$.

\ex[vm20] pOKAZHITE, CHTO $k\hbox{-RASPREDELENNAYA}$ POSLEDOVATELXNOSTX 
UDOVLETVORYAET TESTU "NAIBOLXSHEE IZ~$k$" V SLEDUYUSHCHEM SMYSLE: 
$\Pr(u\le\max(U_n, U_{n+1},~\ldots, U_{n+k-1}<v)=v^k-u^k$.

\rex[vm27] pOKAZHITE, CHTO $\infty\hbox{-RASPREDELENNAYA}$ NA~$[0,1)$ 
POSLEDOVATELXNOSTX UDOVLETVORYAET PROVERKE INTERVALOV V SLEDUYUSHCHEM SMYSLE. 
pUSTX~$0\le\alpha<\beta\le 1$ I~$p=\beta-\alpha$; POLOZHIM~$f(0)=0$, 
I~$f(n)$ DLYA~$n\ge 1$ ESTX NAIMENXSHEE CELOE~$m>f(n-1)$, TAKOE, 
CHTO~$\alpha\le U_m<\beta$. tOGDA~$\Pr(f(n)-f(n-1)=k)=p(1-p)^{k-1}$.

\ex[vm25] pOKAZHITE, CHTO $\infty\hbox{-RASPREDELENNAYA}$ POSLEDOVATELXNOSTX 
UDOVLETVORYAET PROVERKE NA MONOTONNOSTX V SLEDUYUSHCHEM SMYSLE. eSLI~$f(0)=1$ 
I~$f(n)$  DLYA~$n\ge 1$ ESTX NAIMENXSHEE CELOE CHISLO~$m>f(n-1)$, TAKOE, 
CHTO~$U_{m-1}>U_m$, TO 
\EQ{
\Pr(f(n)-f(n-1)=k)=2k/(k+1)!-2(k+1)/(k+2)!.
}

\rex[vm30] pOKAZHITE, CHTO $\infty\hbox{-RASPREDELENNAYA}$ POSLEDOVATELXNOSTX 
UDOVLETVORYAET TESTU SOBIRATELYA KUPONOV DLYA SLUCHAYA, KOGDA IMEYUTSYA TOLXKO 
DVA SORTA KUPONOV, V SLEDUYUSHCHEM SMYSLE. pUSTX $X_1$, $X_2$,~\dots{} ESTX 
$\infty\hbox{-RASPREDELENNAYA}$ DVOICHNAYA POSLEDOVATELXNOSTX. 
pOLOZHIM~$f(0)=0$ I PUSTX~$f(n)$ DLYA~$n\ge 1$ ESTX NAIMENXSHEE 
CELOE~$m>f(n-1)$, TAKOE, CHTO~$\set{X_{f(n-1)+1},~\ldots, X_m}$ ESTX 
MNOZHESTVO~$\set{0, 1}$. dOKAZHITE,CHTO~$\Pr(f(n)-f(n-1)=k)=2^{1-k}$; 
$k\ge 2$. (sR.\ S UPR.~7.)

\ex[vm38] sPRAVEDLIV LI TEST SOBIRATELYA KUPONOV DLYA 
$\infty\hbox{-RASPREDELENNYH}$ POSLEDOVATELXNOSTEJ V SLUCHAE, KOGDA 
IMEETSYA BOLXSHE DVUH SORTOV KUPONOV? (sR.\ S PREDYDUSHCHIM UPRAZHNENIEM.)

\ex[vm50] fRANKLIN DOKAZAL, CHTO ESLI~$r$---ZADANNOE RACIONALXNOE CHISLO, TO 
POSLEDOVATELXNOSTX~$U_n=(r^n\bmod 1)$ NE YAVLYAETSYA 
$2\hbox{-RASPREDELENNOJ}$. sUSHCHESTVUET LI RACIONALXNOE CHISLO~$r$, TAKOE, 
CHTO |TA POSLEDOVATELXNOSTX BUDET RAVNOMERNO RASPREDELENA? v CHASTNOSTI, 
BUDET LI |TA POSLEDOVATELXNOSTX RAVNOMERNO RASPREDELENNOJ V SLUCHAE, 
KOGDA~$r=3/2$? [sR. SO STATXEJ k.~mALERA ({\sl Mathematika,\/} {\bf  4} 
(1957), 122--124).]

\rex[vm22] dOKAZHITE, CHTO ESLI~$U_0$, $U_1$,~\dots{} 
$k\hbox{-RASPREDELENA}$, TO |TIM ZHE SVOJSTVOM OBLADAET I 
POSLEDOVATELXNOSTX~$V_0$, $V_1$,~\dots, GDE~$V_n=\floor{nU_n}/n$.

\ex[vm46] rASSMOTRITE OPREDELENIE~R4, V KOTOROM SLOVO 
"$\infty\hbox{-RASPREDELENNOJ}$" ZAMENENO NA "$1\hbox{-RASPREDELENNOJ}$". 
sUSHCHESTVUET LI POSLEDOVATELXNOSTX, KOTORAYA UDOVLETVORYAET |TOMU BOLEE 
SLABOMU OPREDELENIYU, NO NE YAVLYAETSYA $\infty\hbox{-RASPREDELENNOJ}$? (tO 
ESTX YAVLYAETSYA LI |TO OPREDELENIE DEJSTVITELXNO BOLEE SLABYM?)

\ex[BM50] uDOVLETVORYAET LI POSLEDOVATELXNOSTX~$U_n=(\theta^n\bmod 1)$ 
OPREDELENIYU~R4 DLYA POCHTI VSEH DEJSTVITELXNYH CHISEL~$\theta>1$? (oTVET NA 
|TOT VOPROS MOZHNO POLUCHITX ILI V TOM SLUCHAE, KOGDA NAJDEN OTRICATELXNYJ 
OTVET NA VOPROS UPR.~19, ILI V TOM SLUCHAE, KOGDA POKAZANO, CHTO DLYA LYUBOJ 
POSLEDOVATELXNOSTI RAZLICHNYH POLOZHITELXNYH CELYH CHISEL $s_0$,  $s_1$, 
$s_2$,~\dots{} POSLEDOVATELXNOSTX~$U_n=(\theta^{s_n}\bmod 1)$ 
$\infty\hbox{-RASPREDELENA}$ DLYA POCHTI VSEH~$\theta>1$.)

%% 191
\bye