\input style
\chapnotrue\chapno=3\subchno=3\subsubchno=1
ИТЬ \dfn{ЭМПИРИЧЕСКУЮ ФУНКЦИЮ РАСПРЕДЕЛЕНИЯ~$F_n(x)$:}
$$
F_n(x)={\hbox{ЧИСЛО ТАКИХ $X_1$, $X_2$,~\dots, $X_n$, КОТОРЫЕ~$\le x$} \over n}.
\eqno(10)
$$
эА РИС.~4 ПОКАЗАНЫ ТРИ ЭМПИРИЧЕСКИЕ ФУНКЦИИ РАСПРЕДЕЛЕНИЯ (ВЕРТИКАЛЬНЫЕ 
ЛИНИИ, СТРОГО ГОВОРЯ, НЕ ЯВЛЯЮТСЯ ЧАСТЬЮ ГРАФИКА~$F_n(x)$). ЄАМ ЖЕ 
ИЗОБРАЖЕНЫ И ИСТИННЫЕ ФУНКЦИИ РАСПРЕДЕЛЕНИЯ~$F(x)$. яРИ УВЕЛИЧЕНИИ~$n$ 
ФУНКЦИИ~$F_n(x)$ ДОЛЖНЫ ВСЕ БОЛЕЕ ТОЧНО АППРОКСИМИРОВАТЬ~$F(x)$.

ъРИТЕРИЙ ъОЛМОГОРОВА---ёМИРНОВА (ъё-КРИТЕРИЙ) МОЖНО ИСПОЛЬЗОВАТЬ В ТЕХ 
СЛУЧАЯХ, КОГДА ФУНКЦИЯ~$F(x)$ НЕ ИМЕЕТ СКАЧКОВ. юН ОСНОВАН НА 
\emph{РАЗНОСТИ МЕЖДУ~$F(x)$ И~$F_n(x)$.} яЛОХОЙ ДАТЧИК СЛУЧАЙНЫХ ЧИСЕЛ 
БУДЕТ ДАВАТЬ ЭМПИРИЧЕСКИЕ ФУНКЦИИ РАСПРЕДЕЛЕНИЯ, ПЛОХО 
АППРОКСИМИРУЮЩИЕ~$F(x)$. эА РИС.~4,~b ПРИВЕДЕН ПРИМЕР, КОГДА 
ЗНАЧЕНИЯ~$X_i$ СЛИШКОМ ВЕЛИКИ, ТАК ЧТО КРИВАЯ ЭМПИРИЧЕСКОЙ ФУНКЦИИ 
РАСПРЕДЕЛЕНИЯ ПРОХОДИТ СЛИШКОМ НИЗКО. эА РИС.~4,~c ПРЕДСТАВЛЕН ЕЩЕ ХУДШИЙ 
СЛУЧАЙ; ЯСНО, ЧТО ТАКИЕ БОЛЬШИЕ РАСХОЖДЕНИЯ МЕЖДУ~$F_n(x)$ И~$F(x)$ КРАЙНЕ 
МАЛОВЕРОЯТНЫ; ъё-КРИТЕРИЙ ДОЛЖЕН УКАЗАТЬ, НАСКОЛЬКО ОНИ МАЛОВЕРОЯТНЫ.

фЛЯ ЭТОГО ФОРМИРУЮТСЯ СЛЕДУЮЩИЕ СТАТИСТИКИ:
$$
\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)
$$
чДЕСЬ $K_n^+$~ПОКАЗЫВАЕТ, КАКОВО МАКСИМАЛЬНОЕ ОТКЛОНЕНИЕ ДЛЯ 
СЛУЧАЯ~$F_n>F$, А~$K_n^-$---КАКОВО МАКСИМАЛЬНОЕ ОТКЛОНЕНИЕ ДЛЯ 
СЛУЧАЯ~$F_n<F$. т ПРИМЕРАХ, ПОКАЗАННЫХ НА РИС.~4, ЗНАЧЕНИЯ ЭТИХ 
СТАТИСТИК СЛЕДУЮЩИЕ:
$$
\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{чАМЕЧАНИЕ.} эАЛИЧИЕ МНОЖИТЕЛЯ~$\sqrt{n}$ В ФОРМУЛЕ~(11) МОЖЕТ 
ПОКАЗАТЬСЯ СТРАННЫМ. ёОГЛАСНО УПР.~6, ПРИ ФИКСИРОВАННОМ~$x$ СТАНДАРТНОЕ 
ОТКЛОНЕНИЕ~$F_n(x)$ ОТ~$F(x)$ ПРОПОРЦИОНАЛЬНО~$1/\sqrt{n}$; СЛЕДОВАТЕЛЬНО, 
МНОЖИТЕЛЬ~$\sqrt{n}$ НОРМИРУЕТ СТАТИСТИКИ~$K_n^+$ И~$K_n^-$ ТАКИМ ОБРАЗОМ, 
ЧТОБЫ СТАНДАРТНОЕ ОТКЛОНЕНИЕ НЕ ЗАВИСЕЛО ОТ~$n$.]

ЄЕПЕРЬ МОЖНО, КАК И В СЛУЧАЕ КРИТЕРИЯ~$\chi^2$, НАЙТИ ЗНАЧЕНИЯ~$K_n^+$ 
И~$K_n^-$ В "ПРОЦЕНТИЛЬНОЙ" ТАБЛИЦЕ, ЧТОБЫ ОПРЕДЕЛИТЬ, ИМЕЮТ ЛИ ОНИ 
ВЫСОКУЮ ИЛИ НИЗКУЮ ЗНАЧИМОСТЬ. ё ЭТОЙ ЦЕЛЬЮ ДЛЯ ОБЕИХ ВЕЛИЧИН~$K_n^+$ 
И~$K_n^-$ МОЖНО ВОСПОЛЬЗОВАТЬСЯ ТАБЛ.~2. эАПРИМЕР, ВЕРОЯТНОСТЬ ТОГО, ЧТО 
$K_{30}^-$ БОЛЬШЕ ЧЕМ~$0.8036$, РАВНА~25\%. т ОТЛИЧИЕ ОТ ТАБЛИЦЫ ДЛЯ 
КРИТЕРИЯ~$\chi^2$, КОТОРОЙ МОЖНО ПОЛЬЗОВАТЬСЯ ТОЛЬКО ПРИ БОЛЬШИХ~$n$, В 
ЭТОЙ ТАБЛИЦЕ ПРИВОДЯТСЯ ТОЧНЫЕ ЗНАЧЕНИЯ
%% 62
\picture{РИС.~4. яРИМЕРЫ ЭМПИРИЧЕСКИХ РАСПРЕДЕЛЕНИЙ.}
%% 63

\htable{ЄАБЛИЦА~2}%
{эЕКОТОРЫЕ ДАННЫЕ ДЛЯ РАСПРЕДЕЛЕНИЯ ВЕЛИЧИН~$K_n^+$ И~$K_n^-$}%
{$#$\hfil\bskip&&\bskip\hfil$#$\hfil\bskip\cr
 \noalign{
  \embedpar{\noindent(фЛЯ~$n>30$ ПРИВЕДЕНЫ ТЕОРЕТИЧЕСКИ НЕ ОБОСНОВАННЫЕ 
   ИНТЕРПОЛЯЦИОННЫЕ ФОРМУЛЫ, ТОЧНЫЕ ТОЛЬКО ПРИ~$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
}
ДЛЯ ВСЕХ~$n$, ТАК ЧТО ъё-КРИТЕРИЙ МОЖНО ПРИМЕНЯТЬ ПРИ ЛЮБОМ~$n$.

ЇОРМУЛЫ~(11) НЕ ГОДЯТСЯ ДЛЯ МАШИННЫХ РАСЧЕТОВ, ТАК КАК ТРЕБУЕТСЯ ОТЫСКАТЬ 
МАКСИМАЛЬНОЕ СРЕДИ БЕСКОНЕЧНОГО МНОЖЕСТВА ЧИСЕЛ! юДНАКО ТОТ ФАКТ, 
ЧТО~$F(x)$---НЕУБЫВАЮЩАЯ ФУНКЦИЯ, a $F_n(x)$~ИМЕЕТ КОНЕЧНОЕ ЧИСЛО СКАЧКОВ, 
ПОЗВОЛЯЕТ ОПРЕДЕЛИТЬ СТАТИСТИКИ~$K_n^+$ И~$K_n^-$ С ПОМОЩЬЮ СЛЕДУЮЩЕГО 
ПРОСТОГО АЛГОРИТМА:

{\sl °АГ~1.\/} юПРЕДЕЛЯЮТСЯ ВЫБОРОЧНЫЕ ЗНАЧЕНИЯ~$X_1$, $X_2$,~\dots, $X_n$.

{\sl °АГ~2.\/} чНАЧЕНИЯ~$X_i$ РАСПОЛАГАЮТСЯ В ПОРЯДКЕ ВОЗРАСТАНИЯ ТАК, 
ЧТОБЫ~$X_1\le X_2 \le \ldots \le X_n$. (¤ФФЕКТИВНЫЕ АЛГОРИТМЫ, 
СОРТИРОВКИ БУДУТ РАССМОТРЕНЫ В ГЛ.~5.)

%% 64
{\sl °АГ~3.\/}~эУЖНЫЕ НАМ СТАТИСТИКИ ВЫЧИСЛЯЮТСЯ ТЕПЕРЬ ПО ФОРМУЛАМ
$$
\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)
$$

ёДЕЛАТЬ НАДЛЕЖАЩИЙ ВЫБОР ЧИСЛА ИСПЫТАНИЙ~$n$ В ДАННОМ СЛУЧАЕ НЕСКОЛЬКО 
ЛЕГЧЕ, ЧЕМ ПРИ РАБОТЕ С КРИТЕРИЕМ~$\chi^2$, ХОТЯ НЕКОТОРЫЕ ТРУДНОСТИ 
СОХРАНЯЮТСЯ. хСЛИ ИСТИННОЕ РАСПРЕДЕЛЕНИЕ СЛУЧАЙНЫХ ВЕЛИЧИН~$X_j$ НЕ 
ОТВЕЧАЕТ ФУНКЦИИ~$F(x)$, А ОПИСЫВАЕТСЯ КАКОЙ-ТО ДРУГОЙ ФУНКЦИЕЙ~$G(x)$, 
ПОТРЕБУЕТСЯ СРАВНИТЕЛЬНО МНОГО ИСПЫТАНИЙ, ЧТОБЫ УДОСТОВЕРИТЬСЯ, 
ЧТО~$G(x)\ne F(x)$; $n$~ДОЛЖНО БЫТЬ НАСТОЛЬКО БОЛЬШИМ, ЧТОБЫ СТАЛО 
ЗАМЕТНЫМ РАЗЛИЧИЕ МЕЖДУ~$G_n(x)$ И~$F_n(x)$. ё ДРУГОЙ СТОРОНЫ, ПРИ 
БОЛЬШИХ~$n$ ИМЕЕТСЯ ТЕНДЕНЦИЯ К ОСРЕДНЕНИЮ ЛОКАЛЬНЫХ ОТКЛОНЕНИЙ ОТ 
СЛУЧАЙНОГО ПОВЕДЕНИЯ. ЄАКИЕ ОТКЛОНЕНИЯ ОСОБЕННО НЕЖЕЛАТЕЛЬНЫ В 
БОЛЬШИНСТВЕ ПРИЛОЖЕНИЙ СЛУЧАЙНЫХ ЧИСЕЛ ПРИ РАБОТЕ НА 
ВЫЧИСЛИТЕЛЬНЫХ МАШИНАХ. ё ЭТОЙ ТОЧКИ ЗРЕНИЯ БЫЛО БЫ ПОЛЕЗНО 
\emph{УМЕНЬШИТЬ}~$n$. ЄОТ ФАКТ ЧТО ВСЕ $n$~РЕЗУЛЬТАТОВ ИСПЫТАНИЙ НАДО 
ЗАПОМНИТЬ, ЧТОБЫ ПОТОМ РАСПОЛОЖИТЬ В ПОРЯДКЕ ВОЗРАСТАНИЯ, ТАКЖЕ 
СКЛОНЯЕТ НАС К МЫСЛИ УМЕНЬШИТЬ~$n$. т КАЧЕСТВЕ КОМПРОМИССНОГО 
РЕШЕНИЯ МОЖНО ВЗЯТЬ~$n$ РАВНЫМ, СКАЖЕМ, $1000$ И ВЫЧИСЛИТЬ 
ДОСТАТОЧНО МНОГО ЗНАЧЕНИЙ~$K_{1000}^+$ С ИСПОЛЬЗОВАНИЕМ РАЗНЫХ ЧАСТЕЙ СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ:
$$
 K_{1000}^+(1), \quad K_{1000}^+(2), \quad \ldots, \quad K_{1000}^+(r).
 \eqno(14)
$$
ъ \emph{ЭТИМ} ЧИСЛАМ МОЖНО \emph{ОПЯТЬ} ПРИМЕНИТЬ ъё-КРИТЕРИЙ. ЄЕПЕРЬ УЖЕ 
$F(x)$---ФУНКЦИЯ РАСПРЕДЕЛЕНИЯ ДЛЯ~$K_{1000}^+$, ПРИЧЕМ ОНА ОПРЕДЕЛЯЕТСЯ 
ЭМПИРИЧЕСКОЙ ФУНКЦИЕЙ РАСПРЕДЕЛЕНИЯ~$F_r(x)$, ПОСТРОЕННОЙ ПО СЛУЧАЙНЫМ 
ЗНАЧЕНИЯМ~(14). ъ СЧАСТЬЮ, ФУНКЦИЯ РАСПРЕДЕЛЕНИЯ~$F(x)$ ОЧЕНЬ ПРОСТА: ПРИ 
БОЛЬШИХ ЗНАЧЕНИЯХ~$n$, НАПРИМЕР $n=1000$, РАСПРЕДЕЛЕНИЕ ДЛЯ~$K_n^+$ ХОРОШО 
АППРОКСИМИРУЕТСЯ ФУНКЦИЕЙ
$$
F_{\infty}(x)=1-e^{-2x^2}, \rem{$x \ge 0$}.
\eqno(15)
$$
тСЕ СКАЗАННОЕ ОТНОСИТСЯ И К~$K_n^-$, ТАК КАК~$K_n^+$ И~$K_n^-$ ВЕДУТ СЕБЯ 
ОДИНАКОВО. \emph{ЄАКОЙ ПОДХОД, КОГДА СНАЧАЛА КРИТЕРИЙ МНОГОКРАТНО 
ПРИМЕНЯЕТСЯ ПРИ ОТНОСИТЕЛЬНО НЕБОЛЬШИХ~$n$, А ЗАТЕМ ВСЕ РЕЗУЛЬТАТЫ 
КОМБИНИРУЮТСЯ, ПОСЛЕ ЧЕГО ъё-КРИТЕРИЙ  ПРИМЕНЯЕТСЯ ПОВТОРНО, ПОЗВОЛЯЕТ 
ВЫЯВИТЬ КАК ЛОКАЛЬНЫЕ, ТАК И ГЛОБАЛЬНЫЕ ОТКЛОНЕНИЯ ОТ ЗАДАННОГО ЗАКОНА 
РАСПРЕДЕЛЕНИЯ.}

яОЛНЫЙ ЭКСПЕРИМЕНТ (ХОТЯ ГОРАЗДО МЕНЬШЕГО ОБоЕМА) БЫЛ ПРОВЕДЕН АВТОРОМ В 
ХОДЕ РАБОТЫ НАД НАСТОЯЩЕЙ ГЛАВОЙ. ЄЕСТ "НАИБОЛЬШЕЕ ИЗ~5", ОПИСАННЫЙ В 
СЛЕДУЮЩЕМ РАЗДЕЛЕ, ПРИМЕНЯЛСЯ К~$1000$ РАВНОМЕРНО РАСПРЕДЕЛЕННЫХ СЛУЧАЙНЫХ 
ЧИСЕЛ. яОЛУЧИЛОСЬ
%% 65
200~ЧИСЕЛ $X_1$, $X_2$,~\dots, $X_{200}$, ОТНОСИТЕЛЬНО КОТОРЫХ 
ПРЕДПОЛАГАЛОСЬ, ЧТО ОНИ РАСПРЕДЕЛЕНЫ В СООТВЕТСТВИИ С ФУНКЦИЕЙ~$F(x)=x^5$ 
($0\le x \le 1$). тСЕ РЕЗУЛЬТАТЫ БЫЛИ РАЗДЕЛЕНЫ НА 20~ГРУПП ПО 10~ЧИСЕЛ, И 
ДЛЯ КАЖДОЙ ГРУППЫ ВЫЧИСЛЯЛАСЬ СТАТИСТИКА~$K_{10}^+$. яО ПОЛУЧЕННЫМ ТАКИМ 
ОБРАЗОМ 20~ЗНАЧЕНИЯМ~$K_{10}^+$ БЫЛИ ПОСТРОЕНЫ ЭМПИРИЧЕСКИЕ РАСПРЕДЕЛЕНИЯ, 
ИЗОБРАЖЕННЫЕ НА РИС.~4; ГЛАДКИЕ КРИВЫЕ СООТВЕТСТВУЮТ ПРЕДПОЛАГАЕМОЙ 
ФУНКЦИИ РАСПРЕДЕЛЕНИЯ ДЛЯ СТАТИСТИКИ~$K_{10}^+$. эА РИС.~4,~a 
ПРЕДСТАВЛЕНО ЭМПИРИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ ДЛЯ~$K_{10}^+$, СООТВЕТСТВУЮЩЕЕ 
ПОСЛЕДОВАТЕЛЬНОСТИ СЛУЧАЙНЫХ ЧИСЕЛ
$$
\eqalign{
 Y_{n+1}&=(3141592653Y_n+2718281829) \bmod 2^{35},\cr
     U_n&=Y_n/2^{35}.\cr
}
$$
¤ТУ ПОСЛЕДОВАТЕЛЬНОСТЬ МОЖНО ПРИЗНАТЬ УДОВЛЕТВОРИТЕЛЬНОЙ. ЁИС.~4,~b 
СООТВЕТСТВУЕТ ПОСЛЕДОВАТЕЛЬНОСТИ, ПОЛУЧЕННОЙ МЕТОДОМ ЇИБОНАЧЧИ; ЗДЕСЬ 
НАБЛЮДАЮТСЯ ОТКЛОНЕНИЯ \emph{ГЛОБАЛЬНОГО} ХАРАКТЕРА, Т.~Е.\ МОЖНО ПОКАЗАТЬ,
ЧТО ЗНАЧЕНИЯ~$X_n$ ДЛЯ ТЕСТА "НАИБОЛЬШЕЕ ИЗ~5" НЕ ПОДЧИНЯЮТСЯ 
РАСПРЕДЕЛЕНИЮ~$F(x)=x^5$. эА РИС.~4,~c ПРИВЕДЕНЫ РЕЗУЛЬТАТЫ ПРОВЕРКИ 
ПОСЛЕДОВАТЕЛЬНОСТИ, ПОЛЬЗУЮЩЕЙСЯ СЛАВОЙ СЛАБОГО АЛГОРИТМА:
$$
 Y_{n+1}=((2^{18}+1)Y_n+1)\bmod 2^{35}, \quad U_n=Y_n/2^{35}.
$$

ЁЕЗУЛЬТАТЫ ПРИМЕНЕНИЯ ъё-КРИТЕРИЯ К ЭТИМ ДАННЫМ БЫЛИ УЖЕ ПРИВЕДЕНЫ В~(12). 
юБРАЩАЯСЬ К ТАБЛ.~2 С~$n=20$, ПОЛУЧАЕМ, ЧТО ЗНАЧЕНИЯ~$K_{20}^+$ 
И~$K_{20}^-$ В СЛУЧАЕ~(b) СЛЕГКА ПОДОЗРИТЕЛЬНЫ (ОНИ ПОПАДАЮТ ПОЧТИ 
НА~$95\hbox{-}$ И~$12\%\hbox{-НЫЕ}$ УРОВНИ), НО НЕ НАСТОЛЬКО ПЛОХИ, ЧТОБЫ 
МОЖНО БЫЛО С УВЕРЕННОСТЬЮ ОТБРОСИТЬ ЭТУ ПОСЛЕДОВАТЕЛЬНОСТЬ. 
чНАЧЕНИЕ~$K_{20}^-$ ДЛЯ СЛУЧАЯ~(c), БЕЗУСЛОВНО, НИКУДА НЕ ГОДИТСЯ, ТАК ЧТО 
ТЕСТ "НАИБОЛЬШЕЕ ИЗ~5" ОПРЕДЕЛЕННО ДОКАЗЫВАЕТ НЕПРИГОДНОСТЬ ЭТОГО ДАТЧИКА 
СЛУЧАЙНЫХ ЧИСЕЛ.

т ОПИСАННОМ ЭКСПЕРИМЕНТЕ ъё-КРИТЕРИЙ ДОЛЖЕН ВЫЯВЛЯТЬ ГЛОБАЛЬНЫЕ ОТКЛОНЕНИЯ 
ОТ СЛУЧАЙНОГО ПОВЕДЕНИЯ ХУЖЕ, ЧЕМ ЛОКАЛЬНЫЕ, ТАК КАК КАЖДАЯ ГРУППА 
СОСТОЯЛА ВСЕГО ИЗ 10~ИСПЫТАНИЙ. хСЛИ БЫ БЫЛО ВЗЯТО 20~ГРУПП ПО 
1000~ИСПЫТАНИЙ, ОТКЛОНЕНИЕ В СЛУЧАЕ~(b) БЫЛО БЫ БОЛЕЕ ЗНАЧИТЕЛЬНЫМ. фЛЯ 
ИЛЛЮСТРАЦИИ ЭТОГО ъё-КРИТЕРИЙ БЫЛ ПРИМЕНЕН \emph{СРАЗУ} КО ВСЕМ ДАННЫМ, ПО 
КОТОРЫМ ПОСТРОЕНЫ ГРАФИКИ НА РИС.~4. яРИ ЭТОМ ПОЛУЧИЛИСЬ СЛЕДУЮЩИЕ РЕЗУЛЬТАТЫ:
$$
\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)
$$
ЄЕПЕРЬ УЖЕ СО ВСЕЙ ОПРЕДЕЛЕННОСТЬЮ ВЫЯВИЛИСЬ ГЛОБАЛЬНЫЕ ОТКЛОНЕНИЯ ОТ 
ЗАДАННОГО ЗАКОНА РАСПРЕДЕЛЕНИЯ, КОТОРЫЙ ДАЕТ МЕТОД ЇИБОНАЧЧИ. ыОКАЛЬНЫЕ 
ОТКЛОНЕНИЯ В СЛУЧАЕ~(c) СКАЗЫВАЮТСЯ ВПЛОТЬ ДО~$n=1\,000\,000$, ТАК ЧТО 
ПРИ~$n=200$ ГОВОРИТЬ О ГЛОБАЛЬНЫХ ОТКЛОНЕНИЯХ НЕ ПРИХОДИТСЯ.

%%   66
ъРИТЕРИЙ ъОЛМОГОРОВА---ёМИРНОВА ЗАКЛЮЧАЕТСЯ, ТАКИМ ОБРАЗОМ, В СЛЕДУЮЩЕМ. ё 
ПОМОЩЬЮ $n$~\emph{НЕЗАВИСИМЫХ ИСПЫТАНИЙ} ПОЛУЧАЮТСЯ ЗНАЧЕНИЯ~$X_1$,~\dots, 
$X_n$ СЛУЧАЙНОЙ ВЕЛИЧИНЫ С \emph{НЕПРЕРЫВНОЙ} ФУНКЦИЕЙ 
РАСПРЕДЕЛЕНИЯ~$F(x)$. ($F(x)$~ДОЛЖНА БЫТЬ ТИПА ФУНКЦИЙ, ИЗОБРАЖЕННЫХ НА 
РИС.~3,~b И~3,~c, Т.~Е.\ БЕЗ СКАЧКОВ КАК НА РИС.~3,~a.) чАТЕМ С ПОМОЩЬЮ 
ПРОЦЕДУРЫ, ОПИСАННОЙ ПЕРЕД ФОРМУЛОЙ~(13), ВЫЧИСЛЯЮТСЯ СТАТИСТИКИ~$K_n^+$ 
И~$K_n^-$. ¤ТИ СТАТИСТИКИ ДОЛЖНЫ БЫТЬ РАСПРЕДЕЛЕНЫ В СООТВЕТСТВИИ С ТАБЛ.~2.

ЄЕПЕРЬ МОЖНО СРАВНИТЬ КРИТЕРИИ ъОЛМОГОРОВА---ёМИРНОВА И~$\chi^2$. яРЕЖДЕ 
ВСЕГО СЛЕДУЕТ ЗАМЕТИТЬ, ЧТО ъё-КРИТЕРИЕМ МОЖНО ПОЛЬЗОВАТЬСЯ \emph{В 
СОЧЕТАНИИ С} КРИТЕРИЕМ~$\chi^2$, ЧТОБЫ ПОЛУЧИТЬ ЛУЧШУЮ ПРОЦЕДУРУ, ЧЕМ 
МЕТОД ad hoc, УПОМЯНУТЫЙ ПРИ ЗАВЕРШЕНИИ ОПИСАНИЯ КРИТЕРИЯ~$\chi^2$. (¤ТО 
ЗНАЧИТ, ЧТО СУЩЕСТВУЕТ БОЛЕЕ СОВЕРШЕННЫЙ СПОСОБ, НЕЖЕЛИ ПРОВЕДЕНИЕ ТРЕХ 
ПРОВЕРОК, ЧТОБЫ ВЫЯСНИТЬ, КАК МНОГО РЕЗУЛЬТАТОВ ОКАЖУТСЯ 
"ПОДОЗРИТЕЛЬНЫМИ".) яРЕДПОЛОЖИМ, ЧТО С ПОМОЩЬЮ КРИТЕРИЯ~$\chi^2$ БЫЛИ 
НЕЗАВИСИМО ОБРАБОТАНЫ, СКАЖЕМ, 10~РАЗНЫХ УЧАСТКОВ СЛУЧАЙНОЙ 
ПОСЛЕДОВАТЕЛЬНОСТИ, В РЕЗУЛЬТАТЕ ЧЕГО БЫЛИ ПОЛУЧЕНЫ ЗНАЧЕНИЯ~$V_1$, $V_2$,~\dots, 
$V_{10}$. юБЫЧНЫЙ ПОДСЧЕТ КОЛИЧЕСТВА ПОДОЗРИТЕЛЬНО БОЛЬШИХ ИЛИ 
МАЛЫХ ЗНАЧЕНИЙ~$V$---НЕ ЛУЧШИЙ СПОСОБ АНАЛИЗА (ХОТЯ В ЭКСТРЕМАЛЬНЫХ СЛУЧАЯХ 
ОН БУДЕТ РАБОТАТЬ, И \emph{ОЧЕНЬ} БОЛЬШИЕ ИЛИ \emph{ОЧЕНЬ} МАЛЫЕ ЗНАЧЕНИЯ 
МОГУТ СЛУЖИТЬ УКАЗАНИЕМ НА ТО, ЧТО ДАННАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ 
СОДЕРЖИТ СЛИШКОМ МНОГО ЛОКАЛЬНЫХ ОТКЛОНЕНИЙ). чНАЧИТЕЛЬНО ЛУЧШЕ 
ПОСТРОИТЬ ПО ЭТИМ 10~ЗНАЧЕНИЯМ ЭМПИРИЧЕСКУЮ ФУНКЦИЮ РАСПРЕДЕЛЕНИЯ И 
СРАВНИТЬ ЕЕ С ТЕОРЕТИЧЕСКОЙ ФУНКЦИЕЙ РАСПРЕДЕЛЕНИЯ, КОТОРУЮ МОЖНО ПОЛУЧИТЬ 
С ПОМОЩЬЮ ТАБЛ.~1. яОСЛЕ ОПРЕДЕЛЕНИЯ СТАТИСТИК~$K_{10}^+$ И~$K_{10}^-$ 
ФОРМИРУЕТСЯ ОКОНЧАТЕЛЬНОЕ СУЖДЕНИЕ ОБ ИСХОДЕ ПРОВЕРКИ ПОСЛЕДОВАТЕЛЬНОСТИ С 
ПОМОЩЬЮ КРИТЕРИЯ~$\chi^2$. яРИ~10 ИЛИ ДАЖЕ 100~ЗНАЧЕНИЯХ ВСЕ ЭТО ЛЕГКО 
МОЖНО СДЕЛАТЬ ВРУЧНУЮ, ИСПОЛЬЗУЯ ГРАФИЧЕСКИЕ МЕТОДЫ; ПРИ БОЛЬШЕМ ЧИСЛЕ 
ЗНАЧЕНИЙ~$V$ ПОТРЕБУЕТСЯ ПОДПРОГРАММА ДЛЯ МАШИННОГО РАСЧЕТА 
РАСПРЕДЕЛЕНИЯ~$\chi^2$. юТМЕТИМ, ЧТО \emph{ВСЕ 20~ТОЧЕК НА РИС.~4,~c 
ПОПАДАЮТ В ИНТЕРВАЛ МЕЖДУ $5\hbox{-}$ И~$95\%\hbox{-НЫМИ}$ УРОВНЯМИ,} ТАК 
ЧТО \emph{КАЖДАЯ} ИЗ НИХ В ОТДЕЛЬНОСТИ НЕ МОЖЕТ РАССМАТРИВАТЬСЯ КАК 
ПОДОЗРИТЕЛЬНАЯ; ОДНАКО СУММАРНОЕ ЭМПИРИЧЕСКОЕ РАСПРЕДЕЛЕНИЕ ЯВНО НЕ 
СОВПАДАЕТ С ТЕОРЕТИЧЕСКИМ.

тАЖНОЕ РАЗЛИЧИЕ МЕЖДУ КРИТЕРИЯМИ ъОЛМОГОРОВА---ёМИРНОВА И~$\chi^2$ 
ЗАКЛЮЧАЕТСЯ В ТОМ, ЧТО ПЕРВЫЙ ИЗ НИХ ПРИМЕНЯЕТСЯ К РАСПРЕДЕЛЕНИЯМ, НЕ 
ИМЕЮЩИМ СКАЧКОВ, В ТО ВРЕМЯ КАК ВТОРОЙ---К КУСОЧНО ПОСТОЯННЫМ РАСПРЕДЕЛЕНИЯМ 
(ТАК КАК ВСЕ РЕЗУЛЬТАТЫ ДЕЛЯТСЯ НА $k$~КАТЕГОРИЙ). ЄАКИМ ОБРАЗОМ, ОБЛАСТИ 
ПРИЛОЖЕНИЯ ЭТИХ КРИТЕРИЕВ РАЗЛИЧНЫ. яРАВДА, КРИТЕРИЙ~$\chi^2$ МОЖНО 
ПРИМЕНЯТЬ И ДЛЯ НЕПРЕРЫВНЫХ РАСПРЕДЕЛЕНИЙ, ЕСЛИ РАЗДЕЛИТЬ ВСЮ 
ОБЛАСТЬ ОПРЕДЕЛЕНИЯ~$F(x)$ НА $k$~ЧАСТЕЙ И ПРЕНЕБРЕЧЬ ВАРИАЦИЯМИ В 
ПРЕДЕЛАХ КАЖДОГО ИНТЕРВАЛА. хСЛИ, НАПРИМЕР, МЫ ХОТИМ ВЫЯСНИТЬ,
РАСПРЕДЕЛЕНЫ ЛИ ЗНАЧЕНИЯ~$U_1$, $U_2$,~\dots, $U_n$ РАВНОМЕРНО МЕЖДУ
%% 67
НУЛЕМ И ЕДИНИЦЕЙ, Т.~Е.\ СООТВЕТСТВУЕТ ЛИ ИХ РАСПРЕДЕЛЕНИЕ 
ФУНКЦИИ~$F(x)=x$ ПРИ~$0\le x \le 1$, БУДЕТ ЕСТЕСТВЕННО ПРИМЕНИТЬ 
ъё-КРИТЕРИЙ. эО МОЖНО ТАКЖЕ РАЗДЕЛИТЬ ИНТЕРВАЛ ОТ~$0$ ДО~$1$ НА~$k=100$ 
РАВНЫХ ЧАСТЕЙ, ПОДСЧИТАТЬ, СКОЛЬКО В КАЖДУЮ ИЗ НИХ ПОПАДАЕТ ЗНАЧЕНИЙ~$U$, 
ПОСЛЕ ЧЕГО ИСПОЛЬЗОВАТЬ КРИТЕРИЙ~$\chi^2$ С 99~СТЕПЕНЯМИ СВОБОДЫ. т 
НАСТОЯЩЕЕ ВРЕМЯ НЕ СУЩЕСТВУЕТ ДОСТАТОЧНО ОПРЕДЕЛЕННЫХ ТЕОРЕТИЧЕСКИХ 
РЕЗУЛЬТАТОВ, ПОЗВОЛЯЮЩИХ СРАВНИВАТЬ ЭФФЕКТИВНОСТИ ЭТИХ ДВУХ КРИТЕРИЕВ. 
рВТОР ОБНАРУЖИЛ ПРИМЕРЫ, В КОТОРЫХ ъё-КРИТЕРИИ ВЫЯВЛЯЛ ОТКЛОНЕНИЯ ОТ 
СЛУЧАЙНОСТИ БОЛЕЕ ЯВСТВЕННО, ЧЕМ КРИТЕРИЙ~$\chi^2$, А ТАКЖЕ И ПРИМЕРЫ 
ПРОТИВОПОЛОЖНОГО ХАРАКТЕРА. хСЛИ, НАПРИМЕР, ИНТЕРВАЛЫ, НА КОТОРЫЕ 
РАЗБИВАЕТСЯ ПРОМЕЖУТОК~$(0, 1)$, ПРОНУМЕРОВАНЫ ОТ~$0$ ДО~$99$ И 
ОТКЛОНЕНИЯ ОТ СРЕДНИХ ЗНАЧЕНИЙ ПОЛОЖИТЕЛЬНЫ В ИНТЕРВАЛАХ~$0$--$49$ И 
ОТРИЦАТЕЛЬНЫ В ИНТЕРВАЛАХ~$50$--$99$, ТО ЭМПИРИЧЕСКАЯ 
ФУНКЦИЯ РАСПРЕДЕЛЕНИЯ БУДЕТ ЗНАЧИТЕЛЬНО ДАЛЬШЕ ОТ~$F(x)$, ЧЕМ МОЖНО БЫЛО 
БЫ ПРЕДПОЛОЖИТЬ ПО ЗНАЧЕНИЮ~$\chi^2$. эО ЕСЛИ ОТКЛОНЕНИЯ ПОЛОЖИТЕЛЬНЫ В 
ИНТЕРВАЛАХ~$0$, $2$,~\dots, $98$ И ОТРИЦАТЕЛЬНЫ В ИНТЕРВАЛАХ~$1$, $3$,~\dots, 
$99$, ТО ЭМПИРИЧЕСКАЯ ФУНКЦИЯ РАСПРЕДЕЛЕНИЯ БУДЕТ ГОРАЗДО БЛИЖЕ 
К~$F(x)$. юТСЮДА ВИДНО, ЧТО ХАРАКТЕР РЕГИСТРИРУЕМЫХ ОТКЛОНЕНИЙ НЕСКОЛЬКО 
РАЗЛИЧЕН. фЛЯ $200$~ЧИСЕЛ, ПО КОТОРЫМ ПОСТРОЕНЫ ГРАФИКИ НА РИС.~4, 
КРИТЕРИЙ~$\chi^2$ С~$k=10$ ДАЕТ ЗНАЧЕНИЯ~$V$, РАВНЫЕ~$9.4$, $17.7$ 
И~$39.3$; В ЭТОМ КОНКРЕТНОМ СЛУЧАЕ ПОЛУЧЕННЫЕ ЗНАЧЕНИЯ ВПОЛНЕ СРАВНИМЫ С 
ТЕМИ, КОТОРЫЕ ДАЕТ ъё-КРИТЕРИЙ (СМ.~(16)). фЛЯ НЕПРЕРЫВНЫХ РАСПРЕДЕЛЕНИЙ 
ъё-КРИТЕРИЙ ОБЛАДАЕТ ОПРЕДЕЛЕННЫМИ ПРЕИМУЩЕСТВАМИ, ТАК КАК 
КРИТЕРИЙ~$\chi^2$ ПО ОПРЕДЕЛЕНИЮ ИМЕЕТ ПРИБЛИЖЕННЫЙ ХАРАКТЕР И 
ТРЕБУЕТ ОТНОСИТЕЛЬНО БОЛЬШИХ ЗНАЧЕНИЙ~$n$.

шНТЕРЕСНО ТАКЖЕ ПОСМОТРЕТЬ, КАК ИЗМЕНЯТСЯ РЕЗУЛЬТАТЫ ПРОВЕРКИ ШЕСТИ 
РАЗНЫХ ДАТЧИКОВ СЛУЧАЙНЫХ ЧИСЕЛ, ПРИВЕДЕННЫЕ НА РИС.~2, ЕСЛИ ВМЕСТО 
КРИТЕРИЯ~$\chi^2$ ИСПОЛЬЗОВАТЬ ъё-КРИТЕРИЙ. ¤ТИ РЕЗУЛЬТАТЫ БЫЛИ ПОЛУЧЕНЫ 
ДЛЯ~$n=200$ С ПОМОЩЬЮ КРИТЕРИЯ "НАИБОЛЬШЕЕ ИЗ~$t$" ПРИ~$1\le t \le 5$; 
ПРОМЕЖУТОК~$(0, 1)$ РАЗДЕЛЯЛСЯ НА~$10$~РАВНЫХ ЧАСТЕЙ. яО НИМ МОЖНО 
ВЫЧИСЛИТЬ СТАТИСТИКИ~$K_{200}^+$  И~$K_{200}^-$ И ПОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ 
ПРЕДСТАВИТЬ В ТОМ ЖЕ ВИДЕ, КАК НА РИС.~2 (ОТМЕЧАЯ, КАКИЕ ЗНАЧЕНИЯ ВЫХОДЯТ 
ЗА УРОВЕНЬ~$99\%$ И~Т.~Д.). ¤ТО СДЕЛАНО НА РИС.~5. юТМЕТИМ, ЧТО ДАТЧИК~D 
(МЕТОД ыЕМЕРА), СУДЯ ПО РИС.~5, ВЕСЬМА ПЛОХ, В ТО ВРЕМЯ КАК РЕЗУЛЬТАТЫ 
ОБРАБОТКИ \emph{ТЕХ ЖЕ САМЫХ ДАННЫХ} ПО КРИТЕРИЮ~$\chi^2$ НЕ ОБНАРУЖИЛИ 
НИКАКИХ ОТКЛОНЕНИЙ. фАТЧИК~E (МЕТОД ЇИБОНАЧЧИ), НАОБОРОТ, НА РИС.~5 
ВЫГЛЯДИТ НЕСКОЛЬКО ЛУЧШЕ. їОРОШИЕ ДАТЧИКИ~A И~B УДОВЛЕТВОРЯЮТ ВСЕМ 
КРИТЕРИЯМ. яРИЧИНЫ РАСХОЖДЕНИЙ МЕЖДУ РИС.~2 И~5 ЗАКЛЮЧАЮТСЯ В ПЕРВУЮ 
ОЧЕРЕДЬ В ТОМ, ЧТО (a)~ЧИСЛО ИСПЫТАНИЙ~$200$ НА САМОМ ДЕЛЕ НЕДОСТАТОЧНО 
ВЕЛИКО; (b)~РАЗДЕЛЕНИЕ РЕЗУЛЬТАТОВ НА "НЕГОДНЫЕ", "ПОДОЗРИТЕЛЬНЫЕ" И 
"СЛЕГКА ПОДОЗРИТЕЛЬНЫЕ" САМО ПО СЕБЕ ДОВОЛЬНО ПОДОЗРИТЕЛЬНО.

(сЫЛО БЫ НЕСПРАВЕДЛИВОСТЬЮ ОБВИНЯТЬ ыЕМЕРА В ТОМ, ЧТО ОН
%% 68
ИСПОЛЬЗОВАЛ В 1948~Г.\ "ПЛОХОЙ" ДАТЧИК СЛУЧАЙНЫХ ЧИСЕЛ, ПОТОМУ ЧТО В 
ДАННОМ КОНКРЕТНОМ СЛУЧАЕ ЭТО БЫЛО ВПОЛНЕ ЗАКОННО. ьАШИНА ENIAC РАБОТАЛА 
В ПАРАЛЛЕЛЬНОМ РЕЖИМЕ И ПРОГРАММИРОВАЛАСЬ ПОСРЕДСТВОМ КОММУТАЦИОННОЙ 
ПАНЕЛИ. ыЕМЕР УСТАНОВИЛ ТАКОЙ РЕЖИМ, ПРИ КОТОРОМ СОДЕРЖИМОЕ ОДНОГО ИЗ СУММАТОРОВ
\picture{ЁИС.~5. ЁЕЗУЛЬТАТЫ ПРИМЕНЕНИЯ ъё-КРИТЕРИЯ К ТЕМ ЖЕ ДАННЫМ, ЧТО И НА РИС.~2.}
ПОСТОЯННО УМНОЖАЛОСЬ НА~$23$ ПО МОДУЛЮ~$10^8+1$; СОДЕРЖИМОЕ СУММАТОРА 
ИЗМЕНЯЛОСЬ КАЖДЫЕ НЕСКОЛЬКО МИКРОСЕКУНД. ьНОЖИТЕЛЬ~$23$ СЛИШКОМ МАЛ, ЧТОБЫ 
ТАКУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ МОЖНО БЫЛО СЧИТАТЬ СЛУЧАЙНОЙ: КОРРЕЛЯЦИЯ МЕЖДУ 
СЛЕДУЮЩИМИ НЕПОСРЕДСТВЕННО ДРУГ ЗА ДРУГОМ ЧИСЛАМИ ПРИ ТАКОМ МНОЖИТЕЛЕ 
СЛИШКОМ ВЕЛИКА. эО ПРОМЕЖУТОК ВРЕМЕНИ МЕЖДУ ОБРАЩЕНИЯМИ К СУММАТОРУ,
СОДЕРЖАЩЕМУ СЛУЧАЙНОЕ ЧИСЛО, БЫЛ СРАВНИТЕЛЬНО ВЕЛИК И, КРОМЕ ТОГО, ВСЕ 
ВРЕМЯ МЕНЯЛСЯ. ЄАК ЧТО ФАКТИЧЕСКИ МНОЖИТЕЛЬ БЫЛ РАВЕН~$23^k$, 
ГДЕ~$k$---БОЛЬШОЕ, ИЗМЕНЯЮЩЕЕСЯ ЧИСЛО!)

\section {C. шСТОРИЯ, БИБЛИОГРАФИЯ И ТЕОРИЯ}. ъРИТЕРИЙ~$\chi^2$ БЫЛ 
ПРЕДЛОЖЕН ъАРЛОМ яИРСОНОМ В 1900~Г. ({\sl Philosophical Magazine,\/} 
Series~5, {\bf 50}, 157--175). ¤ТА РАБОТА яИРСОНА СЧИТАЕТСЯ ОДНОЙ ИЗ 
ОСНОВОПОЛАГАЮЩИХ В СОВРЕМЕННОЙ СТАТИСТИКЕ, ТАК КАК ДО НЕЕ 
КАЧЕСТВО ЭКСПЕРИМЕНТАЛЬНЫХ РЕЗУЛЬТАТОВ ОПРЕДЕЛЯЛОСЬ ПРОСТО ПО ТОМУ, 
КАК ОНИ ВЫГЛЯДЯТ НА ГРАФИКЕ. т СВОЕЙ СТАТЬЕ яИРСОН ПРИВОДИТ НЕСКОЛЬКО 
ИНТЕРЕСНЫХ ПРИМЕРОВ НЕПРАВИЛЬНОГО ИСПОЛЬЗОВАНИЯ СТАТИСТИКИ.
%% 68
юН ПОКАЗАЛ ТАКЖЕ, ЧТО В НЕКОТОРЫХ СЛУЧАЯХ РУЛЕТКА (НА КОТОРОЙ ОН 
ЭКСПЕРИМЕНТИРОВАЛ В ьОНТЕ-ъАРЛО В ТЕЧЕНИЕ ДВУХ НЕДЕЛЬ В 1892~Г.) ДАВАЛА 
РЕЗУЛЬТАТЫ, НАСТОЛЬКО ДАЛЕКИЕ ОТ СРЕДНИХ ЗНАЧЕНИЙ, ЧТО ПРИ ПРАВИЛЬНОМ 
УСТРОЙСТВЕ РУЛЕТКИ ОНИ МОГЛИ БЫ ОСУЩЕСТВИТЬСЯ НЕ ЧАЩЕ, ЧЕМ ОДИН РАЗ 
ИЗ~$10^{29}$. юБЩЕЕ ОБСУЖДЕНИЕ КРИТЕРИЯ~$\chi^2$ И ОБШИРНАЯ БИБЛИОГРАФИЯ 
СОДЕРЖАТСЯ В ОБЗОРНОЙ СТАТЬЕ є.~ъОКРЭНА (W.~G.~Cochran, {\sl Annals of 
Mathematical Statistics,\/} {\bf 23} (1952), 315--345).

шЗЛОЖИМ В СОКРАЩЕННОМ ВИДЕ ТЕОРИЮ, ЛЕЖАЩУЮ В ОСНОВЕ КРИТЕРИЯ~$\chi^2$. 
ЄОЧНАЯ ВЕРОЯТНОСТЬ ТОГО, ЧТО~$Y_1=y_1$,~\dots, $Y_k=y_k$ РАВНА, КАК ЛЕГКО 
ВИДЕТЬ,
$$
{n! \over y_1! \ldots y_k!} p_1^{y_1}\ldots p_k^{y_k}.
\eqno(17)
$$
хСЛИ ПРЕДПОЛОЖИТЬ, ЧТО $Y_s$~ИМЕЕТ РАСПРЕДЕЛЕНИЕ яУАССОНА С ПЛОТНОСТЬЮ
$$
{e^{-np_s} (np_s)^{y_s} \over y_s!}
$$
И СЛУЧАЙНЫЕ ВЕЛИЧИНЫ~$Y_s$ НЕЗАВИСИМЫ, ТО ВЕРОЯТНОСТЬ ОСУЩЕСТВЛЕНИЯ 
ЗНАЧЕНИЙ~$(y_1,~\ldots, y_k)$ РАВНА
$$
\prod_{1\le s \le k} {e^{-np_s} (np_s)^{y_s} \over y_s!},
$$
А СУММА~$Y_1+\cdots+Y_k$ БУДЕТ РАВНА~$n$ С ВЕРОЯТНОСТЬЮ
$$
\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!}.
$$
хСЛИ ПОТРЕБОВАТЬ СОБЛЮДЕНИЯ УСЛОВИЯ~$Y_1+\cdots+Y_k=n$, А В 
\emph{ОСТАЛЬНОМ} СЧИТАТЬ СЛУЧАЙНЫЕ ВЕЛИЧИНЫ НЕЗАВИСИМЫМИ, ТО ВЕРОЯТНОСТЬ 
ТОГО, ЧТО~$(Y_1,~\ldots, Y_k)=(y_1,~\ldots, y_k)$, БУДЕТ РАВНА
$$
 \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),
