\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_{-\infty<x<+\infty}(F_n(x)-F(x));\cr
 K_n^-&=\sqrt{n}\max_{-\infty<x<+\infty}(F(x)-F_n(x)).\cr
}
\eqno(11)
$$
zDESX $K_n^+$~POKAZYVAET, KAKOVO MAKSIMALXNOE OTKLONENIE DLYA 
SLUCHAYA~$F_n>F$, A~$K_n^-$---KAKOVO MAKSIMALXNOE OTKLONENIE DLYA 
SLUCHAYA~$F_n<F$. v PRIMERAH, POKAZANNYH NA RIS.~4, ZNACHENIYA |TIH 
STATISTIK SLEDUYUSHCHIE:
$$
\matrix{
          & a     & b     & c     \cr
 K_{20}^+ & 0.492 & 0.134 & 0.313 \cr
 K_{20}^- & 0.536 & 1.027 & 2.101 \cr
}
\eqno(12)
$$

[\emph{zAMECHANIE.} nALICHIE MNOZHITELYA~$\sqrt{n}$ V FORMULE~(11) MOZHET 
POKAZATXSYA STRANNYM. sOGLASNO UPR.~6, PRI FIKSIROVANNOM~$x$ STANDARTNOE 
OTKLONENIE~$F_n(x)$ OT~$F(x)$ PROPORCIONALXNO~$1/\sqrt{n}$; SLEDOVATELXNO, 
MNOZHITELX~$\sqrt{n}$ NORMIRUET STATISTIKI~$K_n^+$ I~$K_n^-$ TAKIM OBRAZOM, 
CHTOBY STANDARTNOE OTKLONENIE NE ZAVISELO OT~$n$.]

tEPERX MOZHNO, KAK I V SLUCHAE KRITERIYA~$\chi^2$, NAJTI ZNACHENIYA~$K_n^+$ 
I~$K_n^-$ V "PROCENTILXNOJ" TABLICE, CHTOBY OPREDELITX, IMEYUT LI ONI 
VYSOKUYU ILI NIZKUYU ZNACHIMOSTX. s |TOJ CELXYU DLYA OBEIH VELICHIN~$K_n^+$ 
I~$K_n^-$ MOZHNO VOSPOLXZOVATXSYA TABL.~2. nAPRIMER, VEROYATNOSTX TOGO, CHTO 
$K_{30}^-$ BOLXSHE CHEM~$0.8036$, RAVNA~25\%. v OTLICHIE OT TABLICY DLYA 
KRITERIYA~$\chi^2$, KOTOROJ MOZHNO POLXZOVATXSYA TOLXKO PRI BOLXSHIH~$n$, V 
|TOJ TABLICE PRIVODYATSYA TOCHNYE ZNACHENIYA
%% 62
\picture{RIS.~4. pRIMERY |MPIRICHESKIH RASPREDELENIJ.}
%% 63

