\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