$$
ЧТО СОВПАДАЕТ С~(17). \emph{ьОЖНО, СЛЕДОВАТЕЛЬНО, СЧИТАТЬ, ЧТО СЛУЧАЙНЫЕ 
ВЕЛИЧИНЫ~$Y$ ИМЕЮТ РАСПРЕДЕЛЕНИЕ яУАССОНА И НЕЗАВИСИМЫ,  С ЕДИНСТВЕННЫМ 
ОГРАНИЧЕНИЕМ, ЧТО ИХ СУММА ФИКСИРОВАНА.}

юБОЗНАЧИМ
$$
Z_s={Y_s-np_s \over \sqrt{np_s}},\quad
V=Z_1^2+\cdots+Z_k^2.
\eqno(18)
$$
єСЛОВИЕ~$Y_1+\cdots+Y_k=n$ МОЖНО ЗАПИСАТЬ В ВИДЕ
$$
\sqrt{p_1}Z_1+\cdots+\sqrt{p_k}Z_k=0.
\eqno(19)
$$
%% 70
ЁАССМОТРИМ $(k-1)\hbox{-МЕРНОЕ}$ ПРОСТРАНСТВО~$S$ ВЕКТОРОВ~$(Z_1,~\ldots,  Z_k)$, 
ДЛЯ КОТОРЫХ ВЫПОЛНЯЕТСЯ УСЛОВИЕ~(19). яРИ БОЛЬШИХ 
ЗНАЧЕНИЯХ~$n$ СЛУЧАЙНЫЕ ВЕЛИЧИНЫ~$Z_s$ ПРИБЛИЗИТЕЛЬНО НОРМАЛЬНЫ 
(СМ.~УПР.~1.2.10-16), ТАК ЧТО ВЕРОЯТНОСТЬ ВЫБОРА ТОЧКИ, 
ПРИНАДЛЕЖАЩЕЙ ЭЛЕМЕНТАРНОМУ ОБоЕМУ~$dZ_2~\ldots{} dZ_k$ В~$S$ 
\emph{ПРИБЛИЖЕННО} ПРОПОРЦИОНАЛЬНА~$\exp(-(Z_1^2+\cdots+Z_k^2)/2)$. 
(шМЕННО ЭТОТ МОМЕНТ В ВЫВОДЕ ПРИВОДИТ К ТОМУ, ЧТО КРИТЕРИЙ~$\chi^2$ 
ЯВЛЯЕТСЯ ЛИШЬ АППРОКСИМАЦИЕЙ, СПРАВЕДЛИВОЙ ДЛЯ БОЛЬШИХ~$n$.) ЄЕПЕРЬ 
ВЕРОЯТНОСТЬ ТОГО, ЧТО~$V\le v$, РАВНА
$$
{\displaystyle\int_{\scriptstyle (Z_1,\ldots, Z_k)\hbox{ В } S\atop\scriptstyle\hbox{ И } 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{ В } S} \exp(-(Z_1^2+\cdots+Z_k^2)/2) \,dz_2\ldots dz_k
}.
\eqno(20)
$$
ЄАК КАК ПЛОСКОСТЬ~(19) ПРОХОДИТ ЧЕРЕЗ НАЧАЛО КООРДИНАТ В $k\hbox{-МЕРНОМ}$ 
ПРОСТРАНСТВЕ, ИНТЕГРИРОВАНИЕ В ЗНАМЕНАТЕЛЕ ПРОВОДИТСЯ ПО ОБоЕМУ СФЕРЫ В 
$(k-1)\hbox{-МЕРНОМ}$ ПРОСТРАНСТВЕ С ЦЕНТРОМ В НАЧАЛЕ КООРДИНАТ. 
яРЕОБРАЗОВАНИЕМ К ОБОБЩЕННЫМ ПОЛЯРНЫМ КООРДИНАТАМ С РАДИУСОМ~$\chi$ И 
УГЛАМИ~$\omega_1$,~\dots, $\omega_{k-2}$ ФОРМУЛА~(20) ПРИВОДИТСЯ К ВИДУ
$$
{\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}
};
$$
ФУНКЦИЯ~$f$ ОПРЕДЕЛЕНА В УПР.~15. яРИ ИНТЕГРИРОВАНИИ ПО УГЛАМ~$\omega_1$,~\dots,
$\omega_{k-2}$ В ЧИСЛИТЕЛЕ И ЗНАМЕНАТЕЛЕ ПОЯВЛЯЕТСЯ МНОЖИТЕЛЬ, НА 
КОТОРЫЙ МОЖНО СОКРАТИТЬ. т КОНЦЕ КОНЦОВ ПОЛУЧАЕТСЯ ФОРМУЛА
$$
{\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)
$$
ПРИБЛИЖЕННО ПРЕДСТАВЛЯЮЩАЯ ВЕРОЯТНОСТЬ ТОГО, ЧТО~$V\le v$.

т ЭТОМ ВЫВОДЕ РАДИУС ОБОЗНАЧЕН ЧЕРЕЗ~$\chi$, КАК В ОРИГИНАЛЬНОЙ РАБОТЕ 
яИРСОНА; ОТСЮДА КРИТЕРИЙ~$\chi^2$ И ПОЛУЧИЛ СВОЕ НАЗВАНИЕ. 
яОДСТАВЛЯЯ~$t=\chi^2/2$, МОЖНО ВЫРАЗИТЬ ИНТЕГРАЛЫ ЧЕРЕЗ НЕПОЛНУЮ 
ГАММА-ФУНКЦИЮ, КОТОРАЯ УЖЕ ИСПОЛЬЗОВАЛАСЬ В П.~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)
$$
ЄАКОВО ОПРЕДЕЛЕНИЕ РАСПРЕДЕЛЕНИЯ~$\chi^2$ С $(k-1)$~СТЕПЕНЯМИ СВОБОДЫ.

%% 71

яЕРЕЙДЕМ ТЕПЕРЬ К ъё-КРИТЕРИЮ. т 1933~Г.\ р.~э.~ъОЛМОГОРОВ ПРЕДЛОЖИЛ 
КРИТЕРИЙ, ОСНОВАННЫЙ НА СТАТИСТИКЕ
$$
K_n=\sqrt{n}\max_{-\infty<x<+\infty}\abs{F_n(x)-F(x)}=\max(K_n^+, K_n^-).
\eqno(23)
$$
ёРЕДИ РЯДА МОДИФИКАЦИЙ ЭТОГО КРИТЕРИЯ, ОПИСАННЫХ В 1939~Г.\ 
э.~т.~ёМИРНОВЫМ, БЫЛА И ТА, КОТОРАЯ ИСПОЛЬЗУЕТСЯ В ЭТОЙ КНИГЕ И ОПИРАЕТСЯ 
НА РАЗДЕЛЬНОЕ ВЫЧИСЛЕНИЕ~$K_n^+$ И~$K_n^-$. ёУЩЕСТВУЕТ ОБШИРНОЕ 
СЕМЕЙСТВО РАЗНОВИДНОСТЕЙ ЭТОГО КРИТЕРИЯ, НО ТЕ ИЗ НИХ, КОТОРЫЕ 
ИСПОЛЬЗУЮТ~$K_n^+$ И~$K_n^-$, ОСОБЕННО УДОБНЫ ДЛЯ МАШИННЫХ РАСЧЕТОВ. 
шСЧЕРПЫВАЮЩИЙ ОБЗОР ЛИТЕРАТУРЫ ПО ъё-КРИТЕРИЮ И ЕГО ОБОБЩЕНИЯМ, ВКЛЮЧАЯ 
ОБШИРНЫЙ СПИСОК ЛИТЕРАТУРЫ, СОДЕРЖИТСЯ В РАБОТЕ фАРЛИНГА 
({\sl Annals of Mathematical Statistics,\/} {\bf 28} (1957), 823--838). 
ЁАБОТА ПРОФ.\ фАРЛИНГА ПРЕДНАЗНАЧЕНА ГЛАВНЫМ ОБРАЗОМ ДЛЯ СПЕЦИАЛИСТОВ В 
ДАННОЙ ОБЛАСТИ.