\htable{tABLICA~2}%
{nEKOTORYE DANNYE DLYA RASPREDELENIYA VELICHIN~$K_n^+$ I~$K_n^-$}%
{$#$\hfil\bskip&&\bskip\hfil$#$\hfil\bskip\cr
 \noalign{
  \embedpar{\noindent(dLYA~$n>30$ 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<x<+\infty}\abs{F_n(x)-F(x)}=\max(K_n^+, K_n^-).
\eqno(23)
$$
sREDI RYADA MODIFIKACIJ |TOGO KRITERIYA, OPISANNYH V 1939~G.\ 
n.~v.~sMIRNOVYM, BYLA I TA, KOTORAYA ISPOLXZUETSYA V |TOJ KNIGE I OPIRAETSYA 
NA RAZDELXNOE VYCHISLENIE~$K_n^+$ I~$K_n^-$. sUSHCHESTVUET OBSHIRNOE 
SEMEJSTVO RAZNOVIDNOSTEJ |TOGO KRITERIYA, NO TE IZ NIH, KOTORYE 
ISPOLXZUYUT~$K_n^+$ I~$K_n^-$, OSOBENNO UDOBNY DLYA MASHINNYH RASCHETOV. 
iSCHERPYVAYUSHCHIJ OBZOR LITERATURY PO ks-KRITERIYU I EGO OBOBSHCHENIYAM, VKLYUCHAYA 
OBSHIRNYJ SPISOK LITERATURY, SODERZHITSYA V RABOTE dARLINGA 
({\sl Annals of Mathematical Statistics,\/} {\bf 28} (1957), 823--838). 
rABOTA PROF.\ dARLINGA PREDNAZNACHENA GLAVNYM OBRAZOM DLYA SPECIALISTOV V 
DANNOJ OBLASTI.

pREZHDE CHEM NACHATX IZUCHENIE RASPREDELENIYA~$K_n^+$ I~$K_n^-$, SFORMULIRUEM 
SLEDUYUSHCHEE FUNDAMENTALXNOE UTVERZHDENIE. \dfn{eSLI~$X$---SLUCHAJNAYA VELICHINA S 
NEPRERYVNOJ FUNKCIEJ RASPREDELENIYA~$F(x)$, TO~$F(X)$---SLUCHAJNOE CHISLO, 
RAVNOMERNO RASPREDELENNOE MEZHDU~$0$ I~$1$.} dLYA DOKAZATELXSTVA |TOGO 
DOSTATOCHNO PROVERITX, CHTO PRI~$0\le y \le 1$ NERAVENSTVO~$F(X)\le y$ 
SPRAVEDLIVO S VEROYATNOSTXYU~$y$. iZ NEPRERYVNOSTI~$F(x)$ SLEDUET, 
CHTO~$F(x_0)=y$ DLYA KAKOGO-TO~$x_0$. pO|TOMU VEROYATNOSTX TOGO, 
CHTO~$F(X)\le y$, ESTX VEROYATNOSTX VYPOLNENIYA NERAVENSTVA~$X\le x_0$. 
pO OPREDELENIYU |TA VEROYATNOSTX ESTX~$F(x_0)$, T.~E.\ RAVNA~$y$.

pUSTX~$Y_j=n F(X_j)$ DLYA~$1\le j \le n$. tOGDA VELICHINY~$Y_j$ 
RASPREDELENY RAVNOMERNO MEZHDU~$0$ I~$n$; ONI NEZAVISIMY, ZA 
ISKLYUCHENIEM TOGO, CHTO~$Y_1\le Y_2 \le \ldots \le Y_n$ (|TO |KVIVALENTNO 
TREBOVANIYU~$X_1\le X_2\le\ldots\le X_n$, KOTOROE PRINIMAETSYA PRI RASCHETAH 
PO FORMULE~(13)). fORMULU~(13) MOZHNO PEREPISATX TEPERX SLEDUYUSHCHIM OBRAZOM:
$$
K_n^+={1\over \sqrt{n}}\max(1-Y_1, 2-Y_2, \ldots, n-Y_n).
$$
eSLI~$0\le t \le n$, TO VEROYATNOSTX NERAVENSTVA~$K_n^+\le t/\sqrt{n}$ ESTX 
VEROYATNOSTX TOGO, CHTO~$Y_j\ge j-t$ DLYA~$1\le j \le n$. eTU 
VEROYATNOSTX NETRUDNO ZAPISATX V VIDE $n\hbox{-KRATNOGO}$ INTEGRALA
$$
{\displaystyle
 \int_{\alpha_n}^n\,dY_n \int_{\alpha_{n-1}}^{Y_n}\,dY_{n-1}\ldots \int_{\alpha_1}^{Y_2}\,dY_1 
\over
 \displaystyle
 \int_0^n\,dY_n \int_0^{Y_n}\,dY_{n-1}\ldots \int_0^{Y_2}\,dY_1
}, \rem{GDE $\alpha_j=\max(j-t, 0)$.}
\eqno(24)
$$
zNAMENATELX |TOGO VYRAZHENIYA RAVEN~$n^n/n!$. dEJSTVITELXNO, KUB,
POSTROENNYJ NA VEKTORAH~$(Y_1, Y_2,~\ldots,  Y_n)$ S~$0\le Y_j<n$, IMEET
%% 72
OB�EM~$n^n$; EGO NADO RAZDELITX NA $n!$~RAVNYH CHASTEJ, SOOTVETSTVUYUSHCHIH 
VSEM VOZMOZHNYM UPORYADOCHENIYAM~$Y_j$. iNTEGRAL V CHISLITELE NESKOLXKO SLOZHNEE,
NO EGO MOZHNO VZYATX SPOSOBOM, OPISANNYM V UPR.~17; V REZULXTATE POLUCHAETSYA 
OBSHCHAYA FORMULA
$$
P\left\{ K_n^+\le {t\over \sqrt{n}}\right\}={t\over n^n}\sum_{0\le k \le t}\perm{n}{k}(k-t)^k(t+n-k)^{n-k-1}.
\eqno(25)
$$
rASPREDELENIE~$K_n^-$ TOCHNO TAKOE ZHE. fORMULA~(25) BYLA VPERVYE POLUCHENA 
bIRNBAUMOM I tINGI; EE MOZHNO ISPOLXZOVATX V SLUCHAYAH, KOTORYE NE OHVACHENY V 
TABL.~2.

v ORIGINALXNOJ RABOTE sMIRNOVA POKAZANO, CHTO
$$
\lim_{n\to\infty} P\{K_n^+\le s\}=1-e^{-2s^2} \rem{PRI~$s \ge 0$.}
\eqno (26)
$$
v SOCHETANII S FORMULOJ~(25) |TO DAET
$$
\lim_{n\to\infty}{s\over\sqrt{n}}
\sum_{\sqrt{ns}<k\le n}\perm{n}{k}\left({k\over n}-{s\over\sqrt{n}}\right)^k \left({s\over\sqrt{n}}+1-{k\over n}\right)^{n-k-1}=e^{-2s^2}, 
 \rem{$s\ge 0$.}
\eqno(27)
$$
nO DOKAZATX |TO PREDELXNOE SOOTNOSHENIE OCHENX TRUDNO. nAIBOLEE 
|LEMENTARNOE DOKAZATELXSTVO PRINADLEZHIT uITTLU 
({\sl Annals of Mathematical Statistics,\/} {\bf 32} (1961), 499--505). 
oNO OSNOVANO NA SLEDUYUSHCHEM PRIEME. v REZULXTATE NEKOTOROGO UVELICHENIYA I 
UMENXSHENIYA~$\alpha$ V~(24) VVODYATSYA SPECIALXNYM OBRAZOM 
MODIFICIROVANNYE STATISTIKI, DLYA KOTORYH VEROYATNOSTI VYCHISLYAYUTSYA TOCHNO, 
I ZATEM POKAZYVAETSYA, CHTO KAK VERHNYAYA, TAK I NIZHNYAYA GRANICY STREMYATSYA 
K~$e^{-2s^2}$.

\excercises
\ex[00] kAKUYU STROKU IZ TABLICY RASPREDELENIYA~$\chi^2$ NADO ISPOLXZOVATX 
DLYA VYYASNENIYA, NE SLISHKOM LI VELIKO ZNACHENIE~$V=7{7\over 48}$ V~(5)?

\ex[20] oPREDELITX VEROYATNOSTX~$p_s$ POYAVLENIYA SUMMY~$s$ DLYA~$2\le s \le 12$ 
PRI BROSANII DVUH KOSTEJ, USTROENNYH SLEDUYUSHCHIM OBRAZOM: V ODNOJ IZ 
NIH~$1$, A V DRUGOJ~$6$ VYPADAYUT ROVNO VDVOE CHASHCHE, CHEM LYUBOE DRUGOE ZNACHENIE.

\rex[23] kOSTI, OPISANNYE V PREDYDUSHCHEM UPRAZHNENII, BROSALISX 
144~RAZA. bYLI POLUCHENY SLEDUYUSHCHIE REZULXTATY:
\ctable{
 $#$\hfil\bskip&&\bskip\hfil$#$\bskip\cr
   s & 2 & 3 &  4 &  5 &  6 &  7 &  8 &  9 & 10 & 11& 12\cr
 Y_s & 2 & 6 & 10 & 16 & 18 & 32 & 20 & 13 & 16 & 9 &  2\cr
}

pRIMENITE K \emph{|TIM} ZNACHENIYAM KRITERIJ~$\chi^2$, POLXZUYASX 
VEROYATNOSTYAMI~(1), T.~E.\ PREDPOLAGAYA, CHTO KOSTI PRAVILXNYE. pOZVOLIT LI V 
TAKOM SLUCHAE KRITERIJ~$\chi^2$ OPREDELITX, CHTO KOSTI NEPRAVILXNYE? eSLI 
NET, TO OB�YASNITE POCHEMU.

\rex[23] nA SAMOM DELE AVTOR POLUCHIL REZULXTATY~(9) V |KSPERIMENTE~1,
IMITIRUYA KOSTI, ODNA IZ KOTORYH NORMALXNAYA, A NA DRUGOJ VYPADAET 
TOLXKO~$1$ ILI~$6$ S RAVNYMI VEROYATNOSTYAMI. vYCHISLITE DLYA |TOGO SLUCHAYA 
VEROYATNOSTI, KOTORYE ZAMENYAT~(1), I S POMOSHCHXYU KRITERIYA~$\chi^2$ OPREDELITE,
SOOTVETSTVUYUT LI REZULXTATY |KSPERIMENTA TAKOMU USTROJSTVU KOSTEJ.

%% 73

\ex[22] pUSTX~$F(x)$---RAVNOMERNOE RASPREDELENIE, IZOBRAZHENNOE NA RIS.~3,b. 
vYCHISLITE~$K^+_{20}$ I~$K^-_{20}$ DLYA SLEDUYUSHCHIH~20 |KSPERIMENTALXNYH ZNACHENIJ:
$$
\matrix{
 0.414, & 0.732, & 0.236, & 0.162, & 0.259, & 0.442, & 0.189, & 0.693, & 0.098, & 0,302, \cr
 0.442, & 0.434, & 0.141, & 0.017, & 0.318, & 0.869, & 0.772, & 0.678, & 0.354, & 0.718. \cr
}
$$
oPREDELITE S POMOSHCHXYU KAZHDOGO IZ |TIH DVUH KRITERIEV, SOOTVETSTVUYUT 
LI |KSPERIMENTALXNYE DANNYE RAVNOMERNOMU RASPREDELENIYU.

\ex[m20] rASSMOTRIM FUNKCIYU~$F_n(x)$, OPREDELENNUYU FORMULOJ~(10), 
PRI FIKSIROVANNOM~$x$. kAKOVA VEROYATNOSTX, CHTO~$F_n(x)=s/n$ DLYA ZADANNOGO 
CELOGO~$s$? kAKOVO SREDNEE ZNACHENIE~$F_n(x)$? kAKOVO SREDNEKVADRATICHNOE OTKLONENIE?

\ex[m15] pOKAZHITE, CHTO~$K^+_n$ I~$K^-_n$ NE MOGUT BYTX OTRICATELXNYMI. kAKOVO
NAIBOLXSHEE VOZMOZHNOE ZNACHENIE~$K^+_n$?

\ex[00] v TEKSTE BYL OPISAN |KSPERIMENT, V KOTOROM V REZULXTATE 
OBRABOTKI POSLEDOVATELXNOSTI SLUCHAJNYH CHISEL BYLO POLUCHENO 20~ZNACHENIJ 
STATISTIKI~$K^+_{10}$. eTI DANNYE, IZOBRAZHENNYE NA RIS.~4, BYLI 
ISSLEDOVANY S POMOSHCHXYU ks-KRITERIYA. pOCHEMU PRI |TOM ISPOLXZOVALISX 
TABLICHNYE ZNACHENIYA DLYA~$n=20$, A NE DLYA~$n=10$?

\rex[20] v OPISANNOM V TEKSTE |KSPERIMENTE NA GRAFIK NANOSILISX 
20~ZNACHENIJ~$K^+_{10}$, VYCHISLENNYH S POMOSHCHXYU TESTA "NAIBOLXSHEE IZ~5", 
KOTORYJ PRIMENYALSYA K RAZNYM CHASTYAM SLUCHAJNOJ POSLEDOVATELXNOSTI. mOZHNO 
BYLO BY VYCHISLITX TAKZHE SOOTVETSTVUYUSHCHIE 20~ZNACHENIJ~$K^-_{10}$; TAK KAK 
RASPREDELENIYA STATISTIK~$K^+_{10}$ I~$K^-_{10}$ SOVPADAYUT, MOZHNO BYLO BY 
OB�EDINITX VSE 40~ZNACHENIJ (20~ZNACHENIJ~$K^+_{10}$ I 
20~ZNACHENIJ~$K^-_{10}$ I PRIMENITX K NIM ks-KRITERIJ, VYCHISLIV~$K^+_{40}$ 
I~$K^-_{40}$. oBSUDITE DOSTOINSTVA |TOJ IDEI.

\rex[20] pREDPOLOZHIM, CHTO REZULXTATY $n$~ISPYTANIJ OBRABOTANY S 
POMOSHCHXYU KRITERIYA~$\chi^2$ I POLUCHENO ZNACHENIE~$V$. zATEM TE ZHE 
$n$~REZULXTATOV OBRABATYVAYUTSYA ESHCHE RAZ (POLUCHAETSYA, ESTESTVENNO, TO ZHE 
SAMOE), POSLE CHEGO DANNYE OBOIH TESTOV OB�EDINYAYUTSYA I RASSMATRIVAYUTSYA KAK 
EDINYJ TEST S CHISLOM ISPYTANIJ~$2n$ (PRI |TOM NARUSHAETSYA TREBOVANIE 
NEZAVISIMOSTI ISPYTANIJ). kAKAYA SVYAZX IMEETSYA MEZHDU VTORYM I PERVYM ZNACHENIEM~$V$?

\ex[20] rESHITE UPR.~10, ZAMENIV KRITERIJ~$\chi^2$ NA KRITERIJ ks.

\ex[M26] pUSTX PRI PRIMENENII KRITERIYA~$\chi^2$ K REZULXTATAM 
$n$~ISPYTANIJ PREDPOLAGAETSYA, CHTO $p_s$---VEROYATNOSTX POPADANIYA V 
KATEGORIYU~$s$. dOPUSTIM, CHTO V DEJSTVITELXNOSTI VEROYATNOSTX POPADANIYA V 
KATEGORIYU~$s$ RAVNA~$q_s\ne p_s$ (SM.~UPR.~3). kONECHNO, ZHELATELXNO, CHTOBY 
KRITERIJ~$\chi^2$ POZVOLIL OBNARUZHITX, CHTO PERVONACHALXNOE PREDPOLOZHENIE 
BYLO NEVERNYM. pOKAZHITE, CHTO PRI DOSTATOCHNO BOLXSHIH~$n$ |TO 
DEJSTVITELXNO BUDET OBNARUZHENO. dOKAZHITE TAKZHE ANALOGICHNYJ REZULXTAT DLYA ks-KRITERIYA.

\ex[m24] pOKAZHITE, CHTO FORMULA~(13) |KVIVALENTNA FORMULE~(11).

\rex[vm26] pUSTX VELICHINY~$Z_s$ ZADANY VYRAZHENIEM~(18). pOKAZHITE 
NEPOSREDSTVENNO S POMOSHCHXYU FORMULY sTERLINGA, CHTO SPRAVEDLIVO 
SLEDUYUSHCHEE RAVENSTVO DLYA POLINOMIALXNOGO RASPREDELENIYA:
$$
n'p_1^{Y_1}\ldots p_k^{Y_k}/Y_1!\ldots Y_k! = 
e^{-V/2}/\sqrt{(2n\pi)^{k-1}p_1\ldots p_k}+O(n^{-k/2}),
$$
ESLI $Z_1$, $Z_2$,~\dots, $Z_k$ OGRANICHENY PRI~$n\to\infty$. (tAKOJ PODHOD 
POZVOLYAET OBOSNOVATX KRITERIJ~$\chi^2$, BOLXSHE OPIRAYASX NA PERVOOSNOVY I 
PROVODYA MENXSHE VYKLADOK, CHEM PRI PODHODE, ISPOLXZOVANNOM V TEKSTE.)

\ex[vm24] oBYCHNO POLYARNYE KOORDINATY V DVUMERNOM PROSTRANSTVE ZADAYUTSYA 
VYRAZHENIYAMI~$x=r\cos\theta$ I~$y=r\sin\theta$. pRI INTEGRIROVANII 
ISPOLXZUETSYA RAVENSTVO~$dx\,dy=r\,dr\,d\theta$. v OBSHCHEM SLUCHAE DLYA 
$n\hbox{-MERNOGO}$ PROSTRANSTVA MOZHNO POLOZHITX
$$
\eqalign{
 x_k &=r\sin\theta_1\ldots\sin\theta_{k-1}\cos\theta_k,\rem{$1\le k <n$,}\cr
 x_n &=r\sin\theta_1\ldots\sin\theta_{n-1}.\cr
}
$$
%% 74
pOKAZHITE, CHTO V |TOM SLUCHAE
$$
 dx_1\,dx_2\,\ldots\,dx_n=\abs{r^{n-1}\sin^{n-2}\theta_1 \ldots \sin\theta_{n-2}\, dr \,d\theta_1\, \ldots \,d\theta_{n-1}}.
$$

\ex[vm35] oBOBSHCHITE TEOREMU~1.2.11.3A TAK, CHTOBY OPREDELITX ZNACHENIE
$$
\gamma(x+1, x+z\sqrt{2x}+y)/\Gamma(x+1)
$$
PRI BOLXSHIH~$x$ I FIKSIROVANNYH~$y$, $z$. oPUSTITE CHLENY~$O(1/x)$. s 
POMOSHCHXYU POLUCHENNOGO REZULXTATA NAJDITE PRIBLIZHENNOE RESHENIE~$t$ URAVNENIYA
$$
\gamma\left({\nu\over 2}, {t\over 2}\right) \bigg/ \Gamma\left({\nu\over 2}\right)=p
$$
PRI BOLXSHIH~$\nu$ I FIKSIROVANNOM~$p$; TAKIM OBRAZOM BUDET NAJDENO 
OB�YASNENIE ASIMPTOTICHESKIH FORMUL, PRIVEDENNYH V TABL.~1. 
(\emph{uKAZANIE:} SM.~UPR.~1.2.11.3-8.)

\ex[vm26] pUSTX~$t$---NEKOTOROE DEJSTVITELXNOE CHISLO, I PUSTX PRI~$0\le k \le n$
$$
P_{nk}(x)=\int_{n-t}^x\,dx_n \int_{n-1-t}^{x_n}\, dx_{n-1} \ldots 
 \int_{k+1-t}^{x_{k+2}}\,dx_{k+1} \int_0^{x_k+1}\, dx_k \ldots 
 \int_0^{x_2}\, dx_1,
$$
A~$P_{00}(x)=1$. dOKAZHITE SLEDUYUSHCHIE SOOTNOSHENIYA:
{\medskip\narrower
\item{a)}$\displaystyle 
 P_{nk}(x)=\int_n^{x+t}\, dx_n \int_{n-1}^{x_n}\, dx_{n-1} \ldots 
 \int_{k+1}^{x_{k+2}}\,dx_{k+1} \int_t^{x_k+1}\,dx_k \ldots \int_x^{x_2}\,dx_1;
$
 \hiddenpar
\item{b)}$\displaystyle 
 P_{n0}(x)=(x+t)^n/n!-(x+t)^{n-1}/(n-1)!;
$
 \hiddenpar
\item{c)}$\displaystyle 
 P_{nk}(x)-P_{n(k-1)}(x)={(k-t)^k\over k!}P_{(n-k)0}(x-k) \rem{PRI $1\le k \le n$;}
$
 \hiddenpar
\item{d)}POLUCHITE OBSHCHUYU FORMULU DLYA~$P_{nk}(x)$ I ISPOLXZUJTE EE DLYA VYVODA FORMULY~(24).
\medskip}

