\input style \chapnotrue\chapno=3\subchno=3\subsubchno=1 ITX \dfn{|MPIRICHESKUYU FUNKCIYU RASPREDELENIYA~$F_n(x)$:} $$ F_n(x)={\hbox{CHISLO TAKIH $X_1$, $X_2$,~\dots, $X_n$, KOTORYE~$\le x$} \over n}. \eqno(10) $$ nA RIS.~4 POKAZANY TRI |MPIRICHESKIE FUNKCII RASPREDELENIYA (VERTIKALXNYE LINII, STROGO GOVORYA, NE YAVLYAYUTSYA CHASTXYU GRAFIKA~$F_n(x)$). tAM ZHE IZOBRAZHENY I ISTINNYE FUNKCII RASPREDELENIYA~$F(x)$. pRI UVELICHENII~$n$ FUNKCII~$F_n(x)$ DOLZHNY VSE BOLEE TOCHNO APPROKSIMIROVATX~$F(x)$. kRITERIJ kOLMOGOROVA---sMIRNOVA (ks-KRITERIJ) MOZHNO ISPOLXZOVATX V TEH SLUCHAYAH, KOGDA FUNKCIYA~$F(x)$ NE IMEET SKACHKOV. oN OSNOVAN NA \emph{RAZNOSTI MEZHDU~$F(x)$ I~$F_n(x)$.} pLOHOJ DATCHIK SLUCHAJNYH CHISEL BUDET DAVATX |MPIRICHESKIE FUNKCII RASPREDELENIYA, PLOHO APPROKSIMIRUYUSHCHIE~$F(x)$. nA RIS.~4,~b PRIVEDEN PRIMER, KOGDA ZNACHENIYA~$X_i$ SLISHKOM VELIKI, TAK CHTO KRIVAYA |MPIRICHESKOJ FUNKCII RASPREDELENIYA PROHODIT SLISHKOM NIZKO. nA RIS.~4,~c PREDSTAVLEN ESHCHE HUDSHIJ SLUCHAJ; YASNO, CHTO TAKIE BOLXSHIE RASHOZHDENIYA MEZHDU~$F_n(x)$ I~$F(x)$ KRAJNE MALOVEROYATNY; ks-KRITERIJ DOLZHEN UKAZATX, NASKOLXKO ONI MALOVEROYATNY. dLYA |TOGO FORMIRUYUTSYA SLEDUYUSHCHIE STATISTIKI: $$ \eqalign{ K_n^+&=\sqrt{n}\max_{-\inftyF$, A~$K_n^-$---KAKOVO MAKSIMALXNOE OTKLONENIE DLYA SLUCHAYA~$F_n30$ PRIVEDENY TEORETICHESKI NE OBOSNOVANNYE INTERPOLYACIONNYE FORMULY, TOCHNYE TOLXKO PRI~$n=\infty$)} } & p=99\% & p=95\% & p=75\% & p=50\% & p=25\% & p=5\% & p=1\%\cr n=1 & 0.01000 & 0.05000 & 0.2500 & 0.5000 & 0.7500 & 0.9500 & 0.9900\cr n=2 & 0.01400 & 0.06749 & 0.2929 & 0.5176 & 0.7071 & 1.0980 & 1.2728\cr n=3 & 0.01699 & 0.07919 & 0.3112 & 0.5147 & 0.7539 & 1.1017 & 1.3589\cr n=4 & 0.01943 & 0.08789 & 0.3202 & 0.5110 & 0.7642 & 1.1304 & 1.3777\cr n=5 & 0.02152 & 0.09471 & 0.3249 & 0.5245 & 0.7674 & 1.1392 & 1.4024\cr n=6 & 0.02336 & 0.1002 & 0.3272 & 0.5319 & 0.7703 & 1.1463 & 1.4144\cr n=7 & 0.02501 & 0.1048 & 0.3280 & 0.5364 & 0.7755 & 1.1537 & 1.4246\cr n=8 & 0.02650 & 0.1086 & 0.3280 & 0.5392 & 0.7797 & 1.1586 & 1.4327\cr n=9 & 0.02786 & 0.1119 & 0.3274 & 0.5411 & 0.7825 & 1.1624 & 1.4388\cr n=10 & 0.02912 & 0.1147 & 0.3297 & 0.5426 & 0.7845 & 1.1658 & 1.4440\cr n=11 & 0.03028 & 0.1172 & 0.3330 & 0.5439 & 0.7863 & 1.1688 & 1.4484\cr n=12 & 0.03137 & 0.1193 & 0.3357 & 0.5453 & 0.7880 & 1.1714 & 1.4521\cr n=15 & 0.03424 & 0.1244 & 0.3412 & 0.5500 & 0.7926 & 1.1773 & 1.4606\cr n=20 & 0.03807 & 0.1298 & 0.3461 & 0.5547 & 0.7975 & 1.1839 & 1.4698\cr n=30 & 0.04354 & 0.1351 & 0.3509 & 0.5605 & 0.8036 & 1.1916 & 1.4801\cr & 0.07089 & 0.1601 & 0.3793 & 0.5887 & 0.8326 & 1.2239 & 1.5174 \cr n>30 & -{0.15\over \sqrt n} & -{0.14\over \sqrt n} & -{0.15\over \sqrt n} & -{0.15\over \sqrt n} & -{0.16\over \sqrt n} & -{0.17\over \sqrt n} & -{0.20\over \sqrt n}\cr } DLYA VSEH~$n$, TAK CHTO ks-KRITERIJ MOZHNO PRIMENYATX PRI LYUBOM~$n$. fORMULY~(11) NE GODYATSYA DLYA MASHINNYH RASCHETOV, TAK KAK TREBUETSYA OTYSKATX MAKSIMALXNOE SREDI BESKONECHNOGO MNOZHESTVA CHISEL! oDNAKO TOT FAKT, CHTO~$F(x)$---NEUBYVAYUSHCHAYA FUNKCIYA, a $F_n(x)$~IMEET KONECHNOE CHISLO SKACHKOV, POZVOLYAET OPREDELITX STATISTIKI~$K_n^+$ I~$K_n^-$ S POMOSHCHXYU SLEDUYUSHCHEGO PROSTOGO ALGORITMA: {\sl shAG~1.\/} oPREDELYAYUTSYA VYBOROCHNYE ZNACHENIYA~$X_1$, $X_2$,~\dots, $X_n$. {\sl shAG~2.\/} zNACHENIYA~$X_i$ RASPOLAGAYUTSYA V PORYADKE VOZRASTANIYA TAK, CHTOBY~$X_1\le X_2 \le \ldots \le X_n$. (eFFEKTIVNYE ALGORITMY, SORTIROVKI BUDUT RASSMOTRENY V GL.~5.) %% 64 {\sl shAG~3.\/}~nUZHNYE NAM STATISTIKI VYCHISLYAYUTSYA TEPERX PO FORMULAM $$ \eqalign{ K_n^+&=\sqrt{n}\max_{1\le j \le n}\left({j\over n}-F(X_j)\right),\cr K_n^-&=\sqrt{n}\max_{1\le j \le n}\left(F(X_j)-{j-1\over n}\right).\cr } \eqno(13) $$ sDELATX NADLEZHASHCHIJ VYBOR CHISLA ISPYTANIJ~$n$ V DANNOM SLUCHAE NESKOLXKO LEGCHE, CHEM PRI RABOTE S KRITERIEM~$\chi^2$, HOTYA NEKOTORYE TRUDNOSTI SOHRANYAYUTSYA. eSLI ISTINNOE RASPREDELENIE SLUCHAJNYH VELICHIN~$X_j$ NE OTVECHAET FUNKCII~$F(x)$, A OPISYVAETSYA KAKOJ-TO DRUGOJ FUNKCIEJ~$G(x)$, POTREBUETSYA SRAVNITELXNO MNOGO ISPYTANIJ, CHTOBY UDOSTOVERITXSYA, CHTO~$G(x)\ne F(x)$; $n$~DOLZHNO BYTX NASTOLXKO BOLXSHIM, CHTOBY STALO ZAMETNYM RAZLICHIE MEZHDU~$G_n(x)$ I~$F_n(x)$. s DRUGOJ STORONY, PRI BOLXSHIH~$n$ IMEETSYA TENDENCIYA K OSREDNENIYU LOKALXNYH OTKLONENIJ OT SLUCHAJNOGO POVEDENIYA. tAKIE OTKLONENIYA OSOBENNO NEZHELATELXNY V BOLXSHINSTVE PRILOZHENIJ SLUCHAJNYH CHISEL PRI RABOTE NA VYCHISLITELXNYH MASHINAH. s |TOJ TOCHKI ZRENIYA BYLO BY POLEZNO \emph{UMENXSHITX}~$n$. tOT FAKT CHTO VSE $n$~REZULXTATOV ISPYTANIJ NADO ZAPOMNITX, CHTOBY POTOM RASPOLOZHITX V PORYADKE VOZRASTANIYA, TAKZHE SKLONYAET NAS K MYSLI UMENXSHITX~$n$. v KACHESTVE KOMPROMISSNOGO RESHENIYA MOZHNO VZYATX~$n$ RAVNYM, SKAZHEM, $1000$ I VYCHISLITX DOSTATOCHNO MNOGO ZNACHENIJ~$K_{1000}^+$ S ISPOLXZOVANIEM RAZNYH CHASTEJ SLUCHAJNOJ POSLEDOVATELXNOSTI: $$ K_{1000}^+(1), \quad K_{1000}^+(2), \quad \ldots, \quad K_{1000}^+(r). \eqno(14) $$ k \emph{|TIM} CHISLAM MOZHNO \emph{OPYATX} PRIMENITX ks-KRITERIJ. tEPERX UZHE $F(x)$---FUNKCIYA RASPREDELENIYA DLYA~$K_{1000}^+$, PRICHEM ONA OPREDELYAETSYA |MPIRICHESKOJ FUNKCIEJ RASPREDELENIYA~$F_r(x)$, POSTROENNOJ PO SLUCHAJNYM ZNACHENIYAM~(14). k SCHASTXYU, FUNKCIYA RASPREDELENIYA~$F(x)$ OCHENX PROSTA: PRI BOLXSHIH ZNACHENIYAH~$n$, NAPRIMER $n=1000$, RASPREDELENIE DLYA~$K_n^+$ HOROSHO APPROKSIMIRUETSYA FUNKCIEJ $$ F_{\infty}(x)=1-e^{-2x^2}, \rem{$x \ge 0$}. \eqno(15) $$ vSE SKAZANNOE OTNOSITSYA I K~$K_n^-$, TAK KAK~$K_n^+$ I~$K_n^-$ VEDUT SEBYA ODINAKOVO. \emph{tAKOJ PODHOD, KOGDA SNACHALA KRITERIJ MNOGOKRATNO PRIMENYAETSYA PRI OTNOSITELXNO NEBOLXSHIH~$n$, A ZATEM VSE REZULXTATY KOMBINIRUYUTSYA, POSLE CHEGO ks-KRITERIJ PRIMENYAETSYA POVTORNO, POZVOLYAET VYYAVITX KAK LOKALXNYE, TAK I GLOBALXNYE OTKLONENIYA OT ZADANNOGO ZAKONA RASPREDELENIYA.} pOLNYJ |KSPERIMENT (HOTYA GORAZDO MENXSHEGO OB®EMA) BYL PROVEDEN AVTOROM V HODE RABOTY NAD NASTOYASHCHEJ GLAVOJ. tEST "NAIBOLXSHEE IZ~5", OPISANNYJ V SLEDUYUSHCHEM RAZDELE, PRIMENYALSYA K~$1000$ RAVNOMERNO RASPREDELENNYH SLUCHAJNYH CHISEL. pOLUCHILOSX %% 65 200~CHISEL $X_1$, $X_2$,~\dots, $X_{200}$, OTNOSITELXNO KOTORYH PREDPOLAGALOSX, CHTO ONI RASPREDELENY V SOOTVETSTVII S FUNKCIEJ~$F(x)=x^5$ ($0\le x \le 1$). vSE REZULXTATY BYLI RAZDELENY NA 20~GRUPP PO 10~CHISEL, I DLYA KAZHDOJ GRUPPY VYCHISLYALASX STATISTIKA~$K_{10}^+$. pO POLUCHENNYM TAKIM OBRAZOM 20~ZNACHENIYAM~$K_{10}^+$ BYLI POSTROENY |MPIRICHESKIE RASPREDELENIYA, IZOBRAZHENNYE NA RIS.~4; GLADKIE KRIVYE SOOTVETSTVUYUT PREDPOLAGAEMOJ FUNKCII RASPREDELENIYA DLYA STATISTIKI~$K_{10}^+$. nA RIS.~4,~a PREDSTAVLENO |MPIRICHESKOE RASPREDELENIE DLYA~$K_{10}^+$, SOOTVETSTVUYUSHCHEE POSLEDOVATELXNOSTI SLUCHAJNYH CHISEL $$ \eqalign{ Y_{n+1}&=(3141592653Y_n+2718281829) \bmod 2^{35},\cr U_n&=Y_n/2^{35}.\cr } $$ eTU POSLEDOVATELXNOSTX MOZHNO PRIZNATX UDOVLETVORITELXNOJ. rIS.~4,~b SOOTVETSTVUET POSLEDOVATELXNOSTI, POLUCHENNOJ METODOM fIBONACHCHI; ZDESX NABLYUDAYUTSYA OTKLONENIYA \emph{GLOBALXNOGO} HARAKTERA, T.~E.\ MOZHNO POKAZATX, CHTO ZNACHENIYA~$X_n$ DLYA TESTA "NAIBOLXSHEE IZ~5" NE PODCHINYAYUTSYA RASPREDELENIYU~$F(x)=x^5$. nA RIS.~4,~c PRIVEDENY REZULXTATY PROVERKI POSLEDOVATELXNOSTI, POLXZUYUSHCHEJSYA SLAVOJ SLABOGO ALGORITMA: $$ Y_{n+1}=((2^{18}+1)Y_n+1)\bmod 2^{35}, \quad U_n=Y_n/2^{35}. $$ rEZULXTATY PRIMENENIYA ks-KRITERIYA K |TIM DANNYM BYLI UZHE PRIVEDENY V~(12). oBRASHCHAYASX K TABL.~2 S~$n=20$, POLUCHAEM, CHTO ZNACHENIYA~$K_{20}^+$ I~$K_{20}^-$ V SLUCHAE~(b) SLEGKA PODOZRITELXNY (ONI POPADAYUT POCHTI NA~$95\hbox{-}$ I~$12\%\hbox{-NYE}$ UROVNI), NO NE NASTOLXKO PLOHI, CHTOBY MOZHNO BYLO S UVERENNOSTXYU OTBROSITX |TU POSLEDOVATELXNOSTX. zNACHENIE~$K_{20}^-$ DLYA SLUCHAYA~(c), BEZUSLOVNO, NIKUDA NE GODITSYA, TAK CHTO TEST "NAIBOLXSHEE IZ~5" OPREDELENNO DOKAZYVAET NEPRIGODNOSTX |TOGO DATCHIKA SLUCHAJNYH CHISEL. v OPISANNOM |KSPERIMENTE ks-KRITERIJ DOLZHEN VYYAVLYATX GLOBALXNYE OTKLONENIYA OT SLUCHAJNOGO POVEDENIYA HUZHE, CHEM LOKALXNYE, TAK KAK KAZHDAYA GRUPPA SOSTOYALA VSEGO IZ 10~ISPYTANIJ. eSLI BY BYLO VZYATO 20~GRUPP PO 1000~ISPYTANIJ, OTKLONENIE V SLUCHAE~(b) BYLO BY BOLEE ZNACHITELXNYM. dLYA ILLYUSTRACII |TOGO ks-KRITERIJ BYL PRIMENEN \emph{SRAZU} KO VSEM DANNYM, PO KOTORYM POSTROENY GRAFIKI NA RIS.~4. pRI |TOM POLUCHILISX SLEDUYUSHCHIE REZULXTATY: $$ \matrix{ & a & b & c \cr K_{200}^+ & 0.477 & 1.537 & 2.819 \cr K_{200}^- & 0.817 & 0.194 & 0.058 \cr } \eqno(16) $$ tEPERX UZHE SO VSEJ OPREDELENNOSTXYU VYYAVILISX GLOBALXNYE OTKLONENIYA OT ZADANNOGO ZAKONA RASPREDELENIYA, KOTORYJ DAET METOD fIBONACHCHI. lOKALXNYE OTKLONENIYA V SLUCHAE~(c) SKAZYVAYUTSYA VPLOTX DO~$n=1\,000\,000$, TAK CHTO PRI~$n=200$ GOVORITX O GLOBALXNYH OTKLONENIYAH NE PRIHODITSYA. %% 66 kRITERIJ kOLMOGOROVA---sMIRNOVA ZAKLYUCHAETSYA, TAKIM OBRAZOM, V SLEDUYUSHCHEM. s POMOSHCHXYU $n$~\emph{NEZAVISIMYH ISPYTANIJ} POLUCHAYUTSYA ZNACHENIYA~$X_1$,~\dots, $X_n$ SLUCHAJNOJ VELICHINY S \emph{NEPRERYVNOJ} FUNKCIEJ RASPREDELENIYA~$F(x)$. ($F(x)$~DOLZHNA BYTX TIPA FUNKCIJ, IZOBRAZHENNYH NA RIS.~3,~b I~3,~c, T.~E.\ BEZ SKACHKOV KAK NA RIS.~3,~a.) zATEM S POMOSHCHXYU PROCEDURY, OPISANNOJ PERED FORMULOJ~(13), VYCHISLYAYUTSYA STATISTIKI~$K_n^+$ I~$K_n^-$. eTI STATISTIKI DOLZHNY BYTX RASPREDELENY V SOOTVETSTVII S TABL.~2. tEPERX MOZHNO SRAVNITX KRITERII kOLMOGOROVA---sMIRNOVA I~$\chi^2$. pREZHDE VSEGO SLEDUET ZAMETITX, CHTO ks-KRITERIEM MOZHNO POLXZOVATXSYA \emph{V SOCHETANII S} KRITERIEM~$\chi^2$, CHTOBY POLUCHITX LUCHSHUYU PROCEDURU, CHEM METOD ad hoc, UPOMYANUTYJ PRI ZAVERSHENII OPISANIYA KRITERIYA~$\chi^2$. (eTO ZNACHIT, CHTO SUSHCHESTVUET BOLEE SOVERSHENNYJ SPOSOB, NEZHELI PROVEDENIE TREH PROVEROK, CHTOBY VYYASNITX, KAK MNOGO REZULXTATOV OKAZHUTSYA "PODOZRITELXNYMI".) pREDPOLOZHIM, CHTO S POMOSHCHXYU KRITERIYA~$\chi^2$ BYLI NEZAVISIMO OBRABOTANY, SKAZHEM, 10~RAZNYH UCHASTKOV SLUCHAJNOJ POSLEDOVATELXNOSTI, V REZULXTATE CHEGO BYLI POLUCHENY ZNACHENIYA~$V_1$, $V_2$,~\dots, $V_{10}$. oBYCHNYJ PODSCHET KOLICHESTVA PODOZRITELXNO BOLXSHIH ILI MALYH ZNACHENIJ~$V$---NE LUCHSHIJ SPOSOB ANALIZA (HOTYA V |KSTREMALXNYH SLUCHAYAH ON BUDET RABOTATX, I \emph{OCHENX} BOLXSHIE ILI \emph{OCHENX} MALYE ZNACHENIYA MOGUT SLUZHITX UKAZANIEM NA TO, CHTO DANNAYA POSLEDOVATELXNOSTX SODERZHIT SLISHKOM MNOGO LOKALXNYH OTKLONENIJ). zNACHITELXNO LUCHSHE POSTROITX PO |TIM 10~ZNACHENIYAM |MPIRICHESKUYU FUNKCIYU RASPREDELENIYA I SRAVNITX EE S TEORETICHESKOJ FUNKCIEJ RASPREDELENIYA, KOTORUYU MOZHNO POLUCHITX S POMOSHCHXYU TABL.~1. pOSLE OPREDELENIYA STATISTIK~$K_{10}^+$ I~$K_{10}^-$ FORMIRUETSYA OKONCHATELXNOE SUZHDENIE OB ISHODE PROVERKI POSLEDOVATELXNOSTI S POMOSHCHXYU KRITERIYA~$\chi^2$. pRI~10 ILI DAZHE 100~ZNACHENIYAH VSE |TO LEGKO MOZHNO SDELATX VRUCHNUYU, ISPOLXZUYA GRAFICHESKIE METODY; PRI BOLXSHEM CHISLE ZNACHENIJ~$V$ POTREBUETSYA PODPROGRAMMA DLYA MASHINNOGO RASCHETA RASPREDELENIYA~$\chi^2$. oTMETIM, CHTO \emph{VSE 20~TOCHEK NA RIS.~4,~c POPADAYUT V INTERVAL MEZHDU $5\hbox{-}$ I~$95\%\hbox{-NYMI}$ UROVNYAMI,} TAK CHTO \emph{KAZHDAYA} IZ NIH V OTDELXNOSTI NE MOZHET RASSMATRIVATXSYA KAK PODOZRITELXNAYA; ODNAKO SUMMARNOE |MPIRICHESKOE RASPREDELENIE YAVNO NE SOVPADAET S TEORETICHESKIM. vAZHNOE RAZLICHIE MEZHDU KRITERIYAMI kOLMOGOROVA---sMIRNOVA I~$\chi^2$ ZAKLYUCHAETSYA V TOM, CHTO PERVYJ IZ NIH PRIMENYAETSYA K RASPREDELENIYAM, NE IMEYUSHCHIM SKACHKOV, V TO VREMYA KAK VTOROJ---K KUSOCHNO POSTOYANNYM RASPREDELENIYAM (TAK KAK VSE REZULXTATY DELYATSYA NA $k$~KATEGORIJ). tAKIM OBRAZOM, OBLASTI PRILOZHENIYA |TIH KRITERIEV RAZLICHNY. pRAVDA, KRITERIJ~$\chi^2$ MOZHNO PRIMENYATX I DLYA NEPRERYVNYH RASPREDELENIJ, ESLI RAZDELITX VSYU OBLASTX OPREDELENIYA~$F(x)$ NA $k$~CHASTEJ I PRENEBRECHX VARIACIYAMI V PREDELAH KAZHDOGO INTERVALA. eSLI, NAPRIMER, MY HOTIM VYYASNITX, RASPREDELENY LI ZNACHENIYA~$U_1$, $U_2$,~\dots, $U_n$ RAVNOMERNO MEZHDU %% 67 NULEM I EDINICEJ, T.~E.\ SOOTVETSTVUET LI IH RASPREDELENIE FUNKCII~$F(x)=x$ PRI~$0\le x \le 1$, BUDET ESTESTVENNO PRIMENITX ks-KRITERIJ. nO MOZHNO TAKZHE RAZDELITX INTERVAL OT~$0$ DO~$1$ NA~$k=100$ RAVNYH CHASTEJ, PODSCHITATX, SKOLXKO V KAZHDUYU IZ NIH POPADAET ZNACHENIJ~$U$, POSLE CHEGO ISPOLXZOVATX KRITERIJ~$\chi^2$ S 99~STEPENYAMI SVOBODY. v NASTOYASHCHEE VREMYA NE SUSHCHESTVUET DOSTATOCHNO OPREDELENNYH TEORETICHESKIH REZULXTATOV, POZVOLYAYUSHCHIH SRAVNIVATX |FFEKTIVNOSTI |TIH DVUH KRITERIEV. aVTOR OBNARUZHIL PRIMERY, V KOTORYH ks-KRITERII VYYAVLYAL OTKLONENIYA OT SLUCHAJNOSTI BOLEE YAVSTVENNO, CHEM KRITERIJ~$\chi^2$, A TAKZHE I PRIMERY PROTIVOPOLOZHNOGO HARAKTERA. eSLI, NAPRIMER, INTERVALY, NA KOTORYE RAZBIVAETSYA PROMEZHUTOK~$(0, 1)$, PRONUMEROVANY OT~$0$ DO~$99$ I OTKLONENIYA OT SREDNIH ZNACHENIJ POLOZHITELXNY V INTERVALAH~$0$--$49$ I OTRICATELXNY V INTERVALAH~$50$--$99$, TO |MPIRICHESKAYA FUNKCIYA RASPREDELENIYA BUDET ZNACHITELXNO DALXSHE OT~$F(x)$, CHEM MOZHNO BYLO BY PREDPOLOZHITX PO ZNACHENIYU~$\chi^2$. nO ESLI OTKLONENIYA POLOZHITELXNY V INTERVALAH~$0$, $2$,~\dots, $98$ I OTRICATELXNY V INTERVALAH~$1$, $3$,~\dots, $99$, TO |MPIRICHESKAYA FUNKCIYA RASPREDELENIYA BUDET GORAZDO BLIZHE K~$F(x)$. oTSYUDA VIDNO, CHTO HARAKTER REGISTRIRUEMYH OTKLONENIJ NESKOLXKO RAZLICHEN. dLYA $200$~CHISEL, PO KOTORYM POSTROENY GRAFIKI NA RIS.~4, KRITERIJ~$\chi^2$ S~$k=10$ DAET ZNACHENIYA~$V$, RAVNYE~$9.4$, $17.7$ I~$39.3$; V |TOM KONKRETNOM SLUCHAE POLUCHENNYE ZNACHENIYA VPOLNE SRAVNIMY S TEMI, KOTORYE DAET ks-KRITERIJ (SM.~(16)). dLYA NEPRERYVNYH RASPREDELENIJ ks-KRITERIJ OBLADAET OPREDELENNYMI PREIMUSHCHESTVAMI, TAK KAK KRITERIJ~$\chi^2$ PO OPREDELENIYU IMEET PRIBLIZHENNYJ HARAKTER I TREBUET OTNOSITELXNO BOLXSHIH ZNACHENIJ~$n$. iNTERESNO TAKZHE POSMOTRETX, KAK IZMENYATSYA REZULXTATY PROVERKI SHESTI RAZNYH DATCHIKOV SLUCHAJNYH CHISEL, PRIVEDENNYE NA RIS.~2, ESLI VMESTO KRITERIYA~$\chi^2$ ISPOLXZOVATX ks-KRITERIJ. eTI REZULXTATY BYLI POLUCHENY DLYA~$n=200$ S POMOSHCHXYU KRITERIYA "NAIBOLXSHEE IZ~$t$" PRI~$1\le t \le 5$; PROMEZHUTOK~$(0, 1)$ RAZDELYALSYA NA~$10$~RAVNYH CHASTEJ. pO NIM MOZHNO VYCHISLITX STATISTIKI~$K_{200}^+$ I~$K_{200}^-$ I POLUCHENNYE REZULXTATY PREDSTAVITX V TOM ZHE VIDE, KAK NA RIS.~2 (OTMECHAYA, KAKIE ZNACHENIYA VYHODYAT ZA UROVENX~$99\%$ I~T.~D.). eTO SDELANO NA RIS.~5. oTMETIM, CHTO DATCHIK~D (METOD lEMERA), SUDYA PO RIS.~5, VESXMA PLOH, V TO VREMYA KAK REZULXTATY OBRABOTKI \emph{TEH ZHE SAMYH DANNYH} PO KRITERIYU~$\chi^2$ NE OBNARUZHILI NIKAKIH OTKLONENIJ. dATCHIK~E (METOD fIBONACHCHI), NAOBOROT, NA RIS.~5 VYGLYADIT NESKOLXKO LUCHSHE. hOROSHIE DATCHIKI~A I~B UDOVLETVORYAYUT VSEM KRITERIYAM. pRICHINY RASHOZHDENIJ MEZHDU RIS.~2 I~5 ZAKLYUCHAYUTSYA V PERVUYU OCHEREDX V TOM, CHTO (a)~CHISLO ISPYTANIJ~$200$ NA SAMOM DELE NEDOSTATOCHNO VELIKO; (b)~RAZDELENIE REZULXTATOV NA "NEGODNYE", "PODOZRITELXNYE" I "SLEGKA PODOZRITELXNYE" SAMO PO SEBE DOVOLXNO PODOZRITELXNO. (bYLO BY NESPRAVEDLIVOSTXYU OBVINYATX lEMERA V TOM, CHTO ON %% 68 ISPOLXZOVAL V 1948~G.\ "PLOHOJ" DATCHIK SLUCHAJNYH CHISEL, POTOMU CHTO V DANNOM KONKRETNOM SLUCHAE |TO BYLO VPOLNE ZAKONNO. mASHINA ENIAC RABOTALA V PARALLELXNOM REZHIME I PROGRAMMIROVALASX POSREDSTVOM KOMMUTACIONNOJ PANELI. lEMER USTANOVIL TAKOJ REZHIM, PRI KOTOROM SODERZHIMOE ODNOGO IZ SUMMATOROV \picture{rIS.~5. rEZULXTATY PRIMENENIYA ks-KRITERIYA K TEM ZHE DANNYM, CHTO I NA RIS.~2.} POSTOYANNO UMNOZHALOSX NA~$23$ PO MODULYU~$10^8+1$; SODERZHIMOE SUMMATORA IZMENYALOSX KAZHDYE NESKOLXKO MIKROSEKUND. mNOZHITELX~$23$ SLISHKOM MAL, CHTOBY TAKUYU POSLEDOVATELXNOSTX MOZHNO BYLO SCHITATX SLUCHAJNOJ: KORRELYACIYA MEZHDU SLEDUYUSHCHIMI NEPOSREDSTVENNO DRUG ZA DRUGOM CHISLAMI PRI TAKOM MNOZHITELE SLISHKOM VELIKA. nO PROMEZHUTOK VREMENI MEZHDU OBRASHCHENIYAMI K SUMMATORU, SODERZHASHCHEMU SLUCHAJNOE CHISLO, BYL SRAVNITELXNO VELIK I, KROME TOGO, VSE VREMYA MENYALSYA. tAK CHTO FAKTICHESKI MNOZHITELX BYL RAVEN~$23^k$, GDE~$k$---BOLXSHOE, IZMENYAYUSHCHEESYA CHISLO!) \section {C. iSTORIYA, BIBLIOGRAFIYA I TEORIYA}. kRITERIJ~$\chi^2$ BYL PREDLOZHEN kARLOM pIRSONOM V 1900~G. ({\sl Philosophical Magazine,\/} Series~5, {\bf 50}, 157--175). eTA RABOTA pIRSONA SCHITAETSYA ODNOJ IZ OSNOVOPOLAGAYUSHCHIH V SOVREMENNOJ STATISTIKE, TAK KAK DO NEE KACHESTVO |KSPERIMENTALXNYH REZULXTATOV OPREDELYALOSX PROSTO PO TOMU, KAK ONI VYGLYADYAT NA GRAFIKE. v SVOEJ STATXE pIRSON PRIVODIT NESKOLXKO INTERESNYH PRIMEROV NEPRAVILXNOGO ISPOLXZOVANIYA STATISTIKI. %% 68 oN POKAZAL TAKZHE, CHTO V NEKOTORYH SLUCHAYAH RULETKA (NA KOTOROJ ON |KSPERIMENTIROVAL V mONTE-kARLO V TECHENIE DVUH NEDELX V 1892~G.) DAVALA REZULXTATY, NASTOLXKO DALEKIE OT SREDNIH ZNACHENIJ, CHTO PRI PRAVILXNOM USTROJSTVE RULETKI ONI MOGLI BY OSUSHCHESTVITXSYA NE CHASHCHE, CHEM ODIN RAZ IZ~$10^{29}$. oBSHCHEE OBSUZHDENIE KRITERIYA~$\chi^2$ I OBSHIRNAYA BIBLIOGRAFIYA SODERZHATSYA V OBZORNOJ STATXE u.~kOKR|NA (W.~G.~Cochran, {\sl Annals of Mathematical Statistics,\/} {\bf 23} (1952), 315--345). iZLOZHIM V SOKRASHCHENNOM VIDE TEORIYU, LEZHASHCHUYU V OSNOVE KRITERIYA~$\chi^2$. tOCHNAYA VEROYATNOSTX TOGO, CHTO~$Y_1=y_1$,~\dots, $Y_k=y_k$ RAVNA, KAK LEGKO VIDETX, $$ {n! \over y_1! \ldots y_k!} p_1^{y_1}\ldots p_k^{y_k}. \eqno(17) $$ eSLI PREDPOLOZHITX, CHTO $Y_s$~IMEET RASPREDELENIE pUASSONA S PLOTNOSTXYU $$ {e^{-np_s} (np_s)^{y_s} \over y_s!} $$ I SLUCHAJNYE VELICHINY~$Y_s$ NEZAVISIMY, TO VEROYATNOSTX OSUSHCHESTVLENIYA ZNACHENIJ~$(y_1,~\ldots, y_k)$ RAVNA $$ \prod_{1\le s \le k} {e^{-np_s} (np_s)^{y_s} \over y_s!}, $$ A SUMMA~$Y_1+\cdots+Y_k$ BUDET RAVNA~$n$ S VEROYATNOSTXYU $$ \sum_{ \scriptstyle y_1+\cdots+y_k=n \atop \scriptstyle y_1, \ldots, y_k \ge 0 }\prod_{1\le s \le k} {e^{-np_s}(np_s)^{y_s}\over y_s!}={e^{-n}n^n\over n!}. $$ eSLI POTREBOVATX SOBLYUDENIYA USLOVIYA~$Y_1+\cdots+Y_k=n$, A V \emph{OSTALXNOM} SCHITATX SLUCHAJNYE VELICHINY NEZAVISIMYMI, TO VEROYATNOSTX TOGO, CHTO~$(Y_1,~\ldots, Y_k)=(y_1,~\ldots, y_k)$, BUDET RAVNA $$ \left(\prod_{1\le s\le k} {e^{np_s}(np_s)^{y_s}\over y_s!}\right) \bigg/ \left({e^{-n}n^n\over n!}\right), $$ CHTO SOVPADAET S~(17). \emph{mOZHNO, SLEDOVATELXNO, SCHITATX, CHTO SLUCHAJNYE VELICHINY~$Y$ IMEYUT RASPREDELENIE pUASSONA I NEZAVISIMY, S EDINSTVENNYM OGRANICHENIEM, CHTO IH SUMMA FIKSIROVANA.} oBOZNACHIM $$ Z_s={Y_s-np_s \over \sqrt{np_s}},\quad V=Z_1^2+\cdots+Z_k^2. \eqno(18) $$ uSLOVIE~$Y_1+\cdots+Y_k=n$ MOZHNO ZAPISATX V VIDE $$ \sqrt{p_1}Z_1+\cdots+\sqrt{p_k}Z_k=0. \eqno(19) $$ %% 70 rASSMOTRIM $(k-1)\hbox{-MERNOE}$ PROSTRANSTVO~$S$ VEKTOROV~$(Z_1,~\ldots, Z_k)$, DLYA KOTORYH VYPOLNYAETSYA USLOVIE~(19). pRI BOLXSHIH ZNACHENIYAH~$n$ SLUCHAJNYE VELICHINY~$Z_s$ PRIBLIZITELXNO NORMALXNY (SM.~UPR.~1.2.10-16), TAK CHTO VEROYATNOSTX VYBORA TOCHKI, PRINADLEZHASHCHEJ |LEMENTARNOMU OB®EMU~$dZ_2~\ldots{} dZ_k$ V~$S$ \emph{PRIBLIZHENNO} PROPORCIONALXNA~$\exp(-(Z_1^2+\cdots+Z_k^2)/2)$. (iMENNO |TOT MOMENT V VYVODE PRIVODIT K TOMU, CHTO KRITERIJ~$\chi^2$ YAVLYAETSYA LISHX APPROKSIMACIEJ, SPRAVEDLIVOJ DLYA BOLXSHIH~$n$.) tEPERX VEROYATNOSTX TOGO, CHTO~$V\le v$, RAVNA $$ {\displaystyle\int_{\scriptstyle (Z_1,\ldots, Z_k)\hbox{ V } S\atop\scriptstyle\hbox{ I } Z_1^2+\cdots+Z_k^2\le v} \exp(-(Z_1^2+\cdots+Z_k^2)/2)\,dz_2\ldots dz_k \over \displaystyle\int_{(Z_1,\ldots, Z_k)\hbox{ V } S} \exp(-(Z_1^2+\cdots+Z_k^2)/2) \,dz_2\ldots dz_k }. \eqno(20) $$ tAK KAK PLOSKOSTX~(19) PROHODIT CHEREZ NACHALO KOORDINAT V $k\hbox{-MERNOM}$ PROSTRANSTVE, INTEGRIROVANIE V ZNAMENATELE PROVODITSYA PO OB®EMU SFERY V $(k-1)\hbox{-MERNOM}$ PROSTRANSTVE S CENTROM V NACHALE KOORDINAT. pREOBRAZOVANIEM K OBOBSHCHENNYM POLYARNYM KOORDINATAM S RADIUSOM~$\chi$ I UGLAMI~$\omega_1$,~\dots, $\omega_{k-2}$ FORMULA~(20) PRIVODITSYA K VIDU $$ {\displaystyle\int_{\chi^2 \le v} e^{-\chi^2/2}\chi^{k-2} f(\omega_1,~\ldots, \omega_{k-2}) \, d\chi\, d\omega_1\ldots d\omega_{k-2} \over \displaystyle\int e^{-\chi^2/2}\chi^{k-2} f(\omega_1, \ldots, \omega_{k-2})\, d\chi\, d\omega_1\ldots d\omega_{k-2} }; $$ FUNKCIYA~$f$ OPREDELENA V UPR.~15. pRI INTEGRIROVANII PO UGLAM~$\omega_1$,~\dots, $\omega_{k-2}$ V CHISLITELE I ZNAMENATELE POYAVLYAETSYA MNOZHITELX, NA KOTORYJ MOZHNO SOKRATITX. v KONCE KONCOV POLUCHAETSYA FORMULA $$ {\displaystyle\int_0^{\sqrt{v}} e^{-\chi^2/2}\chi^{k-2}\, d\chi \over \displaystyle\int_0^\infty e^{-\chi^2/2}\chi^{k-2}\,d\chi }, \eqno(21) $$ PRIBLIZHENNO PREDSTAVLYAYUSHCHAYA VEROYATNOSTX TOGO, CHTO~$V\le v$. v |TOM VYVODE RADIUS OBOZNACHEN CHEREZ~$\chi$, KAK V ORIGINALXNOJ RABOTE pIRSONA; OTSYUDA KRITERIJ~$\chi^2$ I POLUCHIL SVOE NAZVANIE. pODSTAVLYAYA~$t=\chi^2/2$, MOZHNO VYRAZITX INTEGRALY CHEREZ NEPOLNUYU GAMMA-FUNKCIYU, KOTORAYA UZHE ISPOLXZOVALASX V P.~1.2.11.3: $$ \lim_{n\to\infty} P\{V\le v\}=\gamma\left({k-1\over 2}, {v\over2}\right)\bigg/\Gamma\left({k-1\over 2}\right). \eqno(22) $$ tAKOVO OPREDELENIE RASPREDELENIYA~$\chi^2$ S $(k-1)$~STEPENYAMI SVOBODY. %% 71 pEREJDEM TEPERX K ks-KRITERIYU. v 1933~G.\ a.~n.~kOLMOGOROV PREDLOZHIL KRITERIJ, OSNOVANNYJ NA STATISTIKE $$ K_n=\sqrt{n}\max_{-\infty=U_0, U_1, U_2, \ldots\,, \eqno(1) $$ KOTORYE DOLZHNY BYTX RASPREDELENY RAVNOMERNO MEZHDU NUL¸M I EDINICEJ. nEKOTORYE TESTY PREDNAZNACHENY V PERVUYU OCHEREDX DLYA PROVERKI CELOCHISLENNYH POSLEDOVATELXNOSTEJ, A NE POSLEDOVATELXNOSTEJ DEJSTVITELXNYH CHISEL TIPA~(1). v |TOM SLUCHAE PROVERKE PODVERGAETSYA VSPOMOGATELXNAYA POSLEDOVATELXNOSTX $$ \=Y_0, Y_1, Y_2, \ldots\,, \eqno(2) $$ KOTORAYA OPREDELYAETSYA SLEDUYUSHCHIM OBRAZOM: $$ Y_n=\floor{d U_n}. \eqno(3) $$ vHODYASHCHIE V |TU POSLEDOVATELXNOSTX CELYE CHISLA RASPREDELENY RAVNOMERNO MEZHDU~$0$ I~$d-1$, ESLI CHISLA~(1) RASPREDELENY RAVNOMERNO MEZHDU~$0$ I~$1$. zNACHENIE~$d$ MOZHET BYTX LYUBYM; NAPRIMER, NA MASHINE, RABOTAYUSHCHEJ V DVOICHNOJ SISTEME, MOZHNO VYBRATX~$d=64=2^6$; TOGDA~$Y_n$ BUDUT OPREDELYATXSYA SHESTXYU NAIBOLEE ZNACHIMYMI RAZRYADAMI V DVOICHNOM PREDSTAVLENII~$U_n$. chTOBY TEST BYL PREDSTAVITELXNYM, ZNACHENIE~$d$ DOLZHNO BYTX DOSTATOCHNO BOLXSHIM, NO NE SLISHKOM, CHTOBY PRI REALIZACII TESTA NA MASHINE NE VOZNIKALO ZATRUDNENIJ. vVEDENNYE ZDESX OBOZNACHENIYA~$U_n$, $Y_n$ I~$d$ BUDUT ISPOLXZOVATXSYA V DANNOM RAZDELE NEODNOKRATNO. zNACHENIE~$d$ MOZHET BYTX RAZNYM V RAZNYH TESTAH. \section{A.~pROVERKA RAVNOMERNOSTI (PROVERKA CHASTOT)}. pERVOE TREBOVANIE, PRED®YAVLYAEMOE K POSLEDOVATELXNOSTI~(1), ZAKLYUCHAETSYA V TOM, CHTOBY CHISLA~$U_n$ BYLI DEJSTVITELXNO RAVNOMERNO RASPREDELENY MEZHDU NULEM I EDINICEJ. pROVERITX RAVNOMERNOSTX MOZHNO DVUMYA SPOSOBAMI: (a)~S~POMOSHCHXYU KRITERIYA kOLMOGOROVA---sMIRNOVA, VZYAV~$F(x)=x$ PRI~$0\le x \le 1$; (b)~VYBRATX KAKOE-NIBUDX UDOBNOE ZNACHENIE~$d$, NAPRIMER~$100$, NA MASHINE, RABOTAYUSHCHEJ V DESYATICHNOJ %% 76 SISTEME, LIBO~$64$ I~$128$ NA MASHINE, RABOTAYUSHCHEJ V DVOICHNOJ SISTEME, POSLE CHEGO ISPOLXZOVATX POSLEDOVATELXNOSTX~(2) VMESTO~(1). zATEM DLYA KAZHDOGO CELOGO~$r$, $0\le r < d$, PODSCHITATX CHISLO ZNACHENIJ~$Y_j=r$ PRI~$0 \le j < n$ I PRIMENITX KRITERIJ~$\chi^2$ S~$k=d$ I VEROYATNOSTYAMI~$p_s=1/d$. oBOSNOVANIE OBOIH PODHODOV MOZHNO NAJTI V PREDYDUSHCHEM RAZDELE. \section{B.~pROVERKA SERIJ}. pROVERYAETSYA RAVNOMERNOSTX I NEZAVISIMOSTX PAR SLEDUYUSHCHIH DRUG ZA DRUGOM SLUCHAJNYH CHISEL. dLYA |TOGO PODSCHITYVAETSYA, SKOLXKO RAZ VSTRECHAETSYA KAZHDAYA PARA~$(Y_{2j}, Y_{2j+1})=(q, r)$ PRI~$0 \le j < n$. vELICHINY~$q$ I~$m$ MOGUT PRINIMATX LYUBYE ZNACHENIYA OT~$0$ DO~$d$. zATEM PRIMENYAETSYA KRITERIJ~$\chi^2$ S CHISLOM KATEGORIJ~$k=d^2$ I RAVNYMI VEROYATNOSTYAMI~$1/d^2$ VO VSEH KATEGORIYAH. zNACHENIE~$d$ VYBIRAETSYA IZ TEH ZHE SOOBRAZHENIJ, CHTO I V PREDYDUSHCHEM TESTE, NO V DANNOM SLUCHAE ONO DOLZHNO BYTX NESKOLXKO MENXSHE, TAK KAK PRIMENYATX KRITERIJ~$\chi^2$ SLEDUET PRI ZNACHENIYAH~$n$, SUSHCHESTVENNO PREVYSHAYUSHCHIH~$k$ (SKAZHEM, PO KRAJNEJ MERE PRI~$n>5d^2$). oCHEVIDNO, CHTO MOZHNO OBOBSHCHITX |TOT TEST NA TROJKI, CHETVERKI I~T.~D.\ (SM.~UPR.~2); ODNAKO ZNACHENIYA~$d$ DOLZHNY BYTX PRI |TOM REZKO UMENXSHENY, CHTOBY CHISLO KATEGORIJ NE POLUCHALOSX SLISHKOM BOLXSHIM. pO|TOMU PRI OB®EDINENII CHETYREH I BOLEE |LEMENTOV ISPOLXZUYUTSYA MENEE TOCHNYE TESTY, TAKIE, KAK "NAIBOLXSHEE IZ~$t$" ILI PROVERKA KOMBINACIJ (ONI BUDUT OPISANY NIZHE). oTMETIM, CHTO V |TOM TESTE V $n$~ISPYTANIYAH ISPOLXZUETSYA $2n$~CHISEL POSLEDOVATELXNOSTI~(2). bYLO BY OSHIBKOJ SOSTAVLYATX V DANNOM SLUCHAE PARY~$(Y_0, Y_1)$, $(Y_1, Y_2)$,~\dots, $(Y_{n-1}, Y_n)$; PONYATNO LI CHITATELYU, POCHEMU? dLYA PAR~$(Y_{2j+1}, Y_{2j+2})$ MOZHNO BYLO BY SOSTAVITX SPECIALXNYJ TEST I PROVERYATX KAZHDUYU POSLEDOVATELXNOSTX S POMOSHCHXYU OBOIH TESTOV. s DRUGOJ STORONY, KAK POKAZAL gUD, ({\sl Annals af Mathematical Statistics,\/} {\bf 28}, (1957), 262--264), ESLI~$d$---PROSTOE CHISLO, ISPOLXZUYUTSYA PARY~$(Y_0, Y_1)$, $(Y_1, Y_2)$,~\dots, $(Y_{n-1}, Y_n)$ I S POMOSHCHXYU OBYCHNOGO $\chi^2\hbox{-METODA}$ VYCHISLYAYUTSYA KAK STATISTIKA~$V_2$, SOOTVETSTVUYUSHCHAYA PROVERKE SERIJ, \emph{TAK I} STATISTIKA~$V_1$ DLYA PROVERKI RAVNOMERNOSTI~$Y_0$, $Y_1$,~\dots, $Y_{n-1}$ S ODNIM I TEM ZHE ZNACHENIEM~$d$, TO PRI BOLXSHIH~$n$ RAZNOSTX~$V_2-2V_1$ BUDET IMETX RASPREDELENIE~$\chi^2$ S $(d-1)^2$~STEPENYAMI SVOBODY, HOTYA~$V_2$ V DANNOM SLUCHAE IMEET RASPREDELENIE, \emph{OTLICHNOE} OT RASPREDELENIYA~$\chi^2$ S $d^2-1$~STEPENYAMI SVOBODY. \section{C.~pROVERKA INTERVALOV}. v |TOM TESTE PROVERYAETSYA DLINA INTERVALOV MEZHDU POYAVLENIYAMI ZNACHENIJ~$U_j$, PRINADLEZHASHCHIH NEKOTOROMU ZADANNOMU OTREZKU. eSLI~$\alpha$ I~$\beta$---DVA DEJSTVITELXNYH CHISLA, PRICHEM~$0\le\alpha<\beta\le 1$, TO PODSCHITYVAYUTSYA DLINY POSLEDOVATELXNOSTEJ~$U_j$, $U_{j+1}$,~\dots, $U_{j+r}$, V KOTORYH TOLXKO~$U_{j+r}$ %% 77 LEZHIT MEZHDU~$\alpha$ I~$\beta$. (tAKAYA POSLEDOVATELXNOSTX IZ $r+1$~CHISEL OPREDELYAET INTERVAL DLINY~$r$.) \alg G.(vYCHISLENIE DLIN INTERVALOV.) sLEDUYUSHCHIJ ALGORITM POZVOLYAET OPREDELITX CHISLO INTERVALOV DLINY~$0$, $1$,~\dots, $t-1$ I POLNOE CHISLO INTERVALOV BOLXSHEJ DLINY~($\ge t$) V POSLEDOVATELXNOSTI~(1). rASCHET PRODOLZHAETSYA DO TEH POR, POKA NE BUDET ZAREGISTRIROVANO VSEGO $n$~INTERVALOV. \picture{ rIS~ 6. rEALIZACIYA PROVERKI INTERVALOV (PODOBNYE ALGORITMY PRIMENYAYUTSYA I PRI REALIZACII TESTOV SOBIRATELYA KUPONOV I PROVERKI NA MONOTONNOSTX). } \st[nACHALXNAYA USTANOVKA.] uSTANOVITX~$j\asg -1$, $s\asg 0$, A TAKZHE~$|COUNT|[r]\asg 0$ DLYA~$0\le r \le t$. \st[$r=0$.] uSTANOVITX~$r\asg0$. \st[$\alpha \le U_j < \beta$?] uVELICHITX~$j$ NA~$1$. eSLI~$U_j\ge\alpha$ I~$U_j<\beta$, PEREJTI NA~\stp{5}. \st[uVELICHITX~$r$.] uVELICHITX~$r$ NA EDINICU, ZATEM VERNUTXSYA NA~\stp{3}. \st[rEGISTRACIYA DLINY INTERVALA.] (oBNARUZHEN INTERVAL DLINY~$r$.) pRI~$r\ge t$ PRIBAVITX~$1$ K~$|COUNT|[t]$, V PROTIVNOM SLUCHAE PRIBAVITX~$1$ K~$|COUNT|[r]$. \st[oBNARUZHENO $n$~INTERVALOV?] pRIBAVITX~$1$ K~$s$. eSLI~$s0$, VERNUTXSYA NA~\stp{2}. \st[vYCHISLENIE~$f$.] iSKOMOE ZNACHENIE FUNKCII OPREDELITX PO FORMULE $$ \eqalignno{ f&=C[t]+tC[t-1]+t(t-1)C[t-2]+\cdots+t!C[1]=\cr &=(\ldots((C[1]\times2+C[2])\times3+C[3])\times4+\cdots+C[t-1])\times t+C[t]. \endmark & (7)\cr } $$ \algend aLGORITM POSTROEN TAKIM OBRAZOM, CHTO $$ 0\le C[r]X_{j+1}$, POLUCHIM $$ \vert 1\, 2\, 9 \vert 8 \vert 5 \vert 3\, 6\, 7 \vert 0\, 4 \vert. \eqno (9) $$ zDESX VYDELENY VSE NEUBYVAYUSHCHIE PODPOSLEDOVATELXNOSTI: PERVAYA DLINY~3, ZATEM DVE PO~1, ESHCHE ODNA DLINY~3 I ZATEM~2. aLGORITM V UPR.~12 POKAZYVAET, KAK TABULIROVATX DLINY TAKIH OTREZKOV. %% 82 v OTLICHIE OT TESTA SOBIRATELYA KUPONOV ILI PROVERKI INTERVALOV (KOTORYE VO MNOGIH OTNOSHENIYAH POHOZHI NA |TOT TEST) V DANNOM SLUCHAE \emph{NE SLEDUET PRIMENYATX KRITERIJ~$\chi^2$ DLYA ANALIZA POLUCHENNYH DANNYH,} TAK KAK ONI \emph{NE YAVLYAYUTSYA} NEZAVISIMYMI. pOSLE DLINNOGO OTREZKA CHASHCHE POYAVLYAETSYA KOROTKIJ I NAOBOROT. iZ-ZA OTSUTSTVIYA NEZAVISIMOSTI PRYAMOE PRIMENENIE KRITERIYA~$\chi^2$ STANOVITSYA NEZAKONNYM. vMESTO |TOGO, POSLE OPREDELENIYA DLIN OTREZKOV S POMOSHCHXYU ALGORITMA, OPISANNOGO V UPR.~12, VYCHISLYAETSYA STATISTIKA $$ V={1\over n}\sum_{1\le i, j \le 6} (|COUNT|[i]-nb_i)(|COUNT|[j]-nb_j)a_{ij}, \eqno(10) $$ GDE KO|FFICIENTY~$a_{ij}$ I~$b_i$ TAKOVY: $$ \eqalign{ \pmatrix{ a_{11} & a_{12} & a_{13} & a_{14} & a_{15} & a_{16}\cr a_{21} & a_{22} & a_{23} & a_{24} & a_{25} & a_{26}\cr a_{31} & a_{32} & a_{33} & a_{34} & a_{35} & a_{36}\cr a_{41} & a_{42} & a_{43} & a_{44} & a_{45} & a_{46}\cr a_{51} & a_{52} & a_{53} & a_{54} & a_{55} & a_{56}\cr a_{61} & a_{62} & a_{63} & a_{64} & a_{65} & a_{66}\cr }&= \pmatrix{ 4529.4 & 9044.9 & 13568 & 18091 & 22615 & 27892\cr 9044.9 & 18097 & 27139 & 36187 & 45234 & 55789\cr 13568 & 27139 & 40721 & 54281 & 67852 & 83685\cr 18091 & 36187 & 54281 & 72414 & 90470 & 11580\cr 22615 & 45234 & 67852 & 90470 & 113262 & 139476\cr 27892 & 55789 & 83685 & 111580 & 139476 & 172860\cr },\cr \pmatrix{ b_1 & b_2 & b_3 & b_4 & b_5 & b_6 \cr } &= \pmatrix{ 1\over 6 & 5\over 24 & 11\over 120 & 19 \over 720 & 29 \over 5040 & 1\over 840}.\cr } \eqno(11) $$ (zDESX PRIVEDENY PRIBLIZHENNYE ZNACHENIYA KO|FFICIENTOV; TOCHNYE ZNACHENIYA MOZHNO VYCHISLITX PO PRIVEDENNYM NIZHE FORMULAM.) \emph{sTATISTIKA~$V$ V~(10) DOLZHNA IMETX PRI BOLXSHIH~$n$ RASPREDELENIE~$\chi^2$ S SHESTXYU {\rm (A NE PYATXYU)} STEPENYAMI SVOBODY.} zNACHENIE~$n$ DOLZHNO BYTX RAVNO, SKAZHEM, $4000$ ILI BOLXSHE. aNALOGICHNYJ TEST PRIMENYAETSYA DLYA NEVOZRASTAYUSHCHIH OTREZKOV. dOVOLXNO PROSTOJ I BOLEE PRAKTICHNYJ SPOSOB PROVERKI NA MONOTONNOSTX PRIVEDEN V UPR.~14, NO IZ CHISTO MATEMATICHESKIH SOOBRAZHENIJ POLEZNEE BUDET RAZOBRATX |TOT VESXMA SLOZHNYJ TEST. pRISTUPIM K VYVODU FORMUL DLYA NEGO. pUSTX DLYA DANNOJ PERESTANOVKI IZ $n$~|LEMENTOV $Z_{pi}=1$, ESLI S POZICII~$i$ NACHINAETSYA VOZRASTAYUSHCHIJ OTREZOK S DLINOJ NE MENEE~$p$, I~$Z_{pi}=0$ V PROTIVNOM SLUCHAE. v KACHESTVE PRIMERA RASSMOTRIM POSLEDOVATELXNOSTX~(9) S~$n=10$. v DANNOM SLUCHAE $$ Z_{11}=Z_{21}=Z_{31}=Z_{14}=Z_{15}=Z_{16}=Z_{26}=Z_{36}=Z_{19}=Z_{29}=1, $$ A VSE OSTALXNYE~$Z$ RAVNY~$0$. tOGDA $$ R'_p=Z_{p1}+Z_{p2}+\cdots+Z_{pn} \eqno(12 $$ %% 83 ESTX CHISLO OTREZKOV DLINY NE MENEE~$p$, A $$ R_p=R'_p-R'_{p+1} \eqno(13) $$ ESTX CHISLO OTREZKOV, DLINA KOTORYH V TOCHNOSTI RAVNA~$p$. nAM NUZHNO VYCHISLITX SREDNEE ZNACHENIE~$R_p$, A TAKZHE \dfn{KOVARIACIYU}% \note{1}{mY OSTAVLYAEM OBOZNACHENIYA AVTORA DLYA SREDNEGO, KOVARIACII I T.~P., SLEDUYA PEREVODU 1-GO TOMA (SM.~P.~1.2.10).---{\sl pRIM. PEREV.\/}} $$ \covar (R_p, R_q)=\mean ((R_p-\mean (R_p)) (R_q-\mean (R_q))), $$ KOTORAYA SLUZHIT MEROJ VZAIMOZAVISIMOSTI~$R_p$ I~$R_q$. uSREDNENIE NADO PROVODITX PO VSEM VOZMOZHNYM $n!$~PERESTANOVKAM. fORMULY~(12) I~(13) POKAZYVAYUT, CHTO ISKOMYE VELICHINY MOZHNO VYRAZITX CHEREZ SREDNIE ZNACHENIYA~$Z_{pi}$ I~$Z_{pi}Z_{qj}$, PO|TOMU V KACHESTVE PERVOGO SHAGA ZAPISHEM SLEDUYUSHCHIE SOOTNOSHENIYA (V PREDPOLOZHENII, CHTO~$i1$. oTMETIM, CHTO~$Z_{pi}Z_{qj}$ RAVNO LIBO~$0$, LIBO~$1$, TAK CHTO SUMMIROVANIE SVODITSYA K TOMU, CHTOBY PERESCHITATX VSE PERESTANOVKI~$U_1$, $U_2$,~\dots, $U_n$, V KOTORYH~$Z_{pi}=Z_{qj}=0$, A IMENNO $$ U_{i-1}>U_i<\ldotsU_{i+p}<\ldotsn$;\cr } & (18) \cr } $$ GDE $t=\max(p,q)$, $s=p+q$ I $$ \eqalignno{ f(p, q, n) &= (n+1)\left({s(1-pq)+pq\over (p+1)!(q+1)!}-{2s\over (s+1)!}\right)+\cr &+2\left({s-1\over s!}\right)+{(s^2-s-2)pq-s^2-p^2q^2+1\over (p+1)!(q+1)!}. &(19)\cr } $$ kONECHNO, POLXZOVATXSYA TAKIM SLOZHNYM VYRAZHENIEM DLYA KOVARIACII OCHENX NEUDOBNO, NO DRUGOGO VYHODA NET. s POMOSHCHXYU |TIH FORMUL LEGKO VYCHISLITX $$ \eqalign{ \mean(R_p)&=\mean(R'_p)-\mean(R'_{p+1}),\cr \covar (R_p, R'_q)&=\covar(R'_p, R'_q)-\covar(R'_{p+1}, R'_q),\cr \covar(R_p, R_q)&=\covar(R_p, R'_q)-\covar(R_p, R'_{q+1}).\cr } \eqno(20) $$ v RABOTE dZH.~vOLXFOVICA ({\sl Annals of Mathematical Statistics,\/} {\bf 15} (1944), 163--165) DOKAZANO, CHTO PRI~$n\to\infty$ RASPREDELENIE VELICHIN~$R_1$, $R_2$,~\dots, $R_{t-1}$, $R'_t$ STREMITSYA K NORMALXNOMU SO SREDNIM ZNACHENIEM I KOVARIACIEJ, PRIVEDENNYMI VYSHE. oTSYUDA SLEDUET, CHTO MOZHNO POLXZOVATXSYA TAKIM TESTOM. dLYA DANNOJ POSLEDOVATELXNOSTI IZ $n$~SLUCHAJNYH CHISEL VYCHISLYAETSYA~$R_p$---CHISLO MONOTONNYH OTREZKOV DLINY~$p$, GDE~$1\le p < t$, A TAKZHE~$R'_t$---CHISLO OTREZKOV DLINY~$\ge t$. vVEDEM OBOZNACHENIYA $$ \eqalign{ Q_1&=R_1-\mean(R_1), \ldots, Q_{t-1}=R_{t-1}-\mean(R_{t-1}),\cr Q_t&=R'_t-\mean(R'_t).\cr } \eqno(21) $$ %% 85 oBRAZUEM MATRICU KOVARIACIJ~$C$, OBOZNACHAYA, NAPRIMER, $C_{13}=\covar(R_1, R_3)$, TOGDA KAK~$C_{1t}=\covar(R_1, R'_t)$. pRI~$t=6$ POLUCHIM $$ \eqalign{ C&= nC_1+C_2=\cr &= n\pmatrix{ 23 \over 180 & -7 \over 360 & -5 \over 336 & -433 \over 60480 & -13 \over 5670 & -121 \over 181440 \cr -7 \over 360 & 2843 \over 20160 & -989 \over 20160 & -7159 \over 362880 & -10019 \over 1814400 & -1303 \over 907200 \cr -5 \over 336 & -989 \over 20160 & 54563 \over 907200 & -21311 \over 1814400 & -62369 \over 19958400 & -7783 \over 9979200 \cr -433 \over 60480 & -7159 \over 362880 & -21311 \over 1814400 & 886657 \over 39916800 & -257699 \over 239500800 & -62611 \over 239500800 \cr -13 \over 5670 & -10019 \over 1814400 & -62369 \over 19958400 & -257699 \over 239500800 & 29874811 \over 5448643200 & -1407179 \over 21794572800 \cr -121 \over 181440 & -1303 \over 907200 & -7783 \over 9979200 & -62611 \over 239500800 & -1407179 \over 21794572800 & 2134697 \over 1816214400 \cr }+\cr &+\pmatrix{ 83 \over 180 & -29 \over 180 & -11 \over 210 & -41 \over 12096 & 91 \over 25920 & 41 \over 18144 \cr -29 \over 180 & -305 \over 4032 & 319 \over 20160 & 2557 \over 72576 & 10177 \over 604800 & 413 \over 64800 \cr -11 \over 210 & 319 \over 20160 & -58747 \over 907200 & 19703 \over 604800 & 239471 \over 19958400 & 39517 \over 9979200 \cr -41 \over 12096 & 2557 \over 72576 & 19703 \over 604800 & -220837 \over 4435200 & 1196401 \over 239599800 & 360989 \over 239500800 \cr 91 \over 25920 & 10177 \over 604800 & 239471 \over 19958400 & 1196401 \over 239500800 & -139126639 \over 7264857600 & 4577641 \over 10897286400 \cr 41 \over 18144 & 413 \over 64800 & 39517 \over 9979200 & 360989 \over 239500800 & 4577641 \over 10897286400 & -122953057 \over 21794572800 \cr }.\cr } \eqno(22) $$ DLYA~$n\ge 14$. zATEM NAJDEM MATRICU~$A=(a_{ij})$, OBRATNUYU MATRICE~$C$, I VYCHISLIM~$\sum_{1\le i,j \le t} Q_i Q_j a_{ij}$. pRI BOLXSHIH~$n$ REZULXTAT IMEET RASPREDELENIE~$\chi^2$ S~$t$~STEPENYAMI SVOBODY. pRIVEDENNAYA RANEE MATRICA~(11)---REZULXTAT OBRASHCHENIYA MATRICY~$C_1$, PREDSTAVLENNOJ S PYATXYU ZNACHASHCHIMI CIFRAMI. pRI BOLXSHIH~$n$ MATRICA~$A$ BUDET PRIBLIZHENNO RAVNA~$(1/n)C_1^{-1}$. dELALISX POPYTKI ZAPISATX |LEMENTY MATRICY, OBRATNOJ K~$C_1$ KAK RACIONALXNYE CHISLA, NO |TO PRIVODILO K SLISHKOM BOLXSHIM VELICHINAM UZHE PRI~$t=4$. v CHASTNOM SLUCHAE PRI~$n=1000$ |LEMENTY MATRICY~(11) OKAZALISX PRIMERNO NA~1\% NIZHE TOCHNYH ZNACHENIJ, POLUCHENNYH V REZULXTATE OBRASHCHENIYA MATRICY~(22). sTANDARTNYJ METOD OBRASHCHENIYA MATRIC OPISAN V P.~2.2.6, UPR.~18. %%86 \section{H.~tEST "NAIBOLXSHEE IZ~$t$"}. pUSTX~$V_j=\max(U_{tj}, U_{tj+1},~\ldots, U_{tj+t-1})$ PRI~$0\le j < n$. pRIMENIM KRITERIJ kOLMOGOROVA-sMIRNOVA K POSLEDOVATELXNOSTI~$V_0$, $V_1$,~\dots, $V_{n-1}$, PRINIMAYA V KACHESTVE TEORETICHESKOJ FUNKCII RASPREDELENIYA~$F(x)=x^t$, ($0\le x \le 1$). mOZHNO VMESTO |TOGO PROVERYATX NA RAVNOMERNOSTX POSLEDOVATELXNOSTX~$V_0^t$, $V_1^t$,~\dots, $V_{n-1}^t$. dLYA OBOSNOVANIYA |TOGO TESTA DOSTATOCHNO POKAZATX, CHTO $V_j$~RASPREDELENY V SOOTVETSTVII S~$F(x)=x^t$. vEROYATNOSTX TOGO, CHTO~$\max(U_1, U_2,~\ldots, U_t)\le x$, RAVNA VEROYATNOSTI TOGO, CHTO~$U_1\le x$ \emph{I}~$U_2\le x$ \emph{I}~\dots{} \emph{I}~$U_t\le x$; SLEDOVATELXNO, ONA RAVNA PROIZVEDENIYU INDIVIDUALXNYH VEROYATNOSTEJ~$x\cdot x \cdot \ldots \cdot x = x^t$. \section{I.~pOSLEDOVATELXNAYA KORRELYACIYA}. vYCHISLIM STATISTIKU $$ C={n(U_0U_1+\cdots+U_{n-2}U_{n-1}+U_{n-1}U_0)-(U_0+\cdots+U_{n-1})^2 \over n(U_0^2+\cdots+U_{n-1}^2)-(U_0+\cdots+U_{n-1})^2}. \eqno(23) $$ eTO "KO|FFICIENT POSLEDOVATELXNOJ KORRELYACII", KOTORYJ SLUZHIT MEROJ ZAVISIMOSTI~$U_{j+1}$ OT~$U_j$. pRI OCHENX BOLXSHIH~$n$ SUSHCHESTVUET METOD, POZVOLYAYUSHCHIJ REZKO UMENXSHITX VREMYA, KOTOROE TRATITSYA NA RASCHET~$C$ (L.~P.~Schmid, {\sl CACM,\/} {\bf 8} (1965), 115). kO|FFICIENTY KORRELYACII CHASTO UPOTREBLYAYUTSYA V STATISTIKE. eSLI IMEETSYA DVA NABORA VELICHIN~$U_0$, $U_1$,~\dots, $U_{n-1}$ I~$V_0$, $V_1$,~\dots, $V_{n-1}$, TO KO|FFICIENT KORRELYACII MEZHDU NIMI OPREDELYAETSYA SLEDUYUSHCHIM OBRAZOM: $$ C={n\sum(U_j V_j)-(\sum U_j)(\sum V_j) \over \sqrt{(n\sum U_j^2 - (\sum U_j)^2) (n\sum V_j^2 - (\sum V_j)^2)}}. \eqno(24) $$ sUMMIROVANIE V |TOJ FORMULE PROVODITSYA PO VSEM~$j$ V INTERVALE~$0\le j < n$. fORMULA~(23) POLUCHAETSYA V CHASTNOM SLUCHAE~$V_j=U_{(j+1)\bmod n}$. [\emph{zAMECHANIE.} zNAMENATELX VYRAZHENIYA~(24) RAVEN NULYU PRI~$U_0=U_1=\cdots=U_{n-1}$ ILI~$V_0=V_1=\cdots=V_{n-1}$; MY ISKLYUCHAEM |TOT SLUCHAJ IZ RASSMOTRENIYA.) kO|FFICIENT KORRELYACII VSEGDA LEZHIT MEZHDU~$-1$ I~$+1$. kOGDA ON RAVEN NULYU ILI OCHENX MAL, |TO SLUZHIT UKAZANIEM NA NEZAVISIMOSTX VELICHIN~$U_j$ I~$V_j$, A KOGDA ON RAVEN~$\pm 1$, |TI VELICHINY SVYAZANY DRUG S DRUGOM LINEJNOJ ZAVISIMOSTXYU, T.~E.\ DLYA LYUBOGO~$j$ SPRAVEDLIVO RAVENSTVO~$V_j=m \pm aU_j$ PRI NEKOTORYH POSTOYANNYH~$a$ I~$m$ (SM.~UPR.~17). tAKIM OBRAZOM, ZHELATELXNO, CHTOBY ZNACHENIE~$C$, OPREDELENNOE FORMULOJ~(23), BYLO BLIZKO K NULYU. v DEJSTVITELXNOSTI, IZ-ZA TOGO, CHTO~$U_0U_1$ I~$U_1U_2$, KONECHNO, NE YAVLYAYUTSYA NEZAVISIMYMI, KO|FFICIENT POSLEDOVATELXNOJ KORRELYACII NE DOLZHEN BYTX V \emph{TOCHNOSTI} RAVEN NULYU (SM.~UPR.~18). "hOROSHIM" MOZHNO SCHITATX ZNACHENIE~$C$, LEZHASHCHEE MEZHDU~$\mu_n-2\sigma_n$ I~$\mu_n+2\sigma_n$, GDE $$ \mu_n={-1\over (n-1)}, \quad \sigma_n={1\over n-1}\sqrt{n(n-3)\over n+1}, \rem{$n>2$.} \eqno(25) $$ %% 87 zNACHENIE~$C$ DOLZHNO NAHODITXSYA V |TIH PREDELAH V 95\% VSEH SLUCHAEV. fORMULY~(25) POKA IMEYUT PREDPOLOZHITELXNYJ HARAKTER, TAK KAK TOCHNOE RASPREDELENIE~$C$ V TOM SLUCHAE, KOGDA $U$~RASPREDELENY RAVNOMERNO, NEIZVESTNO. sLUCHAJ NORMALXNOGO RASPREDELENIYA VELICHIN~$U$ RASSMOTREN V RABOTE u.~dIKSONA ({\sl Annals of Mathematical Statistics,\/} {\bf 15} (1944), 119--144). oPYT POKAZYVAET, CHTO ISPOLXZOVANIE FORMUL DLYA MATEMATICHESKOGO OZHIDANIYA I SREDNEKVADRATICHNOGO OTKLONENIYA, SOOTVETSTVUYUSHCHIH NORMALXNOMU RASPREDELENIYU, T.~E.~FORMUL~(25), NE PRIVODIT K BOLXSHOJ OSHIBKE. iZVESTNO, CHTO~$\lim_{n\to\infty}\sqrt{n}\sigma_n=1$; SM.~TAKZHE STATXYU aNDERSONA I uOKERA ({\sl Annals of Mathematical Statistics,\/} {\bf 35} (1964), 1296--1303), V KOTOROJ POLUCHENY BOLEE OBSHCHIE REZULXTATY O POSLEDOVATELXNOJ KORRELYACII V \emph{ZAVISIMYH} POSLEDOVATELXNOSTYAH. \section{J.~pROVERKA PODPOSLEDOVATELXNOSTEJ}. nEREDKO VNESHNYAYA PROGRAMMA USTROENA TAK, CHTO EJ TREBUETSYA KAZHDYJ RAZ NEKOTOROE OPREDELENNOE KOLICHESTVO SLUCHAJNYH CHISEL. nAPRIMER, ESLI V PROGRAMME ESTX TRI SLUCHAJNYE VELICHINY~$X$, $Y$ I~$Z$, DLYA OPREDELENIYA IH ZNACHENIJ KAZHDYJ RAZ NUZHNO BUDET GENERIROVATX TRI SLUCHAJNYH CHISLA. dLYA TAKIH PRILOZHENIJ VAZHNO, CHTOBY SLUCHAJNOJ BYLA LYUBAYA POSLEDOVATELXNOSTX, POLUCHENNAYA V REZULXTATE VYBORA KAZHDOGO \emph{TRETXEGO} CHISLA ISHODNOJ POSLEDOVATELXNOSTI. eSLI PROGRAMMA ZAPRASHIVAET KAZHDYJ RAZ $q$~CHISEL, TO S POMOSHCHXYU TESTOV, OPISANNYH VYSHE, MOZHNO PROVERYATX NE ISHODNUYU POSLEDOVATELXNOSTX~$U_0$, $U_1$, $U_2$,~\dots, A V OTDELXNOSTI KAZHDUYU IZ PODPOSLEDOVATELXNOSTEJ $$ U_0, U_q, U_{2q}, \ldots; \quad U_1, U_{q+1}, U_{2q+1}, \ldots; \quad \ldots; \quad U_{q-1}, U_{2q-1},\ldots\,. \eqno(26) $$ oPYT POKAZYVAET, CHTO PRI ISPOLXZOVANII LINEJNOGO KONGRU|NTNOGO METODA HARAKTERISTIKI TAKIH PODPOSLEDOVATELXNOSTEJ PRAKTICHESKI NIKOGDA NE BYVAYUT HUZHE, CHEM U ISHODNOJ POSLEDOVATELXNOSTI, KROME SLUCHAEV, KOGDA~$q$ I CHISLO, ISPOLXZUEMOE V KACHESTVE MODULYA, SODERZHAT DOSTATOCHNO BOLXSHOJ OBSHCHIJ MNOZHITELX. tAK, NA MASHINAH S DVOICHNOJ ARIFMETIKOJ PRI ISPOLXZOVANII ZNACHENIJ~$m$, RAVNYH RAZMERU SLOVA, IZ VSEH~$q<16$ SAMYE PLOHIE REZULXTATY POLUCHAYUTSYA PRI~$q=8$; NA MASHINAH S DESYATICHNOJ ARIFMETIKOJ MOZHNO OZHIDATX NEUDOVLETVORITELXNYH REZULXTATOV PRI~$q=10$. (eTO MOZHNO OB®YASNITX OTCHASTI, ISHODYA IZ PONYATIYA MOSHCHNOSTI POSLEDOVATELXNOSTI, TAK KAK TAKIE ZNACHENIYA~$q$ BUDUT, VOOBSHCHE GOVORYA, PONIZHATX EE MOSHCHNOSTX.) \section{K.~zAMECHANIYA ISTORICHESKOGO HARAKTERA I DALXNEJSHEE OBSUZHDENIE}. sTATISTICHESKIE KRITERII VOZNIKALI ESTESTVENNYM OBRAZOM V PROCESSE %% 88 NAUCHNOJ RABOTY, KOGDA POYAVLYALASX NEOBHODIMOSTX "PRINYATX" ILI "OTVERGNUTX" KAKUYU-LIBO GIPOTEZU, KASAYUSHCHUYUSYA |KSPERIMENTALXNYH DANNYH. lUCHSHIMI SREDI RABOT, POSVYASHCHENNYH PROVERKE NA SLUCHAJNOSTX ISKUSSTVENNYH POSLEDOVATELXNOSTEJ CHISEL, YAVLYAYUTSYA DVE STATXI m.~kENDALLA I~b.~b|BINGTON-sMITA [{\sl Journal of the Royal Statistical Society,\/} {\bf 101} (1938), 147--166, I PRILOZHENIE K |TOMU ZHURNALU, {\bf 6} (1939), 51--61]. v |TIH RABOTAH OPISANA PROVERKA SLUCHAJNYH CIFR OT~$0$ DO~$9$, A NE DEJSTVITELXNYH SLUCHAJNYH CHISEL; DLYA |TOJ CELI PREDLOZHENY PROVERKA CHASTOT, SERIJ, INTERVALOV, A TAKZHE POKER-TEST (HOTYA PROVERKA SERIJ PROIZVODITSYA NEVERNO). kENDALL I b|BINGTON-sMIT ISPOLXZOVALI TAKZHE RAZNOVIDNOSTX TESTA SOBIRATELYA KUPONOV, NO V TOM VIDE, KOTORYJ OPISAN V DANNOJ KNIGE, |TOT TEST BYL PREDLOZHEN gRINVUDOM V 1955~G. tEST PROVERKI MONOTONNOSTI IMEET DOVOLXNO INTERESNUYU ISTORIYU. pERVONACHALXNO V NEM REGISTRIROVALISX ODNOVREMENNO DLINY OTREZKOV KAK S VOZRASTAYUSHCHIMI, TAK I UBYVAYUSHCHIMI CHISLAMI (|TI OTREZKI CHEREDUYUTSYA). sLEDUET OTMETITX, CHTO |TOT TEST, TAK ZHE KAK PROVERKA PERESTANOVOK, NE TREBUET, CHTOBY ZNACHENIYA~$U$ BYLI RASPREDELENY RAVNOMERNO; TREBUETSYA TOLXKO, CHTOBY VEROYATNOSTX TOGO, CHTO~$U_i=U_j$, RAVNYALASX NULYU PRI~$i\ne j$, TAK CHTO |TI TESTY MOZHNO PRIMENYATX K MNOGIM TIPAM SLUCHAJNYH POSLEDOVATELXNOSTEJ. v PRIMITIVNOJ FORME |TOT TEST VPERVYE BYL PREDLOZHEN V RABOTE [J.~Bienaynie, {\sl Comptes Rendus,\/} {\bf 81} (Paris: Acad.\ Sciences, 1875), 417--423]. oKOLO 60~LET SPUSTYA kERM|K I mAK-kENDRIK NAPISALI DVE BOLXSHIE RABOTY, POSVYASHCHENNYE |TOMU VOPROSU [{\sl Proc.\ Royal Society Edinburgh,\/} {\bf 57} (1937), 228--240, 332--376]. v KACHESTVE PRIMERA V NIH POKAZANO S POMOSHCHXYU PROVERKI NA MONOTONNOSTX, CHTO KOLEBANIYA KOLICHESTVA OSADKOV V eDINBURGE V PERIOD S~1785~G.\ PO~1930~G.\ NOSILI SLUCHAJNYJ HARAKTER (HOTYA ONI ISSLEDOVALI TOLXKO SREDNIE I STANDARTNYE OTKLONENIYA OTREZKOV MONOTONNOSTI). s TEH POR |TOT TEST PERIODICHESKI ISPOLXZOVALSYA NA PRAKTIKE, NO TOLXKO V~1944~G.\ BYLO POKAZANO, CHTO PRIMENYATX EGO V SOCHETANII S KRITERIEM~$\chi^2$ NELXZYA. v RABOTE lEVENA I vOLXFOVICA [{\sl Annals of Mathematical Statistics,\/} {\bf 15} (1944), 58--69] BYLA PRIVEDENA PRAVILXNAYA FORMULIROVKA TESTA (S CHEREDUYUSHCHIMISYA OTREZKAMI VOZRASTANIYA I UBYVANIYA) I UKAZANA OSHIBOCHNOSTX EGO PERVONACHALXNOJ FORMULIROVKI. vARIANT TESTA, IZLOZHENNYJ V DANNOJ KNIGE, KOGDA ANALIZIRUYUTSYA DLINY OTREZKOV ILI TOLXKO S VOZRASTANIEM, ILI TOLXKO S UBYVANIEM, NAIBOLEE UDOBEN DLYA REALIZACII NA VYCHISLITELXNOJ MASHINE, PO|TOMU FORMULY DLYA DRUGIH VARIANTOV NE PRIVODYATSYA (SM.~OBZOR Barton~D.~E., Mallows~s.~L., {\sl Annals of Math.\ Statistics,\/} {\bf 36} (1965), 236--260]. iZ VSEH OPISANNYH ZDESX TESTOV PROVERKA CHASTOT I PROVERKA POSLEDOVATELXNOJ KORRELYACII---SAMYE SLABYE, V TOM SMYSLE, CHTO %% 89 PRI ISPYTANII S POMOSHCHXYU |TIH TESTOV POCHTI VSE DATCHIKI SLUCHAJNYH CHISEL DAYUT UDOVLETVORITELXNYE REZULXTATY. vKRATCE TEORETICHESKOE OBOSNOVANIE |TOGO BUDET DANO V~\S~3.5 (SM.~UPR.~3.5-26). k SRAVNITELXNO SILXNYM TESTAM OTNOSITSYA PROVERKA NA MONOTONNOSTX: REZULXTATY UPR.~3.3.3-23, 24 POKAZYVAYUT, CHTO PRI NEDOSTATOCHNO BOLXSHIH ZNACHENIYAH~$m$ POSLEDOVATELXNOSTI, POLUCHENNYE S POMOSHCHXYU LINEJNOGO KONGRU|NTNOGO METODA, IMEYUT POVYSHENNUYU DLINU OTREZKOV MONOTONNOSTI, TAK CHTO |TOT TEST OPREDELENNO POLEZEN. vEROYATNO, U CHITATELYA VOZNIKAET VOPROS: \emph{"zACHEM TAK MNOGO TESTOV?".} mOZHET SOZDATXSYA VPECHATLENIE, CHTO NA ISPYTANIYA DATCHIKOV SLUCHAJNYH CHISEL TRATITSYA BOLXSHE MASHINNOGO "VREMENI, CHEM NA VYRABOTKU SLUCHAJNYH CHISEL V PROCESSE RESHENIYA PRIKLADNYH ZADACH! eTO NEVERNO, HOTYA SLUCHAI CHREZMERNOGO UVLECHENIYA PROVERKAMI VOZMOZHNY. nEOBHODIMOSTX DOSTATOCHNO RAZNOOBRAZNOGO NABORA TESTOV MNOGOKRATNO OTMECHALASX V LITERATURE. v CHASTNOSTI, UKAZYVALOSX, CHTO POSLEDOVATELXNOSTI, POLUCHENNYE S POMOSHCHXYU NEKOTORYH RAZNOVIDNOSTEJ METODA SEREDINY KVADRATA, HOROSHO PROHODYAT PROVERKU CHASTOT, INTERVALOV, KOMBINACIJ, NO OKAZYVAYUTSYA SOVERSHENNO NEGODNYMI PRI PROVERKE SERIJ. iZVESTNO, CHTO DATCHIKI, OSNOVANNYE NA LINEJNOM KONGRU|NTNOM METODE, UDOVLETVORYAYUT PRI MALYH ZNACHENIYAH~$m$ MNOGIM TESTAM, NO NE UDOVLETVORYAYUT PROVERKE NA MONOTONNOSTX, TAK KAK DAYUT SLISHKOM MALO OTREZKOV EDINICHNOJ DLINY. tEST "NAIBOLXSHEE IZ~$t$" TAKZHE POZVOLYAET VYYAVITX PLOHIE DATCHIKI, KOTORYE SO VSEH DRUGIH TOCHEK ZRENIYA VEDUT SEBYA VPOLNE PRIEMLEMO. vEROYATNO, OSNOVNAYA PRICHINA, PO KOTOROJ NEOBHODIMA VSESTORONNYAYA PROVERKA DATCHIKOV, ZAKLYUCHAETSYA V SLEDUYUSHCHEM. eSLI KTO-TO POLXZUETSYA CHUZHIM DATCHIKOM SLUCHAJNYH CHISEL, TO PRI LYUBOM NEDORAZUMENII ON BUDET VINITX |TOT DATCHIK, A NE SVOYU PROGRAMMU. nUZHNO, CHTOBY AVTOR DATCHIKA MOG \emph{DOKAZATX,} CHTO SLUCHAJNYE CHISLA UDOVLETVORYAYUT VSEM TREBOVANIYAM. s DRUGOJ STORONY, ESLI VY PISHETE DATCHIK DLYA SEBYA, A NE DLYA OBSHCHEGO POLXZOVANIYA, MOZHNO NE TRATITX SIL NA EGO PROVERKU; VO VSYAKOM SLUCHAE, ESLI ZA OSNOVU VZYATX KAKOJ-LIBO IZ ALGORITMOV, REKOMENDOVANNYH V |TOJ GLAVE, S BOLXSHOJ VEROYATNOSTXYU |TOT DATCHIK BUDET VPOLNE UDOVLETVORITELXNYM. \excercises \ex[10] pOCHEMU PRI PROVERKE SERIJ (SM.~P.~v) SLEDUET ISPOLXZOVATX PARY~$(Y_0, Y_1)$ $(Y_2, Y_3)$,~\dots, $(Y_{2n-2}, Y_{2n-1})$, A NE~$(Y_0, Y_1)$, $(Y_1, Y_2)$,~\dots, $(Y_{n-1}, Y_n)$? \ex[10] pOKAZHITE, KAK OBOBSHCHITX PROVERKU SERIJ S PAR NA TROJKI, CHETVERKI I~T.~D. \rex[m20] sKOLXKO V SREDNEM POTREBUETSYA PEREBRATX ZNACHENIJ~$U$ PRI PROVERKE INTERVALOV (ALGORITM~G), PREZHDE CHEM BUDET OBNARUZHENO $n$~INTERVALOV, %% 90 V PREDPOLOZHENII, CHTO POSLEDOVATELXNOSTX DEJSTVITELXNO SLUCHAJNAYA? kAKOVO STANDARTNOE OTKLONENIE |TOJ VELICHINY? \ex[12] pOKAZHITE, CHTO PRI PROVERKE INTERVALOV ZAKONNO POLXZOVATXSYA VEROYATNOSTYAMI~(4). \ex[M23] pRI "KLASSICHESKOJ" PROVERKE INTERVALOV, OPISANNOJ kENDALLOM I b|BINGTON-sMITOM, $N$~ZNACHENIJ~$U$, PODLEZHASHCHIH PROVERKE, ISPOLXZUYUTSYA DLYA POSTROENIYA CIKLICHESKOJ POSLEDOVATELXNOSTI, V KOTOROJ $U_{N+j}$~SOVPADAET S~$U_j$. eSLI $n$~CHISEL IZ~$U_0$,~\dots, $U_{N-1}$ POPADAYUT V INTERVAL~$\alpha\le U_j < \beta$, TO V CIKLICHESKOJ POSLEDOVATELXNOSTI IMEETSYA $n$~INTERVALOV. pUSTX~$Z_r$---CHISLO INTERVALOV DLINY~$r$, ESLI~$0\le rX_{j+1}$ OCHEREDNOJ OTREZOK MONOTONNOSTI NACHNETSYA S~$X_{j+2}$, TO DLINY TAKIH OTREZKOV BUDUT NEZAVISIMYMI I MOZHNO BUDET VOSPOLXZOVATXSYA OBYCHNYM KRITERIEM~$\chi^2$ (VMESTO VESXMA SLOZHNOGO METODA, PRIVEDENNOGO V TEKSTE). kAKIMI DOLZHNY BYTX SOOTVETSTVUYUSHCHIE VEROYATNOSTI DLIN OTREZKOV MONOTONNOSTI DLYA |TOGO UPROSHCHENNOGO TESTA? \ex[M20] pOCHEMU ZNACHENIYA~$V_0^t$, $V_1^t$,~\dots, $V_{n-1}^t$ V TESTE "NAIBOLXSHEE IZ~$t$" DOLZHNY BYTX RASPREDELENY RAVNOMERNO MEZHDU NULEM I EDINICEJ? \rex[15] (a)~pUSTX TREBUETSYA PRODELATX VYCHISLENIYA DLYA TESTA "NAIBOLXSHEE IZ~$t$" PRI RAZNYH ZNACHENIYAH~$t$. oBOZNACHIM~$Z_{jt}=\max (U_j, U_{j+1},~\ldots, U_{j+t-1})$. sTUDENT sMYSHL¸NYJ OBNARUZHIL OSTROUMNYJ SPOSOB PEREHODA OT POSLEDOVATELXNOSTI~$Z_{0(t-1)}$, %% 91 $Z_{1(t-1)}$,~\dots{} K POSLEDOVATELXNOSTI~$Z_{0t}$, $Z_{1t}$,~\dots, TREBUYUSHCHIJ MINIMALXNYH VYCHISLENIJ. pOPROBUJTE NAJTI |TOT SPOSOB. (b)~oN ZHE RESHIL IZMENITX METOD "NAIBOLXSHEE IZ~$t$" TAK, CHTOBY~$V_j=\max(U_j,~\ldots, U_{j+t-1})$; DRUGIMI SLOVAMI, $V_j=Z_{jt}$, A %% ?? Z_{(t_j)t} NE~$V_j=Z_{(tj)t}$, KAK UKAZANO V TEKSTE. pRI |TOM ON RASSUZHDAL TAK: \emph{VSE} DOLZHNY IMETX ODINAKOVOE RASPREDELENIE, PO|TOMU TEST DOLZHEN STATX TOLXKO SILXNEE, ESLI ISPOLXZOVATX VSE~$Z_{jt}$, $0\le j h$, ZAMENITX~$c$ NA~$c\bmod h$ S POMOSHCHXYU SOOTNOSHENIYA~(30) LEMMY~C. {\sl shAG~5.\/}~tEPERX SOBLYUDENY USLOVIYA LEMMY~B, TAK CHTO IMEEM $$ \sigma(h, k, c)=-3+{h\over k}+{k\over h}+{1+6c^2\over hk}-\sigma(k, h, c). \eqno (35) $$ dLYA OPREDELENIYA~$\sigma(k, h, c)$ VERNUTXSYA K SHAGU~1. chISLO NEOBHODIMYH ITERACIJ OBYCHNO NEVELIKO; POSLEDOVATELXNYE ZNACHENIYA~$h$ I~$k$ VEDUT SEBYA TAK ZHE, KAK POSLEDOVATELXNOSTX ZNACHENIJ, POLUCHAEMAYA PRI OPREDELENII S POMOSHCHXYU ALGORITMA eVKLIDA (SM.~P.~4.5.2) NAIBOLXSHEGO OBSHCHEGO DELITELYA~$h$ I~$k$. rASSMOTRIM NESKOLXKO PRIMEROV. \proclaim pRIMER~1. nAJTI KO|FFICIENT POSLEDOVATELXNOJ KORRELYACII DLYA SLUCHAYA~$m=2^{35}$, $a=2^{34}+1$, $c=1$. \solution sOGLASNO~(17), IMEEM $$ C=(2^{35}\sigma(2^{34}+1, 2^{35}, 1)-3+6(2^{35}-(2^{34}-1)-1))/(2^{70}-1). \eqno (36) $$ vYPOLNYAYA SHAGI~1 I~2, POLUCHAEM $$ (\sigma(2^{34}+1, 2^{35}, 1)=-\sigma(2^{34}-1, 2^{35}, 1). $$ sOGLASNO SHAGU~5: $$ \sigma(2^{34}-1, 2^{35}, 1)=-3+(2^{34}-1)/2^{35}+2^{35}/(2^{34}-1) +7/2^{35}(2^{34}-1)-\sigma(2^{35}, 2^{34}-1, 1). $$ sOGLASNO SHAGU~1: $$ \sigma(2^{35}, 2^{34}-1, 1)=\sigma(2, 2^{34}-1, 1). $$ tEPERX SHAG~5 DAET $$ \sigma(2, 2^{34}-1, 1)=-3+2/(2^{34}-1)+(2^{34}-1)/2 +7/2(2^{34}-1)-\sigma(2^{34}-1, 2, 1) $$ I $$ \sigma(2^{34}-1, 2, 1)=0. $$ v REZULXTATE POLUCHAEM, CHTO $$ C={1\over 4}+\varepsilon, \rem{$\abs{\varepsilon}<2^{-67}$.} \eqno(37) $$ tAKAYA KORRELYACIYA, BEZUSLOVNO, NEPRIEMLEMA. kONECHNO, |TOT DATCHIK OBLADAET SLISHKOM MALOJ MOSHCHNOSTXYU; MY UZHE OTVERGLI EGO RANEE KAK NESLUCHAJNYJ. \proclaim pRIMER~2. oPREDELITX PRIBLIZITELXNO KO|FFICIENT POSLEDOVATELXNOJ KORRELYACII PRI~$m=10^{10}$, $a=10001$, $b=2113248658$. %% 100 \solution tAK KAK~$C\approx \sigma(a, m,c)/m$, DELAEM SLEDUYUSHCHIE VYCHISLENIYA: \EQ[38]{ \eqalign{ \sigma(10001, 10^{10}, 2113248653) &= \sigma(10001, 10^{10}, 7350)-6(211303)(7886743997)/10^{10};\cr \sigma(10001, 10^{10}, 7350)&\approx -3+10^{10}/10001-\sigma(10^{10}, 10001, 7350);\cr \sigma(10^{10}, 10001, 7350)&=\sigma(100, 10001, 7350)=\cr &=\sigma(100, 10001, 50)-6(73)(2601)/10001;\cr \sigma(100, 10001, 50)&\approx -3+10001/100+100/10001-\sigma(10001, 100, 50);\cr \sigma(10001, 100, 50)&=\sigma(1, 100, 50)=-50,02.\cr C&\approx(-3+999900,01-97,02-50,02+113,91-99895,60)/10^{10}=\cr &=-0,000000003172.\cr } } tAKOE ZNACHENIE~$C$, KONECHNO, UDOVLETVORYAET LYUBYM TREBOVANIYAM. nO MOSHCHNOSTX |TOGO DATCHIKA RAVNA VSEGO~$3$, \emph{TAK CHTO, NESMOTRYA NA OTSUTSTVIE POSLEDOVATELXNOJ KORRELYACII, EGO NELXZYA SCHITATX HOROSHIM ISTOCHNIKOM SLUCHAJNYH CHISEL.} oTSUTSTVIE KORRELYACII--- NEOBHODIMOE, NO NE DOSTATOCHNOE USLOVIE! \proclaim pRIMER~3. oCENITX POSLEDOVATELXNUYU KORRELYACIYU PRI LYUBYH~$a$, $m$, $c$. pERVUYU FAZU PRIVEDENNYH VYSHE RASCHETOV MOZHNO PRODELATX V OBSHCHEM VIDE. pUSTX~$c_0=c\bmod a$. $$ \eqalignno{ \sigma(a, m, c)&=\sigma(a, m, c_0)+{6(c-c_0)\over am}(c+c_0-m)=\cr &=-3+{a\over m}+{m\over a}+{1\over am}+{6c^2\over am}-{6(c-c_0)\over a}-\sigma(m, a, c_0).&(39)\cr } $$ sOGLASNO UPR.~12, $\abs{\sigma(m, a, c_0)}