яРЕЖДЕ ЧЕМ НАЧАТЬ ИЗУЧЕНИЕ РАСПРЕДЕЛЕНИЯ~$K_n^+$ И~$K_n^-$, СФОРМУЛИРУЕМ 
СЛЕДУЮЩЕЕ ФУНДАМЕНТАЛЬНОЕ УТВЕРЖДЕНИЕ. \dfn{хСЛИ~$X$---СЛУЧАЙНАЯ ВЕЛИЧИНА С 
НЕПРЕРЫВНОЙ ФУНКЦИЕЙ РАСПРЕДЕЛЕНИЯ~$F(x)$, ТО~$F(X)$---СЛУЧАЙНОЕ ЧИСЛО, 
РАВНОМЕРНО РАСПРЕДЕЛЕННОЕ МЕЖДУ~$0$ И~$1$.} фЛЯ ДОКАЗАТЕЛЬСТВА ЭТОГО 
ДОСТАТОЧНО ПРОВЕРИТЬ, ЧТО ПРИ~$0\le y \le 1$ НЕРАВЕНСТВО~$F(X)\le y$ 
СПРАВЕДЛИВО С ВЕРОЯТНОСТЬЮ~$y$. шЗ НЕПРЕРЫВНОСТИ~$F(x)$ СЛЕДУЕТ, 
ЧТО~$F(x_0)=y$ ДЛЯ КАКОГО-ТО~$x_0$. яОЭТОМУ ВЕРОЯТНОСТЬ ТОГО, 
ЧТО~$F(X)\le y$, ЕСТЬ ВЕРОЯТНОСТЬ ВЫПОЛНЕНИЯ НЕРАВЕНСТВА~$X\le x_0$. 
яО ОПРЕДЕЛЕНИЮ ЭТА ВЕРОЯТНОСТЬ ЕСТЬ~$F(x_0)$, Т.~Е.\ РАВНА~$y$.

яУСТЬ~$Y_j=n F(X_j)$ ДЛЯ~$1\le j \le n$. ЄОГДА ВЕЛИЧИНЫ~$Y_j$ 
РАСПРЕДЕЛЕНЫ РАВНОМЕРНО МЕЖДУ~$0$ И~$n$; ОНИ НЕЗАВИСИМЫ, ЗА 
ИСКЛЮЧЕНИЕМ ТОГО, ЧТО~$Y_1\le Y_2 \le \ldots \le Y_n$ (ЭТО ЭКВИВАЛЕНТНО 
ТРЕБОВАНИЮ~$X_1\le X_2\le\ldots\le X_n$, КОТОРОЕ ПРИНИМАЕТСЯ ПРИ РАСЧЕТАХ 
ПО ФОРМУЛЕ~(13)). ЇОРМУЛУ~(13) МОЖНО ПЕРЕПИСАТЬ ТЕПЕРЬ СЛЕДУЮЩИМ ОБРАЗОМ:
$$
K_n^+={1\over \sqrt{n}}\max(1-Y_1, 2-Y_2, \ldots, n-Y_n).
$$
хСЛИ~$0\le t \le n$, ТО ВЕРОЯТНОСТЬ НЕРАВЕНСТВА~$K_n^+\le t/\sqrt{n}$ ЕСТЬ 
ВЕРОЯТНОСТЬ ТОГО, ЧТО~$Y_j\ge j-t$ ДЛЯ~$1\le j \le n$. ¤ТУ 
ВЕРОЯТНОСТЬ НЕТРУДНО ЗАПИСАТЬ В ВИДЕ $n\hbox{-КРАТНОГО}$ ИНТЕГРАЛА
$$
{\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{ГДЕ $\alpha_j=\max(j-t, 0)$.}
\eqno(24)
$$
чНАМЕНАТЕЛЬ ЭТОГО ВЫРАЖЕНИЯ РАВЕН~$n^n/n!$. фЕЙСТВИТЕЛЬНО, КУБ,
ПОСТРОЕННЫЙ НА ВЕКТОРАХ~$(Y_1, Y_2,~\ldots,  Y_n)$ С~$0\le Y_j<n$, ИМЕЕТ
%% 72
ОБоЕМ~$n^n$; ЕГО НАДО РАЗДЕЛИТЬ НА $n!$~РАВНЫХ ЧАСТЕЙ, СООТВЕТСТВУЮЩИХ 
ВСЕМ ВОЗМОЖНЫМ УПОРЯДОЧЕНИЯМ~$Y_j$. шНТЕГРАЛ В ЧИСЛИТЕЛЕ НЕСКОЛЬКО СЛОЖНЕЕ,
НО ЕГО МОЖНО ВЗЯТЬ СПОСОБОМ, ОПИСАННЫМ В УПР.~17; В РЕЗУЛЬТАТЕ ПОЛУЧАЕТСЯ 
ОБЩАЯ ФОРМУЛА
$$
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)
$$
ЁАСПРЕДЕЛЕНИЕ~$K_n^-$ ТОЧНО ТАКОЕ ЖЕ. ЇОРМУЛА~(25) БЫЛА ВПЕРВЫЕ ПОЛУЧЕНА 
сИРНБАУМОМ И ЄИНГИ; ЕЕ МОЖНО ИСПОЛЬЗОВАТЬ В СЛУЧАЯХ, КОТОРЫЕ НЕ ОХВАЧЕНЫ В 
ТАБЛ.~2.

т ОРИГИНАЛЬНОЙ РАБОТЕ ёМИРНОВА ПОКАЗАНО, ЧТО
$$
\lim_{n\to\infty} P\{K_n^+\le s\}=1-e^{-2s^2} \rem{ПРИ~$s \ge 0$.}
\eqno (26)
$$
т СОЧЕТАНИИ С ФОРМУЛОЙ~(25) ЭТО ДАЕТ
$$
\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)
$$
эО ДОКАЗАТЬ ЭТО ПРЕДЕЛЬНОЕ СООТНОШЕНИЕ ОЧЕНЬ ТРУДНО. эАИБОЛЕЕ 
ЭЛЕМЕНТАРНОЕ ДОКАЗАТЕЛЬСТВО ПРИНАДЛЕЖИТ єИТТЛУ 
({\sl Annals of Mathematical Statistics,\/} {\bf 32} (1961), 499--505). 
юНО ОСНОВАНО НА СЛЕДУЮЩЕМ ПРИЕМЕ. т РЕЗУЛЬТАТЕ НЕКОТОРОГО УВЕЛИЧЕНИЯ И 
УМЕНЬШЕНИЯ~$\alpha$ В~(24) ВВОДЯТСЯ СПЕЦИАЛЬНЫМ ОБРАЗОМ 
МОДИФИЦИРОВАННЫЕ СТАТИСТИКИ, ДЛЯ КОТОРЫХ ВЕРОЯТНОСТИ ВЫЧИСЛЯЮТСЯ ТОЧНО, 
И ЗАТЕМ ПОКАЗЫВАЕТСЯ, ЧТО КАК ВЕРХНЯЯ, ТАК И НИЖНЯЯ ГРАНИЦЫ СТРЕМЯТСЯ 
К~$e^{-2s^2}$.

\excercises
\ex[00] ъАКУЮ СТРОКУ ИЗ ТАБЛИЦЫ РАСПРЕДЕЛЕНИЯ~$\chi^2$ НАДО ИСПОЛЬЗОВАТЬ 
ДЛЯ ВЫЯСНЕНИЯ, НЕ СЛИШКОМ ЛИ ВЕЛИКО ЗНАЧЕНИЕ~$V=7{7\over 48}$ В~(5)?

\ex[20] юПРЕДЕЛИТЬ ВЕРОЯТНОСТЬ~$p_s$ ПОЯВЛЕНИЯ СУММЫ~$s$ ДЛЯ~$2\le s \le 12$ 
ПРИ БРОСАНИИ ДВУХ КОСТЕЙ, УСТРОЕННЫХ СЛЕДУЮЩИМ ОБРАЗОМ: В ОДНОЙ ИЗ 
НИХ~$1$, А В ДРУГОЙ~$6$ ВЫПАДАЮТ РОВНО ВДВОЕ ЧАЩЕ, ЧЕМ ЛЮБОЕ ДРУГОЕ ЗНАЧЕНИЕ.

\rex[23] ъОСТИ, ОПИСАННЫЕ В ПРЕДЫДУЩЕМ УПРАЖНЕНИИ, БРОСАЛИСЬ 
144~РАЗА. сЫЛИ ПОЛУЧЕНЫ СЛЕДУЮЩИЕ РЕЗУЛЬТАТЫ:
\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
}

яРИМЕНИТЕ К \emph{ЭТИМ} ЗНАЧЕНИЯМ КРИТЕРИЙ~$\chi^2$, ПОЛЬЗУЯСЬ 
ВЕРОЯТНОСТЯМИ~(1), Т.~Е.\ ПРЕДПОЛАГАЯ, ЧТО КОСТИ ПРАВИЛЬНЫЕ. яОЗВОЛИТ ЛИ В 
ТАКОМ СЛУЧАЕ КРИТЕРИЙ~$\chi^2$ ОПРЕДЕЛИТЬ, ЧТО КОСТИ НЕПРАВИЛЬНЫЕ? хСЛИ 
НЕТ, ТО ОБоЯСНИТЕ ПОЧЕМУ.

\rex[23] эА САМОМ ДЕЛЕ АВТОР ПОЛУЧИЛ РЕЗУЛЬТАТЫ~(9) В ЭКСПЕРИМЕНТЕ~1,
ИМИТИРУЯ КОСТИ, ОДНА ИЗ КОТОРЫХ НОРМАЛЬНАЯ, А НА ДРУГОЙ ВЫПАДАЕТ 
ТОЛЬКО~$1$ ИЛИ~$6$ С РАВНЫМИ ВЕРОЯТНОСТЯМИ. тЫЧИСЛИТЕ ДЛЯ ЭТОГО СЛУЧАЯ 
ВЕРОЯТНОСТИ, КОТОРЫЕ ЗАМЕНЯТ~(1), И С ПОМОЩЬЮ КРИТЕРИЯ~$\chi^2$ ОПРЕДЕЛИТЕ,
СООТВЕТСТВУЮТ ЛИ РЕЗУЛЬТАТЫ ЭКСПЕРИМЕНТА ТАКОМУ УСТРОЙСТВУ КОСТЕЙ.

%% 73

\ex[22] яУСТЬ~$F(x)$---РАВНОМЕРНОЕ РАСПРЕДЕЛЕНИЕ, ИЗОБРАЖЕННОЕ НА РИС.~3,b. 
тЫЧИСЛИТЕ~$K^+_{20}$ И~$K^-_{20}$ ДЛЯ СЛЕДУЮЩИХ~20 ЭКСПЕРИМЕНТАЛЬНЫХ ЗНАЧЕНИЙ:
$$
\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
}
$$
юПРЕДЕЛИТЕ С ПОМОЩЬЮ КАЖДОГО ИЗ ЭТИХ ДВУХ КРИТЕРИЕВ, СООТВЕТСТВУЮТ 
ЛИ ЭКСПЕРИМЕНТАЛЬНЫЕ ДАННЫЕ РАВНОМЕРНОМУ РАСПРЕДЕЛЕНИЮ.

\ex[ь20] ЁАССМОТРИМ ФУНКЦИЮ~$F_n(x)$, ОПРЕДЕЛЕННУЮ ФОРМУЛОЙ~(10), 
ПРИ ФИКСИРОВАННОМ~$x$. ъАКОВА ВЕРОЯТНОСТЬ, ЧТО~$F_n(x)=s/n$ ДЛЯ ЗАДАННОГО 
ЦЕЛОГО~$s$? ъАКОВО СРЕДНЕЕ ЗНАЧЕНИЕ~$F_n(x)$? ъАКОВО СРЕДНЕКВАДРАТИЧНОЕ ОТКЛОНЕНИЕ?

\ex[ь15] яОКАЖИТЕ, ЧТО~$K^+_n$ И~$K^-_n$ НЕ МОГУТ БЫТЬ ОТРИЦАТЕЛЬНЫМИ. ъАКОВО
НАИБОЛЬШЕЕ ВОЗМОЖНОЕ ЗНАЧЕНИЕ~$K^+_n$?

\ex[00] т ТЕКСТЕ БЫЛ ОПИСАН ЭКСПЕРИМЕНТ, В КОТОРОМ В РЕЗУЛЬТАТЕ 
ОБРАБОТКИ ПОСЛЕДОВАТЕЛЬНОСТИ СЛУЧАЙНЫХ ЧИСЕЛ БЫЛО ПОЛУЧЕНО 20~ЗНАЧЕНИЙ 
СТАТИСТИКИ~$K^+_{10}$. ¤ТИ ДАННЫЕ, ИЗОБРАЖЕННЫЕ НА РИС.~4, БЫЛИ 
ИССЛЕДОВАНЫ С ПОМОЩЬЮ ъё-КРИТЕРИЯ. яОЧЕМУ ПРИ ЭТОМ ИСПОЛЬЗОВАЛИСЬ 
ТАБЛИЧНЫЕ ЗНАЧЕНИЯ ДЛЯ~$n=20$, А НЕ ДЛЯ~$n=10$?

\rex[20] т ОПИСАННОМ В ТЕКСТЕ ЭКСПЕРИМЕНТЕ НА ГРАФИК НАНОСИЛИСЬ 
20~ЗНАЧЕНИЙ~$K^+_{10}$, ВЫЧИСЛЕННЫХ С ПОМОЩЬЮ ТЕСТА "НАИБОЛЬШЕЕ ИЗ~5", 
КОТОРЫЙ ПРИМЕНЯЛСЯ К РАЗНЫМ ЧАСТЯМ СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ. ьОЖНО 
БЫЛО БЫ ВЫЧИСЛИТЬ ТАКЖЕ СООТВЕТСТВУЮЩИЕ 20~ЗНАЧЕНИЙ~$K^-_{10}$; ТАК КАК 
РАСПРЕДЕЛЕНИЯ СТАТИСТИК~$K^+_{10}$ И~$K^-_{10}$ СОВПАДАЮТ, МОЖНО БЫЛО БЫ 
ОБоЕДИНИТЬ ВСЕ 40~ЗНАЧЕНИЙ (20~ЗНАЧЕНИЙ~$K^+_{10}$ И 
20~ЗНАЧЕНИЙ~$K^-_{10}$ И ПРИМЕНИТЬ К НИМ ъё-КРИТЕРИЙ, ВЫЧИСЛИВ~$K^+_{40}$ 
И~$K^-_{40}$. юБСУДИТЕ ДОСТОИНСТВА ЭТОЙ ИДЕИ.

\rex[20] яРЕДПОЛОЖИМ, ЧТО РЕЗУЛЬТАТЫ $n$~ИСПЫТАНИЙ ОБРАБОТАНЫ С 
ПОМОЩЬЮ КРИТЕРИЯ~$\chi^2$ И ПОЛУЧЕНО ЗНАЧЕНИЕ~$V$. чАТЕМ ТЕ ЖЕ 
$n$~РЕЗУЛЬТАТОВ ОБРАБАТЫВАЮТСЯ ЕЩЕ РАЗ (ПОЛУЧАЕТСЯ, ЕСТЕСТВЕННО, ТО ЖЕ 
САМОЕ), ПОСЛЕ ЧЕГО ДАННЫЕ ОБОИХ ТЕСТОВ ОБоЕДИНЯЮТСЯ И РАССМАТРИВАЮТСЯ КАК 
ЕДИНЫЙ ТЕСТ С ЧИСЛОМ ИСПЫТАНИЙ~$2n$ (ПРИ ЭТОМ НАРУШАЕТСЯ ТРЕБОВАНИЕ 
НЕЗАВИСИМОСТИ ИСПЫТАНИЙ). ъАКАЯ СВЯЗЬ ИМЕЕТСЯ МЕЖДУ ВТОРЫМ И ПЕРВЫМ ЗНАЧЕНИЕМ~$V$?

\ex[20] ЁЕШИТЕ УПР.~10, ЗАМЕНИВ КРИТЕРИЙ~$\chi^2$ НА КРИТЕРИЙ ъё.

\ex[M26] яУСТЬ ПРИ ПРИМЕНЕНИИ КРИТЕРИЯ~$\chi^2$ К РЕЗУЛЬТАТАМ 
$n$~ИСПЫТАНИЙ ПРЕДПОЛАГАЕТСЯ, ЧТО $p_s$---ВЕРОЯТНОСТЬ ПОПАДАНИЯ В 
КАТЕГОРИЮ~$s$. фОПУСТИМ, ЧТО В ДЕЙСТВИТЕЛЬНОСТИ ВЕРОЯТНОСТЬ ПОПАДАНИЯ В 
КАТЕГОРИЮ~$s$ РАВНА~$q_s\ne p_s$ (СМ.~УПР.~3). ъОНЕЧНО, ЖЕЛАТЕЛЬНО, ЧТОБЫ 
КРИТЕРИЙ~$\chi^2$ ПОЗВОЛИЛ ОБНАРУЖИТЬ, ЧТО ПЕРВОНАЧАЛЬНОЕ ПРЕДПОЛОЖЕНИЕ 
БЫЛО НЕВЕРНЫМ. яОКАЖИТЕ, ЧТО ПРИ ДОСТАТОЧНО БОЛЬШИХ~$n$ ЭТО 
ДЕЙСТВИТЕЛЬНО БУДЕТ ОБНАРУЖЕНО. фОКАЖИТЕ ТАКЖЕ АНАЛОГИЧНЫЙ РЕЗУЛЬТАТ ДЛЯ ъё-КРИТЕРИЯ.

\ex[ь24] яОКАЖИТЕ, ЧТО ФОРМУЛА~(13) ЭКВИВАЛЕНТНА ФОРМУЛЕ~(11).

\rex[ть26] яУСТЬ ВЕЛИЧИНЫ~$Z_s$ ЗАДАНЫ ВЫРАЖЕНИЕМ~(18). яОКАЖИТЕ 
НЕПОСРЕДСТВЕННО С ПОМОЩЬЮ ФОРМУЛЫ ёТЕРЛИНГА, ЧТО СПРАВЕДЛИВО 
СЛЕДУЮЩЕЕ РАВЕНСТВО ДЛЯ ПОЛИНОМИАЛЬНОГО РАСПРЕДЕЛЕНИЯ:
$$
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}),
$$
ЕСЛИ $Z_1$, $Z_2$,~\dots, $Z_k$ ОГРАНИЧЕНЫ ПРИ~$n\to\infty$. (ЄАКОЙ ПОДХОД 
ПОЗВОЛЯЕТ ОБОСНОВАТЬ КРИТЕРИЙ~$\chi^2$, БОЛЬШЕ ОПИРАЯСЬ НА ПЕРВООСНОВЫ И 
ПРОВОДЯ МЕНЬШЕ ВЫКЛАДОК, ЧЕМ ПРИ ПОДХОДЕ, ИСПОЛЬЗОВАННОМ В ТЕКСТЕ.)

\ex[ть24] юБЫЧНО ПОЛЯРНЫЕ КООРДИНАТЫ В ДВУМЕРНОМ ПРОСТРАНСТВЕ ЗАДАЮТСЯ 
ВЫРАЖЕНИЯМИ~$x=r\cos\theta$ И~$y=r\sin\theta$. яРИ ИНТЕГРИРОВАНИИ 
ИСПОЛЬЗУЕТСЯ РАВЕНСТВО~$dx\,dy=r\,dr\,d\theta$. т ОБЩЕМ СЛУЧАЕ ДЛЯ 
$n\hbox{-МЕРНОГО}$ ПРОСТРАНСТВА МОЖНО ПОЛОЖИТЬ
$$
\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
яОКАЖИТЕ, ЧТО В ЭТОМ СЛУЧАЕ
$$
 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[ть35] юБОБЩИТЕ ТЕОРЕМУ~1.2.11.3A ТАК, ЧТОБЫ ОПРЕДЕЛИТЬ ЗНАЧЕНИЕ
$$
\gamma(x+1, x+z\sqrt{2x}+y)/\Gamma(x+1)
$$
ПРИ БОЛЬШИХ~$x$ И ФИКСИРОВАННЫХ~$y$, $z$. юПУСТИТЕ ЧЛЕНЫ~$O(1/x)$. ё 
ПОМОЩЬЮ ПОЛУЧЕННОГО РЕЗУЛЬТАТА НАЙДИТЕ ПРИБЛИЖЕННОЕ РЕШЕНИЕ~$t$ УРАВНЕНИЯ
$$
\gamma\left({\nu\over 2}, {t\over 2}\right) \bigg/ \Gamma\left({\nu\over 2}\right)=p
$$
ПРИ БОЛЬШИХ~$\nu$ И ФИКСИРОВАННОМ~$p$; ТАКИМ ОБРАЗОМ БУДЕТ НАЙДЕНО 
ОБоЯСНЕНИЕ АСИМПТОТИЧЕСКИХ ФОРМУЛ, ПРИВЕДЕННЫХ В ТАБЛ.~1. 
(\emph{єКАЗАНИЕ:} СМ.~УПР.~1.2.11.3-8.)

\ex[ть26] яУСТЬ~$t$---НЕКОТОРОЕ ДЕЙСТВИТЕЛЬНОЕ ЧИСЛО, И ПУСТЬ ПРИ~$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,
$$
А~$P_{00}(x)=1$. фОКАЖИТЕ СЛЕДУЮЩИЕ СООТНОШЕНИЯ:
{\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{ПРИ $1\le k \le n$;}
$
 \hiddenpar
\item{d)}ПОЛУЧИТЕ ОБЩУЮ ФОРМУЛУ ДЛЯ~$P_{nk}(x)$ И ИСПОЛЬЗУЙТЕ ЕЕ ДЛЯ ВЫВОДА ФОРМУЛЫ~(24).
\medskip}

\ex[M20] фАЙТЕ "ПРОСТОЕ" ОБоЯСНЕНИЕ, ПОЧЕМУ РАСПРЕДЕЛЕНИЯ ВЕЛИЧИН~$K^+_n$ 
И~$K^-_n$ ОДИНАКОВЫ.

\ex[ть48] ЁАЗРАБОТАЙТЕ КРИТЕРИИ, ПОДОБНЫЕ КРИТЕРИЮ ъОЛМОГОРОВА-ёМИРНОВА, 
ДЛЯ МНОГОМЕРНЫХ РАСПРЕДЕЛЕНИЙ~$F(x_1,~\ldots, x_r)=P\{X_1\le x_1,~\ldots, X_r\le x_r\}$. (юНИ МОГУТ ПОНАДОБИТЬСЯ, НАПРИМЕР, В СВЯЗИ С ТЕСТОМ  
ПРОВЕРКИ СЕРИИ, РАССМОТРЕННЫМ В СЛЕДУЮЩЕМ ПУНКТЕ.)

\ex[ть50] яОЛУЧИТЕ ДАЛЬНЕЙШУЮ ИНФОРМАЦИЮ ОБ АСИМПТОТИЧЕСКОМ ЗНАЧЕНИИ 
ВЕЛИЧИНЫ В ЛЕВОЙ ЧАСТИ РАВЕНСТВА~(27) ПРИ БОЛЬШИХ~$n$. [\emph{чАМЕЧАНИЯ.} 
¤МПИРИЧЕСКИЕ ДАННЫЕ ПОКАЗЫВАЮТ, ЧТО ЭТА ВЕЛИЧИНА МЕНЬШЕ~$e^{-2s^2}$ ПРИ 
ЛЮБЫХ~$n$, НО ТОЧНО ЭТО НЕИЗВЕСТНО. ёОГЛАСНО РАБОТЕ єИТТЛА, ОНА ДОЛЖНА 
НАХОДИТЬСЯ ГДЕ-ТО МЕЖДУ~$\exp(-2s^2-(2s+s^3)/\sqrt{n})$ 
И~$\exp(-2s^2+3.83 s^3/\sqrt{n})$. тЫРАЖЕНИЯ, ПРИВЕДЕННЫЕ В ТАБЛ.~2 ДЛЯ 
БОЛЬШИХ~$n$, ПОЛУЧЕНЫ ЭМПИРИЧЕСКИ НА ОСНОВЕ ОГРАНИЧЕННОГО НАБОРА ДАННЫХ; 
БЫЛО БЫ ПОЛЕЗНО ПОЛУЧИТЬ ТЕОРЕТИЧЕСКИ БОЛЕЕ НАДЕЖНЫЕ ДАННЫЕ.]

\ex[ь40] їОТЯ, КАК БЫЛО УКАЗАНО В ТЕКСТЕ, КРИТЕРИЙ ъОЛМОГОРОВА- ёМИРНОВА 
ПРИМЕНЯЕТСЯ В ТЕХ СЛУЧАЯХ, КОГДА ФУНКЦИЯ РАСПРЕДЕЛЕНИЯ~$F(x)$ НЕПРЕРЫВНА,
МОЖНО, КОНЕЧНО, ПОПРОБОВАТЬ ВЫЧИСЛИТЬ~$K^+_n$ И~$K^-_n$ ДЛЯ 
ДИСКРЕТНЫХ РАСПРЕДЕЛЕНИЙ. яРОАНАЛИЗИРУЙТЕ ВЕРОЯТНОСТНОЕ ПОВЕДЕНИЕ~$K^+_n$ 
И~$K^-_n$ ДЛЯ РАЗНЫХ ТИПОВ ДИСКРЕТНЫХ РАСПРЕДЕЛЕНИЙ~$F(x)$. ёРАВНИТЕ 
ЭФФЕКТИВНОСТЬ ТАКОГО ТЕСТА И КРИТЕРИЯ~$\chi^2$  В КОНКРЕТНЫХ СЛУЧАЯХ.

\ex[ть42] юБСУДИТЕ ИСПОЛЬЗОВАНИЕ "ОТНОШЕНИЯ НАИБОЛЬШЕГО ПРАВДОПОДОБИЯ" В 
КАЧЕСТВЕ АЛЬТЕРНАТИВЫ КРИТЕРИЯ~$\chi^2$ ПРИ ПРОВЕРКЕ ДАТЧИКОВ СЛУЧАЙНЫХ 
ЧИСЕЛ; ПРОВЕДИТЕ ЭКСПЕРИМЕНТЫ, ПРИМЕНЯЯ ЭТИ ДВА ТИПА СТАТИСТИК.

%% 75

\subsubchap{¤МПИРИЧЕСКИЕ ТЕСТЫ} %3.3.2
т ЭТОМ ПУНКТЕ БУДУТ ОПИСАНЫ ДЕВЯТЬ ТИПОВ СПЕЦИАЛИЗИРОВАННЫХ ТЕСТОВ, 
КОТОРЫЕ ПРИМЕНЯЮТСЯ ДЛЯ ПРОВЕРКИ СЛУЧАЙНОСТИ ЧИСЛОВЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ. 
юПИСАНИЕ КАЖДОГО ТЕСТА СОСТОИТ ИЗ ДВУХ ЧАСТЕЙ: (a)~КРАТКОЙ ИНСТРУКЦИИ ПО 
ПРИМЕНЕНИЮ ТЕСТА И (b)~ИЗЛОЖЕНИЯ ТЕОРИИ, ЛЕЖАЩЕЙ В ОСНОВЕ ТЕСТА. 
(ўИТАТЕЛИ С НЕДОСТАТОЧНОЙ МАТЕМАТИЧЕСКОЙ ПОДГОТОВКОЙ МОГУТ ПРИ 
ЖЕЛАНИИ ПРОПУСКАТЬ ТЕОРЕТИЧЕСКИЕ РАССУЖДЕНИЯ. эАОБОРОТ, ЧИТАТЕЛЯ 
СО СКЛОННОСТЬЮ К МАТЕМАТИКЕ МОГУТ ЗАИНТЕРЕСОВАТЬ САМИ ПО 
СЕБЕ КОМБИНАТОРНЫЕ ЗАДАЧИ, ВОЗНИКАЮЩИЕ ЗДЕСЬ, ДАЖЕ ЕСЛИ ОН НЕ СОБИРАЕТСЯ 
ЗАНИМАТЬСЯ ПРОВЕРКОЙ ДАТЧИКОВ СЛУЧАЙНЫХ ЧИСЕЛ.)