\ex[M20] dAJTE "PROSTOE" OB�YASNENIE, POCHEMU RASPREDELENIYA VELICHIN~$K^+_n$ 
I~$K^-_n$ ODINAKOVY.

\ex[vm48] rAZRABOTAJTE KRITERII, PODOBNYE KRITERIYU kOLMOGOROVA-sMIRNOVA, 
DLYA MNOGOMERNYH RASPREDELENIJ~$F(x_1,~\ldots, x_r)=P\{X_1\le x_1,~\ldots, X_r\le x_r\}$. (oNI MOGUT PONADOBITXSYA, NAPRIMER, V SVYAZI S TESTOM  
PROVERKI SERII, RASSMOTRENNYM V SLEDUYUSHCHEM PUNKTE.)

\ex[vm50] pOLUCHITE DALXNEJSHUYU INFORMACIYU OB ASIMPTOTICHESKOM ZNACHENII 
VELICHINY V LEVOJ CHASTI RAVENSTVA~(27) PRI BOLXSHIH~$n$. [\emph{zAMECHANIYA.} 
eMPIRICHESKIE DANNYE POKAZYVAYUT, CHTO |TA VELICHINA MENXSHE~$e^{-2s^2}$ PRI 
LYUBYH~$n$, NO TOCHNO |TO NEIZVESTNO. sOGLASNO RABOTE uITTLA, ONA DOLZHNA 
NAHODITXSYA GDE-TO MEZHDU~$\exp(-2s^2-(2s+s^3)/\sqrt{n})$ 
I~$\exp(-2s^2+3.83 s^3/\sqrt{n})$. vYRAZHENIYA, PRIVEDENNYE V TABL.~2 DLYA 
BOLXSHIH~$n$, POLUCHENY |MPIRICHESKI NA OSNOVE OGRANICHENNOGO NABORA DANNYH; 
BYLO BY POLEZNO POLUCHITX TEORETICHESKI BOLEE NADEZHNYE DANNYE.]

\ex[m40] hOTYA, KAK BYLO UKAZANO V TEKSTE, KRITERIJ kOLMOGOROVA- sMIRNOVA 
PRIMENYAETSYA V TEH SLUCHAYAH, KOGDA FUNKCIYA RASPREDELENIYA~$F(x)$ NEPRERYVNA,
MOZHNO, KONECHNO, POPROBOVATX VYCHISLITX~$K^+_n$ I~$K^-_n$ DLYA 
DISKRETNYH RASPREDELENIJ. pROANALIZIRUJTE VEROYATNOSTNOE POVEDENIE~$K^+_n$ 
I~$K^-_n$ DLYA RAZNYH TIPOV DISKRETNYH RASPREDELENIJ~$F(x)$. sRAVNITE 
|FFEKTIVNOSTX TAKOGO TESTA I KRITERIYA~$\chi^2$  V KONKRETNYH SLUCHAYAH.

\ex[vm42] oBSUDITE ISPOLXZOVANIE "OTNOSHENIYA NAIBOLXSHEGO PRAVDOPODOBIYA" V 
KACHESTVE ALXTERNATIVY KRITERIYA~$\chi^2$ PRI PROVERKE DATCHIKOV SLUCHAJNYH 
CHISEL; PROVEDITE |KSPERIMENTY, PRIMENYAYA |TI DVA TIPA STATISTIK.

%% 75

\subsubchap{eMPIRICHESKIE TESTY} %3.3.2
v |TOM PUNKTE BUDUT OPISANY DEVYATX TIPOV SPECIALIZIROVANNYH TESTOV, 
KOTORYE PRIMENYAYUTSYA DLYA PROVERKI SLUCHAJNOSTI CHISLOVYH POSLEDOVATELXNOSTEJ. 
oPISANIE KAZHDOGO TESTA SOSTOIT IZ DVUH CHASTEJ: (a)~KRATKOJ INSTRUKCII PO 
PRIMENENIYU TESTA I (b)~IZLOZHENIYA TEORII, LEZHASHCHEJ V OSNOVE TESTA. 
(chITATELI S NEDOSTATOCHNOJ MATEMATICHESKOJ PODGOTOVKOJ MOGUT PRI 
ZHELANII PROPUSKATX TEORETICHESKIE RASSUZHDENIYA. nAOBOROT, CHITATELYA 
SO SKLONNOSTXYU K MATEMATIKE MOGUT ZAINTERESOVATX SAMI PO 
SEBE KOMBINATORNYE ZADACHI, VOZNIKAYUSHCHIE ZDESX, DAZHE ESLI ON NE SOBIRAETSYA 
ZANIMATXSYA PROVERKOJ DATCHIKOV SLUCHAJNYH CHISEL.)

kAZHDYJ TEST PRIMENYAETSYA K POSLEDOVATELXNOSTI SLUCHAJNYH CHISEL
$$
\<U_n>=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_n>=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~$s<n$, VERNUTXSYA NA~\stp{2}.
\algend

pOSLE VYPOLNENIYA |TOGO ALGORITMA $k=t+1$~ZNACHENIJ $|COUNT|[0]$, 
$|COUNT|[1]$,~\dots, $|COUNT|[t]$ OBRABATYVAYUTSYA S POMOSHCHXYU 
KRITERIYA~$\chi^2$ S ISPOLXZOVANIEM SLEDUYUSHCHIH ZNACHENIJ VEROYATNOSTEJ:
$$
p_0=p, \quad p_1=p(1-p), \quad p_2=p(1-p)^2, \quad \ldots, \quad p_{t-1}=p(1-p)^{t-1}, \quad p_t=p(1-p)^t. 
\eqno (4)
$$
zDESX $p=\beta-\alpha$~RAVNO VEROYATNOSTI TOGO, CHTO~$\alpha\le U_j<\beta$.  
zNACHENIYA~$n$ I~$t$ OBYCHNO VYBIRAYUTSYA TAKIM OBRAZOM, CHTOBY 
SREDNIE ZNACHENIYA~$|COUNT|[r]$ BYLI NE MENXSHE~5.

chASTO POLAGAYUT LIBO~$\alpha=0$, LIBO~$\beta=1$, CHTOBY UPROSTITX
SHAG~G3 OPISANNOGO ALGORITMA. chASTNYE 
SLUCHAI~$(\alpha, \beta)=\left(0, {1\over 2} \right)$ 
%% 78
ILI~$\left({1\over 2}, 1\right)$ INOGDA NAZYVAYUT PROVERKOJ OTKLONENIJ OT 
SREDNEGO VNIZ ILI VVERH.

fORMULY~(4) DLYA VEROYATNOSTEJ VYVODYATSYA LEGKO; MY PREDOSTAVLYAEM CHITATELYU 
VOZMOZHNOSTX PRODELATX |TO SAMOSTOYATELXNO.
oTMETIM, CHTO V PRIVEDENNOM ZDESX ALGORITME VYCHISLYAYUTSYA DLINY ZADANNOGO 
CHISLA $n$~\emph{INTERVALOV}; POSLEDOVATELXNOSTX PRI |TOM MOZHET POLUCHITXSYA 
PROIZVOLXNOJ DLINY. mOZHNO, NAOBOROT FIKSIROVATX DLINU PROVERYAEMOJ 
POSLEDOVATELXNOSTI (SM.~UPR.~5).

\section{D.~pOKER-TEST (PROVERKA KOMBINACIJ)}. v "KLASSICHESKOM" 
POKER-TESTE RASSMATRIVAYUTSYA $n$~GRUPP IZ PYATI SLEDUYUSHCHIH DRUG ZA DRUGOM 
CELYH CHISEL~$(Y_{5j}, Y_{5j+1}$,~\dots, $Y_{5j+4})$, $0\le j < n$. 
vYDELYAYUTSYA SLEDUYUSHCHIE 7~TIPOV KOMBINACIJ:
\ctable{
 \hfil$#$\bskip&\bskip#\hfil\cr
 abcde & (VSE RAZNYE),\cr
 aabcd & (ODNA PARA),\cr
 aabbc & (DVE PARY),\cr
 aaabc & (TRI ODNOGO VIDA),\cr
 aaabb & (POLNYJ SBOR),\cr
 aaaab & (CHETYRE ODNOGO VIDA),\cr
 aaaaa & (PYATX ODNOGO VIDA).\cr
}
s POMOSHCHXYU KRITERIYA~$\chi^2$ PROVERYAETSYA, SOOTVETSTVUYUT LI 
CHASTOTY KOMBINACII VEROYATNOSTYAM.

dLYA OBLEGCHENIYA PROGRAMMIROVANIYA ZHELATELXNO NESKOLXKO UPROSTITX |TOT TEST. 
hOROSHIM KOMPROMISSOM MOZHET SLUZHITX PODSCHET KOLICHESTVA NESOVPADAYUSHCHIH CHISEL 
V KAZHDOJ PYATERKE chISLO KATEGORIJ PRI |TOM RAVNO PYATI:
$$
\eqalign{
\hbox{5 RAZNYH}&=\hbox{VSE RAZNYE;}\cr
\hbox{4 RAZNYH}&=\hbox{ODNA PARA;}\cr
\hbox{3 RAZNYH}&=\hbox{DVE PARY, ILI TRI ODNOGO VIDA;}\cr
\hbox{2 RAZNYH}&=\hbox{POLNYJ SBOR ILI CHETYRE ODNOGO VIDA;}\cr
\hbox{NET RAZNYH} &= \hbox{PYATX ODNOGO VIDA.}\cr
}
$$
tEST PRI |TOM POCHTI NE UHUDSHAETSYA, A ALGORITM SUSHCHESTVENNO UPROSHCHAETSYA.

v OBSHCHEM SLUCHAE MOZHNO RASSMOTRETX $n$~GRUPP PO~$k$ SLEDUYUSHCHIH PODRYAD CHISEL I 
PODSCHITYVATX CHISLO GRUPP, V KOTORYH IMEETSYA $r$~RAZNYH CHISEL. zATEM 
PRIMENYATX KRITERIJ~$\chi^2$ S VEROYATNOSTYAMI
$$
p_r={d(d-1)\ldots(d-r+1) \over d^k} \Stir{k}{r}.
\eqno(5)
$$
(chISLA sTIRLINGA~$\Stir{k}{r}$ BYLI OPREDELENY V P.~1.2.6; TAM 
ZHE PRIVEDENY FORMULY, PO KOTORYM IH MOZHNO POSCHITATX.) tAK KAK PRI~$r=1$ 
ILI~$2$ VEROYATNOSTX~$p_r$ OCHENX MALA, |TI KATEGORII MOZHNO OB�EDINITX.

