\input style of a Random Sequence" ({\sl BIT,\/} {\bf 5} (1965), 246--250). pOSLEDOVATELXNOSTX, POSTROENNAYA V |TOJ STATXE, CELIKOM SOSTOIT IZ RACIONALXNYH CHISEL. kAZHDOE CHISLO~$U_n$ IMEET KONECHNOE PREDSTAVLENIE V DVOICHNOJ SISTEME SCHISLENIYA. nESKOLXKO BOLEE SLOZHNYJ YAVNYJ SPOSOB POSTROENIYA $\infty\hbox{-RASPREDELENNOJ}$ POSLEDOVATELXNOSTI MOZHNO POLUCHITX IZ PRIVEDENNOJ NIZHE TEOREMY~W. \qsection{C. eKVIVALENTNY LI PONYATIYA $\infty\hbox{-RASPREDELENNOSTI}$ I SLUCHAJNOSTI}? iZ VSEGO SKAZANNOGO VYSHE PRO $\infty\hbox{-RASPREDELENNYE}$ POSLEDOVATELXNOSTI SLEDUET, CHTO PONYATIE $\infty\hbox{-RASPREDELENNOSTI}$ VAZHNO SAMO PO SEBE. mOZHNO TAKZHE S DOSTATOCHNYM OSNOVANIEM SCHITATX, CHTO SLEDUYUSHCHEE OPREDELENIE HOROSHO OPISYVAET INTUITIVNOE PONYATIE SLUCHAJNOSTI. \proclaim oPREDELENIE R1. pOSLEDOVATELXNOSTX NA~$[0, 1)$ NAZYVAETSYA "SLUCHAJNOJ", ESLI ONA $\infty\hbox{-RASPREDELENA}$. mY VIDELI, CHTO TAKIE POSLEDOVATELXNOSTI UDOVLETVORYAYUT VSEM TESTAM P.~3.3.2 I ESHCHE MNOGIM DRUGIM. pOPROBUEM KRITICHESKI PODOJTI K |TOMU OPREDELENIYU. pREZHDE VSEGO, YAVLYAETSYA LI LYUBAYA "ISTINNO SLUCHAJNAYA" POSLEDOVATELXNOSTX $\infty\hbox{-RASPREDELENNOJ}$? sUSHCHESTVUET NESCHETNOE KOLICHESTVO POSLEDOVATELXNOSTEJ~$U_0$, $U_1$,~\dots{} DEJSTVITELXNYH CHISEL, ZAKLYUCHENNYH MEZHDU NULEM I EDINICEJ. eSLI ZNACHENIYA~$U_0$, $U_1$,~\dots{} POLUCHAYUTSYA S POMOSHCHXYU DATCHIKA ISTINNO SLUCHAJNYH CHISEL, LYUBUYU IZ POSLEDOVATELXNOSTEJ MOZHNO SCHITATX RAVNOCENNOJ. pRI |TOM NEKOTORYE IZ |TIH POSLEDOVATELXNOSTEJ (V DEJSTVITELXNOSTI BESKONECHNO BOLXSHOE IH CHISLO) NE BUDUT DAZHE RAVNOMERNO RASPREDELENY. s DRUGOJ STORONY, PRI LYUBOM RAZUMNOM OPREDELENII VEROYATNOSTI NA |TOM PROSTRANSTVE VSEH VOZMOZHNYH POSLEDOVATELXNOSTEJ MY DOLZHNY ZAKLYUCHITX, CHTO SLUCHAJNAYA POSLEDOVATELXNOSTX $\infty\hbox{-RASPREDELENA}$ S \emph{VEROYATNOSTXYU}~$1$. tAKIM OBRAZOM, MY PRIHODIM K FORMALIZACII OPREDELENIYA SLUCHAJNOSTI, DANNOGO fR|NKLINOM (SM.\ NACHALO PARAGRAFA). \proclaim oPREDELENIE R2. pOSLEDOVATELXNOSTX~$\$ NA~$[0, 1)$ NAZYVAETSYA "SLUCHAJNOJ", ESLI DLYA LYUBOGO SVOJSTVA~$P$, TAKOGO, CHTO~$P(\)$ SPRAVEDLIVO S VEROYATNOSTXYU~1 DLYA POSLEDOVATELXNOSTI~$\$ NEZAVISIMYH VYBOROK SLUCHAJNYH VELICHIN IZ RAVNOMERNOGO RASPREDELENIYA, SPRAVEDLIVO~$P(\)$. vOZMOZHNO LI, CHTO OPREDELENIE~R1 |KVIVALENTNO OPREDELENIYU~R2? pOPROBUEM VYDVINUTX PROTIV OPREDELENIYA~R1 NEKOTORYE VOZRAZHENIYA. pREZHDE VSEGO OPREDELENIE~R1 IMEET DELO TOLXKO S PREDELXNYMI SVOJSTVAMI POSLEDOVATELXNOSTI PRI~$n\to\infty$. sUSHCHESTVUYUT $\infty\hbox{-RASPREDELENNYE}$ POSLEDOVATELXNOSTI, NACHINAYUSHCHIESYA OTREZKOM %% 172 IZ MILLIONA NULEJ. sLEDUET LI SCHITATX TAKUYU POSLEDOVATELXNOSTX SLUCHAJNOJ? eTO VOZRAZHENIE NE OCHENX SERXEZNO. pUSTX~$\varepsilon$---LYUBOE POLOZHITELXNOE CHISLO, TOGDA VPOLNE VOZMOZHNO, CHTO KAZHDYJ IZ PERVOGO MILLIONA CHLENOV POSLEDOVATELXNOSTI MENXSHE~$\varepsilon$. kAK MY UZHE OTMECHALI RANEE, NET SPOSOBA, POZVOLYAYUSHCHEGO SUDITX O TOM, SLUCHAJNA ILI NET KONECHNAYA POSLEDOVATELXNOSTX. iSTINNO SLUCHAJNAYA POSLEDOVATELXNOSTX S VEROYATNOSTXYU EDINICA SODERZHIT BESKONECHNO MNOGO OTREZKOV PO MILLIONU POSLEDOVATELXNYH CHLENOV, KAZHDYJ IZ KOTORYH MENXSHE~$\varepsilon$. pOCHEMU ZHE TAKOJ OTREZOK NE MOZHET OKAZATXSYA V NACHALE POSLEDOVATELXNOSTI? s DRUGOJ STORONY, RASSMOTRIM OPREDELENIE~R2, I PUSTX $P$---SVOJSTVO POSLEDOVATELXNOSTI, SOSTOYASHCHEE V TOM, CHTO VSE EE |LEMENTY RAZLICHNY. sVOJSTVO~$P$ SPRAVEDLIVO S VEROYATNOSTXYU EDINICA, PO|TOMU LYUBAYA POSLEDOVATELXNOSTX S MILLIONOM NULEJ PO \emph{|TOMU} KRITERIYU NE YAVLYAETSYA SLUCHAJNOJ. pUSTX TEPERX SVOJSTVO~$P$ ZAKLYUCHAETSYA V TOM, CHTO \emph{NI ODIN} |LEMENT POSLEDOVATELXNOSTI NE RAVEN NULYU. oNO SPRAVEDLIVO S VEROYATNOSTXYU EDINICA, PO|TOMU PO OPREDELENIYU~R2 LYUBAYA POSLEDOVATELXNOSTX, U KOTOROJ ESTX NULEVOJ |LEMENT, NE YAVLYAETSYA SLUCHAJNOJ. rASSMOTRIM BOLEE OBSHCHIJ SLUCHAJ: PUSTX~$x_0$---LYUBOE ZADANNOE CHISLO, ZAKLYUCHENNOE MEZHDU NULEM I EDINICEJ, I~$P$---SVOJSTVO, SOSTOYASHCHEE V TOM, CHTO NI ODIN |LEMENT POSLEDOVATELXNOSTI NE RAVEN~$x_0$. iZ OPREDELENIYA~R2 SLEDUET, CHTO NIKAKAYA SLUCHAJNAYA POSLEDOVATELXNOSTX NE MOZHET SODERZHATX |LEMENT, RAVNYJ~$x_0$! tEPERX MOZHNO DOKAZATX, CHTO \emph{NI ODNA POSLEDOVATELXNOSTX NE MOZHET UDOVLETVORYATX USLOVIYAM, SFORMULIROVANNYM V OPREDELENII}~R2. (v SAMOM DELE, ESLI~$U_0$, $U_1$,~\dots{} ESTX POSLEDOVATELXNOSTX, UDOVLETVORYAYUSHCHAYA |TIM USLOVIYAM, TO POLOZHIM~$x_0=U_0$.) tAKIM OBRAZOM, ESLI~R1---SLISHKOM SLABOE OPREDELENIE, TO R2---SLISHKOM SILXNOE. "pRAVILXNOE" OPREDELENIE DOLZHNO BYTX MENEE OGRANICHITELXNYM, CHEM~R2. oDNAKO MY, VOOBSHCHE GOVORYA, ESHCHE NE DOKAZALI, CHTO R1 SLISHKOM SLABO, PO|TOMU PRODOLZHIM EGO IZUCHENIE. vYSHE GOVORILOSX O TOM, CHTO MOZHNO POSTROITX $\infty\hbox{-RASPREDELENNUYU}$ POSLEDOVATELXNOSTX \emph{RACIONALXNYH} CHISEL. (rAZUMEETSYA, V |TOM NET NICHEGO OSOBENNO UDIVITELXNOGO: SM.\ UPR.~1.8.) pOCHTI VSE DEJSTVITELXNYE CHISLA IRRACIONALXNY, PO|TOMU MOZHNO POTREBOVATX, CHTOBY DLYA SLUCHAJNOJ POSLEDOVATELXNOSTI IMELO MESTO RAVENSTVO \EQ{ \Pr(U_n \hbox{ RACIONALXNO})=0. } zAMETIM, CHTO RAVNOMERNAYA RASPREDELENNOSTX, PO OPREDELENIYU OZNACHAET, CHTO~$\Pr(u\le U_n$". v CHASTNOSTI, ESLI MNOZHESTVO~$S$ SOSTAVLENO IZ RACIONALXNYH CHISEL, ONO IMEET MERU NULX, I, TAKIM OBRAZOM, NIKAKAYA POSLEDOVATELXNOSTX RACIONALXNYH CHISEL NE YAVLYAETSYA RAVNOMERNO RASPREDELENNOJ V |TOM OBOBSHCHENNOM SMYSLE. mOZHNO OZHIDATX, CHTO TEOREMA~B OBOBSHCHAETSYA NA SLUCHAJ INTEGRIROVANIYA V SMYSLE lEBEGA, ESLI POTREBOVATX VYPOLNENIYA SVOJSTVA~\eqref[27]. oDNAKO MY OPYATX PRIHODIM K VYVODU, CHTO OPREDELENIE~\eqref[27] YAVLYAETSYA SLISHKOM ZHESTKIM, POSKOLXKU NI ODNA POSLEDOVATELXNOSTX \emph{NE} OBLADAET |TIM SVOJSTVOM! eSLI $U_0$, $U_1$,~\dots---NEKOTORAYA POSLEDOVATELXNOSTX, TO MERA MNOZHESTVA~$S=\set{U_0, U_1,~\ldots}$ RAVNA NULYU, ODNAKO~$\Pr(U_n\in S)=1$. tAKIM OBRAZOM, PUTEM TEH ZHE RASSUZHDENIJ, S POMOSHCHXYU KOTORYH MY ISKLYUCHILI IZ SLUCHAJNYH POSLEDOVATELXNOSTEJ RACIONALXNYE CHISLA, MOZHNO ISKLYUCHITX VSE SLUCHAJNYE POSLEDOVATELXNOSTI. pOKA VSE ESHCHE NE POKAZANO, CHTO OPREDELENIE~R1 NEPRIGODNO. pROTIV NEGO, ODNAKO, SUSHCHESTVUYUT VESKIE VOZRAZHENIYA. eSLI, NAPRIMER, IMEETSYA SLUCHAJNAYA V INTUITIVNOM SMYSLE POSLEDOVATELXNOSTX, BESKONECHNAYA EE PODPOSLEDOVATELXNOSTX \EQ[28]{ U_0, U_1, U_4, U_9,~\ldots, U_{n^2},~\ldots } DOLZHNA TAKZHE BYTX SLUCHAJNOJ. dLYA $\infty\hbox{-RASPREDELENNOJ}$ POSLEDOVATELXNOSTI |TO NE VSEGDA SPRAVEDLIVO. (dEJSTVITELXNO, ESLI VZYATX LYUBUYU $\infty\hbox{-RASPREDELENNUYU}$ POSLEDOVATELXNOSTX I POLOZHITX~$U_{n^2}\leftarrow 0$ DLYA VSEH~$n$, VELICHINY~$\nu_k(n)$, KOTORYE POYAVLYAYUTSYA PRI PROVERKE $k\hbox{-RASPREDELENNOSTI}$, IZMENYATSYA NE BOLXSHE, CHEM NA VELICHINU PORYADKA~$\sqrt{n}$, TAK CHTO PREDELY OTNOSHENIJ~$\nu_k(n)/n$ NE IZMENYATSYA.) oTSYUDA SLEDUET, CHTO~R1 NE OBLADAET |TIM SVOJSTVOM SLUCHAJNOSTI. pOPROBUEM USILITX~R1 SLEDUYUSHCHIM OBRAZOM. \proclaim oPREDELENIE~R3. pOSLEDOVATELXNOSTX NA~$[0, 1)$ NAZYVAETSYA "SLUCHAJNOJ", ESLI KAZHDAYA EE BESKONECHNAYA PODPOSLEDOVATELXNOSTX $\infty\hbox{-RASPREDELENA}$. oDNAKO I |TO OPREDELENIE OKAZYVAETSYA SLISHKOM OGRANICHITELXNYM, POSKOLXKU IZ LYUBOJ RAVNOMERNO RASPREDELENNOJ POSLEDOVATELXNOSTI~$\$ MOZHNO VYDELITX MONOTONNUYU PODPOSLEDOVATELXNOSTX~$U_{s_0}$ NA~$[0, 1)$ NAZYVAETSYA "SLUCHAJNOJ", ESLI KAKOV BY NI BYL |FFEKTIVNYJ ALGORITM, S POMOSHCHXYU KOTOROGO POLUCHAETSYA BESKONECHNAYA POSLEDOVATELXNOSTX RAZLICHNYH NEOTRICATELXNYH CELYH CHISEL~$s_n$, GDE~$n\ge0$, PODPOSLEDOVATELXNOSTX~$U_{s_0}$, $U_{s_1}$,~\dots, SOOTVETSTVUYUSHCHAYA |TOMU ALGORITMU, YAVLYAETSYA $\infty\hbox{-RASPREDELENNOJ}$. aLGORITMY, O KOTORYH IDET RECHX,---|TO PROCEDURY, VYCHISLYAYUSHCHIE~$s_n$ PO ZADANNOMU~$n$. v |TOM OPREDELENII GOVORITSYA OBO VSEH BESKONECHNYH "REKURSIVNO PERECHISLIMYH" PODPOSLEDOVATELXNOSTYAH V SOOTVETSTVII S OBYCHNYM OPREDELENIEM REKURSIVNOJ PERECHISLIMOSTI (SM.~GL.~11). oTNOSITELXNO DANNOGO OPREDELENIYA SLEDUET SDELATX NESKOLXKO ZAMECHANIJ. pOSLEDOVATELXNOSTX~$\<\pi^n\bmod 1>$ NAVERNYAKA \emph{NE} BUDET UDOVLETVORYATX OPREDELENIYU~R4, POSKOLXKU ILI ONA NE YAVLYAETSYA RAVNOMERNO RASPREDELENNOJ, ILI SUSHCHESTVUET |FFEKTIVNYJ ALGORITM, OPREDELYAYUSHCHIJ BESKONECHNUYU POSLEDOVATELXNOSTX~$s_n$, TAKUYU, CHTO~$(\pi^{s_0}\bmod 1) < (\pi^{s_1}\bmod 1) < \ldots\,$. mOZHNO PO|TOMU UTVERZHDATX, CHTO \emph{NI ODNA YAVNYM OBRAZOM OPREDELENNAYA POSLEDOVATELXNOSTX NE MOZHET UDOVLETVORYATX OPREDELENIYU}~R4. s |TIM SLEDUET SOGLASITXSYA, ESLI SCHITATX, CHTO YAVNYM OBRAZOM OPREDELENNAYA POSLEDOVATELXNOSTX NE MOZHET BYTX DEJSTVITELXNO SLUCHAJNOJ. vPOLNE VOZMOZHNO, ODNAKO, CHTO POSLEDOVATELXNOSTX~$\<\theta^n\bmod 1>$ BUDET UDOVLETVORYATX OPREDELENIYU~R4 DLYA POCHTI VSEH DEJSTVITELXNYH CHISEL~$\theta>1$. zDESX NET PROTIVORECHIYA, POSKOLXKU POCHTI VSE~$\theta$ NEVOZMOZHNO VYCHISLITX S POMOSHCHXYU ALGORITMA. iZVESTNY, NAPRIMER, SLEDUYUSHCHIE FAKTY. (i)~pOSLEDOVATELXNOSTX~$\<\theta^m\bmod 1>$ UDOVLETVORYAET OPREDELENIYU~R4 DLYA POCHTI VSEH DEJSTVITELXNYH~$\theta>1$, ESLI USLOVIE $\infty\hbox{-RASPREDELENNOSTI}$ ZAMENITX NA USLOVIE $1\hbox{-RASPREDELENNOSTI}$. eTA TEOREMA BYLA DOKAZANA yu.~kOKSMOJ ({\sl Compositio Mathematica,\/} {\bf 2} (1935), 250--258). (ii)~pOSLEDOVATELXNOSTX~$\<\theta^{s(n)}\bmod 1>$ $\infty\hbox{-RASPREDELENA}$ DLYA POCHTI VSEH DEJSTVITELXNYH~$\theta>1$, ESLI~$\$ ESTX POSLEDOVATELXNOSTX CELYH CHISEL, TAKIH, CHTO~$s(n+1)-s(n)\to\infty$ PRI~$n\to\infty$. mOZHNO, NAPRIMER, POLOZHITX~$s(n)=n^2$, ILI~$s(n)=\floor{n\log n}$. oPREDELENIE~R4 NAMNOGO SILXNEE OPREDELENIYA~R1, ODNAKO I ONO VSE ESHCHE SLISHKOM SLABO. pUSTX, NAPRIMER, IMEETSYA ISTINNO SLUCHAJNAYA POSLEDOVATELXNOSTX~$\$. oPREDELIM PODPOSLEDOVATELXNOSTX~$\$ SLEDUYUSHCHIM OBRAZOM: $s_0=0$, I DLYA~$n>0$ CHISLO~$s_n$---NAIMENXSHEE POLOZHITELXNOE CELOE, TAKOE, CHTO VSE CHISLA~$U_{s_n-1}$, $U_{s_n-2}$,~\dots, $U_{s_n-n}$ MENXSHE POLOVINY. tEM SAMYM MY RASSMATRIVAEM PODPOSLEDOVATELXNOSTX VELICHIN, SLEDUYUSHCHIH SRAZU ZHE ZA SERIEJ IZ $n$~CHLENOV, KAZHDYJ IZ KOTORYH MENXSHE~$1/2$. pREDPOLOZHIM, CHTO "$U_n<1/2$" SOOTVETSTVUET VYPADENIYU "RESHETKI" PRI BROSANII MONETY. iGROKI OBYCHNO SCHITAYUT, CHTO ESLI MONETA BROSAETSYA CHESTNO, TO DLINNAYA SERIYA VYPADENIYA "RESHETOK" UVELICHIVAET %% 175 VEROYATNOSTX POSLEDUYUSHCHEGO VYPADENIYA "ORLA", I OPREDELENNAYA NAMI PODPOSLEDOVATELXNOSTX~$\$ SOOTVETSTVUET STRATEGII IGROKA, PRI KOTOROJ ON DELAET $n\hbox{-YU}$~STAVKU PRI BROSANII MONETY, SLEDUYUSHCHEM VSLED ZA PERVYM POSLEDOVATELXNYM VYPADENIEM $n$~"RESHETOK". iGROK MOZHET SCHITATX, CHTO~$\Pr(U_{s_n}\ge 1/2)$ PREVOSHODIT POLOVINU, NO, RAZUMEETSYA, V ISTINNO SLUCHAJNOJ POSLEDOVATELXNOSTI ZNACHENIYA~$\$ BUDUT SOVERSHENNO SLUCHAJNYMI. nET TAKOJ STRATEGII, KOTORAYA OBESPECHIVALA BY PREIMUSHCHESTVO V IGRE. v OPREDELENII~R4 NICHEGO NE GOVORITSYA O PODPOSLEDOVATELXNOSTYAH, SOSTAVLENNYH SOGLASNO TAKOJ STRATEGII, PO|TOMU NUZHNO PREDLOZHITX NECHTO BOLXSHEE. oPREDELIM "PRAVILO POSTROENIYA PODPOSLEDOVATELXNOSTI"~$\cR$ KAK BESKONECHNUYU POSLEDOVATELXNOSTX FUNKCIJ~$\$, GDE~$n\ge0$, $f_n$---FUNKCIYA $n$~PEREMENNYH, I~$f_n(x_1,~\ldots, x_n)$ MOZHET PRINIMATX ZNACHENIE~$0$ ILI~$1$. zDESX $x_1$,~\dots, $x_n$ YAVLYAYUTSYA |LEMENTAMI NEKOTOROGO MNOZHESTVA~$S$. (tAKIM OBRAZOM, $f_0$~ESTX POSTOYANNAYA FUNKCIYA, RAVNAYA~$0$ ILI~$1$.) pRAVILO~$\cR$ POSTROENIYA PODPOSLEDOVATELXNOSTI OPREDELYAET PODPOSLEDOVATELXNOSTX LYUBOJ BESKONECHNOJ POSLEDOVATELXNOSTI~$\$ |LEMENTOV~$S$ SLEDUYUSHCHIM OBRAZOM: \dfn{$n\hbox{-J}$ CHLEN~$X_n$ SODERZHITSYA V PODPOSLEDOVATELXNOSTI~$\\cR$ V TOM I TOLXKO TOM SLUCHAE, KOGDA~$f_n(X_0, X_1,~\dots, X_{n-1})=1$.} zAMETIM, CHTO OPREDELENNAYA TAKIM OBRAZOM PODPOSLEDOVATELXNOSTX~$\\cR$ NE OBYAZATELXNO YAVLYAETSYA BESKONECHNOJ I MOZHET DAZHE BYTX PUSTOJ. "pODPOSLEDOVATELXNOSTX IGROKA", OPISANNAYA VYSHE, SOOTVETSTVUET SLEDUYUSHCHEMU PRAVILU POSTROENIYA PODPOSLEDOVATELXNOSTI: "$f_0=1$; $f_n(x_1,~\ldots, x_n)=1$ PRI~$n>0$ V TOM I TOLXKO TOM SLUCHAE, KOGDA SUSHCHESTVUET NEKOTOROE~$k$, $0$ NA~$[0, 1)$ NAZYVAETSYA "SLUCHAJNOJ", ESLI $b\hbox{-ICHNAYA}$ POSLEDOVATELXNOSTX~$\<\floor{bU_n}>$ "SLUCHAJNA" DLYA VSEH CELYH CHISEL~$b\ge2$. } zAMETIM, CHTO V OPREDELENII~R5 PODPOSLEDOVATELXNOSTX "$1\hbox{-RASPREDELENA}$", A NE "$\infty\hbox{-RASPREDELENA}$". iNTERESNO ZAMETITX, CHTO OBSHCHNOSTX PRI |TOM NE TERYAETSYA. v SAMOM DELE, DLYA LYUBOGO $b\hbox{-ICHNOGO}$ CHISLA~$a_1\ldots a_k$ MOZHNO TAK OPREDELITX OCHEVIDNYM OBRAZOM VYCHISLIMOE PRAVILO~$\cR(a_1{}\ldots{}a_k)$ POSTROENIYA PODPOSLEDOVATELXNOSTI. pOLOZHIM~$f_n(x_1,~\dots, x_n)=1$ V TOM I TOLXKO TOM SLUCHAE KOGDA~$n\ge k-1$ I~$x_{n-k+1}=a_1$,~\dots, $x_{n-1}=a_{k-1}$, $x_n=a_k$. eSLI $\$ YAVLYAETSYA $k\hbox{-RASPREDELENNOJ}$ $b\hbox{-ICHNOJ}$ POSLEDOVATELXNOSTXYU, TO UPOMYANUTOE PRAVILO~$\cR(a_1\ldots{}a_k)$, KOTOROE OTBIRAET PODPOSLEDOVATELXNOSTX, SOSTOYASHCHUYU IZ CHLENOV, SLEDUYUSHCHIH SRAZU ZA POYAVLENIEM~$a_1{}\ldots{}a_k$, OPREDELYAET BESKONECHNUYU PODPOSLEDOVATELXNOSTX, I ESLI |TA PODPOSLEDOVATELXNOSTX $1\hbox{-RASPREDELENA}$, TO KAZHDYJ IZ NABOROV, SOSTOYASHCHIH IZ $k+1$~|LEMENTOV $a_1\ldots{}a_k{}a_{k+1}$, PRI USLOVII, CHTO~$0\le a_{k+1}$ S VEROYATNOSTXYU~$1/b^{k+1}$. tAKIM OBRAZOM, INDUKCIEJ PO~$k$ MOZHNO DOKAZATX, CHTO POSLEDOVATELXNOSTX, UDOVLETVORYAYUSHCHAYA OPREDELENIYU~R5, $k\hbox{-pacPREDELENA}$ DLYA VSEH~$k$. aNALOGICHNYM OBRAZOM, RASSMATRIVAYA "KOMPOZICIYU" PRAVIL POSTROENIYA PODPOSLEDOVATELXNOSTEJ (ESLI $\cR_1$~OPREDELYAET BESKONECHNUYU PODPOSLEDOVATELXNOSTX~$\\cR_1$, MOZHNO OPREDELITX~$\cR_1\cR_2$ KAK PRAVILO POSTROENIYA PODPOSLEDOVATELXNOSTI, TAKOE, CHTO~$\\cR_1\cR_2=((\\cR_1) \cR_2)$, MY PRIHODIM K VYVODU, CHTO VSE PODPOSLEDOVATELXNOSTI, OPISANNYE V OPREDELENII~R5, $\infty\hbox{-RASPREDELENY}$ (SM.\ UPR.~32). pOSKOLXKU $\infty\hbox{-RASPREDELENNOSTX}$ SLEDUET IZ OPREDELENIYA~R5 KAK OCHENX CHASTNYJ SLUCHAJ, MOZHNO NADEYATXSYA NA TO, CHTO MY, NAKONEC, SFORMULIROVALI ISKOMOE OPREDELENIE SLUCHAJNOSTI. nO, UVY, OSTAETSYA ESHCHE ODNA PROBLEMA! vOVSE NE OCHEVIDNO, CHTO POSLEDOVATELXNOSTI, UDOVLETVORYAYUSHCHIE OPREDELENIYU~R4, DOLZHNY TAKZHE UDOVLETVORYATX OPREDELENIYU~R5. "vYCHISLIMYE PRAVILA POSTROENIYA PODPOSLEDOVATELXNOSTEJ", KOTORYE MY VVELI, VSEGDA PERECHISLYAYUT PODPOSLEDOVATELXNOSTI~$\$, DLYA KOTORYH~$s_0$ NE OBYAZANA BYTX MONOTONNOJ; DOLZHNO LISHX SOBLYUDATXSYA USLOVIE~$s_n\ne s_m$, PRI~$n=m$. sTOLKNUVSHISX S TAKIM PREPYATSTVIEM, MY PRIHODIM K KOMBINACII OPREDELENIJ~R4 I~R5. \proclaim oPREDELENIE~R6. {$b\hbox{-ICHNAYA}$ POSLEDOVATELXNOSTX~$\$ NAZYVAETSYA "SLUCHAJNOJ", ESLI DLYA LYUBOGO |FFEKTIVNOGO ALGORITMA, OPREDELYAYUSHCHEGO BESKONECHNUYU POSLEDOVATELXNOSTX RAZLICHNYH NEOTRICATELXNYH CELYH CHISEL~$\$ KAK FUNKCIYU OT~$n$ I ZNACHENIJ~$X_{s_0}$,~\dots, $X_{s_{n-1}}$, SOOTVETSTVUYUSHCHAYA PODPOSLEDOVATELXNOSTX~$\$ "SLUCHAJNA" V SMYSLE OPREDELENIYA~R5. \hiddenpar pOSLEDOVATELXNOSTX~$\$ NA~$[0, 1)$ NAZYVAETSYA "SLUCHAJNOJ", ESLI $b\hbox{-ICHNAYA}$ POSLEDOVATELXNOSTX~$\<\floor{bU_n}>$ "SLUCHAJNA" PRI VSEH CELYH CHISLAH~$b\ge 2$. } aVTOR UTVERZHDAET, CHTO |TO OPREDELENIE, NESOMNENNO, OTVECHAET VSEM RAZUMNYM FILOSOFSKIM TREBOVANIYAM, PREDŽYAVLYAEMYM K PONYATIYU SLUCHAJNOSTI, I, TAKIM OBRAZOM, DAET OTVET NA GLAVNYJ VOPROS, POSTAVLENNYJ ZDESX. \section{D.~sUSHCHESTVOVANIE SLUCHAJNYH POSLEDOVATELXNOSTEJ}. mY VIDELI, CHTO OPREDELENIE~R3 POTOMU OKAZALOSX SLISHKOM SILXNYM, CHTO NI ODNA POSLEDOVATELXNOSTX EMU NE UDOVLETVORYALA, I VVODYA OPREDELENIYA~R4, R5 I~R6, MY STARALISX SOHRANITX OSNOVNYE SVOJSTVA OPREDELENIYA~R3. dLYA TOGO CHTOBY POKAZATX, CHTO OPREDELENIE~R6 NE YAVLYAETSYA SLISHKOM OGRANICHITELXNYM, SLEDUET DOKAZATX FAKT SUSHCHESTVOVANIYA POSLEDOVATELXNOSTEJ, UDOVLETVORYAYUSHCHIH SOOTVETSTVUYUSHCHIM TREBOVANIYAM. iSHODYA IZ INTUITIVNYH SOOBRAZHENIJ, NIKTO NE SOMNEVAETSYA V IH SUSHCHESTVOVANII, POSKOLXKU KAZHDYJ VERIT V TO, CHTO ISTINNO SLUCHAJNYE POSLEDOVATELXNOSTI SUSHCHESTVUYUT I UDOVLETVORYAYUT OPREDELENIYU~R6. oDNAKO CHTOBY UBEDITXSYA V SOSTOYATELXNOSTI OPREDELENIYA, NEOBHODIMO DOKAZATELXSTVO. iNTERESNYJ METOD POSTROENIYA POSLEDOVATELXNOSTEJ, UDOVLETVORYAYUSHCHIH OPREDELENIYU~R5, PREDLOZHIL a.~vALXD. sNACHALA STROITSYA OCHENX PROSTAYA $1\hbox{-RASPREDELENNAYA}$ POSLEDOVATELXNOSTX. \proclaim lEMMA~T. pUSTX V DVOICHNOJ SISTEME SCHISLENIYA OPREDELENA POSLEDOVATELXNOSTX DEJSTVITELXNYH CHISEL~$\$: \EQ[29]{ V_0=0, V_1=.1, V_2=.01, V_3=.11, V_4=.001,~\ldots, V_n=.c_r\ldots{}c_1 1, \rem{ESLI~$n=2^r+c_12^{r-1}+\cdots+c_r$.} } pUSTX $I_{b_1\ldots{}b_r}$~OBOZNACHAET MNOZHESTVO TAKIH DEJSTVITELXNYH CHISEL NA OTREZKE~$[0, 1)$, DVOICHNOE PREDSTAVLENIE KOTORYH NACHINAETSYA S~$0.b_1\ldots{}b_r$. tAKIM OBRAZOM, \EQ[30]{ I_{b_1\ldots{}b_r}=[0.b_1\ldots{} b_r, 0.b_1\ldots{}b_r+2^{-r}). } %%178 tOGDA, ESLI $\nu(n)$~OBOZNACHAET KOLICHESTVO CHISEL~$V_k$, SODERZHASHCHIHSYA V~$I_{b_1\ldots{}b_r}$ PRI~$0\le k < n$, IMEET MESTO NERAVENSTVO \EQ[31]{ \abs{\nu(n)/n-2^{-r}}\le 1/n. } \proof pOSKOLXKU $\nu(n)$~ESTX CHISLO TEH~$k$, DLYA KOTORYH~$k\bmod 2^r=b_r\ldots{}b_1$, MY IMEEM~$\nu(n)=t$ ILI~$t+1$, KOGDA~$\floor{n/2^r}=t$. tAKIM OBRAZOM, $\abs{\nu(n)-n/2^r}\le 1$. \proofend iZ FORMULY~\eqref[31] SLEDUET, CHTO POSLEDOVATELXNOSTX~$\<\floor{2^rV_n}>$ YAVLYAETSYA RAVNOMERNO RASPREDELENNOJ $2^r\hbox{-ICHNOJ}$ POSLEDOVATELXNOSTXYU; OTSYUDA I IZ TEOREMY~A ZAKLYUCHAEM, CHTO~$\$---RAVNOMERNO RASPREDELENNAYA NA~$[0, 1)$ POSLEDOVATELXNOSTX. v SAMOM DELE, YASNO, CHTO~$\$ NASTOLXKO RAVNOMERNO RASPREDELENA, NASKOLXKO MOZHET BYTX RAVNOMERNO RASPREDELENNOJ POSLEDOVATELXNOSTX NA~$[0, 1)$! (dALXNEJSHEE OBSUZHDENIE SVOJSTV |TOJ I SVYAZANNYH S NEJ POSLEDOVATELXNOSTEJ IMEETSYA V STATXYAH i.~VAN~DER~kORPUTA ({\sl Proc. Koninklijke Nederlandse Akademie van Wetenschappen,\/} {\bf 38} (1935), 813--821, 1058--1066) I dZH.~hOLTONA ({\sl Numerische Mathematik,\/} {\bf 2} (1960), 84--90, 196). pUSTX TEPERX~$\cR_1$, $\cR_2$,~\dots---BESKONECHNOE MNOZHESTVO PRAVIL POSTROENIYA PODPOSLEDOVATELXNOSTEJ. mY HOTIM NAJTI POSLEDOVATELXNOSTX~$\$, VSE BESKONECHNYE PODPOSLEDOVATELXNOSTI~$\\cR_j$ KOTOROJ RAVNOMERNO RASPREDELENY. \alg W.(pOSLEDOVATELXNOSTX vALXDA.) eTA PROCEDURA OPREDELYAET POSLEDOVATELXNOSTX~$\$ NA~$[0, 1)$, ESLI ZADANO BESKONECHNOE MNOZHESTVO PRAVIL POSTROENIYA PODPOSLEDOVATELXNOSTEJ~$\cR_1$, $\cR_2$,~\dots, OPREDELYAYUSHCHIH PODPOSLEDOVATELXNOSTI POSLEDOVATELXNOSTEJ \emph{RACIONALXNYH} CHISEL NA~$[0, 1)$. pRI VYCHISLENII TREBUETSYA BESKONECHNO BOLXSHOE KOLICHESTVO VSPOMOGATELXNYH PEREMENNYH~$C[a_1,~\ldots,a_r]$, GDE~$r\ge 1$ I~$a_j=0$ ILI~$1$, $1\le j \le r$. v NACHALXNYJ MOMENT VREMENI VSE |TI PEREMENNYE RAVNY NULYU. \st[nACHALXNAYA USTANOVKA~$n$.] uSTANOVITX~$n\asg 0$. \st[nACHALXNAYA USTANOVKA~$r$.] uSTANOVITX~$r\asg 1$. \st[pROVERITX~$\cR_r$.] eSLI |LEMENT~$U_n$, DOLZHEN POPASTX V PODPOSLEDOVATELXNOSTX, OPREDELYAEMUYU~$\cR_r$, NA OSNOVANII ZNACHENIJ~$U_k$, GDE~$0\le k < n$, TO NUZHNO PRISVOITX~$a_r\asg 1$, V PROTIVNOM SLUCHAE---PRISVOITX~$a_r\asg 0$. \st[$B[a_1,~\ldots, a_r]$ POLNO?] eSLI~$C[a_1,~\ldots, a_r]<3\cdot 4^{r-1}$, PEREJTI K~\stp{6}. \st[uVELICHITX~$r$.] uSTANOVITX~$r\asg r+1$ I VOZVRATITXSYA K~\stp{3}. \st[uSTANOVITX~$U_n$.] uVELICHITX~$C[a_1,~\ldots, a_r]$ NA~$1$. pUSTX $k$~ESTX NOVOE ZNACHENIE~$C[a_1,~\ldots, a_r]$. uSTANOVITX~$U_n\asg V_k$, GDE VELICHINA~$V_k$ OPREDELENA VYSHE V LEMME~T. \st[uVELICHITX~$n$.] uVELICHITX~$n$ NA~$1$ I VOZVRATITXSYA K~\stp{2}. \algend %% 179 sTROGO GOVORYA, |TO NE ESTX ALGORITM, POSKOLXKU ON NE KONECHEN. lEGKO, ODNAKO, IZMENITX EGO TAK, CHTOBY ON ZAKANCHIVALSYA, KOGDA $n$~DOSTIGAET ZADANNOJ VELICHINY. chITATELYU LEGCHE BUDET POCHUVSTVOVATX IDEYU PRIVEDENNOGO POSTROENIYA, ESLI ON POPROBUET "PROKRUTITX" EGO VRUCHNUYU, ZAMENIV PRI |TOM CHISLO~$3\cdot 4^{r-1}$ NA SHAGE~W4 NA~$2^r$. aLGORITM~W NE PREDNAZNACHEN DLYA PRIMENENIYA V KACHESTVE DATCHIKA SLUCHAJNYH CHISEL, ON SLUZHIT LISHX TEORETICHESKIM CELYAM. \proclaim tEOREMA~W. pUSTX~$U_n$---POSLEDOVATELXNOSTX RACIONALXNYH CHISEL, OPREDELENNAYA S POMOSHCHXYU ALGORITMA~W, I~$k$---POLOZHITELXNOE CELOE CHISLO. eSLI PODPOSLEDOVATELXNOSTX~$\\cR_k$ BESKONECHNA, TO ONA $1\hbox{-RASPREDELENA}$. \proof pUSTX $A[a_1,~\ldots, a_r]$ OBOZNACHAET PODPOSLEDOVATELXNOSTX (MOZHET BYTX, PUSTUYU) POSLEDOVATELXNOSTI~$\$, SODERZHASHCHUYU TE I TOLXKO TE |LEMENTY~$U_n$, KOTORYE DLYA VSEH~$j$, TAKIH, CHTO~$1\le j \le r$, PRINADLEZHAT PODPOSLEDOVATELXNOSTI~$\\cR_j$, ESLI~$a_j=1$, I NE PRINADLEZHAT PODPOSLEDOVATELXNOSTI~$\\cR_j$, ESLI~$a_j=0$. dOSTATOCHNO DOKAZATX, CHTO DLYA VSEH~$r\ge 1$ I VSEH PAR DVOICHNYH CHISEL~$a_1\ldots{}a_r$ I~$b_1\ldots{}b_r$ IMEET MESTO RAVENSTVO~$\Pr(U_n \in I_{b_1\ldots{}b_r})=2^{-r}$ PO OTNOSHENIYU K PODPOSLEDOVATELXNOSTI~$A[a_1\ldots{}a_r]$ V TOM SLUCHAE, KOGDA POSLEDNYAYA BESKONECHNA [SM.~\eqref[30]]. v SAMOM DELE, ESLI~$r\ge k$, TO BESKONECHNAYA POSLEDOVATELXNOSTX~$\\cR_k$ PREDSTAVLYAET SOBOJ KONECHNOE OBŽEDINENIE NEPERESEKAYUSHCHIHSYA PODPOSLEDOVATELXNOSTEJ~$A[a_1,~\ldots, a_r]$ DLYA~$a_k=1$ I~$a_j=0$ ILI~$1$ PRI~$1\le j \le r$, $j\ne k$; SLEDOVATELXNO, $\Pr(U_n\in I_{b_1\ldots{}b_r})=2^{-r}$ PO OTNOSHENIYU K~$\\cR_k$ (SM.~UPR.~33). dOSTATOCHNO VOSPOLXZOVATXSYA ESHCHE TEOREMOJ~A, CHTOBY POKAZATX, CHTO POSLEDOVATELXNOSTX $1\hbox{-RASPREDELENA}$. pUSTX $B[a_1,~\ldots, a_r]$ OBOZNACHAET PODPOSLEDOVATELXNOSTX |LEMENTOV~$\$, DLYA KOTORYH~$C[a_1,~\ldots, a_r]$ UVELICHIVAETSYA NA EDINICU NA SHAGE~W6 ALGORITMA. kAK VIDNO IZ ALGORITMA, $B[a_1,~\ldots, a_r]$---KONECHNAYA POSLEDOVATELXNOSTX, MAKSIMALXNOE CHISLO |LEMENTOV KOTOROJ RAVNO~$3\cdot4^{r-1}$. vSE CHLENY~$A[a_1,~\ldots, a_r]$, KROME KONECHNOGO IH CHISLA, BERUTSYA IZ PODPOSLEDOVATELXNOSTEJ~$B[a_1,~\ldots, a_r,~\ldots, a_t]$, GDE~$a_j=0$ ILI~$1$ PRI~$r$, GDE~$s_0$---POSLEDOVATELXNOSTX RACIONALXNYH CHISEL NA~$[0, 1)$ I ESLI~$\cR$---VYCHISLIMOE PRAVILO POSTROENIYA PODPOSLEDOVATELXNOSTI CHLENOV $b\hbox{-ICHNOJ}$ POSLEDOVATELXNOSTI, MY MOZHEM PREVRATITX~$\cR$ V VYCHISLIMOE PRAVILO~$\cR'$ POSTROENIYA PODPOSLEDOVATELXNOSTI CHLENOV~$\$, POLOZHIV~$f'_n(x_1,~\ldots, x_n)$ V~$\cR'$ RAVNYM~$f_n(\floor{bx_1},~\ldots, \floor{bx_n})$ V~$\cR$. eSLI POSLEDOVATELXNOSTX~$\\cR'$ RAVNOMERNO RASPREDELENA, TO |TIM ZHE SVOJSTVOM OBLADAET I~$\<\floor{bU_n}>\cR$. mNOZHESTVO VSEH VYCHISLIMYH PRAVIL POSTROENIYA PODPOSLEDOVATELXNOSTEJ $b\hbox{-ICHNYH}$ POSLEDOVATELXNOSTEJ PRI VSEH ZNACHENIYAH~$b$ SCHETNO (POSKOLXKU SUSHCHESTVUET LISHX SCHETNOE KOLICHESTVO |FFEKTIVNYH ALGORITMOV), PO|TOMU EGO |LEMENTY MOZHNO PERECHISLITX V VIDE NEKOTOROJ POSLEDOVATELXNOSTI~$\cR_1$, $\cR_2$,~$\ldots\,$. oTSYUDA SLEDUET, CHTO ALGORITM~W OPREDELYAET POSLEDOVATELXNOSTX NA~$[0, 1)$, KOTORAYA YAVLYAETSYA SLUCHAJNOJ V SMYSLE OPREDELENIYA~R5. tEPERX MY OKAZALISX V NESKOLXKO PARADOKSALXNOM POLOZHENII. kAK OTMECHALOSX RANXSHE, |FFEKTIVNYJ ALGORITM, KOTORYJ OPREDELYAL BY POSLEDOVATELXNOSTX, UDOVLETVORYAYUSHCHUYU OPREDELENIYU~R4, SUSHCHESTVOVATX NE MOZHET, I PO TOJ ZHE PRICHINE NE MOZHET SUSHCHESTVOVATX |FFEKTIVNYJ ALGORITM, OPREDELYAYUSHCHIJ POSLEDOVATELXNOSTX, UDOVLETVORYAYUSHCHUYU OPREDELENIYU~R5. dOKAZATELXSTVO SUSHCHESTVOVANIYA TAKOJ SLUCHAJNOJ POSLEDOVATELXNOSTI PO NEOBHODIMOSTI DOLZHNO BYTX NEKONSTRUKTIVNYM. kAKIM ZHE OBRAZOM |TA POSLEDOVATELXNOSTX POLUCHAETSYA PO ALGORITMU~W? pROTIVORECHIYA ZDESX NET. dELO V TOM, CHTO NEVOZMOZHNO S POMOSHCHXYU |FFEKTIVNOGO ALGORITMA PRONUMEROVATX MNOZHESTVO VSEH ALGORITMOV. dRUGIMI SLOVAMI, |FFEKTIVNYJ ALGORITM, KOTORYJ %% 181 \bye