ъАЖДЫЙ ТЕСТ ПРИМЕНЯЕТСЯ К ПОСЛЕДОВАТЕЛЬНОСТИ СЛУЧАЙНЫХ ЧИСЕЛ
$$
\<U_n>=U_0, U_1, U_2, \ldots\,,
\eqno(1)
$$
КОТОРЫЕ ДОЛЖНЫ БЫТЬ РАСПРЕДЕЛЕНЫ РАВНОМЕРНО МЕЖДУ НУЛ╕М И ЕДИНИЦЕЙ. 
эЕКОТОРЫЕ ТЕСТЫ ПРЕДНАЗНАЧЕНЫ В ПЕРВУЮ ОЧЕРЕДЬ ДЛЯ ПРОВЕРКИ ЦЕЛОЧИСЛЕННЫХ 
ПОСЛЕДОВАТЕЛЬНОСТЕЙ, А НЕ ПОСЛЕДОВАТЕЛЬНОСТЕЙ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ 
ТИПА~(1). т ЭТОМ СЛУЧАЕ ПРОВЕРКЕ ПОДВЕРГАЕТСЯ ВСПОМОГАТЕЛЬНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ
$$
\<Y_n>=Y_0, Y_1, Y_2, \ldots\,,
\eqno(2)
$$
КОТОРАЯ ОПРЕДЕЛЯЕТСЯ СЛЕДУЮЩИМ ОБРАЗОМ:
$$
Y_n=\floor{d U_n}.
\eqno(3)
$$
тХОДЯЩИЕ В ЭТУ ПОСЛЕДОВАТЕЛЬНОСТЬ ЦЕЛЫЕ ЧИСЛА РАСПРЕДЕЛЕНЫ РАВНОМЕРНО 
МЕЖДУ~$0$ И~$d-1$, ЕСЛИ ЧИСЛА~(1) РАСПРЕДЕЛЕНЫ РАВНОМЕРНО МЕЖДУ~$0$ 
И~$1$. чНАЧЕНИЕ~$d$ МОЖЕТ БЫТЬ ЛЮБЫМ; НАПРИМЕР, НА МАШИНЕ, РАБОТАЮЩЕЙ В 
ДВОИЧНОЙ СИСТЕМЕ, МОЖНО ВЫБРАТЬ~$d=64=2^6$; ТОГДА~$Y_n$ БУДУТ ОПРЕДЕЛЯТЬСЯ 
ШЕСТЬЮ НАИБОЛЕЕ ЗНАЧИМЫМИ РАЗРЯДАМИ В ДВОИЧНОМ ПРЕДСТАВЛЕНИИ~$U_n$. 
ўТОБЫ ТЕСТ БЫЛ ПРЕДСТАВИТЕЛЬНЫМ, ЗНАЧЕНИЕ~$d$ ДОЛЖНО БЫТЬ ДОСТАТОЧНО 
БОЛЬШИМ, НО НЕ СЛИШКОМ, ЧТОБЫ ПРИ РЕАЛИЗАЦИИ ТЕСТА НА МАШИНЕ НЕ 
ВОЗНИКАЛО ЗАТРУДНЕНИЙ.

тВЕДЕННЫЕ ЗДЕСЬ ОБОЗНАЧЕНИЯ~$U_n$, $Y_n$ И~$d$ БУДУТ ИСПОЛЬЗОВАТЬСЯ В 
ДАННОМ РАЗДЕЛЕ НЕОДНОКРАТНО. чНАЧЕНИЕ~$d$ МОЖЕТ БЫТЬ РАЗНЫМ В РАЗНЫХ ТЕСТАХ.

\section{A.~яРОВЕРКА РАВНОМЕРНОСТИ (ПРОВЕРКА ЧАСТОТ)}. яЕРВОЕ ТРЕБОВАНИЕ, 
ПРЕДоЯВЛЯЕМОЕ К ПОСЛЕДОВАТЕЛЬНОСТИ~(1), ЗАКЛЮЧАЕТСЯ В ТОМ, ЧТОБЫ 
ЧИСЛА~$U_n$ БЫЛИ ДЕЙСТВИТЕЛЬНО РАВНОМЕРНО РАСПРЕДЕЛЕНЫ МЕЖДУ НУЛЕМ И 
ЕДИНИЦЕЙ. яРОВЕРИТЬ РАВНОМЕРНОСТЬ МОЖНО ДВУМЯ СПОСОБАМИ: (a)~С~ПОМОЩЬЮ 
КРИТЕРИЯ ъОЛМОГОРОВА---ёМИРНОВА, ВЗЯВ~$F(x)=x$ ПРИ~$0\le x \le 1$; 
(b)~ВЫБРАТЬ КАКОЕ-НИБУДЬ УДОБНОЕ ЗНАЧЕНИЕ~$d$, НАПРИМЕР~$100$, НА МАШИНЕ,
РАБОТАЮЩЕЙ В ДЕСЯТИЧНОЙ
%% 76
СИСТЕМЕ, ЛИБО~$64$ И~$128$ НА МАШИНЕ, РАБОТАЮЩЕЙ В ДВОИЧНОЙ СИСТЕМЕ, 
ПОСЛЕ ЧЕГО ИСПОЛЬЗОВАТЬ ПОСЛЕДОВАТЕЛЬНОСТЬ~(2) ВМЕСТО~(1). чАТЕМ ДЛЯ 
КАЖДОГО ЦЕЛОГО~$r$, $0\le r < d$, ПОДСЧИТАТЬ ЧИСЛО ЗНАЧЕНИЙ~$Y_j=r$ 
ПРИ~$0 \le j < n$ И ПРИМЕНИТЬ КРИТЕРИЙ~$\chi^2$ С~$k=d$ И ВЕРОЯТНОСТЯМИ~$p_s=1/d$.

юБОСНОВАНИЕ ОБОИХ ПОДХОДОВ МОЖНО НАЙТИ В ПРЕДЫДУЩЕМ РАЗДЕЛЕ.

\section{B.~яРОВЕРКА СЕРИЙ}. яРОВЕРЯЕТСЯ РАВНОМЕРНОСТЬ И НЕЗАВИСИМОСТЬ ПАР 
СЛЕДУЮЩИХ ДРУГ ЗА ДРУГОМ СЛУЧАЙНЫХ ЧИСЕЛ. фЛЯ ЭТОГО ПОДСЧИТЫВАЕТСЯ, 
СКОЛЬКО РАЗ ВСТРЕЧАЕТСЯ КАЖДАЯ ПАРА~$(Y_{2j}, Y_{2j+1})=(q, r)$ ПРИ~$0 \le j < n$. 
тЕЛИЧИНЫ~$q$ И~$m$ МОГУТ ПРИНИМАТЬ ЛЮБЫЕ ЗНАЧЕНИЯ ОТ~$0$ ДО~$d$. 
чАТЕМ ПРИМЕНЯЕТСЯ КРИТЕРИЙ~$\chi^2$ С ЧИСЛОМ КАТЕГОРИЙ~$k=d^2$ И РАВНЫМИ 
ВЕРОЯТНОСТЯМИ~$1/d^2$ ВО ВСЕХ КАТЕГОРИЯХ. чНАЧЕНИЕ~$d$ ВЫБИРАЕТСЯ ИЗ ТЕХ 
ЖЕ СООБРАЖЕНИЙ, ЧТО И В ПРЕДЫДУЩЕМ ТЕСТЕ, НО В ДАННОМ СЛУЧАЕ ОНО ДОЛЖНО 
БЫТЬ НЕСКОЛЬКО МЕНЬШЕ, ТАК КАК ПРИМЕНЯТЬ КРИТЕРИЙ~$\chi^2$ СЛЕДУЕТ ПРИ 
ЗНАЧЕНИЯХ~$n$, СУЩЕСТВЕННО ПРЕВЫШАЮЩИХ~$k$ (СКАЖЕМ, ПО КРАЙНЕЙ МЕРЕ 
ПРИ~$n>5d^2$).

юЧЕВИДНО, ЧТО МОЖНО ОБОБЩИТЬ ЭТОТ ТЕСТ НА ТРОЙКИ, ЧЕТВЕРКИ И~Т.~Д.\ 
(СМ.~УПР.~2); ОДНАКО ЗНАЧЕНИЯ~$d$ ДОЛЖНЫ БЫТЬ ПРИ ЭТОМ РЕЗКО УМЕНЬШЕНЫ, 
ЧТОБЫ ЧИСЛО КАТЕГОРИЙ НЕ ПОЛУЧАЛОСЬ СЛИШКОМ БОЛЬШИМ. яОЭТОМУ ПРИ 
ОБоЕДИНЕНИИ ЧЕТЫРЕХ И БОЛЕЕ ЭЛЕМЕНТОВ ИСПОЛЬЗУЮТСЯ МЕНЕЕ ТОЧНЫЕ ТЕСТЫ, 
ТАКИЕ, КАК "НАИБОЛЬШЕЕ ИЗ~$t$" ИЛИ ПРОВЕРКА КОМБИНАЦИЙ (ОНИ БУДУТ ОПИСАНЫ НИЖЕ).

юТМЕТИМ, ЧТО В ЭТОМ ТЕСТЕ В $n$~ИСПЫТАНИЯХ ИСПОЛЬЗУЕТСЯ $2n$~ЧИСЕЛ 
ПОСЛЕДОВАТЕЛЬНОСТИ~(2). сЫЛО БЫ ОШИБКОЙ СОСТАВЛЯТЬ В ДАННОМ СЛУЧАЕ 
ПАРЫ~$(Y_0, Y_1)$, $(Y_1, Y_2)$,~\dots, $(Y_{n-1}, Y_n)$; ПОНЯТНО ЛИ 
ЧИТАТЕЛЮ, ПОЧЕМУ? фЛЯ ПАР~$(Y_{2j+1}, Y_{2j+2})$ МОЖНО БЫЛО БЫ СОСТАВИТЬ 
СПЕЦИАЛЬНЫЙ ТЕСТ И ПРОВЕРЯТЬ КАЖДУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ С ПОМОЩЬЮ ОБОИХ 
ТЕСТОВ. ё ДРУГОЙ СТОРОНЫ, КАК ПОКАЗАЛ уУД, 
({\sl Annals af Mathematical Statistics,\/} {\bf 28}, (1957), 262--264), 
ЕСЛИ~$d$---ПРОСТОЕ ЧИСЛО, ИСПОЛЬЗУЮТСЯ ПАРЫ~$(Y_0, Y_1)$, $(Y_1, Y_2)$,~\dots, 
$(Y_{n-1}, Y_n)$ И С ПОМОЩЬЮ ОБЫЧНОГО $\chi^2\hbox{-МЕТОДА}$ ВЫЧИСЛЯЮТСЯ КАК 
СТАТИСТИКА~$V_2$, СООТВЕТСТВУЮЩАЯ ПРОВЕРКЕ СЕРИЙ, \emph{ТАК И} СТАТИСТИКА~$V_1$ 
ДЛЯ ПРОВЕРКИ РАВНОМЕРНОСТИ~$Y_0$, $Y_1$,~\dots, $Y_{n-1}$ С ОДНИМ И ТЕМ ЖЕ 
ЗНАЧЕНИЕМ~$d$, ТО ПРИ БОЛЬШИХ~$n$ РАЗНОСТЬ~$V_2-2V_1$ БУДЕТ ИМЕТЬ 
РАСПРЕДЕЛЕНИЕ~$\chi^2$ С $(d-1)^2$~СТЕПЕНЯМИ СВОБОДЫ, ХОТЯ~$V_2$ В ДАННОМ 
СЛУЧАЕ ИМЕЕТ РАСПРЕДЕЛЕНИЕ, \emph{ОТЛИЧНОЕ} ОТ РАСПРЕДЕЛЕНИЯ~$\chi^2$ С 
$d^2-1$~СТЕПЕНЯМИ СВОБОДЫ.

\section{C.~яРОВЕРКА ИНТЕРВАЛОВ}. т ЭТОМ ТЕСТЕ ПРОВЕРЯЕТСЯ ДЛИНА 
ИНТЕРВАЛОВ МЕЖДУ ПОЯВЛЕНИЯМИ ЗНАЧЕНИЙ~$U_j$, ПРИНАДЛЕЖАЩИХ НЕКОТОРОМУ 
ЗАДАННОМУ ОТРЕЗКУ. хСЛИ~$\alpha$ И~$\beta$---ДВА ДЕЙСТВИТЕЛЬНЫХ ЧИСЛА, 
ПРИЧЕМ~$0\le\alpha<\beta\le 1$, ТО ПОДСЧИТЫВАЮТСЯ ДЛИНЫ 
ПОСЛЕДОВАТЕЛЬНОСТЕЙ~$U_j$, $U_{j+1}$,~\dots, $U_{j+r}$, В КОТОРЫХ 
ТОЛЬКО~$U_{j+r}$
%% 77
ЛЕЖИТ МЕЖДУ~$\alpha$ И~$\beta$. (ЄАКАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ ИЗ 
$r+1$~ЧИСЕЛ ОПРЕДЕЛЯЕТ ИНТЕРВАЛ ДЛИНЫ~$r$.)

\alg G.(тЫЧИСЛЕНИЕ ДЛИН ИНТЕРВАЛОВ.) ёЛЕДУЮЩИЙ АЛГОРИТМ ПОЗВОЛЯЕТ 
ОПРЕДЕЛИТЬ ЧИСЛО ИНТЕРВАЛОВ ДЛИНЫ~$0$, $1$,~\dots, $t-1$ И ПОЛНОЕ ЧИСЛО 
ИНТЕРВАЛОВ БОЛЬШЕЙ ДЛИНЫ~($\ge t$) В ПОСЛЕДОВАТЕЛЬНОСТИ~(1). ЁАСЧЕТ 
ПРОДОЛЖАЕТСЯ ДО ТЕХ ПОР, ПОКА НЕ БУДЕТ ЗАРЕГИСТРИРОВАНО ВСЕГО $n$~ИНТЕРВАЛОВ.
\picture{
 ЁИС~ 6. ЁЕАЛИЗАЦИЯ ПРОВЕРКИ ИНТЕРВАЛОВ (ПОДОБНЫЕ АЛГОРИТМЫ ПРИМЕНЯЮТСЯ И ПРИ 
 РЕАЛИЗАЦИИ ТЕСТОВ СОБИРАТЕЛЯ КУПОНОВ И ПРОВЕРКИ НА МОНОТОННОСТЬ).
}

\st[эАЧАЛЬНАЯ УСТАНОВКА.] єСТАНОВИТЬ~$j\asg -1$, $s\asg 0$, А 
ТАКЖЕ~$|COUNT|[r]\asg 0$ ДЛЯ~$0\le r \le t$.

\st[$r=0$.] єСТАНОВИТЬ~$r\asg0$.

\st[$\alpha \le U_j < \beta$?] єВЕЛИЧИТЬ~$j$ НА~$1$. хСЛИ~$U_j\ge\alpha$ 
И~$U_j<\beta$, ПЕРЕЙТИ НА~\stp{5}.

\st[єВЕЛИЧИТЬ~$r$.] єВЕЛИЧИТЬ~$r$ НА ЕДИНИЦУ, ЗАТЕМ ВЕРНУТЬСЯ НА~\stp{3}.

\st[ЁЕГИСТРАЦИЯ ДЛИНЫ ИНТЕРВАЛА.] (юБНАРУЖЕН ИНТЕРВАЛ ДЛИНЫ~$r$.) 
яРИ~$r\ge t$ ПРИБАВИТЬ~$1$ К~$|COUNT|[t]$, В ПРОТИВНОМ СЛУЧАЕ 
ПРИБАВИТЬ~$1$ К~$|COUNT|[r]$.

\st[юБНАРУЖЕНО $n$~ИНТЕРВАЛОВ?] яРИБАВИТЬ~$1$ К~$s$. хСЛИ~$s<n$, ВЕРНУТЬСЯ НА~\stp{2}.
\algend

яОСЛЕ ВЫПОЛНЕНИЯ ЭТОГО АЛГОРИТМА $k=t+1$~ЗНАЧЕНИЙ $|COUNT|[0]$, 
$|COUNT|[1]$,~\dots, $|COUNT|[t]$ ОБРАБАТЫВАЮТСЯ С ПОМОЩЬЮ 
КРИТЕРИЯ~$\chi^2$ С ИСПОЛЬЗОВАНИЕМ СЛЕДУЮЩИХ ЗНАЧЕНИЙ ВЕРОЯТНОСТЕЙ:
$$
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)
$$
чДЕСЬ $p=\beta-\alpha$~РАВНО ВЕРОЯТНОСТИ ТОГО, ЧТО~$\alpha\le U_j<\beta$.  
чНАЧЕНИЯ~$n$ И~$t$ ОБЫЧНО ВЫБИРАЮТСЯ ТАКИМ ОБРАЗОМ, ЧТОБЫ 
СРЕДНИЕ ЗНАЧЕНИЯ~$|COUNT|[r]$ БЫЛИ НЕ МЕНЬШЕ~5.

ўАСТО ПОЛАГАЮТ ЛИБО~$\alpha=0$, ЛИБО~$\beta=1$, ЧТОБЫ УПРОСТИТЬ
ШАГ~G3 ОПИСАННОГО АЛГОРИТМА. ўАСТНЫЕ 
СЛУЧАИ~$(\alpha, \beta)=\left(0, {1\over 2} \right)$ 
%% 78
ИЛИ~$\left({1\over 2}, 1\right)$ ИНОГДА НАЗЫВАЮТ ПРОВЕРКОЙ ОТКЛОНЕНИЙ ОТ 
СРЕДНЕГО ВНИЗ ИЛИ ВВЕРХ.

ЇОРМУЛЫ~(4) ДЛЯ ВЕРОЯТНОСТЕЙ ВЫВОДЯТСЯ ЛЕГКО; МЫ ПРЕДОСТАВЛЯЕМ ЧИТАТЕЛЮ 
ВОЗМОЖНОСТЬ ПРОДЕЛАТЬ ЭТО САМОСТОЯТЕЛЬНО.
юТМЕТИМ, ЧТО В ПРИВЕДЕННОМ ЗДЕСЬ АЛГОРИТМЕ ВЫЧИСЛЯЮТСЯ ДЛИНЫ ЗАДАННОГО 
ЧИСЛА $n$~\emph{ИНТЕРВАЛОВ}; ПОСЛЕДОВАТЕЛЬНОСТЬ ПРИ ЭТОМ МОЖЕТ ПОЛУЧИТЬСЯ 
ПРОИЗВОЛЬНОЙ ДЛИНЫ. ьОЖНО, НАОБОРОТ ФИКСИРОВАТЬ ДЛИНУ ПРОВЕРЯЕМОЙ 
ПОСЛЕДОВАТЕЛЬНОСТИ (СМ.~УПР.~5).

\section{D.~яОКЕР-ТЕСТ (ПРОВЕРКА КОМБИНАЦИЙ)}. т "КЛАССИЧЕСКОМ" 
ПОКЕР-ТЕСТЕ РАССМАТРИВАЮТСЯ $n$~ГРУПП ИЗ ПЯТИ СЛЕДУЮЩИХ ДРУГ ЗА ДРУГОМ 
ЦЕЛЫХ ЧИСЕЛ~$(Y_{5j}, Y_{5j+1}$,~\dots, $Y_{5j+4})$, $0\le j < n$. 
тЫДЕЛЯЮТСЯ СЛЕДУЮЩИЕ 7~ТИПОВ КОМБИНАЦИЙ:
\ctable{
 \hfil$#$\bskip&\bskip#\hfil\cr
 abcde & (ВСЕ РАЗНЫЕ),\cr
 aabcd & (ОДНА ПАРА),\cr
 aabbc & (ДВЕ ПАРЫ),\cr
 aaabc & (ТРИ ОДНОГО ВИДА),\cr
 aaabb & (ПОЛНЫЙ СБОР),\cr
 aaaab & (ЧЕТЫРЕ ОДНОГО ВИДА),\cr
 aaaaa & (ПЯТЬ ОДНОГО ВИДА).\cr
}
ё ПОМОЩЬЮ КРИТЕРИЯ~$\chi^2$ ПРОВЕРЯЕТСЯ, СООТВЕТСТВУЮТ ЛИ 
ЧАСТОТЫ КОМБИНАЦИИ ВЕРОЯТНОСТЯМ.

фЛЯ ОБЛЕГЧЕНИЯ ПРОГРАММИРОВАНИЯ ЖЕЛАТЕЛЬНО НЕСКОЛЬКО УПРОСТИТЬ ЭТОТ ТЕСТ. 
їОРОШИМ КОМПРОМИССОМ МОЖЕТ СЛУЖИТЬ ПОДСЧЕТ КОЛИЧЕСТВА НЕСОВПАДАЮЩИХ ЧИСЕЛ 
В КАЖДОЙ ПЯТЕРКЕ ўИСЛО КАТЕГОРИЙ ПРИ ЭТОМ РАВНО ПЯТИ:
$$
\eqalign{
\hbox{5 РАЗНЫХ}&=\hbox{ВСЕ РАЗНЫЕ;}\cr
\hbox{4 РАЗНЫХ}&=\hbox{ОДНА ПАРА;}\cr
\hbox{3 РАЗНЫХ}&=\hbox{ДВЕ ПАРЫ, ИЛИ ТРИ ОДНОГО ВИДА;}\cr
\hbox{2 РАЗНЫХ}&=\hbox{ПОЛНЫЙ СБОР ИЛИ ЧЕТЫРЕ ОДНОГО ВИДА;}\cr
\hbox{НЕТ РАЗНЫХ} &= \hbox{ПЯТЬ ОДНОГО ВИДА.}\cr
}
$$
ЄЕСТ ПРИ ЭТОМ ПОЧТИ НЕ УХУДШАЕТСЯ, А АЛГОРИТМ СУЩЕСТВЕННО УПРОЩАЕТСЯ.

т ОБЩЕМ СЛУЧАЕ МОЖНО РАССМОТРЕТЬ $n$~ГРУПП ПО~$k$ СЛЕДУЮЩИХ ПОДРЯД ЧИСЕЛ И 
ПОДСЧИТЫВАТЬ ЧИСЛО ГРУПП, В КОТОРЫХ ИМЕЕТСЯ $r$~РАЗНЫХ ЧИСЕЛ. чАТЕМ 
ПРИМЕНЯТЬ КРИТЕРИЙ~$\chi^2$ С ВЕРОЯТНОСТЯМИ
$$
p_r={d(d-1)\ldots(d-r+1) \over d^k} \Stir{k}{r}.
\eqno(5)
$$
(ўИСЛА ёТИРЛИНГА~$\Stir{k}{r}$ БЫЛИ ОПРЕДЕЛЕНЫ В П.~1.2.6; ТАМ 
ЖЕ ПРИВЕДЕНЫ ФОРМУЛЫ, ПО КОТОРЫМ ИХ МОЖНО ПОСЧИТАТЬ.) ЄАК КАК ПРИ~$r=1$ 
ИЛИ~$2$ ВЕРОЯТНОСТЬ~$p_r$ ОЧЕНЬ МАЛА, ЭТИ КАТЕГОРИИ МОЖНО ОБоЕДИНИТЬ.

%% 79
яРИВЕДЕННАЯ ВЫШЕ ФОРМУЛА ДЛЯ~$p_r$ ПОЛУЧАЕТСЯ СЛЕДУЮЩИМ ОБРАЗОМ. 
тЫЧИСЛЯЕТСЯ, СКОЛЬКО ГРУПП ПО $k$~ЧИСЕЛ, КАЖДОЕ ИЗ КОТОРЫХ МОЖЕТ ПРИНИМАТЬ 
ЗНАЧЕНИЯ ОТ~$0$ ДО~$d-1$, СОДЕРЖАТ $r$~РАЗНЫХ ЭЛЕМЕНТОВ. чАТЕМ РЕЗУЛЬТАТЫ 
ДЕЛЯТСЯ НА~$d^k$---ОБЩЕЕ КОЛИЧЕСТВО РАЗЛИЧНЫХ ГРУПП. ЄАК КАК 
$d(d-1)\ldots(d-r+1)$~ЕСТЬ ЧИСЛО РАЗМЕЩЕНИЙ ИЗ $d$~ЭЛЕМЕНТОВ ПО~$r$, 
ОСТАЕТСЯ ТОЛЬКО ПОКАЗАТЬ, ЧТО~$\Stir{k}{r}$---ЧИСЛО СПОСОБОВ, КОТОРЫМИ 
МОЖНО РАСПРЕДЕЛИТЬ
$k$~ЭЛЕМЕНТОВ ПО $r$~КАТЕГОРИЯМ. юКОНЧАТЕЛЬНО ФОРМУЛА~(5) ВЫВОДИТСЯ С 
ПОМОЩЬЮ РЕЗУЛЬТАТОВ УПР.~1.2.6-64.

\section{E.~ЄЕСТ СОБИРАТЕЛЯ КУПОНОВ}. ¤ТОТ ТЕСТ И ТОЛЬКО ЧТО 
ОПИСАННЫЙ СВЯЗАНЫ МЕЖДУ СОБОЙ ПРИМЕРНО ТАК ЖЕ, КАК ТЕСТЫ ПРОВЕРКИ 
ИНТЕРВАЛОВ И ПРОВЕРКИ ЧАСТОТ. шСПОЛЬЗУЕТСЯ ПОСЛЕДОВАТЕЛЬНОСТЬ~$Y_0$, 
$Y_1$,~\dots{} И ОПРЕДЕЛЯЮТСЯ ДЛИНЫ СЕГМЕНТОВ~$Y_{j+1}$, $Y_{j+2}$,~\dots, 
$Y_{j+r}$, НЕОБХОДИМЫХ ДЛЯ ТОГО, ЧТОБЫ СОБРАТЬ "ПОЛНЫЙ НАБОР" ЦЕЛЫХ ЧИСЕЛ 
ОТ~$0$ ДО~$d-1$. ¤ТО МОЖНО СДЕЛАТЬ С ПОМОЩЬЮ СЛЕДУЮЩЕГО АЛГОРИТМА.

\alg C.(ЁЕАЛИЗАЦИЯ ТЕСТА СОБИРАТЕЛЯ КУПОНОВ.) фЛЯ ЗАДАННОЙ 
ПОСЛЕДОВАТЕЛЬНОСТИ ЦЕЛЫХ ЧИСЕЛ~$Y_0$, $Y_1$,~\dots{} ($0\le Y_j<d$) ЭТОТ 
АЛГОРИТМ ОПРЕДЕЛЯЕТ ДЛИНЫ~$n$ ПОСЛЕДОВАТЕЛЬНЫХ СЕГМЕНТОВ ПО ТОЛЬКО ЧТО 
СФОРМУЛИРОВАННОМУ ПРАВИЛУ. яО ОКОНЧАНИИ РАБОТЫ АЛГОРИТМА В~$|COUNT|[r]$ 
ПРИ~$0\le r < t$ НАХОДИТСЯ ЧИСЛО СЕГМЕНТОВ ДЛИНЫ~$r$, А 
В~$|COUNT|[t]$---ЧИСЛО СЕГМЕНТОВ ДЛИНЫ~$\ge t$.

\st[эАЧАЛЬНАЯ УСТАНОВКА.] єСТАНОВИТЬ~$j\asg -1$, $s\asg 0$, А 
ТАКЖЕ~$|COUNT|[r]\asg 0$ ДЛЯ~$0\le r \le t$. 

\st[$q, r=0$.] єСТАНОВИТЬ~$q\asg r \asg 0$, А ТАКЖЕ~$|OCCURS|[k]\asg 0$ 
ДЛЯ~$0\le k < d$. 

\st[ёЛЕДУЮЩЕЕ ИСПЫТАНИЕ.] єВЕЛИЧИТЬ~$r$ И~$j$ НА~$1$. 
хСЛИ~$|OCCURS|[Y_j]\ne0$, ПОВТОРИТЬ ЭТИ ОПЕРАЦИИ.

\st[яОЛНЫЙ НАБОР?] єСТАНОВИТЬ~$|OCCURS|[Y_j]\asg 1$, $q\asg q+1$.
(эА ДАННЫЙ МОМЕНТ ОБНАРУЖЕНО $q$~РАЗНЫХ ЗНАЧЕНИЙ. хСЛИ~$q=d$, ЭТО ЗНАЧИТ, 
ЧТО ПОЛУЧЕН ПОЛНЫЙ НАБОР.) яРИ~$q<d$ ПЕРЕЙТИ НА~\stp{3}.

\st[ЁЕГИСТРАЦИЯ ДЛИНЫ СЕГМЕНТА.] яРИ~$r\ge t$ ПРИБАВИТЬ~$1$ К~$|COUNT|[t]$,
В ПРОТИВНОМ СЛУЧАЕ ПРИБАВИТЬ~$1$ К~$|COUNT|[r]$.

\st[юБНАРУЖЕНО $n$~СЕГМЕНТОВ?] яРИБАВИТЬ~$1$ К~$s$. хСЛИ~$s<n$, 
ВЕРНУТЬСЯ НА~\stp{2}.
\algend