%% 79
pRIVEDENNAYA VYSHE FORMULA DLYA~$p_r$ POLUCHAETSYA SLEDUYUSHCHIM OBRAZOM. 
vYCHISLYAETSYA, SKOLXKO GRUPP PO $k$~CHISEL, KAZHDOE IZ KOTORYH MOZHET PRINIMATX 
ZNACHENIYA OT~$0$ DO~$d-1$, SODERZHAT $r$~RAZNYH |LEMENTOV. zATEM REZULXTATY 
DELYATSYA NA~$d^k$---OBSHCHEE KOLICHESTVO RAZLICHNYH GRUPP. tAK KAK 
$d(d-1)\ldots(d-r+1)$~ESTX CHISLO RAZMESHCHENIJ IZ $d$~|LEMENTOV PO~$r$, 
OSTAETSYA TOLXKO POKAZATX, CHTO~$\Stir{k}{r}$---CHISLO SPOSOBOV, KOTORYMI 
MOZHNO RASPREDELITX
$k$~|LEMENTOV PO $r$~KATEGORIYAM. oKONCHATELXNO FORMULA~(5) VYVODITSYA S 
POMOSHCHXYU REZULXTATOV UPR.~1.2.6-64.

\section{E.~tEST SOBIRATELYA KUPONOV}. eTOT TEST I TOLXKO CHTO 
OPISANNYJ SVYAZANY MEZHDU SOBOJ PRIMERNO TAK ZHE, KAK TESTY PROVERKI 
INTERVALOV I PROVERKI CHASTOT. iSPOLXZUETSYA POSLEDOVATELXNOSTX~$Y_0$, 
$Y_1$,~\dots{} I OPREDELYAYUTSYA DLINY SEGMENTOV~$Y_{j+1}$, $Y_{j+2}$,~\dots, 
$Y_{j+r}$, NEOBHODIMYH DLYA TOGO, CHTOBY SOBRATX "POLNYJ NABOR" CELYH CHISEL 
OT~$0$ DO~$d-1$. eTO MOZHNO SDELATX S POMOSHCHXYU SLEDUYUSHCHEGO ALGORITMA.

\alg C.(rEALIZACIYA TESTA SOBIRATELYA KUPONOV.) dLYA ZADANNOJ 
POSLEDOVATELXNOSTI CELYH CHISEL~$Y_0$, $Y_1$,~\dots{} ($0\le Y_j<d$) |TOT 
ALGORITM OPREDELYAET DLINY~$n$ POSLEDOVATELXNYH SEGMENTOV PO TOLXKO CHTO 
SFORMULIROVANNOMU PRAVILU. pO OKONCHANII RABOTY ALGORITMA V~$|COUNT|[r]$ 
PRI~$0\le r < t$ NAHODITSYA CHISLO SEGMENTOV DLINY~$r$, A 
V~$|COUNT|[t]$---CHISLO SEGMENTOV DLINY~$\ge t$.

\st[nACHALXNAYA USTANOVKA.] uSTANOVITX~$j\asg -1$, $s\asg 0$, A 
TAKZHE~$|COUNT|[r]\asg 0$ DLYA~$0\le r \le t$. 

\st[$q, r=0$.] uSTANOVITX~$q\asg r \asg 0$, A TAKZHE~$|OCCURS|[k]\asg 0$ 
DLYA~$0\le k < d$. 

\st[sLEDUYUSHCHEE ISPYTANIE.] uVELICHITX~$r$ I~$j$ NA~$1$. 
eSLI~$|OCCURS|[Y_j]\ne0$, POVTORITX |TI OPERACII.

\st[pOLNYJ NABOR?] uSTANOVITX~$|OCCURS|[Y_j]\asg 1$, $q\asg q+1$.
(nA DANNYJ MOMENT OBNARUZHENO $q$~RAZNYH ZNACHENIJ. eSLI~$q=d$, |TO ZNACHIT, 
CHTO POLUCHEN POLNYJ NABOR.) pRI~$q<d$ PEREJTI NA~\stp{3}.

\st[rEGISTRACIYA DLINY SEGMENTA.] pRI~$r\ge t$ PRIBAVITX~$1$ K~$|COUNT|[t]$,
V PROTIVNOM SLUCHAE PRIBAVITX~$1$ K~$|COUNT|[r]$.

\st[oBNARUZHENO $n$~SEGMENTOV?] pRIBAVITX~$1$ K~$s$. eSLI~$s<n$, 
VERNUTXSYA NA~\stp{2}.
\algend

pRIMER ISPOLXZOVANIYA |TOGO ALGORITMA PRIVEDEN V UPR.~7. mOZHNO PREDSTAVITX 
SEBE, CHTO RECHX IDET O MALXCHIKE, SOBIRAYUSHCHEM $d$~TIPOV KUPONOV. pO ODNOMU 
KUPONU SODERZHITSYA V KAZHDOJ UPAKOVKE S KASHEJ DLYA ZAVTRAKA, PRICHEM 
RASPREDELENY ONI SLUCHAJNYM OBRAZOM. mALXCHIK EST KASHU DO TEH POR, POKA NE 
SOBERET POLNYJ KOMPLEKT KUPONOV.

%% 80

sODERZHIMOE SCHETCHIKOV~$|COUNT|[d]$,  $|COUNT|[d+1]$,~\dots, $|COUNT|[t]$ 
OBRABATYVAETSYA S POMOSHCHXYU KRITERIYA~$\chi^2$ S~$k=t-d+1$~STEPENYAMI SVOBODY 
POSLE TOGO, KAK ALGORITM~C ZAVERSHIL RABOTU. sOOTVETSTVUYUSHCHIE VEROYATNOSTI RAVNY:
$$
p_r={d!\over d^r}\Stir{r-1}{d-1}, 
\qquad d\le r<t, 
\qquad p_t=1-{d!\over d^{t-1}}\Stir{t-1}{d}.
\eqno(6)
$$
dLYA VYVODA |TIH FORMUL DOSTATOCHNO ZAMETITX, CHTO, SOGLASNO~(5), VEROYATNOSTX 
TOGO, CHTO SEGMENT DLINY~$r$ \emph{NEPOLNYJ,} T.~E.\ SODERZHIT NE VSE IZ 
VOZMOZHNYH $d$~ZNACHENIJ, RAVNA
$$
q_r=1-{d!\over d^r}\Stir{r}{d}.
$$
tOGDA FORMULY~(6) POLUCHAYUTSYA NEPOSREDSTVENNO IZ 
SOOTNOSHENIJ~$p_r=q_{r-1}-q_r$, $d\le r < t$ I~$p_t=q_{t-1}$.

fORMULY, VOZNIKAYUSHCHIE V SVYAZI S RAZLICHNYMI \emph{OBOBSHCHENIYAMI} |TOGO TESTA, 
RASSMOTRENY V UPR.~9 I~10, A TAKZHE V RABOTE g.~FON~shELLINGA 
({\sl AMM,\/} {\bf 61} (1954), 306--311).

\section{F.~pROVERKA PERESTANOVOK}. rAZDELIM ISHODNUYU POSLEDOVATELXNOSTX 
NA $n$~GRUPP PO $t$~|LEMENTOV V KAZHDOJ: 
$(U_{jt}$, $U_{jt+1}$,~\dots, $U_{jt+t-1})$, $0\le j < n$. v KAZHDOJ GRUPPE 
VOZMOZHNO VSEGO $t!$~VARIANTOV OTNOSITELXNOGO RASPOLOZHENIYA CHISEL. 
pODSCHITYVAETSYA, SKOLXKO RAZ VSTRECHAETSYA KAZHDOE KONKRETNOE OTNOSITELXNOE 
RASPOLOZHENIE, POSLE CHEGO PRIMENYAETSYA 
KRITERIJ~$\chi^2$ S~$k=t!$ I VEROYATNOSTYAMI~$1/t!$ nAPRIMER, PRI~$t=3$ 
CHISLO KATEGORIJ RAVNO SHESTI: $U_{3j}<U_{3j+1}<U_{3j+2}$ 
ILI~$U_{3j}<U_{3j+2}<U_{3j+1}$ ILI~\dots{} ILI~$U_{3j+2}<U_{3j+1}<U_{3j}$. 
pRI |TOM PREDPOLAGAETSYA, CHTO TOCHNOE RAVENSTVO DVUH CHISEL NEVOZMOZHNO: 
DEJSTVITELXNO, VEROYATNOSTX TAKOGO SOBYTIYA RAVNA NULYU.

pRI REALIZACII |TOGO TESTA NA MASHINE UDOBNO VOSPOLXZOVATXSYA SLEDUYUSHCHIM 
ALGORITMOM, KOTORYJ INTERESEN I SAM PO SEBE.

\alg P.(aNALIZ PERESTANOVOK.) lYUBOMU NABORU NESOVPADAYUSHCHIH 
|LEMENTOV~$(U_1,~\ldots, U_t)$ STAVITSYA V SOOTVETSTVIE CELOCHISLENNAYA 
FUNKCIYA~$f(U_1,~\ldots, U_t)$, TAKAYA, CHTO
$$
0\le f(U_1, \ldots, U_t)<t!
$$
I~$f(U_1,~\ldots, U_t)=f(V_1,~\ldots, V_t)$ V TOM I TOLXKO TOM SLUCHAE,
KOGDA |LEMENTY V~$(U_1,~\ldots, U_t)$ I~$(V_1,~\dots, V_t)$ RASPOLOZHENY V 
ODINAKOVOM PORYADKE. v PROGRAMME ISPOLXZUETSYA VSPOMOGATELXNAYA 
TABLICA~$C[1]$,~\dots, $C[t]$.

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

\st[oPREDELITX MAKSIMUM.] oPREDELITX MAKSIMALXNOE IZ 
ZNACHENIJ~$\set{U_1,~\ldots, U_r}$. dOPUSTIM |TO~$U_s$. zATEM 
USTANOVITX~$C[r]\asg s-1$.
%% 81
\st[zAMENA.] vZAIMOZAMENITX~$U_r\xchg U_s$.

\st[uMENXSHENIE~$r$.] vYCHESTX IZ~$r$ EDINICU. eSLI~$r>0$, 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]<r
\eqno(8)
$$
(SM.~SHAG~P2) I, V CHASTNOSTI, $C[1]$ VSEGDA RAVNO NULYU. tAK KAK 
$C[r]$~MOZHET PRINIMATX $r$~RAZLICHNYH ZNACHENIJ, OBSHCHEE 
KOLICHESTVO RAZNOVIDNOSTEJ TABLICY~$C$ RAVNO~$t!$. iZ FORMUL~(7) I~(8) 
LEGKO VIDETX, CHTO~$0\le f < t!$. k KONCU RABOTY ALGORITMA 
VELICHINY~$(U_1,~\ldots, U_t)$ BUDUT RASSTAVLENY V PORYADKE VOZRASTANIYA.

dLYA DOKAZATELXSTVA TOGO, CHTO REZULXTAT~$f$, POLUCHENNYJ S POMOSHCHXYU 
ALGORITMA~P, HARAKTERIZUET EDINSTVENNYM OBRAZOM PORYADOK SLEDOVANIYA CHISEL 
V ISHODNOJ POSLEDOVATELXNOSTI~$(U_1,~\ldots, U_t)$, POKAZHEM, CHTO |TOT 
ALGORITM MOZHNO ISPOLXZOVATX DLYA RESHENIYA OBRATNOJ ZADACHI. pUSTX ZADANO 
NEKOTOROE ZNACHENIE~$f$ I~$t$ |LEMENTOV~$(U_1,~\ldots, U_t)$, 
PRICHEM~$0\le f<t!$ I~$U_1<U_2<\ldots<U_t$. uSTANOVIM~$C[t]\asg f \bmod t$, 
$C[t-1]\asg \floor{f/t}\bmod(t-1)$, $C[t-2]\asg \floor{\floor{f/t}/(t-1)}\bmod (t-2)$ 
I~T.~D., VYPOLNYAYA, TAKIM OBRAZOM, SHAG~P5 V OBRATNOM PORYADKE. zATEM 
PROIZVEDEM ZAMENY~$U_1\xchg U_{C[1]+1}$, $U_2\xchg U_{C[2]+1}$,~\dots, 
$U_t\xchg U_{C[f]+1}$ V UKAZANNOM PORYADKE. lEGKO VIDETX, CHTO PRI |TOM 
LIKVIDIRUYUTSYA POSLEDSTVIYA VYPOLNENIYA SHAGOV P1--P4. tOT FAKT, CHTO 
ZNACHENIE~$f$ POZVOLYAET VOSSTANOVITX ISHODNYJ PORYADOK POSLEDOVATELXNOSTI, 
DOKAZYVAET PRAVILXNOSTX ALGORITMA~P.

\section{G. pROVERKA NA MONOTONNOSTX}. eTOT TEST VYYAVLYAET "NEUBYVANIE" I 
"NEVOZRASTANIE", T.~E.\ ANALIZIRUYUTSYA DLINY \emph{MONOTONNYH} 
PODPOSLEDOVATELXNOSTEJ CHISEL V ISHODNOJ POSLEDOVATELXNOSTI.

v KACHESTVE PRIMERA RASSMOTRIM POSLEDOVATELXNOSTX IZ 
10~CIFR "$1298536704$"; OTMECHAYA VERTIKALXNYMI LINIYAMI NACHALO I 
KONEC POSLEDOVATELXNOSTI, A TAKZHE VSE MESTA, GDE~$X_j>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~$i<j$):
$$
\eqalign{
{1\over n!}\sum Z_{pi}&=\cases{
  (p+\delta_{i1})/(p+1)! & PRI~$i\le n-p+1$;\cr
                       0 & V PROTIVNOM SLUCHAE;\cr
 }\cr
{1\over n!}\sum Z_{pi}Z_{qj}&=\cases{
                       (p+\delta_{i1})q/(p+1)!(q+1)! & PRI $i+p<j\le n-q+1$;\cr
 (p+\delta_{i1})/(p+1)!q!-(p+q+\delta_{i1})/(p+q+1)! & PRI~$i+p=j\le n-q+1$;\cr 
                                                   0 & V PROTIVNOM SLUCHAE.\cr
 }
}
\eqno(14)
$$
sUMMIROVANIE PROVODITSYA ZDESX PO VSEM VOZMOZHNYM PERESTANOVKAM. chTOBY 
POKAZATX, KAK VYVODYATSYA |TI FORMULY, RASSMOTRIM SAMYJ SLOZHNYJ SLUCHAJ, 
KOGDA~$i+p=j\le n-q+1$ I~$i>1$. 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<\ldots<U_{i+p-1}>U_{i+p}<\ldots<U_{i+p+q-1}.
\eqno(15)
$$
chISLO TAKIH PERESTANOVOK MOZHNO OPREDELITX S POMOSHCHXYU SLEDUYUSHCHIH 
SOOBRAZHENIJ: SUSHCHESTVUET $\perm{n}{p+1+q}$~SPOSOBOV VYBORA |LEMENTOV 
POSLEDOVATELXNOSTI, UKAZANNYH V~(15); IMEETSYA
$$
(p+q+1)\perm{p+q}{p}-\perm{p+q+1}{p+1}-\perm{p+q+1}{1}+1
\eqno(16)
$$
%% 84
SPOSOBOV RASPOLOZHENIYA IH V PORYADKE, UKAZANNOM V~(15), (SM.~UPR.~13) 
I~$(n-p-q-1)!$~SPOSOBOV RASPOLOZHENIYA OSTALXNYH
|LEMENTOV. tAKIM OBRAZOM, NADO UMNOZHITX~(16) 
NA~$\perm{n}{p+q+1}\times(n-p-q-1)!$ I POSLE DELENIYA NA~$n!$ POLUCHAETSYA 
ISKOMYJ REZULXTAT.