яРИМЕР ИСПОЛЬЗОВАНИЯ ЭТОГО АЛГОРИТМА ПРИВЕДЕН В УПР.~7. ьОЖНО ПРЕДСТАВИТЬ 
СЕБЕ, ЧТО РЕЧЬ ИДЕТ О МАЛЬЧИКЕ, СОБИРАЮЩЕМ $d$~ТИПОВ КУПОНОВ. яО ОДНОМУ 
КУПОНУ СОДЕРЖИТСЯ В КАЖДОЙ УПАКОВКЕ С КАШЕЙ ДЛЯ ЗАВТРАКА, ПРИЧЕМ 
РАСПРЕДЕЛЕНЫ ОНИ СЛУЧАЙНЫМ ОБРАЗОМ. ьАЛЬЧИК ЕСТ КАШУ ДО ТЕХ ПОР, ПОКА НЕ 
СОБЕРЕТ ПОЛНЫЙ КОМПЛЕКТ КУПОНОВ.

%% 80

ёОДЕРЖИМОЕ СЧЕТЧИКОВ~$|COUNT|[d]$,  $|COUNT|[d+1]$,~\dots, $|COUNT|[t]$ 
ОБРАБАТЫВАЕТСЯ С ПОМОЩЬЮ КРИТЕРИЯ~$\chi^2$ С~$k=t-d+1$~СТЕПЕНЯМИ СВОБОДЫ 
ПОСЛЕ ТОГО, КАК АЛГОРИТМ~C ЗАВЕРШИЛ РАБОТУ. ёООТВЕТСТВУЮЩИЕ ВЕРОЯТНОСТИ РАВНЫ:
$$
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)
$$
фЛЯ ВЫВОДА ЭТИХ ФОРМУЛ ДОСТАТОЧНО ЗАМЕТИТЬ, ЧТО, СОГЛАСНО~(5), ВЕРОЯТНОСТЬ 
ТОГО, ЧТО СЕГМЕНТ ДЛИНЫ~$r$ \emph{НЕПОЛНЫЙ,} Т.~Е.\ СОДЕРЖИТ НЕ ВСЕ ИЗ 
ВОЗМОЖНЫХ $d$~ЗНАЧЕНИЙ, РАВНА
$$
q_r=1-{d!\over d^r}\Stir{r}{d}.
$$
ЄОГДА ФОРМУЛЫ~(6) ПОЛУЧАЮТСЯ НЕПОСРЕДСТВЕННО ИЗ 
СООТНОШЕНИЙ~$p_r=q_{r-1}-q_r$, $d\le r < t$ И~$p_t=q_{t-1}$.

ЇОРМУЛЫ, ВОЗНИКАЮЩИЕ В СВЯЗИ С РАЗЛИЧНЫМИ \emph{ОБОБЩЕНИЯМИ} ЭТОГО ТЕСТА, 
РАССМОТРЕНЫ В УПР.~9 И~10, А ТАКЖЕ В РАБОТЕ у.~ФОН~°ЕЛЛИНГА 
({\sl AMM,\/} {\bf 61} (1954), 306--311).

\section{F.~яРОВЕРКА ПЕРЕСТАНОВОК}. ЁАЗДЕЛИМ ИСХОДНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ 
НА $n$~ГРУПП ПО $t$~ЭЛЕМЕНТОВ В КАЖДОЙ: 
$(U_{jt}$, $U_{jt+1}$,~\dots, $U_{jt+t-1})$, $0\le j < n$. т КАЖДОЙ ГРУППЕ 
ВОЗМОЖНО ВСЕГО $t!$~ВАРИАНТОВ ОТНОСИТЕЛЬНОГО РАСПОЛОЖЕНИЯ ЧИСЕЛ. 
яОДСЧИТЫВАЕТСЯ, СКОЛЬКО РАЗ ВСТРЕЧАЕТСЯ КАЖДОЕ КОНКРЕТНОЕ ОТНОСИТЕЛЬНОЕ 
РАСПОЛОЖЕНИЕ, ПОСЛЕ ЧЕГО ПРИМЕНЯЕТСЯ 
КРИТЕРИЙ~$\chi^2$ С~$k=t!$ И ВЕРОЯТНОСТЯМИ~$1/t!$ эАПРИМЕР, ПРИ~$t=3$ 
ЧИСЛО КАТЕГОРИЙ РАВНО ШЕСТИ: $U_{3j}<U_{3j+1}<U_{3j+2}$ 
ИЛИ~$U_{3j}<U_{3j+2}<U_{3j+1}$ ИЛИ~\dots{} ИЛИ~$U_{3j+2}<U_{3j+1}<U_{3j}$. 
яРИ ЭТОМ ПРЕДПОЛАГАЕТСЯ, ЧТО ТОЧНОЕ РАВЕНСТВО ДВУХ ЧИСЕЛ НЕВОЗМОЖНО: 
ДЕЙСТВИТЕЛЬНО, ВЕРОЯТНОСТЬ ТАКОГО СОБЫТИЯ РАВНА НУЛЮ.

яРИ РЕАЛИЗАЦИИ ЭТОГО ТЕСТА НА МАШИНЕ УДОБНО ВОСПОЛЬЗОВАТЬСЯ СЛЕДУЮЩИМ 
АЛГОРИТМОМ, КОТОРЫЙ ИНТЕРЕСЕН И САМ ПО СЕБЕ.

\alg P.(рНАЛИЗ ПЕРЕСТАНОВОК.) ыЮБОМУ НАБОРУ НЕСОВПАДАЮЩИХ 
ЭЛЕМЕНТОВ~$(U_1,~\ldots, U_t)$ СТАВИТСЯ В СООТВЕТСТВИЕ ЦЕЛОЧИСЛЕННАЯ 
ФУНКЦИЯ~$f(U_1,~\ldots, U_t)$, ТАКАЯ, ЧТО
$$
0\le f(U_1, \ldots, U_t)<t!
$$
И~$f(U_1,~\ldots, U_t)=f(V_1,~\ldots, V_t)$ В ТОМ И ТОЛЬКО ТОМ СЛУЧАЕ,
КОГДА ЭЛЕМЕНТЫ В~$(U_1,~\ldots, U_t)$ И~$(V_1,~\dots, V_t)$ РАСПОЛОЖЕНЫ В 
ОДИНАКОВОМ ПОРЯДКЕ. т ПРОГРАММЕ ИСПОЛЬЗУЕТСЯ ВСПОМОГАТЕЛЬНАЯ 
ТАБЛИЦА~$C[1]$,~\dots, $C[t]$.

\st[эАЧАЛЬНАЯ УСТАНОВКА.] єСТАНОВИТЬ~$r\asg t$. 

\st[юПРЕДЕЛИТЬ МАКСИМУМ.] юПРЕДЕЛИТЬ МАКСИМАЛЬНОЕ ИЗ 
ЗНАЧЕНИЙ~$\set{U_1,~\ldots, U_r}$. фОПУСТИМ ЭТО~$U_s$. чАТЕМ 
УСТАНОВИТЬ~$C[r]\asg s-1$.
%% 81
\st[чАМЕНА.] тЗАИМОЗАМЕНИТЬ~$U_r\xchg U_s$.

\st[єМЕНЬШЕНИЕ~$r$.] тЫЧЕСТЬ ИЗ~$r$ ЕДИНИЦУ. хСЛИ~$r>0$, ВЕРНУТЬСЯ НА~\stp{2}.

\st[тЫЧИСЛЕНИЕ~$f$.] шСКОМОЕ ЗНАЧЕНИЕ ФУНКЦИИ ОПРЕДЕЛИТЬ ПО ФОРМУЛЕ
$$
\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

рЛГОРИТМ ПОСТРОЕН ТАКИМ ОБРАЗОМ, ЧТО
$$
0\le C[r]<r
\eqno(8)
$$
(СМ.~ШАГ~P2) И, В ЧАСТНОСТИ, $C[1]$ ВСЕГДА РАВНО НУЛЮ. ЄАК КАК 
$C[r]$~МОЖЕТ ПРИНИМАТЬ $r$~РАЗЛИЧНЫХ ЗНАЧЕНИЙ, ОБЩЕЕ 
КОЛИЧЕСТВО РАЗНОВИДНОСТЕЙ ТАБЛИЦЫ~$C$ РАВНО~$t!$. шЗ ФОРМУЛ~(7) И~(8) 
ЛЕГКО ВИДЕТЬ, ЧТО~$0\le f < t!$. ъ КОНЦУ РАБОТЫ АЛГОРИТМА 
ВЕЛИЧИНЫ~$(U_1,~\ldots, U_t)$ БУДУТ РАССТАВЛЕНЫ В ПОРЯДКЕ ВОЗРАСТАНИЯ.

фЛЯ ДОКАЗАТЕЛЬСТВА ТОГО, ЧТО РЕЗУЛЬТАТ~$f$, ПОЛУЧЕННЫЙ С ПОМОЩЬЮ 
АЛГОРИТМА~P, ХАРАКТЕРИЗУЕТ ЕДИНСТВЕННЫМ ОБРАЗОМ ПОРЯДОК СЛЕДОВАНИЯ ЧИСЕЛ 
В ИСХОДНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ~$(U_1,~\ldots, U_t)$, ПОКАЖЕМ, ЧТО ЭТОТ 
АЛГОРИТМ МОЖНО ИСПОЛЬЗОВАТЬ ДЛЯ РЕШЕНИЯ ОБРАТНОЙ ЗАДАЧИ. яУСТЬ ЗАДАНО 
НЕКОТОРОЕ ЗНАЧЕНИЕ~$f$ И~$t$ ЭЛЕМЕНТОВ~$(U_1,~\ldots, U_t)$, 
ПРИЧЕМ~$0\le f<t!$ И~$U_1<U_2<\ldots<U_t$. єСТАНОВИМ~$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)$ 
И~Т.~Д., ВЫПОЛНЯЯ, ТАКИМ ОБРАЗОМ, ШАГ~P5 В ОБРАТНОМ ПОРЯДКЕ. чАТЕМ 
ПРОИЗВЕДЕМ ЗАМЕНЫ~$U_1\xchg U_{C[1]+1}$, $U_2\xchg U_{C[2]+1}$,~\dots, 
$U_t\xchg U_{C[f]+1}$ В УКАЗАННОМ ПОРЯДКЕ. ыЕГКО ВИДЕТЬ, ЧТО ПРИ ЭТОМ 
ЛИКВИДИРУЮТСЯ ПОСЛЕДСТВИЯ ВЫПОЛНЕНИЯ ШАГОВ P1--P4. ЄОТ ФАКТ, ЧТО 
ЗНАЧЕНИЕ~$f$ ПОЗВОЛЯЕТ ВОССТАНОВИТЬ ИСХОДНЫЙ ПОРЯДОК ПОСЛЕДОВАТЕЛЬНОСТИ, 
ДОКАЗЫВАЕТ ПРАВИЛЬНОСТЬ АЛГОРИТМА~P.

\section{G. яРОВЕРКА НА МОНОТОННОСТЬ}. ¤ТОТ ТЕСТ ВЫЯВЛЯЕТ "НЕУБЫВАНИЕ" И 
"НЕВОЗРАСТАНИЕ", Т.~Е.\ АНАЛИЗИРУЮТСЯ ДЛИНЫ \emph{МОНОТОННЫХ} 
ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ ЧИСЕЛ В ИСХОДНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ.

т КАЧЕСТВЕ ПРИМЕРА РАССМОТРИМ ПОСЛЕДОВАТЕЛЬНОСТЬ ИЗ 
10~ЦИФР "$1298536704$"; ОТМЕЧАЯ ВЕРТИКАЛЬНЫМИ ЛИНИЯМИ НАЧАЛО И 
КОНЕЦ ПОСЛЕДОВАТЕЛЬНОСТИ, А ТАКЖЕ ВСЕ МЕСТА, ГДЕ~$X_j>X_{j+1}$, ПОЛУЧИМ
$$
\vert 1\, 2\, 9 \vert 8 \vert 5 \vert 3\, 6\, 7 \vert 0\, 4 \vert.
\eqno (9)
$$
чДЕСЬ ВЫДЕЛЕНЫ ВСЕ НЕУБЫВАЮЩИЕ ПОДПОСЛЕДОВАТЕЛЬНОСТИ: ПЕРВАЯ ДЛИНЫ~3, 
ЗАТЕМ ДВЕ ПО~1, ЕЩЕ ОДНА ДЛИНЫ~3 И ЗАТЕМ~2. рЛГОРИТМ В УПР.~12 ПОКАЗЫВАЕТ, 
КАК ТАБУЛИРОВАТЬ ДЛИНЫ ТАКИХ ОТРЕЗКОВ.
%% 82
т ОТЛИЧИЕ ОТ ТЕСТА СОБИРАТЕЛЯ КУПОНОВ ИЛИ ПРОВЕРКИ ИНТЕРВАЛОВ (КОТОРЫЕ 
ВО МНОГИХ ОТНОШЕНИЯХ ПОХОЖИ НА ЭТОТ ТЕСТ) В ДАННОМ СЛУЧАЕ \emph{НЕ СЛЕДУЕТ 
ПРИМЕНЯТЬ КРИТЕРИЙ~$\chi^2$ ДЛЯ АНАЛИЗА ПОЛУЧЕННЫХ ДАННЫХ,} ТАК КАК ОНИ 
\emph{НЕ ЯВЛЯЮТСЯ} НЕЗАВИСИМЫМИ. яОСЛЕ ДЛИННОГО ОТРЕЗКА ЧАЩЕ ПОЯВЛЯЕТСЯ 
КОРОТКИЙ И НАОБОРОТ. шЗ-ЗА ОТСУТСТВИЯ НЕЗАВИСИМОСТИ ПРЯМОЕ ПРИМЕНЕНИЕ 
КРИТЕРИЯ~$\chi^2$ СТАНОВИТСЯ НЕЗАКОННЫМ. тМЕСТО ЭТОГО, ПОСЛЕ ОПРЕДЕЛЕНИЯ 
ДЛИН ОТРЕЗКОВ С ПОМОЩЬЮ АЛГОРИТМА, ОПИСАННОГО В УПР.~12, ВЫЧИСЛЯЕТСЯ СТАТИСТИКА
$$
V={1\over n}\sum_{1\le i, j \le 6} 
(|COUNT|[i]-nb_i)(|COUNT|[j]-nb_j)a_{ij},
\eqno(10)
$$
ГДЕ КОЭФФИЦИЕНТЫ~$a_{ij}$ И~$b_i$ ТАКОВЫ:
$$
\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)
$$
(чДЕСЬ ПРИВЕДЕНЫ ПРИБЛИЖЕННЫЕ ЗНАЧЕНИЯ КОЭФФИЦИЕНТОВ; ТОЧНЫЕ ЗНАЧЕНИЯ 
МОЖНО ВЫЧИСЛИТЬ ПО ПРИВЕДЕННЫМ НИЖЕ ФОРМУЛАМ.) \emph{ёТАТИСТИКА~$V$ В~(10) 
ДОЛЖНА ИМЕТЬ ПРИ БОЛЬШИХ~$n$ РАСПРЕДЕЛЕНИЕ~$\chi^2$ С ШЕСТЬЮ {\rm (А НЕ 
ПЯТЬЮ)} СТЕПЕНЯМИ СВОБОДЫ.} чНАЧЕНИЕ~$n$ ДОЛЖНО БЫТЬ РАВНО, СКАЖЕМ, $4000$ 
ИЛИ БОЛЬШЕ. рНАЛОГИЧНЫЙ ТЕСТ ПРИМЕНЯЕТСЯ ДЛЯ НЕВОЗРАСТАЮЩИХ ОТРЕЗКОВ.

фОВОЛЬНО ПРОСТОЙ И БОЛЕЕ ПРАКТИЧНЫЙ СПОСОБ ПРОВЕРКИ НА МОНОТОННОСТЬ 
ПРИВЕДЕН В УПР.~14, НО ИЗ ЧИСТО МАТЕМАТИЧЕСКИХ СООБРАЖЕНИЙ ПОЛЕЗНЕЕ БУДЕТ 
РАЗОБРАТЬ ЭТОТ ВЕСЬМА СЛОЖНЫЙ ТЕСТ.

яРИСТУПИМ К ВЫВОДУ ФОРМУЛ ДЛЯ НЕГО. яУСТЬ ДЛЯ ДАННОЙ ПЕРЕСТАНОВКИ ИЗ 
$n$~ЭЛЕМЕНТОВ $Z_{pi}=1$, ЕСЛИ С ПОЗИЦИИ~$i$ НАЧИНАЕТСЯ ВОЗРАСТАЮЩИЙ 
ОТРЕЗОК С ДЛИНОЙ НЕ МЕНЕЕ~$p$, И~$Z_{pi}=0$ В ПРОТИВНОМ СЛУЧАЕ. т 
КАЧЕСТВЕ ПРИМЕРА РАССМОТРИМ ПОСЛЕДОВАТЕЛЬНОСТЬ~(9) С~$n=10$. т ДАННОМ СЛУЧАЕ
$$
Z_{11}=Z_{21}=Z_{31}=Z_{14}=Z_{15}=Z_{16}=Z_{26}=Z_{36}=Z_{19}=Z_{29}=1,
$$
А ВСЕ ОСТАЛЬНЫЕ~$Z$ РАВНЫ~$0$. ЄОГДА
$$
R'_p=Z_{p1}+Z_{p2}+\cdots+Z_{pn}
\eqno(12
$$
%% 83
ЕСТЬ ЧИСЛО ОТРЕЗКОВ ДЛИНЫ НЕ МЕНЕЕ~$p$, А
$$
R_p=R'_p-R'_{p+1}
\eqno(13)
$$
ЕСТЬ ЧИСЛО ОТРЕЗКОВ, ДЛИНА КОТОРЫХ В ТОЧНОСТИ РАВНА~$p$. эАМ НУЖНО 
ВЫЧИСЛИТЬ СРЕДНЕЕ ЗНАЧЕНИЕ~$R_p$, А ТАКЖЕ \dfn{КОВАРИАЦИЮ}%
\note{1}{ьЫ ОСТАВЛЯЕМ ОБОЗНАЧЕНИЯ АВТОРА ДЛЯ СРЕДНЕГО, КОВАРИАЦИИ И Т.~П.,
 СЛЕДУЯ ПЕРЕВОДУ 1-ГО ТОМА (СМ.~П.~1.2.10).---{\sl яРИМ. ПЕРЕВ.\/}}
$$
\covar (R_p, R_q)=\mean ((R_p-\mean (R_p)) (R_q-\mean (R_q))),
$$
КОТОРАЯ СЛУЖИТ МЕРОЙ ВЗАИМОЗАВИСИМОСТИ~$R_p$ И~$R_q$. єСРЕДНЕНИЕ НАДО 
ПРОВОДИТЬ ПО ВСЕМ ВОЗМОЖНЫМ $n!$~ПЕРЕСТАНОВКАМ.

ЇОРМУЛЫ~(12) И~(13) ПОКАЗЫВАЮТ, ЧТО ИСКОМЫЕ ВЕЛИЧИНЫ МОЖНО ВЫРАЗИТЬ ЧЕРЕЗ 
СРЕДНИЕ ЗНАЧЕНИЯ~$Z_{pi}$ И~$Z_{pi}Z_{qj}$, ПОЭТОМУ В КАЧЕСТВЕ ПЕРВОГО 
ШАГА ЗАПИШЕМ СЛЕДУЮЩИЕ СООТНОШЕНИЯ (В ПРЕДПОЛОЖЕНИИ, ЧТО~$i<j$):
$$
\eqalign{
{1\over n!}\sum Z_{pi}&=\cases{
  (p+\delta_{i1})/(p+1)! & ПРИ~$i\le n-p+1$;\cr
                       0 & В ПРОТИВНОМ СЛУЧАЕ;\cr
 }\cr
{1\over n!}\sum Z_{pi}Z_{qj}&=\cases{
                       (p+\delta_{i1})q/(p+1)!(q+1)! & ПРИ $i+p<j\le n-q+1$;\cr
 (p+\delta_{i1})/(p+1)!q!-(p+q+\delta_{i1})/(p+q+1)! & ПРИ~$i+p=j\le n-q+1$;\cr 
                                                   0 & В ПРОТИВНОМ СЛУЧАЕ.\cr
 }
}
\eqno(14)
$$
ёУММИРОВАНИЕ ПРОВОДИТСЯ ЗДЕСЬ ПО ВСЕМ ВОЗМОЖНЫМ ПЕРЕСТАНОВКАМ. ўТОБЫ 
ПОКАЗАТЬ, КАК ВЫВОДЯТСЯ ЭТИ ФОРМУЛЫ, РАССМОТРИМ САМЫЙ СЛОЖНЫЙ СЛУЧАЙ, 
КОГДА~$i+p=j\le n-q+1$ И~$i>1$. юТМЕТИМ, ЧТО~$Z_{pi}Z_{qj}$ РАВНО 
ЛИБО~$0$, ЛИБО~$1$, ТАК ЧТО СУММИРОВАНИЕ СВОДИТСЯ К ТОМУ, ЧТОБЫ 
ПЕРЕСЧИТАТЬ ВСЕ ПЕРЕСТАНОВКИ~$U_1$, $U_2$,~\dots, $U_n$, В 
КОТОРЫХ~$Z_{pi}=Z_{qj}=0$, А ИМЕННО
$$
U_{i-1}>U_i<\ldots<U_{i+p-1}>U_{i+p}<\ldots<U_{i+p+q-1}.
\eqno(15)
$$
ўИСЛО ТАКИХ ПЕРЕСТАНОВОК МОЖНО ОПРЕДЕЛИТЬ С ПОМОЩЬЮ СЛЕДУЮЩИХ 
СООБРАЖЕНИЙ: СУЩЕСТВУЕТ $\perm{n}{p+1+q}$~СПОСОБОВ ВЫБОРА ЭЛЕМЕНТОВ 
ПОСЛЕДОВАТЕЛЬНОСТИ, УКАЗАННЫХ В~(15); ИМЕЕТСЯ
$$
(p+q+1)\perm{p+q}{p}-\perm{p+q+1}{p+1}-\perm{p+q+1}{1}+1
\eqno(16)
$$
%% 84
СПОСОБОВ РАСПОЛОЖЕНИЯ ИХ В ПОРЯДКЕ, УКАЗАННОМ В~(15), (СМ.~УПР.~13) 
И~$(n-p-q-1)!$~СПОСОБОВ РАСПОЛОЖЕНИЯ ОСТАЛЬНЫХ
ЭЛЕМЕНТОВ. ЄАКИМ ОБРАЗОМ, НАДО УМНОЖИТЬ~(16) 
НА~$\perm{n}{p+q+1}\times(n-p-q-1)!$ И ПОСЛЕ ДЕЛЕНИЯ НА~$n!$ ПОЛУЧАЕТСЯ 
ИСКОМЫЙ РЕЗУЛЬТАТ.

шЗ СООТНОШЕНИЙ~(14) В РЕЗУЛЬТАТЕ ДОВОЛЬНО ГРОМОЗДКИХ ПРЕОБРАЗОВАНИЙ 
МОЖНО ПОЛУЧИТЬ
$$
\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) & ПРИ $p+q\le n$;\cr
\mean(R'_t)-\mean(R'_p)\mean(R'_q) & ПРИ $p+q>n$;\cr
} & (18) \cr
}
$$
ГДЕ $t=\max(p,q)$, $s=p+q$ И
$$
\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
}
$$
ъОНЕЧНО, ПОЛЬЗОВАТЬСЯ ТАКИМ СЛОЖНЫМ ВЫРАЖЕНИЕМ ДЛЯ КОВАРИАЦИИ ОЧЕНЬ 
НЕУДОБНО, НО ДРУГОГО ВЫХОДА НЕТ. ё ПОМОЩЬЮ ЭТИХ ФОРМУЛ ЛЕГКО ВЫЧИСЛИТЬ
$$
\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)
$$
т РАБОТЕ фЖ.~тОЛЬФОВИЦА ({\sl Annals of Mathematical Statistics,\/} {\bf 15} 
(1944), 163--165) ДОКАЗАНО, ЧТО ПРИ~$n\to\infty$ 
РАСПРЕДЕЛЕНИЕ ВЕЛИЧИН~$R_1$, $R_2$,~\dots, $R_{t-1}$, $R'_t$ СТРЕМИТСЯ К 
НОРМАЛЬНОМУ СО СРЕДНИМ ЗНАЧЕНИЕМ И КОВАРИАЦИЕЙ, ПРИВЕДЕННЫМИ ВЫШЕ. юТСЮДА 
СЛЕДУЕТ, ЧТО МОЖНО ПОЛЬЗОВАТЬСЯ ТАКИМ ТЕСТОМ. фЛЯ ДАННОЙ 
ПОСЛЕДОВАТЕЛЬНОСТИ ИЗ $n$~СЛУЧАЙНЫХ ЧИСЕЛ 
ВЫЧИСЛЯЕТСЯ~$R_p$---ЧИСЛО МОНОТОННЫХ ОТРЕЗКОВ ДЛИНЫ~$p$, ГДЕ~$1\le p < t$, 
А ТАКЖЕ~$R'_t$---ЧИСЛО ОТРЕЗКОВ ДЛИНЫ~$\ge t$. тВЕДЕМ ОБОЗНАЧЕНИЯ
$$
\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
юБРАЗУЕМ МАТРИЦУ КОВАРИАЦИЙ~$C$, ОБОЗНАЧАЯ, НАПРИМЕР, $C_{13}=\covar(R_1, R_3)$, 
ТОГДА КАК~$C_{1t}=\covar(R_1, R'_t)$. яРИ~$t=6$ ПОЛУЧИМ
$$
\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)
$$
ДЛЯ~$n\ge 14$. чАТЕМ НАЙДЕМ МАТРИЦУ~$A=(a_{ij})$, ОБРАТНУЮ МАТРИЦЕ~$C$,
И ВЫЧИСЛИМ~$\sum_{1\le i,j \le t} Q_i Q_j a_{ij}$. яРИ БОЛЬШИХ~$n$ 
РЕЗУЛЬТАТ ИМЕЕТ РАСПРЕДЕЛЕНИЕ~$\chi^2$ С~$t$~СТЕПЕНЯМИ СВОБОДЫ.

яРИВЕДЕННАЯ РАНЕЕ МАТРИЦА~(11)---РЕЗУЛЬТАТ ОБРАЩЕНИЯ МАТРИЦЫ~$C_1$, 
ПРЕДСТАВЛЕННОЙ С ПЯТЬЮ ЗНАЧАЩИМИ ЦИФРАМИ. яРИ БОЛЬШИХ~$n$ МАТРИЦА~$A$ 
БУДЕТ ПРИБЛИЖЕННО РАВНА~$(1/n)C_1^{-1}$. фЕЛАЛИСЬ ПОПЫТКИ ЗАПИСАТЬ 
ЭЛЕМЕНТЫ МАТРИЦЫ, ОБРАТНОЙ К~$C_1$ КАК РАЦИОНАЛЬНЫЕ ЧИСЛА, НО ЭТО 
ПРИВОДИЛО К СЛИШКОМ БОЛЬШИМ ВЕЛИЧИНАМ УЖЕ ПРИ~$t=4$. т ЧАСТНОМ СЛУЧАЕ 
ПРИ~$n=1000$ ЭЛЕМЕНТЫ МАТРИЦЫ~(11) ОКАЗАЛИСЬ ПРИМЕРНО НА~1\% НИЖЕ ТОЧНЫХ 
ЗНАЧЕНИЙ, ПОЛУЧЕННЫХ В РЕЗУЛЬТАТЕ ОБРАЩЕНИЯ МАТРИЦЫ~(22). ёТАНДАРТНЫЙ 
МЕТОД ОБРАЩЕНИЯ МАТРИЦ ОПИСАН В П.~2.2.6, УПР.~18.

%%86