iZ SOOTNOSHENIJ~(14) V REZULXTATE DOVOLXNO GROMOZDKIH PREOBRAZOVANIJ 
MOZHNO POLUCHITX
$$
\eqalignno{
\mean (R'_p)&=\mean (Z_{p1}+\cdots+Z_{pn})=\cr 
&=(n+1)p/(p+1)!-(p-1)/p!, \rem{$1\le p\le n$;} & (17)\cr
}
$$
$$
\eqalignno{
\covar(R'_pR_q) &=\mean(R'_pR'_q)-\mean (R'_p)\mean (R'_q)=\cr
&=\sum_{1\le i, j \le n} {1\over n!} \sum Z_{pi} Z_{pj}-\mean(R'_p)\mean(R'_q)=\cr
&=\cases{
\mean(R'_t)+f(p, q, n) & PRI $p+q\le n$;\cr
\mean(R'_t)-\mean(R'_p)\mean(R'_q) & PRI $p+q>n$;\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 r<t$, A~$Z_t$---CHISLO INTERVALOV DLINY~$\ge t$. pOKAZHITE, CHTO 
VELICHINA~$V=\sum_{0\le r\le t} (Z_r-np_r)^2 \Big/ np_r$ DOLZHNA IMETX 
PRI~$N\to\infty$ RASPREDELENIE~$\chi^2$ S $t$~STEPENYAMI SVOBODY, GDE 
$p_r$~OPREDELENY VYRAZHENIEM~(4).

\ex[40](X.~gIRINGER) aNALIZ CHASTOT POYAVLENIYA RAZLICHNYH CIFR V DESYATICHNOM 
PREDSTAVLENII CHISLA~$e=2.71828\ldots$ DAET DLYA PERVYH 2000~CIFR 
ZNACHENIE~$\chi^2=1.06$. eTO UKAZYVAET NA TO, CHTO CHASTOTY LEZHAT ZNACHITELXNO 
BLIZHE K SREDNIM ZNACHENIYAM, RAVNYM~$200$, CHEM MOZHNO BYLO BY OZHIDATX PRI 
SLUCHAJNOM  RASPREDELENII (VEROYATNOSTX ZNACHENIJ~$\chi^2\ge 1.15$ 
RAVNA~$99.9\%$). eSLI PRIMENITX TOT ZHE TEST K PERVYM $10\,000$~CIFRAM, 
POLUCHAETSYA RAZUMNOE ZNACHENIE~$\chi^2=8.61$; NO FAKT STOLX PRAVILXNOGO 
RASPREDELENIYA PERVYH 2000~CIFR OSTAETSYA UDIVITELXNYM. pROIZOJDET LI TO ZHE 
SAMOE PRI PREDSTAVLENII~$e$ V SISTEME SCHISLENIYA S DRUGIM OSNOVANIEM? 
(sM.~{\sl AMM,\/} {\bf 72} (1965), 483--500.)

\ex[08] pROVERXTESPOMOSHCHXYU TESTA SOBIRATELYA KUPONOV (ALGORITM~C) PRI~$d=3$ 
I~$n=7$ SLEDUYUSHCHUYU POSLEDOVATELXNOSTX: $1101221022120202001212201010201121$.
 kAKOVY DLINY SEMI PODPOSLEDOVATELXNOSTEJ?

% ex. 8
\rex[M22] sKOLXKO V SREDNEM NADO PEREBRATX ZNACHENIJ~$U$  V TESTE 
SOBIRATELYA KUPONOV (ALGORITM~C) DLYA POLUCHENIYA $n$~POLNYH NABOROV, ESLI 
POSLEDOVATELXNOSTX SLUCHAJNAYA?  oPREDELITE TAKZHE STANDARTNOE OTKLONENIE 
|TOJ VELICHINY. (\emph{uKAZANIE:} SM.\  FORMULU~1.2.9-28.)

% ex. 9
\ex[M21] oBOBSHCHITE TEST SOBIRATELYA KUPONOV TAK, CHTOBY DALXNEJSHIJ POISK 
PREKRASHCHALSYA POSLE TOGO, KAK NAJDENO $w$~RAZLICHNYH ZNACHENIJ, GDE~$w\le 
d$---POLOZHITELXNOE CELOE CHISLO. kAKIE VEROYATNOSTI NADO ISPOLXZOVATX V |TOM 
SLUCHAE VMESTO~(6).

\ex[M23] vYPOLNITE UPR.~8 DLYA OBOBSHCHENNOGO TESTA SOBIRATELYA KUPONOV, 

\ex[00] v PREDSTAVLENII~(9) DLYA KONKRETNOJ POSLEDOVATELXNOSTI OTMECHENY 
VOZRASTAYUSHCHIE OTREZKI; KAKOVY UBYVAYUSHCHIE OTREZKI DLYA TOJ ZHE POSLEDOVATELXNOSTI?

\ex[22] zADANO $n$~RAZLICHNYH CHISEL~$U_0$, $U_1$,~\dots, $U_{n-1}$. 
zAPISHITE ALGORITM, KOTORYJ OPREDELYAET DLINY VSEH OTREZKOV VOZRASTANIYA V 
|TOJ POSLEDOVATELXNOSTI. v REZULXTATE RABOTY ALGORITMA V~$|COUNT|[r]$ 
PRI~$1\le r \le 5$  DOLZHNO NAHODITXSYA CHISLO OTREZKOV DLINY~$r$, A 
V~$|COUNT|[6]$---CHISLO OTREZKOV DLINY~$6$ ILI BOLEE.

\ex[M23] pOKAZHITE, CHTO~(16) ESTX CHISLO PERESTANOVOK TIPA~(15) 
IZ~$p+q+1$~RAZLICHNYH |LEMENTOV.

\ex[M15] eSLI MY BUDEM "VYBRASYVATX" |LEMENT, NEPOSREDSTVENNO SLEDUYUSHCHIJ ZA 
OTREZKOM MONOTONNOSTI, TAK CHTO V SLUCHAE~$X_j>X_{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 <n$, A NE 
ODNO IZ KAZHDYH $t$~ZNACHENIJ. oDNAKO PRI PROVERKE RAVNOMERNOSTI 
ZNACHENIJ~$V_j^t$ POLUCHILISX KRAJNE VYSOKIE ZNACHENIYA STATISTIKI~$V$, PRICHEM 
PRI UVELICHENII~$t$ ONI STANOVILISX ESHCHE BOLXSHE. kAK |TO MOGLO POLUCHITXSYA?

\ex[m25]{(a)~zADANY PROIZVOLXNYE CHISLA~$X_1$,~\dots, $X_n$, $Y_1$,~\dots, 
$Y_n$, PRICHEM
$$
\bar x = {1\over n} \sum_{1\le k \le n} X_k, \qquad
\bar y = {1\over n} \sum_{1\le k \le n} Y_k.
$$
oBOZNACHIM~$X'_k=X_k-\bar x$, $Y'_k=Y_k-\bar y$. pOKAZHITE, CHTO KO|FFICIENT 
KORRELYACII~$C$, VYCHISLENNYJ PO FORMULE~(24), RAVEN
$$
\sum_{1\le k \le n} X'_k Y'_k \bigg/ \sqrt{\sum_{1\le k \le n} {X'_k}^2} 
\sqrt{\sum_{1\le k \le n}{Y'_k}^2}.
$$
 \hiddenpar
(b)~pUSTX~$C=N/D$, GDE~$N$ I~$D$---CHISLITELX I ZNAMENATELX TOLXKO CHTO 
PRIVEDENNOGO VYRAZHENIYA. pOKAZHITE, CHTO~$N^2\le D^2$, T.~E.~$-1\le C \le +1$; 
POLUCHITE FORMULU DLYA RAZNOSTI~$D^2-N^2$. (\emph{uKAZANIE:} SM.~UPR.~1.2.3-30.)
 \hiddenpar
(c)~pOKAZHITE, CHTO PRI~$C=\pm1$ DLYA~$1\le k \le n$ MOZHNO NAJTI TAKIE 
POSTOYANNYE~$a$, $b$, $m$ NE VSE RAVNYE NULYU, CHTO~$a X_k+b Y_k=m$.
}

\ex[m20] (a)~pOKAZHITE, CHTO PRI~$n=2$ KO|FFICIENT 
POSLEDOVATELXNOJ KORRELYACII~(23) \emph{VSEGDA} RAVEN~$-1$ (ESLI 
ZNAMENATELX NE RAVEN NULYU). (b)~pOKAZHITE, CHTO PRI~$n=3$ KO|FFICIENT 
POSLEDOVATELXNOJ KORRELYACII VSEGDA RAVEN~$-{1\over2}$. (c)~pOKAZHITE, CHTO 
ZNAMENATELX V~(23) RAVEN NULYU TOGDA I TOLXKO
TOGDA, KOGDA~$U_0=U_1=\cdots=U_{n-1}$.

\ex[m40] chEMU RAVNY SREDNEE ZNACHENIE I STANDARTNOE OTKLONENIE 
KO|FFICIENTA POSLEDOVATELXNOJ KORRELYACII~(23), KOGDA~$n=4$, A 
ZNACHENIYA~$U$ NEZAVISIMY I RASPREDELENY RAVNOMERNO MEZHDU NULEM I EDINICEJ?

\ex[m50] oPREDELITE RASPREDELENIE KO|FFICIENTA POSLEDOVATELXNOJ 
KORRELYACII~(23) PRI PROIZVOLXNOM~$n$, PREDPOLAGAYA, CHTO SLUCHAJNYE 
VELICHINY~$U_j$ NEZAVISIMY I RASPREDELENY RAVNOMERNO MEZHDU NULEM I EDINICEJ.

\ex[19] kAKOE ZNACHENIE~$f$ DAST ALGORITM~P DLYA 
PERESTANOVKI~$(1, 2, 9, 8, 5, 3, 6, 7, 0, 4)$?

\ex[18] dLYA KAKOJ PERESTANOVKI NABORA CELYH 
CHISEL~$\set{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}$ ALGORITM~P DAST ZNACHENIE~$f=1024$?

\subsubchap{*tEORETICHESKIE TESTY} %3.3.3
hOTYA LYUBOJ DATCHIK SLUCHAJNYH CHISEL MOZHNO PROVERITX S POMOSHCHXYU METODOV, 
OPISANNYH V PREDYDUSHCHEM PUNKTE, GORAZDO LUCHSHE IMETX "\dfn{APRIORNYE} TESTY",
T.~E.\ TEORETICHESKIE REZULXTATY, KOTORYE POZVOLYAYUT SKAZATX ZARANEE, 
KAKIM BUDET ISHOD ISPYTANIJ DATCHIKA. tAKOGO RODA TEORETICHESKIE REZULXTATY 
POZVOLYAYUT ZNACHITELXNO GLUBZHE PONYATX SPOSOBY POROZHDENIYA SLUCHAJNYH CHISEL, 
CHEM |MPIRICHESKIE DANNYE, POLUCHENNYE METODOM "PROB I OSHIBOK". zDESX BUDUT 
BOLEE DETALXNO IZUCHENY LINEJNYE KONGRU|NTNYE POSLEDOVATELXNOSTI;
%% 92
ZNAYA, KAKIMI DOLZHNY BYTX SLUCHAJNYE CHISLA ESHCHE
DO IH VYRABOTKI, MY IMEEM BOLXSHE NADEZHDY PRAVILXNO VYBRATX ZNACHENIYA~$a$, 
$m$ I~$c$.

pOSTROITX TEORIYU LINEJNOGO KONGRU|NTNOGO METODA OCHENX TRUDNO, HOTYA 
OPREDELENNYH USPEHOV V |TOJ OBLASTI DOSTICHX UDALOSX. pOLUCHENNYE DO SIH 
POR REZULXTATY OTNOSYATSYA GLAVNYM OBRAZOM K \emph{STATISTICHESKOMU ANALIZU 
POSLEDOVATELXNOSTI NA POLNOM PERIODE.} v TAKOJ POSTANOVKE ZADACHA IMEET 
SMYSL NE DLYA VSEH TESTOV; NAPRIMER, PRI PROVERKE RAVNOMERNOSTI 
RASPREDELENIYA NA VSEM PERIODE BUDUT POLUCHATXSYA SLISHKOM HOROSHIE 
REZULXTATY. oDNAKO PROVERKU SERIJ, INTERVALOV, PERESTANOVOK I~T.~D.\ 
MOZHNO USPESHNO PROVODITX I NA POLNOM PERIODE.

dLYA NACHALA DOKAZHEM PROSTOE \emph{APRIORNOE} UTVERZHDENIE, KASAYUSHCHEESYA 
NAIMENEE SLOZHNOGO VARIANTA PROVERKI PERESTANOVOK sUTX NASHEJ PERVOJ TEOREMY 
SOSTOIT V TOM, CHTO ESLI DATCHIK OBLADAET VYSOKOJ MOSHCHNOSTXYU, TO PRIMERNO V 
POLOVINE SLUCHAEV BUDET VYPOLNYATXSYA NERAVENSTVO~$X_{n+1}<X_n$.

\proclaim tEOREMA~P. pUSTX~$X_0$, $a$, $c$ I~$m$ OPREDELYAYUT LINEJNUYU 
KONGRU|NTNUYU POSLEDOVATELXNOSTX S MAKSIMALXNYM PERIODOM; PUSTX~$b=a-1$, 
a~$d$---NAIBOLXSHIJ OBSHCHIJ DELITELX~$m$ I~$b$. tOGDA VEROYATNOSTX TOGO, 
CHTO~$X_{n+1}<X_n$, RAVNA~${1\over2}+r$, GDE
$$
r=(2(c \bmod d)-d)/2m;
$$
SLEDOVATELXNO, $\abs{r}<d/2m$.

tEHNIKA, KOTORAYA ISPOLXZUETSYA PRI DOKAZATELXSTVE |TOJ TEOREMY, INTERESNA 
I SAMA PO SEBE. nACHNEM S TOGO, CHTO VVEDEM
$$
s(x)=(ax+c)\bmod m.
\eqno(1)
$$
tOGDA~$X_{n+1}=s(X_n)$ I TREBUETSYA PODSCHITATX CHISLO TAKIH CELYH~$x$,
CHTO~$0\le x < m$ I~$s(x)<x$ (TAK KAK KAZHDOE TAKOE CHISLO VSTRECHAETSYA, 
GDE-TO V PREDELAH PERIODA). mY HOTIM POKAZATX, CHTO |TO CHISLO RAVNO
$$
{1\over2}(m+2(c \bmod d)-d).
\eqno(2)
$$
pRI~$a=1$ TEOREMA SPRAVEDLIVA: LEGKO VIDETX, CHTO V |TOM SLUCHAE $s(x)<x$ 
TOLXKO PRI~$x+c\ge m$, A |TO IMEET MESTO $c$~RAZ.

\proclaim lEMMA~A. pUSTX~$\alpha$ u~$\beta$---DEJSTVITELXNYE CHISLA, 
A~$n$---CELOE CHISLO. v |TOM SLUCHAE 
$$
\eqalignno{
 &\alpha < n \le \beta \rem{TOGDA I TOLXKO TOGDA, KOGDA~$\floor{\alpha}<n\le\floor{\beta}$;} & (3)\cr
 &\alpha\le n < \beta  \rem{TOGDA I TOLXKO TOGDA, KOGDA~$\ceil{\alpha}\le n <\ceil{\beta}$.} & (4)\cr
}
$$

eTI FORMULY SLEDUYUT NEPOSREDSTVENNO IZ OPREDELENIJ "POTOLKA" I "POLA"; SM.~UPR.~1.2.4-3.\endmark
%% 93

dLYA LYUBOGO CELOGO~$x$,  $0\le x < m$,  OPREDELIM~$k(x)=\floor{(ax+c)/m}$; 
TOGDA~$s(x)=ax+c-k(x)m$ I~$k(x)\le(ax+c)/m$, OTKUDA SLEDUET, CHTO 
NERAVENSTVO~$s(x)<x$ |KVIVALENTNO
$$
(k(x)m-c)/a \le x < (k(x)m-c)/b.
\eqno(5)
$$
dALEE, |TI NERAVENSTVA EDINSTVENNYM OBRAZOM OPREDELYAYUT~$k(x)$, POSKOLXKU 
IZ NIH VYTEKAYUT NERAVENSTVA
$$
{ax+c\over m}\le k(x) < {bx+c\over m} < {ax+c\over m}+1.
$$

v SOOTVETSTVII S LEMMOJ~A MOZHNO UTVERZHDATX, CHTO~$s(x)<x$ I~$0\le x <m$ 
TOGDA I TOLXKO TOGDA, KOGDA VYPOLNENO ODNO IZ VZAIMOISKLYUCHAYUSHCHIH USLOVIJ:
$$
\eqalignno{
 \hbox{(i)~} & \ceil{(km-c)/a}\le x < \ceil{(km-c)/b} \rem{DLYA KAKOGO-LIBO~$k$, $0<k<a$;} & (6) \cr
\hbox{(ii)~} & \ceil{m-c/a} \le x < m. \cr
}
$$

chISLO TAKIH CELYH~$x$ RAVNO
$$
m+\sum_{0<k\le b} \ceil{(km-c)/b}-\sum_{0<k\le a}\ceil{(km-c)/a}.
\eqno(7)
$$
tEOREMA BUDET DOKAZANA, ESLI MY POKAZHEM, CHTO~(7) RAVNO~(2). sUMMY V 
VYRAZHENII~(7) MOZHNO VYCHISLITX TAK, KAK OPISANO V UPR.~1.2.4-37; MY 
VOSPOLXZUEMSYA DRUGIM METODOM, CHTOBY PRODEMONSTRIROVATX ESHCHE ODIN SPOSOB 
RESHENIYA ZADACH TAKOGO TIPA. 

oPREDELIM PREZHDE VSEGO SLEDUYUSHCHIE FUNKCII:
$$
\eqalignno{
 \delta(z)&=\floor{z}+1-\ceil{z}=\cases{
   1, & ESLI $z$ CELOE;    \cr
   0, & ESLI $z$ NE CELOE; \cr
 } & (8) \cr
((z))&=z-\floor{z}-{1\over2}+{1\over2}\delta(z)=z-\ceil{z}+{1\over2}-{1\over2}\delta(z). & (9)\cr
}
$$
pOSLEDNYAYA PREDSTAVLYAET SOBOJ "PILOOBRAZNUYU FUNKCIYU", ISPOLXZUEMUYU V 
TEORII RYADOV fURXE; EE GRAFIK POKAZAN NA RIS.~7. pREIMUSHCHESTVA RABOTY S 
FUNKCIEJ~$((z))$ PO SRAVNENIYU S~$\floor{z}$ ILI~$\ceil{z}$ OPREDELYAYUTSYA 
TEM, CHTO ONA OBLADAET RYADOM POLEZNYH
\picture{rIS.~7. pILOOBRAZNAYA FUNKCIYA~$((z))$.}
%% 94                      	
SVOJSTV:
$$
\eqalignno{
\dlp-z\drp &= -\dlp z \drp; & (10) \cr
\dlp z+n \drp &= \dlp z \drp z, \rem{ESLI $n$ CELOE;} & (11) \cr
\dlp z \drp + \dlp z+{1\over n}\drp+\cdots+\dlp z+{n-1\over n}\drp&=\dlp nz \drp,
  \rem{ESLI~$n$---POLOZHITELXNOE CELOE CHISLO} & (12)\cr
}
$$
(SM.~UPR.~2). mENYAYA OBOZNACHENIYA, MOZHNO PREOBRAZOVATX~(7) SLEDUYUSHCHIM OBRAZOM:
$$
{1\over 2}\left(m-1+\sum_{0<k\le a}\delta\left({km-c\over a}\right)
-\sum_{0<k\le b}\delta\left({km-c\over b}\right)\right)
+\sum_{0<k\le a}\dlp{km-c\over a}\drp-\sum_{0<k\le b}\dlp{km-c\over b}\drp.
\eqno(13)
$$
nA VID |TA FORMULA HUZHE TOJ, S KOTOROJ MY NACHINALI, NO V DEJSTVITELXNOSTI 
VSE VHODYASHCHIE V NEE SUMMY LEGKO VYCHISLYAYUTSYA. tAK KAK~$m$ I~$a$ VZAIMNO 
PROSTY, MY ZNAEM, CHTO $(km-c)\bmod a$ PRINIMAET V OPREDELENNOM PORYADKE 
KAZHDOE IZ ZNACHENIJ~$0$, $1$,~\dots, $a-1$ PRI~$0<k\le a$, TAK CHTO
$$
\sum_{0<k\le a}\delta\left({km-c\over a}\right)=1,\qquad
\sum_{0<k\le a}\dlp{km-c\over a}\drp=0.
$$
(sPRAVEDLIVOSTX VTOROJ FORMULY VYTEKAET IZ RAVENSTV~(10) I~(11).) dALEE, 
ESLI CHISLA~$m$ I~$b$---NE VZAIMNO PROSTYE, A~$c$ I~$b$---VZAIMNO PROSTYE, 
TO~$(km-c)/b$ NE MOZHET BYTX CELYM, PO|TOMU VTORAYA SUMMA V~(13) ISCHEZAET. 
nAKONEC, IMEYUT MESTO RAVENSTVA
$$
\eqalign{
 \dlp {km-c\over b}\drp &=\dlp{km-d\floor{c/d}-c\bmod d \over b}\drp=\cr
                        &=\dlp{km/d-\floor{c/d}\over b/d}\drp-{c\bmod d \over b}+{1\over 2}\delta\left({km/d-\floor{c/d}\over b/d}\right),\cr
}
$$
TAK KAK~$0\le (c\bmod d)/b<1/(b/d)$. sUMMA
$$
\sum_{0<k\le b} \dlp{km-c\over b}\drp
$$
RAVNA, SLEDOVATELXNO, ${1\over 2}d-c\bmod d$, TAK KAK~$m/d$ I~$b/d$ 
VZAIMNO PROSTY. tEOREMA~P DOKAZANA.
\proofend

dOKAZATELXSTVO TEOREMY~P DEMONSTRIRUET TRUDNOSTX ZADACHI \emph{APRIORNOJ} 
PROVERKI SLUCHAJNYH CHISEL, ODNAKO ONO V TO ZHE VREMYA POKAZYVAET I EE 
VYPOLNIMOSTX. dALEE, IZ |TOJ TEOREMY SLEDUET CHTO PRAKTICHESKI PRI LYUBOM 
VYBORE~$a$ I~$c$ NERAVENSTVO~$X_{n+1}<X_n$ BUDET VYPOLNYATXSYA S NUZHNOJ 
CHASTOTOJ, VO VSYAKOM SLUCHAE NA VSEM PERIODE, KROME TEH SLUCHAEV, KOGDA~$d$ 
VELIKO. bOLXSHIE ZNACHENIYA~$d$
%% 95
SOOTVETSTVUYUT MALOJ MOSHCHNOSTI, CHTO, KAK MY ZNAEM, NEZHELATELXNO.

sLEDUYUSHCHAYA TEOREMA DAET BOLEE VAZHNYJ KRITERIJ DLYA VYBORA~$a$ I~$c$; V NEJ 
RASSMATRIVAETSYA \emph{KO|FFICIENT POSLEDOVATELXNOJ KORRELYACII} NA POLNOM 
PERIODE. eTOT KO|FFICIENT BYL OPREDELEN V P.~3.3.2 (SM.\ FORMULU~(23)):
$$
C=\left(m\sum_{0\le x < m} x s(x)-\left(\sum_{0\le x < m} x\right)^2\right)
\bigg/\left(m\sum_{0\le x<m}x^2-\left(\sum_{0\le x<m} x\right)^2\right).
\eqno(14)
$$
pUSTX~$x'$---TAKOJ |LEMENT, CHTO~$s'(x)=0$. tOGDA
$$
s(x)=m\dlp{ax+c\over m}\drp+{m\over 2},
\rem{ESLI~$x\ne x'$.}
\eqno(15)
$$
dLYA UPROSHCHENIYA ZAPISI FORMUL VOSPOLXZUEMSYA ODNOJ VAZHNOJ FUNKCIEJ, KOTORAYA 
CHASTO VOZNIKAET VO MNOGIH MATEMATICHESKIH ZADACHAH:
$$
\sigma(h, k, c)=12\sum_{0\le j < k}\dlp{j\over k}\drp\dlp{hj+c\over k}\drp;
\eqno(16)
$$
ONA NAZYVAETSYA \dfn{OBOBSHCHENNOJ SUMMOJ dEDEKINDA.}

tAK KAK
$$
\sum_{0\le x<m} x={m(m-1)\over 2} \quad\hbox{I}\quad
\sum_{0\le x<m} x^2={m(m-1)(2m-1)\over 6},
$$
TO FORMULU~(14) DOVOLXNO PROSTO PREOBRAZOVATX K VIDU
$$
C={m\sigma(a, m, c)-3+6(m-x'-c)\over m^2-1}.
\eqno(17)
$$
pOSKOLXKU~$m$ OBYCHNO OCHENX VELIKO, MOZHNO OTBROSITX CHLENY PORYADKA~$1/m$ I 
ZAPISATX PRIBLIZHENNOE RAVENSTVO
$$
C\approx \sigma(a, m, c)/m
\eqno(18)
$$
S OSHIBKOJ, MENXSHEJ~$6/m$ PO ABSOLYUTNOJ VELICHINE.

pROVERKA POSLEDOVATELXNOJ KORRELYACII SVODITSYA PRI |TOM K OPREDELENIYU SUMMY 
dEDEKINDA~$\sigma(a, m, c)$. 
vYCHISLENIE~$\sigma(a, m, c)$ NEPOSREDSTVENNO PO FORMULE~(16) EDVA LI PROSHCHE 
PRYAMOGO VYCHISLENIYA KO|FFICIENTA KORRELYACII, NO, K SCHASTXYU, SUSHCHESTVUYUT 
PROSTYE METODY BYSTROGO POLUCHENIYA ZNACHENIJ SUMM dEDEKINDA.

\proclaim lEMMA~B. ("zAKON VZAIMNOSTI" DLYA SUMM dEDEKINDA.) eSLI~$0\le c < h$, 
$0\le c < k$ I CHISLA~$h$ I~$k$ VZAIMNO PROSTYE, TO
$$
\sigma(h, k, c)+\sigma(k, h, c)={h\over k}+{k\over h}+{1\over 
hk}+{6c^2\over hk}-3.
\eqno(19)
$$
%% 96
\proof mY PREDOSTAVLYAEM CHITATELYU POKAZATX, CHTO V |TIH PREDPOLOZHENIYAH SPRAVEDLIVO
$$
\sigma(h, k, c)+\sigma(k, h, c)=\sigma(h, k, 0)+\sigma(k, h, 0)+6c^2/hk
\eqno(20)
$$
(SM.~UPR.~6). tEPERX DOSTATOCHNO RASSMOTRETX TOLXKO SLUCHAJ~$c=0$.

pRIVEDEM PRINADLEZHASHCHEE l.~kARLICU DOKAZATELXSTVO, OSNOVANNOE NA 
ISPOLXZOVANII KOMPLEKSNYH KORNEJ IZ EDINICY. sUSHCHESTVUET BOLEE PROSTOE 
DOKAZATELXSTVO, TREBUYUSHCHEE TOLXKO |LEMENTARNYH MANIPULYACIJ S SUMMAMI 
(SM.~UPR.~7); ODNAKO PRIVEDENNYJ NIZHE SPOSOB BOLEE POUCHITELEN, TAK KAK V 
NEM ISPOLXZUETSYA TEHNIKA, KOTORAYA MOZHET BYTX POLEZNA I V DRUGIH ZADACHAH TAKOGO TIPA.

oPREDELIM POLINOMY~$f(x)$ I~$g(x)$ SLEDUYUSHCHIM OBRAZOM:
$$
\eqalign{
f(x)&=1+x+\cdots+x^{k-1}=(x^k-1)/(x-1),\cr
g(x)&=x+2x^2+\cdots+(k-1)x^{k-1}=xf'(x)=\cr
&=kx^k/(x-1)-x(x^k-1)/(x-1)^2.\cr
}
\eqno(21)
$$
eSLI~$\omega=e^{2\pi i/k}$---KOMPLEKSNYJ KORENX STEPENI~$k$ IZ EDINICY TO, 
SOGLASNO~(1.2.9-13),
$$
{1\over k}\sum_{0<j\le k} \omega^{jr}g(\omega^jx)=rx^r
\rem{PRI $0\le r < k$.} 
\eqno (52)
$$
pOLOZHIM~$x=1$; TOGDA~$g(\omega^j x)=k/(\omega^j-1)$ PRI~$j\ne k$ 
I~$k(k-1)/2$ PRI~$j=k$. oTSYUDA SLEDUET, CHTO
$$
r \bmod k \sum_{0<j<k} {\omega^{-jr}\over \omega^j-1}+{1\over2}(k-1),
\rem{ESLI~$r$---CELOE.}
\eqno (23)
$$
(tAK KAK, SOGLASNO~(22), PRAVAYA CHASTX RAVNA~$r$ PRI~$0 \le r < k$ I PRI 
DOBAVLENII K~$r$ KRATNOGO~$k$ ONA NE IZMENYAETSYA.) sLEDOVATELXNO,
$$
\left(\left({r\over k}\right)\right)=
{1\over k}\sum_{0<j<k}{\omega^{-jr}\over \omega^j-1}-{1\over 2k}+{1\over2} 
\delta\left({r\over k}\right).
\eqno(24)
$$
eTA VAZHNAYA FORMULA, KOTORAYA SPRAVEDLIVA DLYA LYUBYH CELYH~$r$, POZVOLYAET 
SVESTI~$((r/k))$ K SUMME, VKLYUCHAYUSHCHEJ KORNI STEPENI~$k$ IZ EDINICY; PRI 
|TOM VOZNIKAET CELYJ RYAD NOVYH VOZMOZHNOSTEJ.
v CHASTNOSTI, IMEET MESTO SLEDUYUSHCHAYA FORMULA:
$$
\sigma(h, k, 0)+{3(k-1)\over k^2}=
{12\over k^2}\sum_{0<r<k}\sum_{0<i<k}\sum_{0<j<k}
{\omega^{-ir}\over\omega^i-1}{\omega^{-jh_r}\over \omega^j-1}.
\eqno(25)
$$
pRAVUYU CHASTX |TOJ FORMULY MOZHNO UPROSTITX, PROVEDYA SUMMIROVANIE PO~$r$; 
ESLI~$s\bmod k \ne 0$, TO~$\sum_{0\le r < k} \omega^{rs}=f(\omega^s)=0$. 
fORMULA~(25) SVODITSYA K
$$
\sigma(h, k, 0)+{3(k-1)\over k}=
{12\over k}\sum_{0<j<k}{1\over (\omega^{-j^h}-1)(\omega^j-1)}.
\eqno(26)
$$
%% 97
aNALOGICHNAYA FORMULA S ZAMENOJ~$\omega$ NA~$\zeta=e^{2\pi i/h}$ SPRAVEDLIVA 
DLYA~$\sigma(k, h, 0)$.

vOPROS O TOM, CHTO DELATX DALXSHE S SUMMOJ V~(26), NE OCHEVIDEN; ODNAKO 
SUSHCHESTVUET |LEGANTNYJ SPOSOB DALXNEJSHIH PREOBRAZOVANIJ, OSNOVANNYJ NA 
TOM FAKTE, CHTO KAZHDYJ CHLEN SUMMY YAVLYAETSYA FUNKCIEJ~$\omega^j$, $0<j<k$, I 
PO SUSHCHESTVU SUMMIRUYUTSYA VSE KORNI STEPENI~$k$ IZ EDINICY, KROME~$1$. 
zAMETIM, CHTO DLYA LYUBYH NESOVPADAYUSHCHIH KOMPLEKSNYH CHISEL~$x_1$, $x_2$,~\dots,
$x_n$ SPRAVEDLIVO SLEDUYUSHCHEE RAVENSTVO:
$$
\sum_{1<j\le n} {1\over 
(x_j-x_1)\ldots(x_j-x_{j-1})(x-x_j)(x_j-x_{j+1})\ldots (x_j-x_n)}={1\over (x-x_1)\ldots(x-x_n)},
\eqno(27)
$$
KOTOROE SLEDUET IZ OBYCHNOGO RAZLOZHENIYA PRAVOJ CHASTI NA |LEMENTARNYE 
DROBI. dALEE, ESLI~$q(x)=(x-y_1)(x-y_2)\ldots(x-y_m)$, TO
$$
q'(y_j)=(y_j-y_1)\ldots(y_j-y_{j-1})(y_j-y_{j+1})\ldots(y_j-y_m).
\eqno(28)
$$
eTO RAVENSTVO CHASTO ISPOLXZUETSYA DLYA UPROSHCHENIYA VYRAZHENIJ TAKOGO TIPA, KAK 
LEVAYA CHASTX~(27). eSLI~$h$ I~$k$ VZAIMNO PROSTY, TO VSE ZNACHENIYA~$\omega$, 
$\omega^2$,~\dots, $\omega^{k-1}$, $\zeta$, $\zeta^2$,~\dots, 
$\zeta^{h-1}$ NE SOVPADAYUT DRUG S DRUGOM. sLEDOVATELXNO, MOZHNO 
RASSMATRIVATX~(27) KAK CHASTNYJ SLUCHAJ 
POLINOMA~$(x-\omega)\ldots(x-\omega^{k-1})(x-\zeta)\ldots(x-\zeta^{h-1})=(x^k-1)(x^h-1)/(x-1)^2$, 
OTKUDA SLEDUET RAVENSTVO
$$
{1\over h}\sum_{0<j<h}{\zeta^j(\zeta^j-1)^2\over (\zeta^{ik}-1)(x-\zeta^j)}
+{1\over k}\sum_{0<j<k}{\omega^j(\omega^j-1)^2\over 
(\omega^{jh}-1)(x-\omega^j)}={(x-1)^2\over (x^h-1)(x^k-1)}.
\eqno(29)
$$
iZ |TOGO RAVENSTVA VYTEKAET MNOGO INTERESNYH SLEDSTVIJ, I ONO PRIVODIT K 
CELOMU RYADU SOOTNOSHENIJ VZAIMNOSTI DLYA SUMM, TAKIH, KAK~(26). nAPRIMER, 
ESLI PRODIFFERENCIROVATX~(29) DVAZHDY PO~$x$ I POLOZHITX~$x=1$, TO POLUCHITSYA
$$
{2\over h}\sum_{0<j<h}{\zeta^j(\zeta^j-1)^2\over (\zeta^{jk}-1)(1-\zeta^j)^3}
+{2\over k}\sum_{0<j<k}{\omega^j(\omega^j-1)^2\over (\omega^{jk}-1)(1-\omega^j)^3}=
{1\over 6}\left({h\over k}+{k\over h}+{1\over hk}\right)+{1\over2}-{1\over 2h} -{1\over 2k}.
$$
zAMENYAYA V |TIH SUMMAH~$j$ NA~$h-j$ I~$k-j$, POLUCHIM [SR.~(26)]
$$
{1\over6}\left(\sigma(k, h, 0)+{3(h-1)\over h}\right)
+{1\over6}\left(\sigma(h, k, 0)+{3(k-1)\over k}\right)
={1\over 6}\left({h\over k}+{k\over h}+{1\over hk}\right)+{1\over2}-{1\over 2h}-{1\over 2k},
$$
CHTO |KVIVALENTNO TREBUEMOMU REZULXTATU. 
\proofend
%%  98

\proclaim lEMMA~C. eSLI CHISLA~$h$ I~$k$ VZAIMNO PROSTYE I~$0<c<k$, TO
$$
\sigma(h, k, c)=\sigma(h, k, c \bmod h)+{6r\over k}(c+c\bmod h-k)+d,
\eqno(30)
$$
GDE~$r=\floor{c/h}$, $d=0$ PRI~$c\bmod h \ne 0$ I~$d=3$ PRI~$c \bmod h=0$. 

\proof pRI LYUBOM~$c$ IMEEM
$$
\eqalignno{
\sigma(h, k, c+h)&=12\sum_{0\le j <k}\dlp{j\over k}\drp\dlp{hj+c+h\over k}\drp=\cr
&=12\sum_{0\le j <k} \dlp{j-1\over k}\drp \dlp{hj+c\over k}\drp=\cr
&=\sigma(h, k, c)+6\dlp{h+c\over k}\drp+6\dlp{c\over k}\drp, & (31)\cr
}
$$
TAK KAK, SOGLASNO~(9),
$$
\dlp{j-1\over k}\drp = \dlp{j\over k}\drp -{1\over k}+{1\over 2}\sigma 
\left({j+1\over k}\right)+{1\over 2}\sigma\left({j\over k}\right).
\eqno(32)
$$
pUSTX TEPERX~$c_0=c\bmod h$, TAK CHTO~$0<c=c_0+rh<k$. tOGDA
$$
\eqalign{
 \sigma(h, k, c)&=\sigma(h, k, c_0)+12\sum_{0\le j <r}\dlp{c_0+hj\over k}\drp +6\dlp{c\over k}\drp -6\dlp{c_0\over k}\drp=\cr
                &=\sigma(h, k, c_0)+12\sum_{0\le j <r}\left({c_0+hj\over k}-{1\over 2}\right) +6\left({c\over k}-{1\over 2}\right)-6\left({c_0\over k}-{1\over 2}\right)+d.\cr
}
$$
pROSTOE SUMMIROVANIE ZAVERSHAET DOKAZATELXSTVO.
\proofend

lEMMY~B I~C POZVOLYAYUT SFORMULIROVATX SLEDUYUSHCHUYU |FFEKTIVNUYU PROCEDURU 
VYCHISLENIYA~$\sigma(h, k, c)$ V SLUCHAE, KOGDA~$h$ I~$k$ VZAIMNO PROSTY.

{\sl shAG~1.\/}~dOBAVLYATX (ILI VYCHITATX) KRATNYE~$k$ K (IZ)~$h$ I~$c$ (ESLI 
|TO NEOBHODIMO), S TEM CHTOBY PRIVESTI IH K 
INTERVALAM~$-{k\over 2}<h\le {k\over 2}$, $-{k\over 2}<c\le {k\over 2}$
(ILI K INTERVALAM~$0<h \le k$,  $0\le c < k$). tAKAYA OPERACIYA ZAKONNA, 
POTOMU CHTO PO OPREDELENIYU
$$
\sigma(h\pm nk, k, c)=\sigma(h, k, c)=\sigma(h, k, c\pm nk).
\eqno(33)
$$

{\sl shAG~2.\/}~eSLI~$h$ ILI~$c$ OTRICATELXNY, SDELATX IH POLOZHITELXNYMI, 
ISPOLXZUYA RAVENSTVA
$$
\eqalign{
\sigma(-h, k, c)&=-\sigma(h, k, c),\cr
\sigma(h, k, -c)&=\sigma(h, k, c).\cr
}
\eqno(34)
$$

{\sl shAG~3.\/} eSLI~$k=1$ ILI~$k=2$, TO~$\sigma(h, k, c)=0$ 
(TAK KAK~$\dlp j/1 \drp=\dlp j/2 \drp =0$). 

%% 99
{\sl shAG~4.\/}~eSLI~$c>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)}<a$, PO|TOMU
\EQ[40]{
 C\approx {\sigma(a, m, c)\over m}\approx {1\over a}\left(1-6{c\over m}+6\left({c\over m}\right)^2\right).
}
pRI |TOM MY PRENEBREGLI CHLENAMI
\EQ{
 {3\over m}\left(1-2{c_0\over a}+{a-x'-c\over m}\right)+{1\over m}\sigma(m, a, c_0)+O\left({1\over m^2}\right),
}
TAK CHTO MOZHNO SKAZATX, CHTO POGRESHNOSTX VYRAZHENIYA~\eqref[40] NE 
PREVYSHAET~$a/m$. gLAVNYJ VKLAD V OSHIBKU DAET CHLEN~$\sigma(m, a, c_0)/m$. 
pOLUCHENNYE REZULXTATY MOZHNO SUMMIROVATX SLEDUYUSHCHIM OBRAZOM.

\proclaim tEOREMA~S. kO|FFICIENT POSLEDOVATELXNOJ KORRELYACII DLYA LINEJNOJ 
KONGRU|NTNOJ POSLEDOVATELXNOSTI S MAKSIMALXNYM PERIODOM OPREDELYAETSYA 
PRIBLIZHENNYM VYRAZHENIEM~\eqref[40] S OSHIBKOJ,
%% 101
\bye