\section{H.~ЄЕСТ "НАИБОЛЬШЕЕ ИЗ~$t$"}. 
яУСТЬ~$V_j=\max(U_{tj}, U_{tj+1},~\ldots, U_{tj+t-1})$ ПРИ~$0\le j < n$. 
яРИМЕНИМ КРИТЕРИЙ ъОЛМОГОРОВА-ёМИРНОВА К 
ПОСЛЕДОВАТЕЛЬНОСТИ~$V_0$, $V_1$,~\dots, $V_{n-1}$, 
ПРИНИМАЯ В КАЧЕСТВЕ ТЕОРЕТИЧЕСКОЙ ФУНКЦИИ РАСПРЕДЕЛЕНИЯ~$F(x)=x^t$, 
($0\le x \le 1$). ьОЖНО ВМЕСТО ЭТОГО ПРОВЕРЯТЬ НА РАВНОМЕРНОСТЬ 
ПОСЛЕДОВАТЕЛЬНОСТЬ~$V_0^t$, $V_1^t$,~\dots, $V_{n-1}^t$.

фЛЯ ОБОСНОВАНИЯ ЭТОГО ТЕСТА ДОСТАТОЧНО ПОКАЗАТЬ, ЧТО $V_j$~РАСПРЕДЕЛЕНЫ 
В СООТВЕТСТВИИ С~$F(x)=x^t$. тЕРОЯТНОСТЬ ТОГО, 
ЧТО~$\max(U_1, U_2,~\ldots, U_t)\le x$, РАВНА ВЕРОЯТНОСТИ ТОГО, 
ЧТО~$U_1\le x$ \emph{И}~$U_2\le x$ \emph{И}~\dots{} \emph{И}~$U_t\le x$; 
СЛЕДОВАТЕЛЬНО, ОНА РАВНА ПРОИЗВЕДЕНИЮ ИНДИВИДУАЛЬНЫХ 
ВЕРОЯТНОСТЕЙ~$x\cdot x \cdot \ldots \cdot x = x^t$.

\section{I.~яОСЛЕДОВАТЕЛЬНАЯ КОРРЕЛЯЦИЯ}. тЫЧИСЛИМ СТАТИСТИКУ
$$
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)
$$
¤ТО "КОЭФФИЦИЕНТ ПОСЛЕДОВАТЕЛЬНОЙ КОРРЕЛЯЦИИ", КОТОРЫЙ СЛУЖИТ МЕРОЙ 
ЗАВИСИМОСТИ~$U_{j+1}$ ОТ~$U_j$. яРИ ОЧЕНЬ БОЛЬШИХ~$n$ СУЩЕСТВУЕТ МЕТОД, 
ПОЗВОЛЯЮЩИЙ РЕЗКО УМЕНЬШИТЬ ВРЕМЯ, КОТОРОЕ ТРАТИТСЯ НА РАСЧЕТ~$C$ 
(L.~P.~Schmid, {\sl CACM,\/} {\bf 8} (1965), 115).

ъОЭФФИЦИЕНТЫ КОРРЕЛЯЦИИ ЧАСТО УПОТРЕБЛЯЮТСЯ В СТАТИСТИКЕ. хСЛИ ИМЕЕТСЯ ДВА 
НАБОРА ВЕЛИЧИН~$U_0$, $U_1$,~\dots, $U_{n-1}$ И~$V_0$, $V_1$,~\dots, 
$V_{n-1}$, ТО КОЭФФИЦИЕНТ КОРРЕЛЯЦИИ МЕЖДУ НИМИ ОПРЕДЕЛЯЕТСЯ СЛЕДУЮЩИМ ОБРАЗОМ:
$$
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)
$$
ёУММИРОВАНИЕ В ЭТОЙ ФОРМУЛЕ ПРОВОДИТСЯ ПО ВСЕМ~$j$ В ИНТЕРВАЛЕ~$0\le j < n$. 
ЇОРМУЛА~(23) ПОЛУЧАЕТСЯ В ЧАСТНОМ СЛУЧАЕ~$V_j=U_{(j+1)\bmod n}$. 
[\emph{чАМЕЧАНИЕ.} чНАМЕНАТЕЛЬ ВЫРАЖЕНИЯ~(24) РАВЕН НУЛЮ 
ПРИ~$U_0=U_1=\cdots=U_{n-1}$ ИЛИ~$V_0=V_1=\cdots=V_{n-1}$; МЫ ИСКЛЮЧАЕМ 
ЭТОТ СЛУЧАЙ ИЗ РАССМОТРЕНИЯ.)

ъОЭФФИЦИЕНТ КОРРЕЛЯЦИИ ВСЕГДА ЛЕЖИТ МЕЖДУ~$-1$ И~$+1$. ъОГДА ОН РАВЕН НУЛЮ 
ИЛИ ОЧЕНЬ МАЛ, ЭТО СЛУЖИТ УКАЗАНИЕМ НА НЕЗАВИСИМОСТЬ ВЕЛИЧИН~$U_j$ И~$V_j$,
А КОГДА ОН РАВЕН~$\pm 1$, ЭТИ ВЕЛИЧИНЫ СВЯЗАНЫ ДРУГ С ДРУГОМ ЛИНЕЙНОЙ 
ЗАВИСИМОСТЬЮ, Т.~Е.\ ДЛЯ ЛЮБОГО~$j$ СПРАВЕДЛИВО РАВЕНСТВО~$V_j=m \pm aU_j$ 
ПРИ НЕКОТОРЫХ ПОСТОЯННЫХ~$a$ И~$m$ (СМ.~УПР.~17).

ЄАКИМ ОБРАЗОМ, ЖЕЛАТЕЛЬНО, ЧТОБЫ ЗНАЧЕНИЕ~$C$, ОПРЕДЕЛЕННОЕ ФОРМУЛОЙ~(23), 
БЫЛО БЛИЗКО К НУЛЮ. т ДЕЙСТВИТЕЛЬНОСТИ, ИЗ-ЗА ТОГО, ЧТО~$U_0U_1$ 
И~$U_1U_2$, КОНЕЧНО, НЕ ЯВЛЯЮТСЯ НЕЗАВИСИМЫМИ, КОЭФФИЦИЕНТ 
ПОСЛЕДОВАТЕЛЬНОЙ КОРРЕЛЯЦИИ НЕ ДОЛЖЕН БЫТЬ В \emph{ТОЧНОСТИ} РАВЕН НУЛЮ 
(СМ.~УПР.~18). "їОРОШИМ" МОЖНО СЧИТАТЬ ЗНАЧЕНИЕ~$C$, ЛЕЖАЩЕЕ 
МЕЖДУ~$\mu_n-2\sigma_n$ И~$\mu_n+2\sigma_n$, ГДЕ
$$
\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
чНАЧЕНИЕ~$C$ ДОЛЖНО НАХОДИТЬСЯ В ЭТИХ ПРЕДЕЛАХ В 95\% ВСЕХ СЛУЧАЕВ.

ЇОРМУЛЫ~(25) ПОКА ИМЕЮТ ПРЕДПОЛОЖИТЕЛЬНЫЙ ХАРАКТЕР, ТАК КАК ТОЧНОЕ 
РАСПРЕДЕЛЕНИЕ~$C$ В ТОМ СЛУЧАЕ, КОГДА $U$~РАСПРЕДЕЛЕНЫ РАВНОМЕРНО, 
НЕИЗВЕСТНО. ёЛУЧАЙ НОРМАЛЬНОГО РАСПРЕДЕЛЕНИЯ ВЕЛИЧИН~$U$ РАССМОТРЕН В 
РАБОТЕ є.~фИКСОНА ({\sl Annals of Mathematical Statistics,\/} {\bf 15} 
(1944), 119--144). юПЫТ ПОКАЗЫВАЕТ, ЧТО ИСПОЛЬЗОВАНИЕ ФОРМУЛ ДЛЯ 
МАТЕМАТИЧЕСКОГО ОЖИДАНИЯ И СРЕДНЕКВАДРАТИЧНОГО ОТКЛОНЕНИЯ, 
СООТВЕТСТВУЮЩИХ НОРМАЛЬНОМУ РАСПРЕДЕЛЕНИЮ, Т.~Е.~ФОРМУЛ~(25), НЕ 
ПРИВОДИТ К БОЛЬШОЙ ОШИБКЕ. шЗВЕСТНО, 
ЧТО~$\lim_{n\to\infty}\sqrt{n}\sigma_n=1$; СМ.~ТАКЖЕ СТАТЬЮ рНДЕРСОНА И 
єОКЕРА ({\sl Annals of Mathematical Statistics,\/} {\bf 35} (1964), 1296--1303), 
В КОТОРОЙ ПОЛУЧЕНЫ БОЛЕЕ ОБЩИЕ РЕЗУЛЬТАТЫ О ПОСЛЕДОВАТЕЛЬНОЙ 
КОРРЕЛЯЦИИ В \emph{ЗАВИСИМЫХ} ПОСЛЕДОВАТЕЛЬНОСТЯХ.

\section{J.~яРОВЕРКА ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ}. эЕРЕДКО ВНЕШНЯЯ ПРОГРАММА 
УСТРОЕНА ТАК, ЧТО ЕЙ ТРЕБУЕТСЯ КАЖДЫЙ РАЗ НЕКОТОРОЕ ОПРЕДЕЛЕННОЕ 
КОЛИЧЕСТВО СЛУЧАЙНЫХ ЧИСЕЛ. эАПРИМЕР, ЕСЛИ В ПРОГРАММЕ ЕСТЬ ТРИ СЛУЧАЙНЫЕ 
ВЕЛИЧИНЫ~$X$, $Y$ И~$Z$, ДЛЯ ОПРЕДЕЛЕНИЯ ИХ ЗНАЧЕНИЙ КАЖДЫЙ РАЗ НУЖНО 
БУДЕТ ГЕНЕРИРОВАТЬ ТРИ СЛУЧАЙНЫХ ЧИСЛА. фЛЯ ТАКИХ ПРИЛОЖЕНИЙ ВАЖНО, ЧТОБЫ 
СЛУЧАЙНОЙ БЫЛА ЛЮБАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ, ПОЛУЧЕННАЯ В РЕЗУЛЬТАТЕ 
ВЫБОРА КАЖДОГО \emph{ТРЕТЬЕГО} ЧИСЛА ИСХОДНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ. 
хСЛИ ПРОГРАММА ЗАПРАШИВАЕТ КАЖДЫЙ РАЗ $q$~ЧИСЕЛ, ТО С ПОМОЩЬЮ ТЕСТОВ, 
ОПИСАННЫХ ВЫШЕ, МОЖНО ПРОВЕРЯТЬ НЕ ИСХОДНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ~$U_0$, 
$U_1$, $U_2$,~\dots, А В ОТДЕЛЬНОСТИ КАЖДУЮ ИЗ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ
$$
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)
$$

юПЫТ ПОКАЗЫВАЕТ, ЧТО ПРИ ИСПОЛЬЗОВАНИИ ЛИНЕЙНОГО КОНГРУЭНТНОГО МЕТОДА 
ХАРАКТЕРИСТИКИ ТАКИХ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ ПРАКТИЧЕСКИ НИКОГДА НЕ БЫВАЮТ 
ХУЖЕ, ЧЕМ У ИСХОДНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ, КРОМЕ СЛУЧАЕВ, КОГДА~$q$ И 
ЧИСЛО, ИСПОЛЬЗУЕМОЕ В КАЧЕСТВЕ МОДУЛЯ, СОДЕРЖАТ ДОСТАТОЧНО БОЛЬШОЙ ОБЩИЙ 
МНОЖИТЕЛЬ. ЄАК, НА МАШИНАХ С ДВОИЧНОЙ АРИФМЕТИКОЙ ПРИ ИСПОЛЬЗОВАНИИ 
ЗНАЧЕНИЙ~$m$, РАВНЫХ РАЗМЕРУ СЛОВА, ИЗ ВСЕХ~$q<16$ САМЫЕ ПЛОХИЕ РЕЗУЛЬТАТЫ 
ПОЛУЧАЮТСЯ ПРИ~$q=8$; НА МАШИНАХ С ДЕСЯТИЧНОЙ АРИФМЕТИКОЙ МОЖНО ОЖИДАТЬ 
НЕУДОВЛЕТВОРИТЕЛЬНЫХ РЕЗУЛЬТАТОВ ПРИ~$q=10$. (¤ТО МОЖНО ОБоЯСНИТЬ 
ОТЧАСТИ, ИСХОДЯ ИЗ ПОНЯТИЯ МОЩНОСТИ ПОСЛЕДОВАТЕЛЬНОСТИ, ТАК КАК ТАКИЕ 
ЗНАЧЕНИЯ~$q$ БУДУТ, ВООБЩЕ ГОВОРЯ, ПОНИЖАТЬ ЕЕ МОЩНОСТЬ.)

\section{K.~чАМЕЧАНИЯ ИСТОРИЧЕСКОГО ХАРАКТЕРА И ДАЛЬНЕЙШЕЕ ОБСУЖДЕНИЕ}.
ёТАТИСТИЧЕСКИЕ КРИТЕРИИ ВОЗНИКАЛИ ЕСТЕСТВЕННЫМ ОБРАЗОМ В ПРОЦЕССЕ
%% 88
НАУЧНОЙ РАБОТЫ, КОГДА ПОЯВЛЯЛАСЬ НЕОБХОДИМОСТЬ "ПРИНЯТЬ" ИЛИ 
"ОТВЕРГНУТЬ" КАКУЮ-ЛИБО ГИПОТЕЗУ, КАСАЮЩУЮСЯ ЭКСПЕРИМЕНТАЛЬНЫХ ДАННЫХ. 
ыУЧШИМИ СРЕДИ РАБОТ, ПОСВЯЩЕННЫХ ПРОВЕРКЕ НА СЛУЧАЙНОСТЬ ИСКУССТВЕННЫХ 
ПОСЛЕДОВАТЕЛЬНОСТЕЙ ЧИСЕЛ, ЯВЛЯЮТСЯ ДВЕ СТАТЬИ ь.~ъЕНДАЛЛА 
И~с.~сЭБИНГТОН-ёМИТА [{\sl Journal of the Royal Statistical Society,\/} 
{\bf 101} (1938), 147--166, И ПРИЛОЖЕНИЕ К ЭТОМУ ЖУРНАЛУ, {\bf 6} (1939), 51--61]. 
т ЭТИХ РАБОТАХ ОПИСАНА ПРОВЕРКА СЛУЧАЙНЫХ ЦИФР ОТ~$0$ ДО~$9$, 
А НЕ ДЕЙСТВИТЕЛЬНЫХ СЛУЧАЙНЫХ ЧИСЕЛ; ДЛЯ ЭТОЙ ЦЕЛИ ПРЕДЛОЖЕНЫ ПРОВЕРКА 
ЧАСТОТ, СЕРИЙ, ИНТЕРВАЛОВ, А ТАКЖЕ ПОКЕР-ТЕСТ (ХОТЯ ПРОВЕРКА 
СЕРИЙ ПРОИЗВОДИТСЯ НЕВЕРНО). ъЕНДАЛЛ И сЭБИНГТОН-ёМИТ ИСПОЛЬЗОВАЛИ ТАКЖЕ 
РАЗНОВИДНОСТЬ ТЕСТА СОБИРАТЕЛЯ КУПОНОВ, НО В ТОМ ВИДЕ, КОТОРЫЙ ОПИСАН В 
ДАННОЙ КНИГЕ, ЭТОТ ТЕСТ БЫЛ ПРЕДЛОЖЕН уРИНВУДОМ В 1955~Г.

ЄЕСТ ПРОВЕРКИ МОНОТОННОСТИ ИМЕЕТ ДОВОЛЬНО ИНТЕРЕСНУЮ ИСТОРИЮ. 
яЕРВОНАЧАЛЬНО В НЕМ РЕГИСТРИРОВАЛИСЬ ОДНОВРЕМЕННО ДЛИНЫ ОТРЕЗКОВ КАК С 
ВОЗРАСТАЮЩИМИ, ТАК И УБЫВАЮЩИМИ ЧИСЛАМИ (ЭТИ ОТРЕЗКИ ЧЕРЕДУЮТСЯ). ёЛЕДУЕТ 
ОТМЕТИТЬ, ЧТО ЭТОТ ТЕСТ, ТАК ЖЕ КАК ПРОВЕРКА ПЕРЕСТАНОВОК, НЕ ТРЕБУЕТ, 
ЧТОБЫ ЗНАЧЕНИЯ~$U$ БЫЛИ РАСПРЕДЕЛЕНЫ РАВНОМЕРНО; ТРЕБУЕТСЯ ТОЛЬКО, ЧТОБЫ 
ВЕРОЯТНОСТЬ ТОГО, ЧТО~$U_i=U_j$, РАВНЯЛАСЬ НУЛЮ ПРИ~$i\ne j$, ТАК ЧТО 
ЭТИ ТЕСТЫ МОЖНО ПРИМЕНЯТЬ К МНОГИМ ТИПАМ СЛУЧАЙНЫХ ПОСЛЕДОВАТЕЛЬНОСТЕЙ. 
т ПРИМИТИВНОЙ ФОРМЕ ЭТОТ ТЕСТ ВПЕРВЫЕ БЫЛ ПРЕДЛОЖЕН В РАБОТЕ 
[J.~Bienaynie, {\sl Comptes Rendus,\/} {\bf 81} (Paris: Acad.\  Sciences, 1875), 417--423]. 
юКОЛО 60~ЛЕТ СПУСТЯ ъЕРМЭК И ьАК-ъЕНДРИК НАПИСАЛИ ДВЕ 
БОЛЬШИЕ РАБОТЫ, ПОСВЯЩЕННЫЕ ЭТОМУ ВОПРОСУ [{\sl Proc.\ Royal Society 
Edinburgh,\/} {\bf 57} (1937), 228--240, 332--376]. т КАЧЕСТВЕ ПРИМЕРА В 
НИХ ПОКАЗАНО С ПОМОЩЬЮ ПРОВЕРКИ НА МОНОТОННОСТЬ, ЧТО КОЛЕБАНИЯ КОЛИЧЕСТВА 
ОСАДКОВ В ¤ДИНБУРГЕ В ПЕРИОД С~1785~Г.\ ПО~1930~Г.\ НОСИЛИ 
СЛУЧАЙНЫЙ ХАРАКТЕР (ХОТЯ ОНИ ИССЛЕДОВАЛИ ТОЛЬКО СРЕДНИЕ И 
СТАНДАРТНЫЕ ОТКЛОНЕНИЯ ОТРЕЗКОВ МОНОТОННОСТИ). ё ТЕХ ПОР ЭТОТ ТЕСТ 
ПЕРИОДИЧЕСКИ ИСПОЛЬЗОВАЛСЯ НА ПРАКТИКЕ, НО ТОЛЬКО В~1944~Г.\ 
БЫЛО ПОКАЗАНО, ЧТО ПРИМЕНЯТЬ ЕГО В СОЧЕТАНИИ С КРИТЕРИЕМ~$\chi^2$ 
НЕЛЬЗЯ. т РАБОТЕ ыЕВЕНА И тОЛЬФОВИЦА [{\sl Annals of Mathematical 
Statistics,\/} {\bf 15} (1944), 58--69] БЫЛА ПРИВЕДЕНА ПРАВИЛЬНАЯ 
ФОРМУЛИРОВКА ТЕСТА (С ЧЕРЕДУЮЩИМИСЯ ОТРЕЗКАМИ ВОЗРАСТАНИЯ И УБЫВАНИЯ) 
И УКАЗАНА ОШИБОЧНОСТЬ ЕГО ПЕРВОНАЧАЛЬНОЙ ФОРМУЛИРОВКИ. тАРИАНТ ТЕСТА, 
ИЗЛОЖЕННЫЙ В ДАННОЙ КНИГЕ, КОГДА АНАЛИЗИРУЮТСЯ ДЛИНЫ ОТРЕЗКОВ ИЛИ ТОЛЬКО С 
ВОЗРАСТАНИЕМ, ИЛИ ТОЛЬКО С УБЫВАНИЕМ, НАИБОЛЕЕ УДОБЕН ДЛЯ РЕАЛИЗАЦИИ НА 
ВЫЧИСЛИТЕЛЬНОЙ МАШИНЕ, ПОЭТОМУ ФОРМУЛЫ ДЛЯ ДРУГИХ ВАРИАНТОВ НЕ 
ПРИВОДЯТСЯ (СМ.~ОБЗОР Barton~D.~E., Mallows~ё.~L., {\sl Annals of Math.\ 
Statistics,\/} {\bf 36}  (1965), 236--260].

шЗ ВСЕХ ОПИСАННЫХ ЗДЕСЬ ТЕСТОВ ПРОВЕРКА ЧАСТОТ И ПРОВЕРКА ПОСЛЕДОВАТЕЛЬНОЙ 
КОРРЕЛЯЦИИ---САМЫЕ СЛАБЫЕ, В ТОМ СМЫСЛЕ, ЧТО
%% 89
ПРИ ИСПЫТАНИИ С ПОМОЩЬЮ ЭТИХ ТЕСТОВ ПОЧТИ ВСЕ ДАТЧИКИ СЛУЧАЙНЫХ ЧИСЕЛ 
ДАЮТ УДОВЛЕТВОРИТЕЛЬНЫЕ РЕЗУЛЬТАТЫ. тКРАТЦЕ ТЕОРЕТИЧЕСКОЕ ОБОСНОВАНИЕ 
ЭТОГО БУДЕТ ДАНО В~\S~3.5 (СМ.~УПР.~3.5-26). ъ СРАВНИТЕЛЬНО СИЛЬНЫМ ТЕСТАМ 
ОТНОСИТСЯ ПРОВЕРКА НА МОНОТОННОСТЬ: РЕЗУЛЬТАТЫ УПР.~3.3.3-23, 24 
ПОКАЗЫВАЮТ, ЧТО ПРИ НЕДОСТАТОЧНО БОЛЬШИХ ЗНАЧЕНИЯХ~$m$ ПОСЛЕДОВАТЕЛЬНОСТИ,
ПОЛУЧЕННЫЕ С ПОМОЩЬЮ ЛИНЕЙНОГО КОНГРУЭНТНОГО МЕТОДА, ИМЕЮТ ПОВЫШЕННУЮ 
ДЛИНУ ОТРЕЗКОВ МОНОТОННОСТИ, ТАК ЧТО ЭТОТ ТЕСТ ОПРЕДЕЛЕННО ПОЛЕЗЕН.

тЕРОЯТНО, У ЧИТАТЕЛЯ ВОЗНИКАЕТ ВОПРОС: \emph{"чАЧЕМ ТАК МНОГО ТЕСТОВ?".} 
ьОЖЕТ СОЗДАТЬСЯ ВПЕЧАТЛЕНИЕ, ЧТО НА ИСПЫТАНИЯ ДАТЧИКОВ СЛУЧАЙНЫХ ЧИСЕЛ 
ТРАТИТСЯ БОЛЬШЕ МАШИННОГО "ВРЕМЕНИ, ЧЕМ НА ВЫРАБОТКУ СЛУЧАЙНЫХ ЧИСЕЛ В 
ПРОЦЕССЕ РЕШЕНИЯ ПРИКЛАДНЫХ ЗАДАЧ! ¤ТО НЕВЕРНО, ХОТЯ СЛУЧАИ ЧРЕЗМЕРНОГО 
УВЛЕЧЕНИЯ ПРОВЕРКАМИ ВОЗМОЖНЫ.

эЕОБХОДИМОСТЬ ДОСТАТОЧНО РАЗНООБРАЗНОГО НАБОРА ТЕСТОВ МНОГОКРАТНО 
ОТМЕЧАЛАСЬ В ЛИТЕРАТУРЕ. т ЧАСТНОСТИ, УКАЗЫВАЛОСЬ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТИ, 
ПОЛУЧЕННЫЕ С ПОМОЩЬЮ НЕКОТОРЫХ РАЗНОВИДНОСТЕЙ МЕТОДА СЕРЕДИНЫ КВАДРАТА, 
ХОРОШО ПРОХОДЯТ ПРОВЕРКУ ЧАСТОТ, ИНТЕРВАЛОВ, КОМБИНАЦИЙ, НО ОКАЗЫВАЮТСЯ 
СОВЕРШЕННО НЕГОДНЫМИ ПРИ ПРОВЕРКЕ СЕРИЙ. шЗВЕСТНО, ЧТО ДАТЧИКИ, 
ОСНОВАННЫЕ НА ЛИНЕЙНОМ КОНГРУЭНТНОМ МЕТОДЕ, УДОВЛЕТВОРЯЮТ ПРИ 
МАЛЫХ ЗНАЧЕНИЯХ~$m$ МНОГИМ ТЕСТАМ, НО НЕ УДОВЛЕТВОРЯЮТ ПРОВЕРКЕ 
НА МОНОТОННОСТЬ, ТАК КАК ДАЮТ СЛИШКОМ МАЛО ОТРЕЗКОВ ЕДИНИЧНОЙ ДЛИНЫ. ЄЕСТ 
"НАИБОЛЬШЕЕ ИЗ~$t$" ТАКЖЕ ПОЗВОЛЯЕТ ВЫЯВИТЬ ПЛОХИЕ ДАТЧИКИ, КОТОРЫЕ СО 
ВСЕХ ДРУГИХ ТОЧЕК ЗРЕНИЯ ВЕДУТ СЕБЯ ВПОЛНЕ ПРИЕМЛЕМО.

тЕРОЯТНО, ОСНОВНАЯ ПРИЧИНА, ПО КОТОРОЙ НЕОБХОДИМА ВСЕСТОРОННЯЯ ПРОВЕРКА 
ДАТЧИКОВ, ЗАКЛЮЧАЕТСЯ В СЛЕДУЮЩЕМ. хСЛИ КТО-ТО ПОЛЬЗУЕТСЯ ЧУЖИМ ДАТЧИКОМ 
СЛУЧАЙНЫХ ЧИСЕЛ, ТО ПРИ ЛЮБОМ НЕДОРАЗУМЕНИИ ОН БУДЕТ ВИНИТЬ ЭТОТ ДАТЧИК, А 
НЕ СВОЮ ПРОГРАММУ. эУЖНО, ЧТОБЫ АВТОР ДАТЧИКА МОГ \emph{ДОКАЗАТЬ,} ЧТО 
СЛУЧАЙНЫЕ ЧИСЛА УДОВЛЕТВОРЯЮТ ВСЕМ ТРЕБОВАНИЯМ. ё ДРУГОЙ СТОРОНЫ, ЕСЛИ 
ВЫ ПИШЕТЕ ДАТЧИК ДЛЯ СЕБЯ, А НЕ ДЛЯ ОБЩЕГО ПОЛЬЗОВАНИЯ, МОЖНО НЕ ТРАТИТЬ 
СИЛ НА ЕГО ПРОВЕРКУ; ВО ВСЯКОМ СЛУЧАЕ, ЕСЛИ ЗА ОСНОВУ ВЗЯТЬ КАКОЙ-ЛИБО ИЗ 
АЛГОРИТМОВ, РЕКОМЕНДОВАННЫХ В ЭТОЙ ГЛАВЕ, С БОЛЬШОЙ ВЕРОЯТНОСТЬЮ ЭТОТ 
ДАТЧИК БУДЕТ ВПОЛНЕ УДОВЛЕТВОРИТЕЛЬНЫМ.

\excercises

\ex[10] яОЧЕМУ ПРИ ПРОВЕРКЕ СЕРИЙ (СМ.~П.~т) СЛЕДУЕТ ИСПОЛЬЗОВАТЬ 
ПАРЫ~$(Y_0, Y_1)$ $(Y_2, Y_3)$,~\dots, $(Y_{2n-2}, Y_{2n-1})$, А НЕ~$(Y_0, Y_1)$, 
$(Y_1, Y_2)$,~\dots, $(Y_{n-1}, Y_n)$? 

\ex[10] яОКАЖИТЕ, КАК ОБОБЩИТЬ ПРОВЕРКУ СЕРИЙ С ПАР НА ТРОЙКИ, ЧЕТВЕРКИ И~Т.~Д.

\rex[ь20] ёКОЛЬКО В СРЕДНЕМ ПОТРЕБУЕТСЯ ПЕРЕБРАТЬ ЗНАЧЕНИЙ~$U$ ПРИ 
ПРОВЕРКЕ ИНТЕРВАЛОВ (АЛГОРИТМ~G), ПРЕЖДЕ ЧЕМ БУДЕТ ОБНАРУЖЕНО $n$~ИНТЕРВАЛОВ,
%% 90
В ПРЕДПОЛОЖЕНИИ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ ДЕЙСТВИТЕЛЬНО СЛУЧАЙНАЯ? ъАКОВО 
СТАНДАРТНОЕ ОТКЛОНЕНИЕ ЭТОЙ ВЕЛИЧИНЫ?

\ex[12] яОКАЖИТЕ, ЧТО ПРИ ПРОВЕРКЕ ИНТЕРВАЛОВ ЗАКОННО ПОЛЬЗОВАТЬСЯ ВЕРОЯТНОСТЯМИ~(4).

\ex[M23] яРИ "КЛАССИЧЕСКОЙ" ПРОВЕРКЕ ИНТЕРВАЛОВ,  ОПИСАННОЙ ъЕНДАЛЛОМ И 
сЭБИНГТОН-ёМИТОМ, $N$~ЗНАЧЕНИЙ~$U$, ПОДЛЕЖАЩИХ ПРОВЕРКЕ, ИСПОЛЬЗУЮТСЯ ДЛЯ 
ПОСТРОЕНИЯ ЦИКЛИЧЕСКОЙ ПОСЛЕДОВАТЕЛЬНОСТИ, В КОТОРОЙ $U_{N+j}$~СОВПАДАЕТ  
С~$U_j$. хСЛИ $n$~ЧИСЕЛ ИЗ~$U_0$,~\dots, $U_{N-1}$ ПОПАДАЮТ В 
ИНТЕРВАЛ~$\alpha\le U_j < \beta$, ТО В ЦИКЛИЧЕСКОЙ ПОСЛЕДОВАТЕЛЬНОСТИ 
ИМЕЕТСЯ $n$~ИНТЕРВАЛОВ. яУСТЬ~$Z_r$---ЧИСЛО ИНТЕРВАЛОВ ДЛИНЫ~$r$, 
ЕСЛИ~$0\le r<t$, А~$Z_t$---ЧИСЛО ИНТЕРВАЛОВ ДЛИНЫ~$\ge t$. яОКАЖИТЕ, ЧТО 
ВЕЛИЧИНА~$V=\sum_{0\le r\le t} (Z_r-np_r)^2 \Big/ np_r$ ДОЛЖНА ИМЕТЬ 
ПРИ~$N\to\infty$ РАСПРЕДЕЛЕНИЕ~$\chi^2$ С $t$~СТЕПЕНЯМИ СВОБОДЫ, ГДЕ 
$p_r$~ОПРЕДЕЛЕНЫ ВЫРАЖЕНИЕМ~(4).

\ex[40](X.~уИРИНГЕР) рНАЛИЗ ЧАСТОТ ПОЯВЛЕНИЯ РАЗЛИЧНЫХ ЦИФР В ДЕСЯТИЧНОМ 
ПРЕДСТАВЛЕНИИ ЧИСЛА~$e=2.71828\ldots$ ДАЕТ ДЛЯ ПЕРВЫХ 2000~ЦИФР 
ЗНАЧЕНИЕ~$\chi^2=1.06$. ¤ТО УКАЗЫВАЕТ НА ТО, ЧТО ЧАСТОТЫ ЛЕЖАТ ЗНАЧИТЕЛЬНО 
БЛИЖЕ К СРЕДНИМ ЗНАЧЕНИЯМ, РАВНЫМ~$200$, ЧЕМ МОЖНО БЫЛО БЫ ОЖИДАТЬ ПРИ 
СЛУЧАЙНОМ  РАСПРЕДЕЛЕНИИ (ВЕРОЯТНОСТЬ ЗНАЧЕНИЙ~$\chi^2\ge 1.15$ 
РАВНА~$99.9\%$). хСЛИ ПРИМЕНИТЬ ТОТ ЖЕ ТЕСТ К ПЕРВЫМ $10\,000$~ЦИФРАМ, 
ПОЛУЧАЕТСЯ РАЗУМНОЕ ЗНАЧЕНИЕ~$\chi^2=8.61$; НО ФАКТ СТОЛЬ ПРАВИЛЬНОГО 
РАСПРЕДЕЛЕНИЯ ПЕРВЫХ 2000~ЦИФР ОСТАЕТСЯ УДИВИТЕЛЬНЫМ. яРОИЗОЙДЕТ ЛИ ТО ЖЕ 
САМОЕ ПРИ ПРЕДСТАВЛЕНИИ~$e$ В СИСТЕМЕ СЧИСЛЕНИЯ С ДРУГИМ ОСНОВАНИЕМ? 
(ёМ.~{\sl AMM,\/} {\bf 72} (1965), 483--500.)

\ex[08] яРОВЕРЬТЕСПОМОЩЬЮ ТЕСТА СОБИРАТЕЛЯ КУПОНОВ (АЛГОРИТМ~C) ПРИ~$d=3$ 
И~$n=7$ СЛЕДУЮЩУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ: $1101221022120202001212201010201121$.
 ъАКОВЫ ДЛИНЫ СЕМИ ПОДПОСЛЕДОВАТЕЛЬНОСТЕЙ?

% ex. 8
\rex[M22] ёКОЛЬКО В СРЕДНЕМ НАДО ПЕРЕБРАТЬ ЗНАЧЕНИЙ~$U$  В ТЕСТЕ 
СОБИРАТЕЛЯ КУПОНОВ (АЛГОРИТМ~C) ДЛЯ ПОЛУЧЕНИЯ $n$~ПОЛНЫХ НАБОРОВ, ЕСЛИ 
ПОСЛЕДОВАТЕЛЬНОСТЬ СЛУЧАЙНАЯ?  юПРЕДЕЛИТЕ ТАКЖЕ СТАНДАРТНОЕ ОТКЛОНЕНИЕ 
ЭТОЙ ВЕЛИЧИНЫ. (\emph{єКАЗАНИЕ:} СМ.\  ФОРМУЛУ~1.2.9-28.)

% ex. 9
\ex[M21] юБОБЩИТЕ ТЕСТ СОБИРАТЕЛЯ КУПОНОВ ТАК, ЧТОБЫ ДАЛЬНЕЙШИЙ ПОИСК 
ПРЕКРАЩАЛСЯ ПОСЛЕ ТОГО, КАК НАЙДЕНО $w$~РАЗЛИЧНЫХ ЗНАЧЕНИЙ, ГДЕ~$w\le 
d$---ПОЛОЖИТЕЛЬНОЕ ЦЕЛОЕ ЧИСЛО. ъАКИЕ ВЕРОЯТНОСТИ НАДО ИСПОЛЬЗОВАТЬ В ЭТОМ 
СЛУЧАЕ ВМЕСТО~(6).

\ex[M23] тЫПОЛНИТЕ УПР.~8 ДЛЯ ОБОБЩЕННОГО ТЕСТА СОБИРАТЕЛЯ КУПОНОВ, 

\ex[00] т ПРЕДСТАВЛЕНИИ~(9) ДЛЯ КОНКРЕТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ ОТМЕЧЕНЫ 
ВОЗРАСТАЮЩИЕ ОТРЕЗКИ; КАКОВЫ УБЫВАЮЩИЕ ОТРЕЗКИ ДЛЯ ТОЙ ЖЕ ПОСЛЕДОВАТЕЛЬНОСТИ?

\ex[22] чАДАНО $n$~РАЗЛИЧНЫХ ЧИСЕЛ~$U_0$, $U_1$,~\dots, $U_{n-1}$. 
чАПИШИТЕ АЛГОРИТМ, КОТОРЫЙ ОПРЕДЕЛЯЕТ ДЛИНЫ ВСЕХ ОТРЕЗКОВ ВОЗРАСТАНИЯ В 
ЭТОЙ ПОСЛЕДОВАТЕЛЬНОСТИ. т РЕЗУЛЬТАТЕ РАБОТЫ АЛГОРИТМА В~$|COUNT|[r]$ 
ПРИ~$1\le r \le 5$  ДОЛЖНО НАХОДИТЬСЯ ЧИСЛО ОТРЕЗКОВ ДЛИНЫ~$r$, А 
В~$|COUNT|[6]$---ЧИСЛО ОТРЕЗКОВ ДЛИНЫ~$6$ ИЛИ БОЛЕЕ.

\ex[M23] яОКАЖИТЕ, ЧТО~(16) ЕСТЬ ЧИСЛО ПЕРЕСТАНОВОК ТИПА~(15) 
ИЗ~$p+q+1$~РАЗЛИЧНЫХ ЭЛЕМЕНТОВ.

\ex[M15] хСЛИ МЫ БУДЕМ "ВЫБРАСЫВАТЬ" ЭЛЕМЕНТ, НЕПОСРЕДСТВЕННО СЛЕДУЮЩИЙ ЗА 
ОТРЕЗКОМ МОНОТОННОСТИ, ТАК ЧТО В СЛУЧАЕ~$X_j>X_{j+1}$ ОЧЕРЕДНОЙ ОТРЕЗОК 
МОНОТОННОСТИ НАЧНЕТСЯ С~$X_{j+2}$, ТО ДЛИНЫ ТАКИХ ОТРЕЗКОВ БУДУТ 
НЕЗАВИСИМЫМИ И МОЖНО БУДЕТ ВОСПОЛЬЗОВАТЬСЯ ОБЫЧНЫМ КРИТЕРИЕМ~$\chi^2$ 
(ВМЕСТО ВЕСЬМА СЛОЖНОГО МЕТОДА, ПРИВЕДЕННОГО В ТЕКСТЕ). ъАКИМИ ДОЛЖНЫ БЫТЬ 
СООТВЕТСТВУЮЩИЕ ВЕРОЯТНОСТИ ДЛИН ОТРЕЗКОВ МОНОТОННОСТИ ДЛЯ ЭТОГО 
УПРОЩЕННОГО ТЕСТА?

\ex[M20] яОЧЕМУ ЗНАЧЕНИЯ~$V_0^t$, $V_1^t$,~\dots, $V_{n-1}^t$ В ТЕСТЕ 
"НАИБОЛЬШЕЕ ИЗ~$t$" ДОЛЖНЫ БЫТЬ РАСПРЕДЕЛЕНЫ РАВНОМЕРНО МЕЖДУ НУЛЕМ И ЕДИНИЦЕЙ?

\rex[15] (a)~яУСТЬ ТРЕБУЕТСЯ ПРОДЕЛАТЬ ВЫЧИСЛЕНИЯ ДЛЯ ТЕСТА "НАИБОЛЬШЕЕ 
ИЗ~$t$" ПРИ РАЗНЫХ ЗНАЧЕНИЯХ~$t$. 
юБОЗНАЧИМ~$Z_{jt}=\max (U_j, U_{j+1},~\ldots, U_{j+t-1})$. ёТУДЕНТ ёМЫШЛ╕НЫЙ 
ОБНАРУЖИЛ ОСТРОУМНЫЙ СПОСОБ ПЕРЕХОДА ОТ ПОСЛЕДОВАТЕЛЬНОСТИ~$Z_{0(t-1)}$,
%% 91
$Z_{1(t-1)}$,~\dots{} К 
ПОСЛЕДОВАТЕЛЬНОСТИ~$Z_{0t}$, $Z_{1t}$,~\dots, ТРЕБУЮЩИЙ МИНИМАЛЬНЫХ 
ВЫЧИСЛЕНИЙ. яОПРОБУЙТЕ НАЙТИ ЭТОТ СПОСОБ.

(b)~юН ЖЕ РЕШИЛ ИЗМЕНИТЬ МЕТОД "НАИБОЛЬШЕЕ ИЗ~$t$" ТАК, 
ЧТОБЫ~$V_j=\max(U_j,~\ldots, U_{j+t-1})$; ДРУГИМИ СЛОВАМИ, $V_j=Z_{jt}$, 
А 
%% ?? Z_{(t_j)t}
НЕ~$V_j=Z_{(tj)t}$, КАК УКАЗАНО В ТЕКСТЕ. яРИ ЭТОМ ОН РАССУЖДАЛ ТАК: 
\emph{ВСЕ} ДОЛЖНЫ ИМЕТЬ ОДИНАКОВОЕ РАСПРЕДЕЛЕНИЕ, ПОЭТОМУ ТЕСТ ДОЛЖЕН 
СТАТЬ ТОЛЬКО СИЛЬНЕЕ, ЕСЛИ ИСПОЛЬЗОВАТЬ ВСЕ~$Z_{jt}$, $0\le j <n$, А НЕ 
ОДНО ИЗ КАЖДЫХ $t$~ЗНАЧЕНИЙ. юДНАКО ПРИ ПРОВЕРКЕ РАВНОМЕРНОСТИ 
ЗНАЧЕНИЙ~$V_j^t$ ПОЛУЧИЛИСЬ КРАЙНЕ ВЫСОКИЕ ЗНАЧЕНИЯ СТАТИСТИКИ~$V$, ПРИЧЕМ 
ПРИ УВЕЛИЧЕНИИ~$t$ ОНИ СТАНОВИЛИСЬ ЕЩЕ БОЛЬШЕ. ъАК ЭТО МОГЛО ПОЛУЧИТЬСЯ?

\ex[ь25]{(a)~чАДАНЫ ПРОИЗВОЛЬНЫЕ ЧИСЛА~$X_1$,~\dots, $X_n$, $Y_1$,~\dots, 
$Y_n$, ПРИЧЕМ
$$
\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.
$$
юБОЗНАЧИМ~$X'_k=X_k-\bar x$, $Y'_k=Y_k-\bar y$. яОКАЖИТЕ, ЧТО КОЭФФИЦИЕНТ 
КОРРЕЛЯЦИИ~$C$, ВЫЧИСЛЕННЫЙ ПО ФОРМУЛЕ~(24), РАВЕН
$$
\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)~яУСТЬ~$C=N/D$, ГДЕ~$N$ И~$D$---ЧИСЛИТЕЛЬ И ЗНАМЕНАТЕЛЬ ТОЛЬКО ЧТО 
ПРИВЕДЕННОГО ВЫРАЖЕНИЯ. яОКАЖИТЕ, ЧТО~$N^2\le D^2$, Т.~Е.~$-1\le C \le +1$; 
ПОЛУЧИТЕ ФОРМУЛУ ДЛЯ РАЗНОСТИ~$D^2-N^2$. (\emph{єКАЗАНИЕ:} СМ.~УПР.~1.2.3-30.)
 \hiddenpar
(c)~яОКАЖИТЕ, ЧТО ПРИ~$C=\pm1$ ДЛЯ~$1\le k \le n$ МОЖНО НАЙТИ ТАКИЕ 
ПОСТОЯННЫЕ~$a$, $b$, $m$ НЕ ВСЕ РАВНЫЕ НУЛЮ, ЧТО~$a X_k+b Y_k=m$.
}

\ex[ь20] (a)~яОКАЖИТЕ, ЧТО ПРИ~$n=2$ КОЭФФИЦИЕНТ 
ПОСЛЕДОВАТЕЛЬНОЙ КОРРЕЛЯЦИИ~(23) \emph{ВСЕГДА} РАВЕН~$-1$ (ЕСЛИ 
ЗНАМЕНАТЕЛЬ НЕ РАВЕН НУЛЮ). (b)~яОКАЖИТЕ, ЧТО ПРИ~$n=3$ КОЭФФИЦИЕНТ 
ПОСЛЕДОВАТЕЛЬНОЙ КОРРЕЛЯЦИИ ВСЕГДА РАВЕН~$-{1\over2}$. (c)~яОКАЖИТЕ, ЧТО 
ЗНАМЕНАТЕЛЬ В~(23) РАВЕН НУЛЮ ТОГДА И ТОЛЬКО
ТОГДА, КОГДА~$U_0=U_1=\cdots=U_{n-1}$.

\ex[ь40] ўЕМУ РАВНЫ СРЕДНЕЕ ЗНАЧЕНИЕ И СТАНДАРТНОЕ ОТКЛОНЕНИЕ 
КОЭФФИЦИЕНТА ПОСЛЕДОВАТЕЛЬНОЙ КОРРЕЛЯЦИИ~(23), КОГДА~$n=4$, А 
ЗНАЧЕНИЯ~$U$ НЕЗАВИСИМЫ И РАСПРЕДЕЛЕНЫ РАВНОМЕРНО МЕЖДУ НУЛЕМ И ЕДИНИЦЕЙ?

\ex[ь50] юПРЕДЕЛИТЕ РАСПРЕДЕЛЕНИЕ КОЭФФИЦИЕНТА ПОСЛЕДОВАТЕЛЬНОЙ 
КОРРЕЛЯЦИИ~(23) ПРИ ПРОИЗВОЛЬНОМ~$n$, ПРЕДПОЛАГАЯ, ЧТО СЛУЧАЙНЫЕ 
ВЕЛИЧИНЫ~$U_j$ НЕЗАВИСИМЫ И РАСПРЕДЕЛЕНЫ РАВНОМЕРНО МЕЖДУ НУЛЕМ И ЕДИНИЦЕЙ.

\ex[19] ъАКОЕ ЗНАЧЕНИЕ~$f$ ДАСТ АЛГОРИТМ~P ДЛЯ 
ПЕРЕСТАНОВКИ~$(1, 2, 9, 8, 5, 3, 6, 7, 0, 4)$?

\ex[18] фЛЯ КАКОЙ ПЕРЕСТАНОВКИ НАБОРА ЦЕЛЫХ 
ЧИСЕЛ~$\set{0, 1, 2, 3, 4, 5, 6, 7, 8, 9}$ АЛГОРИТМ~P ДАСТ ЗНАЧЕНИЕ~$f=1024$?

\subsubchap{*ЄЕОРЕТИЧЕСКИЕ ТЕСТЫ} %3.3.3
їОТЯ ЛЮБОЙ ДАТЧИК СЛУЧАЙНЫХ ЧИСЕЛ МОЖНО ПРОВЕРИТЬ С ПОМОЩЬЮ МЕТОДОВ, 
ОПИСАННЫХ В ПРЕДЫДУЩЕМ ПУНКТЕ, ГОРАЗДО ЛУЧШЕ ИМЕТЬ "\dfn{АПРИОРНЫЕ} ТЕСТЫ",
Т.~Е.\ ТЕОРЕТИЧЕСКИЕ РЕЗУЛЬТАТЫ, КОТОРЫЕ ПОЗВОЛЯЮТ СКАЗАТЬ ЗАРАНЕЕ, 
КАКИМ БУДЕТ ИСХОД ИСПЫТАНИЙ ДАТЧИКА. ЄАКОГО РОДА ТЕОРЕТИЧЕСКИЕ РЕЗУЛЬТАТЫ 
ПОЗВОЛЯЮТ ЗНАЧИТЕЛЬНО ГЛУБЖЕ ПОНЯТЬ СПОСОБЫ ПОРОЖДЕНИЯ СЛУЧАЙНЫХ ЧИСЕЛ, 
ЧЕМ ЭМПИРИЧЕСКИЕ ДАННЫЕ, ПОЛУЧЕННЫЕ МЕТОДОМ "ПРОБ И ОШИБОК". чДЕСЬ БУДУТ 
БОЛЕЕ ДЕТАЛЬНО ИЗУЧЕНЫ ЛИНЕЙНЫЕ КОНГРУЭНТНЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ;
%% 92
ЗНАЯ, КАКИМИ ДОЛЖНЫ БЫТЬ СЛУЧАЙНЫЕ ЧИСЛА ЕЩЕ
ДО ИХ ВЫРАБОТКИ, МЫ ИМЕЕМ БОЛЬШЕ НАДЕЖДЫ ПРАВИЛЬНО ВЫБРАТЬ ЗНАЧЕНИЯ~$a$, 
$m$ И~$c$.

яОСТРОИТЬ ТЕОРИЮ ЛИНЕЙНОГО КОНГРУЭНТНОГО МЕТОДА ОЧЕНЬ ТРУДНО, ХОТЯ 
ОПРЕДЕЛЕННЫХ УСПЕХОВ В ЭТОЙ ОБЛАСТИ ДОСТИЧЬ УДАЛОСЬ. яОЛУЧЕННЫЕ ДО СИХ 
ПОР РЕЗУЛЬТАТЫ ОТНОСЯТСЯ ГЛАВНЫМ ОБРАЗОМ К \emph{СТАТИСТИЧЕСКОМУ АНАЛИЗУ 
ПОСЛЕДОВАТЕЛЬНОСТИ НА ПОЛНОМ ПЕРИОДЕ.} т ТАКОЙ ПОСТАНОВКЕ ЗАДАЧА ИМЕЕТ 
СМЫСЛ НЕ ДЛЯ ВСЕХ ТЕСТОВ; НАПРИМЕР, ПРИ ПРОВЕРКЕ РАВНОМЕРНОСТИ 
РАСПРЕДЕЛЕНИЯ НА ВСЕМ ПЕРИОДЕ БУДУТ ПОЛУЧАТЬСЯ СЛИШКОМ ХОРОШИЕ 
РЕЗУЛЬТАТЫ. юДНАКО ПРОВЕРКУ СЕРИЙ, ИНТЕРВАЛОВ, ПЕРЕСТАНОВОК И~Т.~Д.\ 
МОЖНО УСПЕШНО ПРОВОДИТЬ И НА ПОЛНОМ ПЕРИОДЕ.

фЛЯ НАЧАЛА ДОКАЖЕМ ПРОСТОЕ \emph{АПРИОРНОЕ} УТВЕРЖДЕНИЕ, КАСАЮЩЕЕСЯ 
НАИМЕНЕЕ СЛОЖНОГО ВАРИАНТА ПРОВЕРКИ ПЕРЕСТАНОВОК ёУТЬ НАШЕЙ ПЕРВОЙ ТЕОРЕМЫ 
СОСТОИТ В ТОМ, ЧТО ЕСЛИ ДАТЧИК ОБЛАДАЕТ ВЫСОКОЙ МОЩНОСТЬЮ, ТО ПРИМЕРНО В 
ПОЛОВИНЕ СЛУЧАЕВ БУДЕТ ВЫПОЛНЯТЬСЯ НЕРАВЕНСТВО~$X_{n+1}<X_n$.

\proclaim ЄЕОРЕМА~P. яУСТЬ~$X_0$, $a$, $c$ И~$m$ ОПРЕДЕЛЯЮТ ЛИНЕЙНУЮ 
КОНГРУЭНТНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ С МАКСИМАЛЬНЫМ ПЕРИОДОМ; ПУСТЬ~$b=a-1$, 
a~$d$---НАИБОЛЬШИЙ ОБЩИЙ ДЕЛИТЕЛЬ~$m$ И~$b$. ЄОГДА ВЕРОЯТНОСТЬ ТОГО, 
ЧТО~$X_{n+1}<X_n$, РАВНА~${1\over2}+r$, ГДЕ
$$
r=(2(c \bmod d)-d)/2m;
$$
СЛЕДОВАТЕЛЬНО, $\abs{r}<d/2m$.

ЄЕХНИКА, КОТОРАЯ ИСПОЛЬЗУЕТСЯ ПРИ ДОКАЗАТЕЛЬСТВЕ ЭТОЙ ТЕОРЕМЫ, ИНТЕРЕСНА 
И САМА ПО СЕБЕ. эАЧНЕМ С ТОГО, ЧТО ВВЕДЕМ
$$
s(x)=(ax+c)\bmod m.
\eqno(1)
$$
ЄОГДА~$X_{n+1}=s(X_n)$ И ТРЕБУЕТСЯ ПОДСЧИТАТЬ ЧИСЛО ТАКИХ ЦЕЛЫХ~$x$,
ЧТО~$0\le x < m$ И~$s(x)<x$ (ТАК КАК КАЖДОЕ ТАКОЕ ЧИСЛО ВСТРЕЧАЕТСЯ, 
ГДЕ-ТО В ПРЕДЕЛАХ ПЕРИОДА). ьЫ ХОТИМ ПОКАЗАТЬ, ЧТО ЭТО ЧИСЛО РАВНО
$$
{1\over2}(m+2(c \bmod d)-d).
\eqno(2)
$$
яРИ~$a=1$ ТЕОРЕМА СПРАВЕДЛИВА: ЛЕГКО ВИДЕТЬ, ЧТО В ЭТОМ СЛУЧАЕ $s(x)<x$ 
ТОЛЬКО ПРИ~$x+c\ge m$, А ЭТО ИМЕЕТ МЕСТО $c$~РАЗ.

\proclaim ыЕММА~A. яУСТЬ~$\alpha$ u~$\beta$---ДЕЙСТВИТЕЛЬНЫЕ ЧИСЛА, 
А~$n$---ЦЕЛОЕ ЧИСЛО. т ЭТОМ СЛУЧАЕ 
$$
\eqalignno{
 &\alpha < n \le \beta \rem{ТОГДА И ТОЛЬКО ТОГДА, КОГДА~$\floor{\alpha}<n\le\floor{\beta}$;} & (3)\cr
 &\alpha\le n < \beta  \rem{ТОГДА И ТОЛЬКО ТОГДА, КОГДА~$\ceil{\alpha}\le n <\ceil{\beta}$.} & (4)\cr
}
$$

¤ТИ ФОРМУЛЫ СЛЕДУЮТ НЕПОСРЕДСТВЕННО ИЗ ОПРЕДЕЛЕНИЙ "ПОТОЛКА" И "ПОЛА"; СМ.~УПР.~1.2.4-3.\endmark
%% 93

фЛЯ ЛЮБОГО ЦЕЛОГО~$x$,  $0\le x < m$,  ОПРЕДЕЛИМ~$k(x)=\floor{(ax+c)/m}$; 
ТОГДА~$s(x)=ax+c-k(x)m$ И~$k(x)\le(ax+c)/m$, ОТКУДА СЛЕДУЕТ, ЧТО 
НЕРАВЕНСТВО~$s(x)<x$ ЭКВИВАЛЕНТНО
$$
(k(x)m-c)/a \le x < (k(x)m-c)/b.
\eqno(5)
$$
фАЛЕЕ, ЭТИ НЕРАВЕНСТВА ЕДИНСТВЕННЫМ ОБРАЗОМ ОПРЕДЕЛЯЮТ~$k(x)$, ПОСКОЛЬКУ 
ИЗ НИХ ВЫТЕКАЮТ НЕРАВЕНСТВА
$$
{ax+c\over m}\le k(x) < {bx+c\over m} < {ax+c\over m}+1.
$$

т СООТВЕТСТВИИ С ЛЕММОЙ~A МОЖНО УТВЕРЖДАТЬ, ЧТО~$s(x)<x$ И~$0\le x <m$ 
ТОГДА И ТОЛЬКО ТОГДА, КОГДА ВЫПОЛНЕНО ОДНО ИЗ ВЗАИМОИСКЛЮЧАЮЩИХ УСЛОВИЙ:
$$
\eqalignno{
 \hbox{(i)~} & \ceil{(km-c)/a}\le x < \ceil{(km-c)/b} \rem{ДЛЯ КАКОГО-ЛИБО~$k$, $0<k<a$;} & (6) \cr
\hbox{(ii)~} & \ceil{m-c/a} \le x < m. \cr
}
$$

ўИСЛО ТАКИХ ЦЕЛЫХ~$x$ РАВНО
$$
m+\sum_{0<k\le b} \ceil{(km-c)/b}-\sum_{0<k\le a}\ceil{(km-c)/a}.
\eqno(7)
$$
ЄЕОРЕМА БУДЕТ ДОКАЗАНА, ЕСЛИ МЫ ПОКАЖЕМ, ЧТО~(7) РАВНО~(2). ёУММЫ В 
ВЫРАЖЕНИИ~(7) МОЖНО ВЫЧИСЛИТЬ ТАК, КАК ОПИСАНО В УПР.~1.2.4-37; МЫ 
ВОСПОЛЬЗУЕМСЯ ДРУГИМ МЕТОДОМ, ЧТОБЫ ПРОДЕМОНСТРИРОВАТЬ ЕЩЕ ОДИН СПОСОБ 
РЕШЕНИЯ ЗАДАЧ ТАКОГО ТИПА. 

юПРЕДЕЛИМ ПРЕЖДЕ ВСЕГО СЛЕДУЮЩИЕ ФУНКЦИИ:
$$
\eqalignno{
 \delta(z)&=\floor{z}+1-\ceil{z}=\cases{
   1, & ЕСЛИ $z$ ЦЕЛОЕ;    \cr
   0, & ЕСЛИ $z$ НЕ ЦЕЛОЕ; \cr
 } & (8) \cr
((z))&=z-\floor{z}-{1\over2}+{1\over2}\delta(z)=z-\ceil{z}+{1\over2}-{1\over2}\delta(z). & (9)\cr
}
$$
яОСЛЕДНЯЯ ПРЕДСТАВЛЯЕТ СОБОЙ "ПИЛООБРАЗНУЮ ФУНКЦИЮ", ИСПОЛЬЗУЕМУЮ В 
ТЕОРИИ РЯДОВ ЇУРЬЕ; ЕЕ ГРАФИК ПОКАЗАН НА РИС.~7. яРЕИМУЩЕСТВА РАБОТЫ С 
ФУНКЦИЕЙ~$((z))$ ПО СРАВНЕНИЮ С~$\floor{z}$ ИЛИ~$\ceil{z}$ ОПРЕДЕЛЯЮТСЯ 
ТЕМ, ЧТО ОНА ОБЛАДАЕТ РЯДОМ ПОЛЕЗНЫХ
\picture{ЁИС.~7. яИЛООБРАЗНАЯ ФУНКЦИЯ~$((z))$.}
%% 94                      	
СВОЙСТВ:
$$
\eqalignno{
\dlp-z\drp &= -\dlp z \drp; & (10) \cr
\dlp z+n \drp &= \dlp z \drp z, \rem{ЕСЛИ $n$ ЦЕЛОЕ;} & (11) \cr
\dlp z \drp + \dlp z+{1\over n}\drp+\cdots+\dlp z+{n-1\over n}\drp&=\dlp nz \drp,
  \rem{ЕСЛИ~$n$---ПОЛОЖИТЕЛЬНОЕ ЦЕЛОЕ ЧИСЛО} & (12)\cr
}
$$
(СМ.~УПР.~2). ьЕНЯЯ ОБОЗНАЧЕНИЯ, МОЖНО ПРЕОБРАЗОВАТЬ~(7) СЛЕДУЮЩИМ ОБРАЗОМ:
$$
{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)
$$
эА ВИД ЭТА ФОРМУЛА ХУЖЕ ТОЙ, С КОТОРОЙ МЫ НАЧИНАЛИ, НО В ДЕЙСТВИТЕЛЬНОСТИ 
ВСЕ ВХОДЯЩИЕ В НЕЕ СУММЫ ЛЕГКО ВЫЧИСЛЯЮТСЯ. ЄАК КАК~$m$ И~$a$ ВЗАИМНО 
ПРОСТЫ, МЫ ЗНАЕМ, ЧТО $(km-c)\bmod a$ ПРИНИМАЕТ В ОПРЕДЕЛЕННОМ ПОРЯДКЕ 
КАЖДОЕ ИЗ ЗНАЧЕНИЙ~$0$, $1$,~\dots, $a-1$ ПРИ~$0<k\le a$, ТАК ЧТО
$$
\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.
$$
(ёПРАВЕДЛИВОСТЬ ВТОРОЙ ФОРМУЛЫ ВЫТЕКАЕТ ИЗ РАВЕНСТВ~(10) И~(11).) фАЛЕЕ, 
ЕСЛИ ЧИСЛА~$m$ И~$b$---НЕ ВЗАИМНО ПРОСТЫЕ, А~$c$ И~$b$---ВЗАИМНО ПРОСТЫЕ, 
ТО~$(km-c)/b$ НЕ МОЖЕТ БЫТЬ ЦЕЛЫМ, ПОЭТОМУ ВТОРАЯ СУММА В~(13) ИСЧЕЗАЕТ. 
эАКОНЕЦ, ИМЕЮТ МЕСТО РАВЕНСТВА
$$
\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
}
$$
ТАК КАК~$0\le (c\bmod d)/b<1/(b/d)$. ёУММА
$$
\sum_{0<k\le b} \dlp{km-c\over b}\drp
$$
РАВНА, СЛЕДОВАТЕЛЬНО, ${1\over 2}d-c\bmod d$, ТАК КАК~$m/d$ И~$b/d$ 
ВЗАИМНО ПРОСТЫ. ЄЕОРЕМА~P ДОКАЗАНА.
\proofend

фОКАЗАТЕЛЬСТВО ТЕОРЕМЫ~P ДЕМОНСТРИРУЕТ ТРУДНОСТЬ ЗАДАЧИ \emph{АПРИОРНОЙ} 
ПРОВЕРКИ СЛУЧАЙНЫХ ЧИСЕЛ, ОДНАКО ОНО В ТО ЖЕ ВРЕМЯ ПОКАЗЫВАЕТ И ЕЕ 
ВЫПОЛНИМОСТЬ. фАЛЕЕ, ИЗ ЭТОЙ ТЕОРЕМЫ СЛЕДУЕТ ЧТО ПРАКТИЧЕСКИ ПРИ ЛЮБОМ 
ВЫБОРЕ~$a$ И~$c$ НЕРАВЕНСТВО~$X_{n+1}<X_n$ БУДЕТ ВЫПОЛНЯТЬСЯ С НУЖНОЙ 
ЧАСТОТОЙ, ВО ВСЯКОМ СЛУЧАЕ НА ВСЕМ ПЕРИОДЕ, КРОМЕ ТЕХ СЛУЧАЕВ, КОГДА~$d$ 
ВЕЛИКО. сОЛЬШИЕ ЗНАЧЕНИЯ~$d$
%% 95
СООТВЕТСТВУЮТ МАЛОЙ МОЩНОСТИ, ЧТО, КАК МЫ ЗНАЕМ, НЕЖЕЛАТЕЛЬНО.

ёЛЕДУЮЩАЯ ТЕОРЕМА ДАЕТ БОЛЕЕ ВАЖНЫЙ КРИТЕРИЙ ДЛЯ ВЫБОРА~$a$ И~$c$; В НЕЙ 
РАССМАТРИВАЕТСЯ \emph{КОЭФФИЦИЕНТ ПОСЛЕДОВАТЕЛЬНОЙ КОРРЕЛЯЦИИ} НА ПОЛНОМ 
ПЕРИОДЕ. ¤ТОТ КОЭФФИЦИЕНТ БЫЛ ОПРЕДЕЛЕН В П.~3.3.2 (СМ.\ ФОРМУЛУ~(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)
$$
яУСТЬ~$x'$---ТАКОЙ ЭЛЕМЕНТ, ЧТО~$s'(x)=0$. ЄОГДА
$$
s(x)=m\dlp{ax+c\over m}\drp+{m\over 2},
\rem{ЕСЛИ~$x\ne x'$.}
\eqno(15)
$$
фЛЯ УПРОЩЕНИЯ ЗАПИСИ ФОРМУЛ ВОСПОЛЬЗУЕМСЯ ОДНОЙ ВАЖНОЙ ФУНКЦИЕЙ, КОТОРАЯ 
ЧАСТО ВОЗНИКАЕТ ВО МНОГИХ МАТЕМАТИЧЕСКИХ ЗАДАЧАХ:
$$
\sigma(h, k, c)=12\sum_{0\le j < k}\dlp{j\over k}\drp\dlp{hj+c\over k}\drp;
\eqno(16)
$$
ОНА НАЗЫВАЕТСЯ \dfn{ОБОБЩЕННОЙ СУММОЙ фЕДЕКИНДА.}

ЄАК КАК
$$
\sum_{0\le x<m} x={m(m-1)\over 2} \quad\hbox{И}\quad
\sum_{0\le x<m} x^2={m(m-1)(2m-1)\over 6},
$$
ТО ФОРМУЛУ~(14) ДОВОЛЬНО ПРОСТО ПРЕОБРАЗОВАТЬ К ВИДУ
$$
C={m\sigma(a, m, c)-3+6(m-x'-c)\over m^2-1}.
\eqno(17)
$$
яОСКОЛЬКУ~$m$ ОБЫЧНО ОЧЕНЬ ВЕЛИКО, МОЖНО ОТБРОСИТЬ ЧЛЕНЫ ПОРЯДКА~$1/m$ И 
ЗАПИСАТЬ ПРИБЛИЖЕННОЕ РАВЕНСТВО
$$
C\approx \sigma(a, m, c)/m
\eqno(18)
$$
С ОШИБКОЙ, МЕНЬШЕЙ~$6/m$ ПО АБСОЛЮТНОЙ ВЕЛИЧИНЕ.

яРОВЕРКА ПОСЛЕДОВАТЕЛЬНОЙ КОРРЕЛЯЦИИ СВОДИТСЯ ПРИ ЭТОМ К ОПРЕДЕЛЕНИЮ СУММЫ 
фЕДЕКИНДА~$\sigma(a, m, c)$. 
тЫЧИСЛЕНИЕ~$\sigma(a, m, c)$ НЕПОСРЕДСТВЕННО ПО ФОРМУЛЕ~(16) ЕДВА ЛИ ПРОЩЕ 
ПРЯМОГО ВЫЧИСЛЕНИЯ КОЭФФИЦИЕНТА КОРРЕЛЯЦИИ, НО, К СЧАСТЬЮ, СУЩЕСТВУЮТ 
ПРОСТЫЕ МЕТОДЫ БЫСТРОГО ПОЛУЧЕНИЯ ЗНАЧЕНИЙ СУММ фЕДЕКИНДА.

\proclaim ыЕММА~B. ("чАКОН ВЗАИМНОСТИ" ДЛЯ СУММ фЕДЕКИНДА.) хСЛИ~$0\le c < h$, 
$0\le c < k$ И ЧИСЛА~$h$ И~$k$ ВЗАИМНО ПРОСТЫЕ, ТО
$$
\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 ьЫ ПРЕДОСТАВЛЯЕМ ЧИТАТЕЛЮ ПОКАЗАТЬ, ЧТО В ЭТИХ ПРЕДПОЛОЖЕНИЯХ СПРАВЕДЛИВО
$$
\sigma(h, k, c)+\sigma(k, h, c)=\sigma(h, k, 0)+\sigma(k, h, 0)+6c^2/hk
\eqno(20)
$$
(СМ.~УПР.~6). ЄЕПЕРЬ ДОСТАТОЧНО РАССМОТРЕТЬ ТОЛЬКО СЛУЧАЙ~$c=0$.

яРИВЕДЕМ ПРИНАДЛЕЖАЩЕЕ ы.~ъАРЛИЦУ ДОКАЗАТЕЛЬСТВО, ОСНОВАННОЕ НА 
ИСПОЛЬЗОВАНИИ КОМПЛЕКСНЫХ КОРНЕЙ ИЗ ЕДИНИЦЫ. ёУЩЕСТВУЕТ БОЛЕЕ ПРОСТОЕ 
ДОКАЗАТЕЛЬСТВО, ТРЕБУЮЩЕЕ ТОЛЬКО ЭЛЕМЕНТАРНЫХ МАНИПУЛЯЦИЙ С СУММАМИ 
(СМ.~УПР.~7); ОДНАКО ПРИВЕДЕННЫЙ НИЖЕ СПОСОБ БОЛЕЕ ПОУЧИТЕЛЕН, ТАК КАК В 
НЕМ ИСПОЛЬЗУЕТСЯ ТЕХНИКА, КОТОРАЯ МОЖЕТ БЫТЬ ПОЛЕЗНА И В ДРУГИХ ЗАДАЧАХ ТАКОГО ТИПА.

юПРЕДЕЛИМ ПОЛИНОМЫ~$f(x)$ И~$g(x)$ СЛЕДУЮЩИМ ОБРАЗОМ:
$$
\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)
$$
хСЛИ~$\omega=e^{2\pi i/k}$---КОМПЛЕКСНЫЙ КОРЕНЬ СТЕПЕНИ~$k$ ИЗ ЕДИНИЦЫ ТО, 
СОГЛАСНО~(1.2.9-13),
$$
{1\over k}\sum_{0<j\le k} \omega^{jr}g(\omega^jx)=rx^r
\rem{ПРИ $0\le r < k$.} 
\eqno (52)
$$
яОЛОЖИМ~$x=1$; ТОГДА~$g(\omega^j x)=k/(\omega^j-1)$ ПРИ~$j\ne k$ 
И~$k(k-1)/2$ ПРИ~$j=k$. юТСЮДА СЛЕДУЕТ, ЧТО
$$
r \bmod k \sum_{0<j<k} {\omega^{-jr}\over \omega^j-1}+{1\over2}(k-1),
\rem{ЕСЛИ~$r$---ЦЕЛОЕ.}
\eqno (23)
$$
(ЄАК КАК, СОГЛАСНО~(22), ПРАВАЯ ЧАСТЬ РАВНА~$r$ ПРИ~$0 \le r < k$ И ПРИ 
ДОБАВЛЕНИИ К~$r$ КРАТНОГО~$k$ ОНА НЕ ИЗМЕНЯЕТСЯ.) ёЛЕДОВАТЕЛЬНО,
$$
\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)
$$
¤ТА ВАЖНАЯ ФОРМУЛА, КОТОРАЯ СПРАВЕДЛИВА ДЛЯ ЛЮБЫХ ЦЕЛЫХ~$r$, ПОЗВОЛЯЕТ 
СВЕСТИ~$((r/k))$ К СУММЕ, ВКЛЮЧАЮЩЕЙ КОРНИ СТЕПЕНИ~$k$ ИЗ ЕДИНИЦЫ; ПРИ 
ЭТОМ ВОЗНИКАЕТ ЦЕЛЫЙ РЯД НОВЫХ ВОЗМОЖНОСТЕЙ.
т ЧАСТНОСТИ, ИМЕЕТ МЕСТО СЛЕДУЮЩАЯ ФОРМУЛА:
$$
\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)
$$
яРАВУЮ ЧАСТЬ ЭТОЙ ФОРМУЛЫ МОЖНО УПРОСТИТЬ, ПРОВЕДЯ СУММИРОВАНИЕ ПО~$r$; 
ЕСЛИ~$s\bmod k \ne 0$, ТО~$\sum_{0\le r < k} \omega^{rs}=f(\omega^s)=0$. 
ЇОРМУЛА~(25) СВОДИТСЯ К
$$
\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
рНАЛОГИЧНАЯ ФОРМУЛА С ЗАМЕНОЙ~$\omega$ НА~$\zeta=e^{2\pi i/h}$ СПРАВЕДЛИВА 
ДЛЯ~$\sigma(k, h, 0)$.

тОПРОС О ТОМ, ЧТО ДЕЛАТЬ ДАЛЬШЕ С СУММОЙ В~(26), НЕ ОЧЕВИДЕН; ОДНАКО 
СУЩЕСТВУЕТ ЭЛЕГАНТНЫЙ СПОСОБ ДАЛЬНЕЙШИХ ПРЕОБРАЗОВАНИЙ, ОСНОВАННЫЙ НА 
ТОМ ФАКТЕ, ЧТО КАЖДЫЙ ЧЛЕН СУММЫ ЯВЛЯЕТСЯ ФУНКЦИЕЙ~$\omega^j$, $0<j<k$, И 
ПО СУЩЕСТВУ СУММИРУЮТСЯ ВСЕ КОРНИ СТЕПЕНИ~$k$ ИЗ ЕДИНИЦЫ, КРОМЕ~$1$. 
чАМЕТИМ, ЧТО ДЛЯ ЛЮБЫХ НЕСОВПАДАЮЩИХ КОМПЛЕКСНЫХ ЧИСЕЛ~$x_1$, $x_2$,~\dots,
$x_n$ СПРАВЕДЛИВО СЛЕДУЮЩЕЕ РАВЕНСТВО:
$$
\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)
$$
КОТОРОЕ СЛЕДУЕТ ИЗ ОБЫЧНОГО РАЗЛОЖЕНИЯ ПРАВОЙ ЧАСТИ НА ЭЛЕМЕНТАРНЫЕ 
ДРОБИ. фАЛЕЕ, ЕСЛИ~$q(x)=(x-y_1)(x-y_2)\ldots(x-y_m)$, ТО
$$
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)
$$
¤ТО РАВЕНСТВО ЧАСТО ИСПОЛЬЗУЕТСЯ ДЛЯ УПРОЩЕНИЯ ВЫРАЖЕНИЙ ТАКОГО ТИПА, КАК 
ЛЕВАЯ ЧАСТЬ~(27). хСЛИ~$h$ И~$k$ ВЗАИМНО ПРОСТЫ, ТО ВСЕ ЗНАЧЕНИЯ~$\omega$, 
$\omega^2$,~\dots, $\omega^{k-1}$, $\zeta$, $\zeta^2$,~\dots, 
$\zeta^{h-1}$ НЕ СОВПАДАЮТ ДРУГ С ДРУГОМ. ёЛЕДОВАТЕЛЬНО, МОЖНО 
РАССМАТРИВАТЬ~(27) КАК ЧАСТНЫЙ СЛУЧАЙ 
ПОЛИНОМА~$(x-\omega)\ldots(x-\omega^{k-1})(x-\zeta)\ldots(x-\zeta^{h-1})=(x^k-1)(x^h-1)/(x-1)^2$, 
ОТКУДА СЛЕДУЕТ РАВЕНСТВО
$$
{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)
$$
шЗ ЭТОГО РАВЕНСТВА ВЫТЕКАЕТ МНОГО ИНТЕРЕСНЫХ СЛЕДСТВИЙ, И ОНО ПРИВОДИТ К 
ЦЕЛОМУ РЯДУ СООТНОШЕНИЙ ВЗАИМНОСТИ ДЛЯ СУММ, ТАКИХ, КАК~(26). эАПРИМЕР, 
ЕСЛИ ПРОДИФФЕРЕНЦИРОВАТЬ~(29) ДВАЖДЫ ПО~$x$ И ПОЛОЖИТЬ~$x=1$, ТО ПОЛУЧИТСЯ
$$
{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}.
$$
чАМЕНЯЯ В ЭТИХ СУММАХ~$j$ НА~$h-j$ И~$k-j$, ПОЛУЧИМ [СР.~(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},
$$
ЧТО ЭКВИВАЛЕНТНО ТРЕБУЕМОМУ РЕЗУЛЬТАТУ. 
\proofend
%%  98

\proclaim ыЕММА~C. хСЛИ ЧИСЛА~$h$ И~$k$ ВЗАИМНО ПРОСТЫЕ И~$0<c<k$, ТО
$$
\sigma(h, k, c)=\sigma(h, k, c \bmod h)+{6r\over k}(c+c\bmod h-k)+d,
\eqno(30)
$$
ГДЕ~$r=\floor{c/h}$, $d=0$ ПРИ~$c\bmod h \ne 0$ И~$d=3$ ПРИ~$c \bmod h=0$. 

\proof яРИ ЛЮБОМ~$c$ ИМЕЕМ
$$
\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
}
$$
ТАК КАК, СОГЛАСНО~(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)
$$
яУСТЬ ТЕПЕРЬ~$c_0=c\bmod h$, ТАК ЧТО~$0<c=c_0+rh<k$. ЄОГДА
$$
\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
}
$$
яРОСТОЕ СУММИРОВАНИЕ ЗАВЕРШАЕТ ДОКАЗАТЕЛЬСТВО.
\proofend

ыЕММЫ~B И~C ПОЗВОЛЯЮТ СФОРМУЛИРОВАТЬ СЛЕДУЮЩУЮ ЭФФЕКТИВНУЮ ПРОЦЕДУРУ 
ВЫЧИСЛЕНИЯ~$\sigma(h, k, c)$ В СЛУЧАЕ, КОГДА~$h$ И~$k$ ВЗАИМНО ПРОСТЫ.

{\sl °АГ~1.\/}~фОБАВЛЯТЬ (ИЛИ ВЫЧИТАТЬ) КРАТНЫЕ~$k$ К (ИЗ)~$h$ И~$c$ (ЕСЛИ 
ЭТО НЕОБХОДИМО), С ТЕМ ЧТОБЫ ПРИВЕСТИ ИХ К 
ИНТЕРВАЛАМ~$-{k\over 2}<h\le {k\over 2}$, $-{k\over 2}<c\le {k\over 2}$
(ИЛИ К ИНТЕРВАЛАМ~$0<h \le k$,  $0\le c < k$). ЄАКАЯ ОПЕРАЦИЯ ЗАКОННА, 
ПОТОМУ ЧТО ПО ОПРЕДЕЛЕНИЮ
$$
\sigma(h\pm nk, k, c)=\sigma(h, k, c)=\sigma(h, k, c\pm nk).
\eqno(33)
$$

{\sl °АГ~2.\/}~хСЛИ~$h$ ИЛИ~$c$ ОТРИЦАТЕЛЬНЫ, СДЕЛАТЬ ИХ ПОЛОЖИТЕЛЬНЫМИ, 
ИСПОЛЬЗУЯ РАВЕНСТВА
$$
\eqalign{
\sigma(-h, k, c)&=-\sigma(h, k, c),\cr
\sigma(h, k, -c)&=\sigma(h, k, c).\cr
}
\eqno(34)
$$

{\sl °АГ~3.\/} хСЛИ~$k=1$ ИЛИ~$k=2$, ТО~$\sigma(h, k, c)=0$ 
(ТАК КАК~$\dlp j/1 \drp=\dlp j/2 \drp =0$). 

%% 99
{\sl °АГ~4.\/}~хСЛИ~$c>h$, ЗАМЕНИТЬ~$c$ НА~$c\bmod h$ С ПОМОЩЬЮ 
СООТНОШЕНИЯ~(30) ЛЕММЫ~C.

{\sl °АГ~5.\/}~ЄЕПЕРЬ СОБЛЮДЕНЫ УСЛОВИЯ ЛЕММЫ~B, ТАК ЧТО ИМЕЕМ
$$
\sigma(h, k, c)=-3+{h\over k}+{k\over h}+{1+6c^2\over hk}-\sigma(k, h, c). 
\eqno (35)
$$
фЛЯ ОПРЕДЕЛЕНИЯ~$\sigma(k, h, c)$ ВЕРНУТЬСЯ К ШАГУ~1.

ўИСЛО НЕОБХОДИМЫХ ИТЕРАЦИЙ ОБЫЧНО НЕВЕЛИКО; ПОСЛЕДОВАТЕЛЬНЫЕ 
ЗНАЧЕНИЯ~$h$ И~$k$ ВЕДУТ СЕБЯ ТАК ЖЕ, КАК ПОСЛЕДОВАТЕЛЬНОСТЬ ЗНАЧЕНИЙ, 
ПОЛУЧАЕМАЯ ПРИ ОПРЕДЕЛЕНИИ С ПОМОЩЬЮ АЛГОРИТМА хВКЛИДА (СМ.~П.~4.5.2) 
НАИБОЛЬШЕГО ОБЩЕГО ДЕЛИТЕЛЯ~$h$ И~$k$. ЁАССМОТРИМ НЕСКОЛЬКО ПРИМЕРОВ.

\proclaim яРИМЕР~1. эАЙТИ КОЭФФИЦИЕНТ ПОСЛЕДОВАТЕЛЬНОЙ КОРРЕЛЯЦИИ ДЛЯ 
СЛУЧАЯ~$m=2^{35}$, $a=2^{34}+1$, $c=1$.

\solution ёОГЛАСНО~(17), ИМЕЕМ
$$
C=(2^{35}\sigma(2^{34}+1, 2^{35}, 1)-3+6(2^{35}-(2^{34}-1)-1))/(2^{70}-1). 
\eqno (36)
$$
тЫПОЛНЯЯ ШАГИ~1 И~2, ПОЛУЧАЕМ
$$
(\sigma(2^{34}+1, 2^{35}, 1)=-\sigma(2^{34}-1, 2^{35}, 1).
$$
ёОГЛАСНО ШАГУ~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).
$$
ёОГЛАСНО ШАГУ~1:
$$
\sigma(2^{35}, 2^{34}-1, 1)=\sigma(2, 2^{34}-1, 1).
$$
ЄЕПЕРЬ ШАГ~5 ДАЕТ
$$
\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)
$$
И
$$
\sigma(2^{34}-1, 2, 1)=0.
$$
т РЕЗУЛЬТАТЕ ПОЛУЧАЕМ, ЧТО
$$
C={1\over 4}+\varepsilon, \rem{$\abs{\varepsilon}<2^{-67}$.}
\eqno(37)
$$
ЄАКАЯ КОРРЕЛЯЦИЯ, БЕЗУСЛОВНО, НЕПРИЕМЛЕМА. ъОНЕЧНО, ЭТОТ ДАТЧИК ОБЛАДАЕТ 
СЛИШКОМ МАЛОЙ МОЩНОСТЬЮ; МЫ УЖЕ ОТВЕРГЛИ ЕГО РАНЕЕ КАК НЕСЛУЧАЙНЫЙ.

\proclaim яРИМЕР~2. юПРЕДЕЛИТЬ ПРИБЛИЗИТЕЛЬНО КОЭФФИЦИЕНТ ПОСЛЕДОВАТЕЛЬНОЙ 
КОРРЕЛЯЦИИ ПРИ~$m=10^{10}$, $a=10001$, $b=2113248658$.

%% 100

\solution ЄАК КАК~$C\approx \sigma(a, m,c)/m$, ДЕЛАЕМ СЛЕДУЮЩИЕ ВЫЧИСЛЕНИЯ:
\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
  }
}

ЄАКОЕ ЗНАЧЕНИЕ~$C$, КОНЕЧНО, УДОВЛЕТВОРЯЕТ ЛЮБЫМ ТРЕБОВАНИЯМ. эО МОЩНОСТЬ 
ЭТОГО ДАТЧИКА РАВНА ВСЕГО~$3$, \emph{ТАК ЧТО, НЕСМОТРЯ НА ОТСУТСТВИЕ 
ПОСЛЕДОВАТЕЛЬНОЙ КОРРЕЛЯЦИИ, ЕГО НЕЛЬЗЯ СЧИТАТЬ ХОРОШИМ ИСТОЧНИКОМ 
СЛУЧАЙНЫХ ЧИСЕЛ.} юТСУТСТВИЕ КОРРЕЛЯЦИИ--- НЕОБХОДИМОЕ, НО НЕ ДОСТАТОЧНОЕ УСЛОВИЕ!

\proclaim яРИМЕР~3. юЦЕНИТЬ ПОСЛЕДОВАТЕЛЬНУЮ КОРРЕЛЯЦИЮ ПРИ ЛЮБЫХ~$a$, $m$, $c$.

яЕРВУЮ ФАЗУ ПРИВЕДЕННЫХ ВЫШЕ РАСЧЕТОВ МОЖНО ПРОДЕЛАТЬ В ОБЩЕМ ВИДЕ. 
яУСТЬ~$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
}
$$
ёОГЛАСНО УПР.~12, $\abs{\sigma(m, a, c_0)}<a$, ПОЭТОМУ
\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).
}
яРИ ЭТОМ МЫ ПРЕНЕБРЕГЛИ ЧЛЕНАМИ
\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),
}
ТАК ЧТО МОЖНО СКАЗАТЬ, ЧТО ПОГРЕШНОСТЬ ВЫРАЖЕНИЯ~\eqref[40] НЕ 
ПРЕВЫШАЕТ~$a/m$. уЛАВНЫЙ ВКЛАД В ОШИБКУ ДАЕТ ЧЛЕН~$\sigma(m, a, c_0)/m$. 
яОЛУЧЕННЫЕ РЕЗУЛЬТАТЫ МОЖНО СУММИРОВАТЬ СЛЕДУЮЩИМ ОБРАЗОМ.

\proclaim ЄЕОРЕМА~S. ъОЭФФИЦИЕНТ ПОСЛЕДОВАТЕЛЬНОЙ КОРРЕЛЯЦИИ ДЛЯ ЛИНЕЙНОЙ 
КОНГРУЭНТНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ С МАКСИМАЛЬНЫМ ПЕРИОДОМ ОПРЕДЕЛЯЕТСЯ 
ПРИБЛИЖЕННЫМ ВЫРАЖЕНИЕМ~\eqref[40] С ОШИБКОЙ,
%% 101
\bye