\input style
\chapnotrue\chapno=3\subchno=4\subsubchno=1
\subsubchap{сЛУЧАЙНАЯ ВЫБОРКА И ПЕРЕМЕШИВАНИЕ\note{1}%
{в ОРИГИНАЛЕ shuffling---ТАСОВАНИЕ.---{\sl пРИМ. ПЕРЕВ.\/}}} % 3.4.2
пРИ ОБРАБОТКЕ ДАННЫХ ЧАСТО БЫВАЕТ НЕОБХОДИМО СЛУЧАЙНЫМ ОБРАЗОМ И
БЕСПРИСТРАСТНО ВЫБРАТЬ $n$~ЗАПИСЕЙ ИЗ ФАЙЛА, В КОТОРОМ СОДЕРЖИТСЯ
$N$~ЗАПИСЕЙ. тАКАЯ ЗАДАЧА ВОЗНИКАЕТ, НАПРИМЕР, ПРИ КОНТРОЛЕ КАЧЕСТВА ИЛИ В
ДРУГИХ СТАТИСТИЧЕСКИХ ВЫЧИСЛЕНИЯХ, ГДЕ ТРЕБУЮТСЯ ВЫБОРКИ. оБЫЧНО $N$ ОЧЕНЬ
ВЕЛИКО, ТАК ЧТО ОДНОВРЕМЕННО ХРАНИТЬ ВСЕ ДАННЫЕ В ПАМЯТИ НЕВОЗМОЖНО,
ПОЭТОМУ НУЖНО НАЙТИ ТАКУЮ ЭФФЕКТИВНУЮ ПРОЦЕДУРУ ВЫБОРА $n$~ЗАПИСЕЙ,
КОТОРАЯ ПОЗВОЛИЛА БЫ СРАЗУ РЕШАТЬ, ПРИНЯТЬ ИЛИ ОТКЛОНИТЬ КАЖДУЮ
ПРОХОДЯЩУЮ ЗАПИСЬ.

дЛЯ РЕШЕНИЯ ЭТОЙ ЗАДАЧИ БЫЛО ПРЕДЛОЖЕНО НЕСКОЛЬКО МЕТОДОВ. нАИБОЛЕЕ
ОЧЕВИДЕН ТАКОЙ ПОДХОД, КОГДА ЛЮБАЯ ЗАПИСЬ ВЫБИРАЕТСЯ С ОДНОЙ И ТОЙ ЖЕ
ВЕРОЯТНОСТЬЮ~$n/N$. иНОГДА ЭТОТ СПОСОБ ОКАЗЫВАЕТСЯ УДОБНЫМ, НО ПРИ ЕГО
ИСПОЛЬЗОВАНИИ В ВЫБОРКЕ ПОЛУЧАЕТСЯ $n$~ЗАПИСЕЙ ТОЛЬКО В \emph{СРЕДНЕМ,}
ПРИЧЕМ СТАНДАРТНОЕ ОТКЛОНЕНИЕ РАВНО~$\sqrt{n(1-(n/N))}$: ВЫБОРКА МОЖЕТ
ОКАЗАТЬСЯ ИЛИ СЛИШКОМ БОЛЬШОЙ, ИЛИ СЛИШКОМ МАЛОЙ ДЛЯ ДОСТИЖЕНИЯ ЖЕЛАЕМЫХ
РЕЗУЛЬТАТОВ.

пРИВЕДЕМ ПРОСТУЮ МОДИФИКАЦИЮ ЭТОГО "ОЧЕВИДНОГО" МЕТОДА, ЛИШЕННУЮ ТАКОГО
НЕДОСТАТКА. еСЛИ $m$~ЗАПИСЕЙ УЖЕ БЫЛО ОТОБРАНО, МЫ ДОЛЖНЫ ВКЛЮЧИТЬ
$(t+1)\hbox{-Ю}$~ЗАПИСЬ В ВЫБОРКУ С ВЕРОЯТНОСТЬЮ~$(n-m)/(N-t)$. эТА
ВЕРОЯТНОСТЬ ВЫРАЖАЕТСЯ ИМЕННО ТАКОЙ ВЕЛИЧИНОЙ, ПОСКОЛЬКУ ИЗ ВСЕХ ВОЗМОЖНЫХ
СПОСОБОВ ВЫБОРА $n$~ЗАПИСЕЙ ИЗ~$N$ ТАКИМ ОБРАЗОМ, ЧТО $m$~ИЗ НИХ
ОТБИРАЮТСЯ ИЗ ПЕРВЫ~$t$,  В ТОЧНОСТИ
$$
\perm{N-t-1}{n-m-1}\bigg/\perm{N-t}{n-m}={n-m\over N-t}
\eqno(1)
$$
ДОЛЯ СПОСОБОВ ВЫБИРАЕТ $(t+1)\hbox{-Й}$~ЭЛЕМЕНТ.

вЫСКАЗАННУЮ ИДЕЮ МОЖНО ОФОРМИТЬ В ВИДЕ СЛЕДУЮЩЕГО АЛГОРИТМА:
\alg S.(мЕТОД ВЫБОРКИ.) вЫБРАТЬ СЛУЧАЙНЫМ ОБРАЗОМ $n$~ЗАПИСЕЙ ИЗ~$N$,
ГДЕ~$0<n\le N$.

\st[нАЧАЛЬНАЯ УСТАНОВКА.] уСТАНОВИТЬ~$t\asg 0$, $m\asg 0$.

\st[вЫРАБОТАТЬ~$U$.] вЫРАБОТАТЬ СЛУЧАЙНОЕ ЧИСЛО~$U$,
РАВНОМЕРНО РАСПРЕДЕЛЕННОЕ МЕЖДУ НУЛЕМ И ЕДИНИЦЕЙ.

\st[пРОВЕРИТЬ.] еСЛИ~$(N-t)U \ge n-m$, ПЕРЕЙТИ К~\stp{5}.

%% 152

\st[оТОБРАТЬ.] вКЛЮЧИТЬ ЗАПИСЬ В ВЫБОРКУ И УВЕЛИЧИТЬ~$m$ И~$t$ НА~$1$.
еСЛИ~$m<n$, ПЕРЕЙТИ К~\stp{2}, В ПРОТИВНОМ СЛУЧАЕ ВЫБОРКА СДЕЛАНА И
АЛГОРИТМ ЗАКОНЧЕН.

\st[пРОПУСТИТЬ.] пРОПУСТИТЬ СЛЕДУЮЩУЮ ЗАПИСЬ (НЕ ВКЛЮЧАТЬ ЕЕ В ВЫБОРКУ),
УВЕЛИЧИТЬ~$t$ НА~$1$ И ПЕРЕЙТИ К~\stp{2}.
\algend

нА ПЕРВЫЙ ВЗГЛЯД ЭТОТ АЛГОРИТМ МОЖЕТ ПОКАЗАТЬСЯ НЕНАДЕЖНЫМ И ДАЖЕ
НЕПРАВИЛЬНЫМ, НО ВНИМАТЕЛЬНЫЙ АНАЛИЗ (СМ. УПРАЖНЕНИЯ, ПОМЕЩЕННЫЕ НИЖЕ)
ПОКАЗЫВАЕТ, ЧТО ОН АБСОЛЮТНО ВЕРЕН. нЕТРУДНО УБЕДИТЬСЯ, ЧТО
\medskip
\item{(a)}~ОТБИРАЕТСЯ \emph{РОВНО} $n$~ЭЛЕМЕНТОВ,
\item{(b)}~ВЫБОРКА СОВЕРШЕННО СЛУЧАЙНА: В ЧАСТНОСТИ, ВЕРОЯТНОСТЬ ВЫБОРА
ЛЮБОГО ЗАДАННОГО ЭЛЕМЕНТА, НАПРИМЕР ПОСЛЕДНЕГО ЭЛЕМЕНТА ФАЙЛА, РАВНА~$n/N$.
\medskip

уТВЕРЖДЕНИЕ~(b) СПРАВЕДЛИВО НЕСМОТРЯ НА ТО, ЧТО МЫ \emph{НЕ} ВЫБИРАЕМ
$(t+1)\hbox{-Й}$~ЭЛЕМЕНТ С ВЕРОЯТНОСТЬЮ~$n/N$---МЫ ВЫБИРАЕМ ЕГО В
СООТВЕТСТВИИ С ФОРМУЛОЙ~(1)! эТО ПРИВЕЛО К НЕКОТОРОЙ ПУТАНИЦЕ В
ПУБЛИКАЦИЯХ. мОЖЕТ ЛИ ЧИТАТЕЛЬ ОБоЯСНИТЬ ЭТО КАЖУЩЕЕСЯ ПРОТИВОРЕЧИЕ?

({\sl зАМЕЧАНИЕ.\/} дЛЯ ТОГО ЧТОБЫ ИЗБЕЖАТЬ КОРРЕЛЯЦИЙ МЕЖДУ ВЫБОРКАМИ,
ПОЛУЧЕННЫМИ ПРИ РАЗЛИЧНЫХ ПРОСЧЕТАХ ПО АЛГОРИТМУ~S, СЛЕДУЕТ БРАТЬ
РАЗЛИЧНЫЕ ИСТОЧНИКИ СЛУЧАЙНЫХ ЧИСЕЛ~$U$. дЛЯ ЭТОГО, НАПРИМЕР, МОЖНО БРАТЬ
РАЗЛИЧНЫЕ~$X_0$ В ЛИНЕЙНОМ КОНГРУЭНТНОМ МЕТОДЕ. зНАЧЕНИЕ~$X_0$ МОЖЕТ
БЫТЬ СВЯЗАНО С КАЛЕНДАРНОЙ ДАТОЙ, ИЛИ С ПОСЛЕДНИМ ЗНАЧЕНИЕМ~$X$,
ПОЛУЧЕННЫМ В ПРЕДЫДУЩЕМ ПРОСЧЕТЕ.)

оБЫЧНО НАМ НЕ НУЖНО БУДЕТ ПРОСМАТРИВАТЬ ВСЕ $N$~ЗАПИСЕЙ;
ДЕЙСТВИТЕЛЬНО, ПОСКОЛЬКУ В~(b) УКАЗАНО, ЧТО ПОСЛЕДНЯЯ ЗАПИСЬ ВЫБИРАЕТСЯ С
ВЕРОЯТНОСТЬЮ~$n/N$, В $(1-n/N)$~ДОЛЕ ВСЕХ СЛУЧАЕВ  АЛГОРИТМ ЗАКОНЧИТ СВОЮ
РАБОТУ \emph{ПРЕЖДЕ,} ЧЕМ ДОЙДЕТ ДО ПОСЛЕДНЕЙ ЗАПИСИ. сРЕДНЕЕ ЧИСЛО
РАССМОТРЕННЫХ ЗАПИСЕЙ ДЛЯ~$n=2$ СОСТАВЛЯЕТ ОКОЛО~$(2/3)N$; ОБЩИЕ ФОРМУЛЫ
ДАНЫ В УПР.~5 И~6.

аЛГОРИТМ~S ПРИМЕНИМ ЛИШЬ В ТОМ СЛУЧАЕ, КОГДА ВЕЛИЧИНА~$N$ ЗАРАНЕЕ ИЗВЕСТНА.
пРЕДПОЛОЖИМ ТЕПЕРЬ, ЧТО МЫ ХОТИМ СЛУЧАЙНЫМ ОБРАЗОМ ВЫБРАТЬ
$n$~ЭЛЕМЕНТОВ ИЗ ФАЙЛА, НО НЕ ЗНАЕМ, ИЗ СКОЛЬКИХ ЭЛЕМЕНТОВ ОН СОСТОИТ.
мОЖНО СНАЧАЛА ПЕРЕСЧИТАТЬ ВСЕ ЭЛЕМЕНТЫ, А ПОТОМ, ЧТОБЫ СДЕЛАТЬ ВЫБОРКУ,
ПЕРЕБРАТЬ ИХ ВТОРИЧНО. оДНАКО, ВООБЩЕ ГОВОРЯ, ЛУЧШЕ СРАЗУ ПРИ ПЕРЕСЧЕТЕ
ОТОБРАТЬ $m\ge n$~ЭЛЕМЕНТОВ, ГДЕ $m$~ГОРАЗДО МЕНЬШЕ~$N$, С ТЕМ, ЧТОБЫ
ВТОРОЙ РАЗ ПЕРЕБИРАТЬ ТОЛЬКО $m$~ЭЛЕМЕНТОВ. вЕСЬ ФОКУС, РАЗУМЕЕТСЯ,
ЗАКЛЮЧАЕТСЯ В ТОМ, ЧТОБЫ В РЕЗУЛЬТАТЕ ПОЛУЧИТЬ ИСТИННО СЛУЧАЙНУЮ ВЫБОРКУ
ИЗ ПЕРВОНАЧАЛЬНОГО ФАЙЛА.

сЕЙЧАС МЫ ОПИШЕМ ОСТРОУМНЫЙ ПРИЕМ, РЕАЛИЗУЮЩИЙ ЭТУ ДОВОЛЬНО
НЕПРАВДОПОДОБНУЮ ИДЕЮ. дОПУСТИМ, ИМЕЕТСЯ ДАТЧИК СЛУЧАЙНЫХ ЧИСЕЛ,
СПОСОБНЫЙ ПОРОДИТЬ ПО КРАЙНЕЙ МЕРЕ $N$~РАЗЛИЧНЫХ
%% 153
ЗНАЧЕНИЙ, ПРЕЖДЕ ЧЕМ КАКОЕ-ЛИБО ЗНАЧЕНИЕ ПОВТОРИТСЯ, НАПРИМЕР---ЭТО
ЛИНЕЙНАЯ КОНГРУЭНТНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ С ПЕРИОДОМ, БОЛЬШИМ~$N$. (дЛИНЫ
ПЕРИОДОВ ОБЫЧНО СОСТАВЛЯЮТ НЕСКОЛЬКО МИЛЛИАРДОВ.) дЛЯ ДАТЧИКА МОЖНО
РЕКОМЕНДОВАТЬ АЛГОРИТМ~3.2.2M, ПРЕДЛОЖЕННЫЙ мАКЛАРЕНОМ И мАРСАЛЬЕЙ.

иДЕЯ СОСТОИТ В ТОМ, ЧТОБЫ ВЫЧИСЛИТЬ $N$~СЛУЧАЙНЫХ ВЕЛИЧИН И УСТАНОВИТЬ,
КАКИЕ~$n$ ИЗ НИХ ЯВЛЯЮТСЯ НАИБОЛЬШИМИ. сООТВЕТСТВУЮЩИЕ ИМ $n$~ЗАПИСЕЙ И
СОСТАВЯТ ОКОНЧАТЕЛЬНУЮ ВЫБОРКУ. вО ВРЕМЯ ПЕРВОГО ПЕРЕБОРА МЫ СОЗДАЕМ
"РЕЗЕРВУАР", В КОТОРЫЙ ВХОДЯТ ТОЛЬКО ТАКИЕ $m$~ЗАПИСЕЙ---ВОЗМОЖНЫЕ
КАНДИДАТЫ В ВЫБОРКУ, ЧТО ПЕРЕД СООТВЕТСТВУЮЩИМИ ИМ СЛУЧАЙНЫМИ ВЕЛИЧИНАМИ
НЕТ $n$ БОЛЬШИХ ЗНАЧЕНИЙ (ПЕРВЫЕ $n$~ЭЛЕМЕНТОВ ВСЕГДА ПОПАДАЮТ В РЕЗЕРВУАР).

\alg R.(вЫБОРКА С РЕЗЕРВУАРОМ.) дЛЯ ТОГО ЧТОБЫ ФОРМАЛИЗОВАТЬ ОПИСАННЫЙ
ВЫШЕ ПРОЦЕСС, ВВЕДЕМ ВСПОМОГАТЕЛЬНУЮ ТАБЛИЦУ ИЗ $n$~ЭЛЕМЕНТОВ ВИДА~$(Y, I)$,
ГДЕ~$Y$---СЛУЧАЙНАЯ ВЕЛИЧИНА, СООТВЕТСТВУЮЩАЯ $I\hbox{-Й}$~ЗАПИСИ В
РЕЗЕРВУАРЕ. вНАЧАЛЕ ЭТА ТАБЛИЦА ЦЕЛИКОМ ЗАПОЛНЕНА ЭЛЕМЕНТАМИ~$(0, 0)$.

\st[нАЧАЛЬНАЯ УСТАНОВКА.] уСТАНОВИТЬ~$m\asg 0$.

\st[вЫРАБОТАТЬ~$U$.] пУСТЬ~$U$---СЛУЧАЙНАЯ ВЕЛИЧИНА,
РАВНОМЕРНО РАСПРЕДЕЛЕННАЯ МЕЖДУ НУЛЕМ И ЕДИНИЦЕЙ. (кАК ОБоЯСНЯЛОСЬ РАНЕЕ,
ПРЕДПОЛАГАЕТСЯ, ЧТО $U$ \emph{НЕ РАВНО} НИКАКОМУ ИЗ РАНЕЕ ПОЛУЧЕННЫХ НА
ЭТОМ ШАГЕ СЛУЧАЙНЫХ ЧИСЕЛ.)

\st[пРОВЕРИТЬ.] пУСТЬ НАИМЕНЬШЕЕ ЗНАЧЕНИЕ~$Y$ ВО ВСПОМОГАТЕЛЬНОЙ
ТАБЛИЦЕ~$(Y, I)$ РАВНО~$Y_0$. еСЛИ~$U<Y_0$, ПЕРЕЙТИ К~\stp{6}.

\st[дОБАВИТЬ В РЕЗЕРВУАР.] пЕРЕНЕСТИ СЛЕДУЮЩУЮ ЗАПИСЬ ИЗ ФАЙЛА В РЕЗЕРВУАР
И УВЕЛИЧИТЬ~$m$ НА~$1$.

\st[оБНОВИТЬ ТАБЛИЦУ.] зАМЕНИТЬ ЭЛЕМЕНТ ТАБЛИЦЫ~$(Y_0, I_0)$ НА~$(U, m)$.
пЕРЕЙТИ К~\stp{7}.

\st[пРОПУСТИТЬ.] пРОПУСТИТЬ СЛЕДУЮЩУЮ ЗАПИСЬ ФАЙЛА.

\st[кОНЕЦ ФАЙЛА?] еСЛИ В ФАЙЛЕ БОЛЬШЕ НЕТ ЗАПИСЕЙ, ПЕРЕЙТИ К~\stp{8}, В
ПРОТИВНОМ СЛУЧАЕ---К~\stp{2}.

\st[вТОРОЙ ПЕРЕБОР.] оТСОРТИРОВАТЬ ЭЛЕМЕНТЫ ТАБЛИЦЫ~$(Y, I)$ ПО~$I$.
зАПИСИ В РЕЗЕРВУАРЕ, СООТВЕТСТВУЮЩИЕ РЕЗУЛЬТИРУЮЩИМ
ЗНАЧЕНИЯМ~$I_1<I_2<\ldots<I_n$, СОСТАВЛЯЮТ ОКОНЧАТЕЛЬНУЮ ВЫБОРКУ.
\algend

чИТАТЕЛЬ ДОЛЖЕН ПРОРАБОТАТЬ ПРИМЕР ПРИМЕНЕНИЯ ЭТОГО АЛГОРИТМА В УПР.~9.

тАБЛИЦУ~$(Y, I)$ В АЛГОРИТМЕ~R МОЖНО СОСТАВИТЬ ТАКИМ ОБРАЗОМ, ЧТО
ПОИСК~$Y_0$ НА ШАГЕ~R3 БУДЕТ ОЧЕНЬ БЫСТРЫМ И ПЕРЕНОС~$(U, m)$ НА ШАГЕ~R5
ТАКЖЕ БУДЕТ ЭФФЕКТИВНЫМ. зА ПОДРОБНОСТЯМИ ЧИТАТЕЛЬ ОТСЫЛАЕТСЯ К АЛГОРИТМАМ
ВЫБОРКИ ДЕРЕВЬЕВ В ГЛ.~5.
%% 154

пРИ ПРИМЕНЕНИИ АЛГОРИТМА~R ВОЗНИКАЕТ ЕСТЕСТВЕННЫЙ ВОПРОС:
кАКОВ ОЖИДАЕМЫЙ РАЗМЕР~$m$ РЕЗЕРВУАРА?" иЗ УПР.~11 СЛЕДУЕТ, ЧТО СРЕДНЕЕ
ЗНАЧЕНИЕ~$m$ РАВНО~$n(1+H_N-H_n)$, ЧТО ПРИБЛИЖЕННО РАВНО~$n(1+\ln(N/n))$.
сЛЕДОВАТЕЛЬНО, ПРИ~$N/n=1000$ В РЕЗЕРВУАРЕ
БУДЕТ ПРИБЛИЗИТЕЛЬНО В 125~РАЗ МЕНЬШЕ ЭЛЕМЕНТОВ, ЧЕМ В ФАЙЛЕ.

зАМЕТИМ, ЧТО АЛГОРИТМЫ~S И~R МОЖНО ИСПОЛЬЗОВАТЬ ДЛЯ ТОГО, ЧТОБЫ
ПОЛУЧАТЬ ВЫБОРКИ ПО НЕСКОЛЬКИМ НЕЗАВИСИМЫМ КАТЕГОРИЯМ ОДНОВРЕМЕННО.
нАПРИМЕР, ИМЕЯ БОЛЬШОЙ ФАЙЛ ИМЕН И АДРЕСОВ ЖИТЕЛЕЙ сша, МОЖНО ПОЛУЧИТЬ
СЛУЧАЙНЫЕ ВЫБОРКИ РОВНО ПО 10~ЧЕЛОВЕК КАЖДОГО ИЗ 50~ШТАТОВ, НЕ ПЕРЕБИРАЯ
50~РАЗ ВЕСЬ ФАЙЛ И НЕ СОРТИРУЯ ФАЙЛ ПО ШТАТАМ.

аЛГОРИТМЫ~S И~R И НЕСКОЛЬКО ДРУГИХ МЕТОДОВ ПОЛУЧЕНИЯ ВЫБОРОК
ОБСУЖДАЮТСЯ В СТАТЬЕ ч. фАНЯ, м. мАЛЛЕРА И и. рЕЗУХИ
[{\sl Journal of the American Statistical Association,\/} {\bf 57} (1962), 387--402].
оТМЕТИМ, ЧТО АЛГОРИТМ~S НЕЗАВИСИМО РАЗРАБОТАЛ т.~дЖОУНС
[{\sl CACM,\/} {\bf 5} (1962), 343].


{\sl зАДАЧУ О ВЫБОРКЕ,\/} КАК МЫ ЕЕ ЗДЕСЬ ОПИСЫВАЕМ, МОЖНО РАССМАТРИВАТЬ
КАК ВЫЧИСЛЕНИЕ СЛУЧАЙНОГО СОЧЕТАНИЯ В СООТВЕТСТВИИ
С ОБЫЧНЫМ ОПРЕДЕЛЕНИЕМ СОЧЕТАНИЯ ИЗ $N$~ЭЛЕМЕНТОВ ПО~$n$ (СМ.~П.~1.2.6).
рАССМОТРИМ ТЕПЕРЬ ЗАДАЧУ ВЫЧИСЛЕНИЯ СЛУЧАЙНОЙ \emph{ПЕРЕСТАНОВКИ}
$t$~ОБоЕКТОВ. мЫ НАЗОВЕМ ЕЕ \dfn{ЗАДАЧЕЙ ПЕРЕМЕШИВАНИЯ} (ИЛИ ТАСОВАНИЯ),
ПОСКОЛЬКУ ТАСОВАНИЕ КОЛОДЫ ИЗ 52~КАРТ ЕСТЬ СЛУЧАЙНАЯ ИХ ПЕРЕСТАНОВКА.

сУЩЕСТВУЮТ ДВА ОСНОВНЫХ СПОСОБА ПЕРЕМЕШИВАНИЯ. в ПЕРВОМ, ПРЕДЛОЖЕННОМ
с.~уЛАМОМ В НАЧАЛЕ ПЯТИДЕСЯТЫХ ГОДОВ ИСПОЛЬЗУЕТСЯ, НАПРИМЕР, ПЯТЬ
ПОДПРОГРАММ, КАЖДАЯ ИЗ КОТОРЫХ ПРОИЗВОДИТ ОПРЕДЕЛЕННУЮ ПЕРЕСТАНОВКУ
ЭЛЕМЕНТОВ $X_1$, $X_2$,~\dots, $X_t$. пРЕДПОЛОЖИМ, ЧТО НУЖНО ПОЛУЧИТЬ
\emph{ПОСЛЕДОВАТЕЛЬНОСТЬ}  СЛУЧАЙНЫХ ПЕРЕСТАНОВОК. дЛЯ ПОЛУЧЕНИЯ ОЧЕРЕДНОЙ
ПЕРЕСТАНОВКИ НАШЕЙ ПОСЛЕДОВАТЕЛЬНОСТИ МЫ ДЕЙСТВУЕМ НА ПРЕДЫДУЩУЮ ТРЕМЯ
ИЗ ПЯТИ ПЕРЕСТАНОВОК. эТИ ТРИ ПЕРЕСТАНОВКИ ВЫБИРАЮТСЯ СЛУЧАЙНЫМ ОБРАЗОМ
И НЕ ОБЯЗАТЕЛЬНО ОТЛИЧАЮТСЯ ДРУГ ОТ ДРУГА.

эТОТ МЕТОД ПОХОЖ НА СПОСОБ, КОТОРЫМ ЛЮДИ ОБЫЧНО ТАСУЮТ КОЛОДУ КАРТ
(СМ.~УПР.~13). мОЖЕТ БЫТЬ, ЧИТАТЕЛЮ БУДЕТ ИНТЕРЕСНО УЗНАТЬ, КАКИЕ
ПЕРЕСТАНОВКИ ПОЛУЧАЮТСЯ В КОЛОДЕ, ПЕРЕТАСОВАННОЙ ШУЛЕРОМ. дЛЯ ТОГО ЧТОБЫ
ЭТО ВЫЯСНИТЬ, АВТОР ПОПРОСИЛ у.~лОГЭНА (СПЕЦИАЛИСТА ПО ВЫЧИСЛИТЕЛЬНОЙ
ТЕХНИКЕ И ТАСОВАНИЮ КАРТ) ЗАФИКСИРОВАТЬ РЕЗУЛЬТАТЫ ТРЕХ
ПЕРЕМЕШИВАНИЙ КОЛОДЫ ИЗ 52~КАРТ. пОЛУЧИЛИСЬ СЛЕДУЮЩИЕ ПЕРЕСТАНОВКИ:
$$
\eqalign{
\pi_1&=(1\,23\,31)\,(2\,42\,20)\,(3\,34\,52\,48\,24\,28\,39\,50\,15\,40\,
41\,9\,17\,38\,25\,43\,47\,14\,8\,13\,35\,11\,22\,10\,12\,36\,49\,46\,44\,
4\,37)\,(5\,19\,18\,45)\,(6)\,(7\,30)\,(16\,51\,27\,32)\,(21\,29\,33\,26)\cr
\pi_2&=(1\,5\,24\,15\,36\,19)\,(2\,18\,27\,52\,37\,44\,25\,47\,50\,46\,20\,
7\,17\,10)\,(3\,28\,6\,39\,13\,23\,41\,43\,11\,38\,49\,12\,4\,34\,8\,40\,
21\,14\,30\,16\,45\,51\,22\,9\,33\,32\,35\,31\,26)\,(29\,42)\,(48)\cr
%% 154
\pi_3&=(1\,42\,19\,40\,30)\,(2\,51\,10\,34\,44\,48)\,(3\,12\,33\,49\,8\,
23\,20\,25\,14\,7\,43\,36)\, (4\,11\,26\,16\,46\,32\,24\,28\,9\,31\,29\,
52\,21\,5\,47\,13\,39\,38\,17\, 15\,37\,45\,6\,41\,50\,27)\,(18\,22\,35)\cr
}
$$
эТИ ПЕРЕСТАНОВКИ ПРЕДСТАВЛЕНЫ С ПОМОЩЬЮ ЦИКЛОВ (СР.~П.~1.3.3). дЛЯ ТОГО
ЧТОБЫ НАИБОЛЕЕ ЭФФЕКТИВНЫМ СПОСОБОМ ПРОИЗВЕСТИ ПЕРЕСТАНОВКУ
ПОСЛЕДОВАТЕЛЬНОСТИ ЧИСЕЛ, СЛЕДУЕТ ИСПОЛЬЗОВАТЬ ЕЕ ЦИКЛИЧЕСКУЮ СТРУКТУРУ.
еСЛИ, НАПРИМЕР, ИСПОЛЬЗОВАТЬ \MIX, ПЕРВАЯ ИЗ ПРИВЕДЕННЫХ ВЫШЕ ПЕРЕСТАНОВОК
МОЖЕТ БЫТЬ ЗАПРОГРАММИРОВАНА КАК
$$
\vcenter{
\mixcode
LDA & X+1
LDX & X+31
STX & X+1
LDX & X+23
STX & X+31
STA & X+23
LDA & X+2
LDX & X+20
\endmixcode
}
$$
И~Т.~Д.

мЫ ХОТИМ БЫТЬ УВЕРЕНЫ В ТОМ, ЧТО ЕСЛИ ИСПОЛЬЗОВАТЬ НАШ НАБОР ИЗ ПЯТИ
ЗАДАННЫХ ПЕРЕСТАНОВОК В НАДЛЕЖАЩЕЙ ПОСЛЕДОВАТЕЛЬНОСТИ, ТО МОЖНО ПОЛУЧИТЬ
ВСЕ $t!$~ВОЗМОЖНЫХ ПЕРЕСТАНОВОК. мОЖНО ПОКАЗАТЬ, ЧТО, ЕСЛИ ДВЕ
ПЕРЕСТАНОВКИ СЛЕДУЮЩЕГО ВИДА:
$$
\eqalignter{
\pi_1&=(1\,2) & \rem{(ЛЮБОЕ ПРОИЗВЕДЕНИЕ НЕПЕРЕСЕКАЮЩИХСЯ ЦИКЛОВ, КАЖДЫЙ ИЗ НИХ НЕЧЕТНОЙ ДЛИНЫ),}\cr
\pi_2&=(1)& \rem{(ЛЮБОЙ ЦИКЛ ДЛИНЫ~$t-1$, В КОТОРЫЙ НЕ ВХОДИТ ЭЛЕМЕНТ~$1$),}\cr
}
\eqno(2)
$$
ВКЛЮЧЕНЫ В НАБОР, МОЖНО ПОЛУЧИТЬ ЛЮБУЮ ПЕРЕСТАНОВКУ ИЗ $t$~ЭЛЕМЕНТОВ ПУТЕМ
ПОСЛЕДОВАТЕЛЬНОГО ПРИМЕНЕНИЯ~$\pi_1$ И~$\pi_2$ В НЕКОТОРОМ ПОРЯДКЕ
(СМ.~УПР.~12.) дЖ.~дИКСОН ПОКАЗАЛ, ЧТО ПОЧТИ~$3/4$ ИЗ ВСЕХ ПАР
ПЕРЕСТАНОВОК ОБЛАДАЮТ ЭТИМ СВОЙСТВОМ ({\sl Math.~Z.,\/} {\bf 110} (1969), 199--205).

вТОРОЙ МЕТОД ПЕРЕМЕШИВАНИЯ ТЕСНО СВЯЗАН С АЛГОРИТМОМ~3.3.2P. чИТАТЕЛЬ
ДОЛЖЕН ВЕРНУТЬСЯ К ЭТОМУ АЛГОРИТМУ, КОТОРЫЙ ДАЕТ ПРОСТОЕ СООТВЕТСТВИЕ
МЕЖДУ КАЖДОЙ ИЗ $t!$~ВОЗМОЖНЫХ ПЕРЕСТАНОВОК И НАБОРОМ ЧИСЕЛ $C[1]$,
$C[2]$,~\dots, $C[t]$, ГДЕ~$0\le C[j]<j$. мОЖНО ЛЕГКО ПОЛУЧИТЬ СЛУЧАЙНЫЙ
НАБОР ЧИСЕЛ, ПОСЛЕ ЧЕГО С ПОМОЩЬЮ УПОМЯНУТОГО СООТВЕТСТВИЯ ПОЛУЧИТЬ
СЛУЧАЙНУЮ ПЕРЕСТАНОВКУ.

\alg P.(пЕРЕМЕШИВАНИЕ.) пУСТЬ $X_1$, $X_2$,~\dots, $X_t$---НАБОР $t$~ЧИСЕЛ,
КОТОРЫЙ НУЖНО ПЕРЕМЕШАТЬ.

\st[нАЧАЛЬНАЯ УСТАНОВКА.] уСТАНОВИТЬ~$j\asg t$.

\st[вЫРАБОТАТЬ~$U$.] вЫРАБОТАТЬ СЛУЧАЙНОЕ ЧИСЛО~$U$,
РАВНОМЕРНО РАСПРЕДЕЛЕННОЕ МЕЖДУ НУЛЕМ И ЕДИНИЦЕЙ.

%% 156

\st[оБМЕН.] уСТАНОВИТЬ~$k\asg \floor{jU}+1$. (тЕПЕРЬ $k$~ЕСТЬ СЛУЧАЙНОЕ
ЦЕЛОЕ ЧИСЛО, РАСПОЛОЖЕННОЕ В ПРОМЕЖУТКЕ МЕЖДУ~$1$ И~$j$.)
вЗАИМОЗАМЕНИТЬ~$X_k\xchg X_j$.

\st[уМЕНЬШИТЬ~$j$.] уМЕНЬШИТЬ~$j$ НА~$1$. еСЛИ~$j>1$, ВОЗВРАТИТЬСЯ К ШАГУ~\stp{2}.
\algend

эТОТ АЛГОРИТМ ВПЕРВЫЕ ОПУБЛИКОВАЛИ л.~мОЗЕС И р.~оУКФОРД (Tables of Random
Permutations (Stanford University Press, 1963)) И р.~дУРСТЕНФЕЛД
({\sl CACM,\/} {\bf 7} (1964), 420). аЛГОРИТМ ЛУЧШЕ, ЧЕМ МЕТОД уЛАМА, ПОТОМУ
ЧТО ОН, В САМОМ ДЕЛЕ, ВЫРАБАТЫВАЕТ "ДЕЙСТВИТЕЛЬНО СЛУЧАЙНЫЕ" ПЕРЕСТАНОВКИ И
ИСПОЛЬЗУЕТ МЕНЬШУЮ ПАМЯТЬ.

\excercises
\ex[M12] оБоЯСНИТЕ ФОРМУЛУ~(1).

\ex[20] дОКАЖИТЕ, ЧТО ПРИ ИСПОЛЬЗОВАНИИ АЛГОРИТМА~S ОТБИРАЮТСЯ ТОЧНО
$n$~ЗАПИСЕЙ ПРИ УСЛОВИИ, ЧТО~$0<n \le N$.

\rex[22] в АЛГОРИТМЕ~S $(t+1)\hbox{-Й}$~ЭЛЕМЕНТ ВЫБИРАЕТСЯ С
ВЕРОЯТНОСТЬЮ~$(n-m)/(N-t)$, А \emph{НЕ} $n/N$. в ТЕКСТЕ, ОДНАКО, НАПИСАНО,
ЧТО ВЫБОР ПРОВОДИТСЯ БЕСПРИСТРАСТНО, ТАК ЧТО КАЖДЫЙ ЭЛЕМЕНТ ДОЛЖЕН
ВЫБИРАТЬСЯ С \emph{РАВНОЙ} ВЕРОЯТНОСТЬЮ! кАКИМ ОБРАЗОМ МОГУТ БЫТЬ
ОДНОВРЕМЕННО СПРАВЕДЛИВЫ ОБА ЭТИ УТВЕРЖДЕНИЯ?

\ex[м23] пУСТЬ $p(m, t)$~ЕСТЬ ВЕРОЯТНОСТЬ ТОГО, ЧТО ИЗ ПЕРВЫХ
$t$~ЭЛЕМЕНТОВ ВЫБИРАЕТСЯ РОВНО~$m$. пОЛЬЗУЯСЬ НЕПОСРЕДСТВЕННО АЛГОРИТМОМ~S,
ПОКАЖИТЕ, ЧТО
$$
p(m, t)=\perm{t}{m}\perm{N-t}{n-m}\bigg/\perm{N}{n} \rem{ДЛЯ $0\le t \le N$.}
$$

\ex[м24] чЕМУ РАВНО СРЕДНЕЕ ЗНАЧЕНИЕ~$t$ В МОМЕНТ ЗАВЕРШЕНИЯ
РАБОТЫ АЛГОРИТМА~S? (дРУГИМИ СЛОВАМИ, СКОЛЬКО ЗАПИСЕЙ ИЗ ОБЩЕГО ЧИСЛА~$N$
МЫ ПЕРЕБЕРЕМ, ПРЕЖДЕ ЧЕМ ВЫБОРКА БУДЕТ ЗАКОНЧЕНА?)

\ex[M24] чЕМУ РАВНО СТАНДАРТНОЕ ОТКЛОНЕНИЕ ВЕЛИЧИНЫ, ВЫЧИСЛЕННОЙ
В ПРЕДЫДУЩЕМ УПРАЖНЕНИИ?

\rex[м25] дОКАЖИТЕ, ЧТО ПРИ ИСПОЛЬЗОВАНИИ АЛГОРИТМА~S ЛЮБОЙ \emph{ЗАДАННЫЙ}
НАБОР ИЗ $n$~ЗАПИСЕЙ ИЗ ОБЩЕГО ЧИСЛА~$N$ ПОЛУЧАЕТСЯ С
ВЕРОЯТНОСТЬЮ~$1/\perm{N}{n}$. тЕМ САМЫМ БУДЕТ ПОКАЗАНО, ЧТО ВЫБОРКА
ПРОИЗВОДИТСЯ СОВЕРШЕННО БЕСПРИСТРАСТНО.

\rex[18] чТО ПРОИЗОЙДЕТ ПРИ РАБОТЕ АЛГОРИТМА~R, ЕСЛИ В ФАЙЛЕ
СОДЕРЖИТСЯ МЕНЬШЕ $n$~ЗАПИСЕЙ? пРЕДЛОЖИТЕ НЕБОЛЬШУЮ МОДИФИКАЦИЮ АЛГОРИТМА
ДЛЯ ОБНАРУЖЕНИЯ ТАКОГО СЛУЧАЯ.

\ex[22] пРЕДПОЛОЖИМ, ЧТО МЫ ИСПОЛЬЗУЕМ АЛГОРИТМ~R ДЛЯ~$n=3$, А
ФАЙЛ СОСТОИТ ИЗ 20~ЗАПИСЕЙ, И НА ШАГЕ~R2 БЫЛИ ПОЛУЧЕНЫ СЛЕДУЮЩИЕ СЛУЧАЙНЫЕ ЗНАЧЕНИЯ~$U$:
\ctable{
$#$,\bskip&&\bskip$#$,\bskip\cr
0.53 & 0.97 & 0.66 & 0.30 & 0.81 & 0.19 & 0.09 & 0.31 & 0.67 &  0.62 \cr
0.04 & 0.05 & 0.73 & 0.54 & 0.42 & 0.99 & 0.40 & 0.78 & 0.69 & 0.80;\cr
}
20~ЗАПИСЕЙ ЗАНУМЕРОВАНЫ ОТ~$1$ ДО~$20$. кАКИЕ ЗАПИСИ ПОПАДУТ В
РЕЗЕРВУАР? кАКИЕ ЗАПИСИ ПОПАДУТ В ОКОНЧАТЕЛЬНУЮ ВЫБОРКУ?

\ex[30] кАКИМ ОБРАЗОМ НУЖНО СКОМПОНОВАТЬ ТАБЛИЦУ~$(Y, I)$ В
АЛГОРИТМЕ~R (ОБ ЭТОМ УПОМИНАЛОСЬ В ТЕКСТЕ), ЧТОБЫ ЭФФЕКТИВНО ВЫПОЛНЯЛИСЬ
ПОИСК И ПЕРЕНОС НА ШАГАХ~R3 И~R5?

\rex[м25] пРЕДПОЛОЖИМ, ЧТО $p_m$~ЕСТЬ ВЕРОЯТНОСТЬ ТОГО, ЧТО ПРИ
ПЕРВОМ ПЕРЕБОРЕ ПО АЛГОРИТМУ~R В РЕЗЕРВУАР ПОПАДУТ РОВНО $m$~ЭЛЕМЕНТОВ. оПРЕДЕЛИТЕ
%% 157
ПРОИЗВОДЯЩУЮ ФУНКЦИЮ~$G(z)=\sum_m p_m z^m$ И ВЫЧИСЛИТЕ СРЕДНЕЕ И
СТАНДАРТНОЕ ОТКЛОНЕНИЕ (ИСПОЛЬЗУЙТЕ МАТЕРИАЛ П.~1.2.10).

\ex[м23] пУСТЬ~$\pi_1$, $\pi_2$---ПЕРЕСТАНОВКИ, ОПРЕДЕЛЯЕМЫЕ
СООТНОШЕНИЯМИ~(2). дОКАЖИТЕ СПРАВЕДЛИВОСТЬ СЛЕДУЮЩИХ УТВЕРЖДЕНИЙ,
(a)~нЕКОТОРАЯ СТЕПЕНЬ~$\pi_1$ РАВНА ЦИКЛУ~$(1\,2)$. (b)~нЕКОТОРОЕ
ПРОИЗВЕДЕНИЕ $\pi_1$ И~$\pi_2$ РАВНО ЦИКЛУ~$(1\,k)$ ДЛЯ ЛЮБОГО~$k$, $2\le k \le t$.
(c)~лЮБОЙ ЦИКЛ~$(j\,k)$, $j\ne k$, МОЖЕТ БЫТЬ ПОЛУЧЕН КАК
ПРОИЗВЕДЕНИЕ $\pi_1$ И~$\pi_2$. (d)~вСЕ ПЕРЕСТАНОВКИ ИЗ $t$~ЭЛЕМЕНТОВ
МОГУТ БЫТЬ ПОЛУЧЕНЫ КАК ПРОИЗВЕДЕНИЕ $\pi_1$ И~$\pi_2$.

\ex[M23] (с.~гОЛОМБ.) оБЫЧНЫЙ СПОСОБ ТАСОВАНИЯ КАРТ СОСТОИТ В СЛЕДУЮЩЕМ:
КОЛОДА ДЕЛИТСЯ'НА ДВЕ ПО ВОЗМОЖНОСТИ РАВНЫЕ ЧАСТИ, КОТОРЫЕ ВСТАВЛЯЮТСЯ
ОДНА В ДРУГУЮ. (в ПРАВИЛАХ КАРТОЧНЫХ ИГР, ОПУБЛИКОВАННЫХ хОЙЛОМ, ЧИТАЕМ:
"дЛЯ ТОГО ЧТОБЫ ХОРОШО ПЕРЕМЕШАТЬ КАРТЫ ТАКИМ СПОСОБОМ, НУЖНО ПЕРЕТАСОВАТЬ
ИХ ОКОЛО ТРЕХ РАЗ".) рАССМОТРИМ КОЛОДУ ИЗ $2n-1$~КАРТ $X_1$, $X_2$,~\dots,
$X_{2n-1}$. оПЕРАЦИЯ "ИДЕАЛЬНОГО ТАСОВАНИЯ"~$s$ РАЗДЕЛЯЕТ КОЛОДУ НА ДВЕ
ЧАСТИ $X_1$, $X_2$,~\dots{}, $X_n$ И~$X_{n+1}$,~\dots, $X_{2n-1}$ И
ИДЕАЛЬНО СМЕШИВАЕТ ИХ ТАК, ЧТО ПОЛУЧАЕТСЯ ПОСЛЕДОВАТЕЛЬНОСТЬ $X_1$,
$X_{n+1}$, $X_2$, $X_{n+2}$,~\dots, $X_{2n-1}$, $X_n$. оПЕРАЦИЯ
"СНЯТИЯ"~$c^j$ ПЕРЕВОДИТ ПОСЛЕДОВАТЕЛЬНОСТЬ $X_1$, $X_2$,~\dots,
$X_{2n-1}$ В ПОСЛЕДОВАТЕЛЬНОСТЬ  $X_{j+1}$,~\dots, $X_{2n-1}$, $X_1$,~\dots,
$X_j$. пОКАЖИТЕ, ЧТО ПРИ КОМБИНИРОВАНИИ "ИДЕАЛЬНЫХ ТАСОВАНИЙ" И
"СНЯТИЙ" МОЖНО ПОЛУЧИТЬ НЕ БОЛЕЕ ЧЕМ $(2n-1)(2n-2)$~РАЗЛИЧНЫХ
ПОСЛЕДОВАТЕЛЬНОСТЕЙ КАРТ ПРИ УСЛОВИИ, ЧТО~$n>1$.

%% 158
\subchap{* что такое случайная последовательность?} % 3.5*

\section{A. вВОДНЫЕ ЗАМЕЧАНИЯ}. в ЭТОЙ ГЛАВЕ УЖЕ ГОВОРИЛОСЬ О ТОМ, КАК
ПОЛУЧАТЬ ПОСЛЕДОВАТЕЛЬНОСТИ
$$
\<U_n>=U_0, U_1, U_2, \ldots
\eqno(1)
$$
ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ, ЗАКЛЮЧЕННЫХ МЕЖДУ НУЛЕМ И ЕДИНИЦЕЙ, Т.~Е.\ ТАКИХ,
ЧТО~$0\le U_n<1$. эТИ ПОСЛЕДОВАТЕЛЬНОСТИ НАЗЫВАЛИСЬ "СЛУЧАЙНЫМИ", ХОТЯ ПО
СПОСОБУ ПОЛУЧЕНИЯ ОНИ БЫЛИ СОВЕРШЕННО ДЕТЕРМИНИРОВАННЫМИ. дЛЯ ТОГО ЧТОБЫ
ОПРАВДАТЬ ЭТО НАЗВАНИЕ, МЫ ПИСАЛИ, ЧТО ЧИСЛА "ВЕДУТ СЕБЯ ТАК, КАК ЕСЛИ БЫ
ОНИ БЫЛИ ДЕЙСТВИТЕЛЬНО СЛУЧАЙНЫМИ". дЛЯ ПРАКТИЧЕСКИХ ЦЕЛЕЙ (В НАСТОЯЩЕЕ
ВРЕМЯ) ТАКОГО ЗАЯВЛЕНИЯ МОЖЕТ БЫТЬ И ДОСТАТОЧНО, ОДНАКО ОНО
ОБХОДИТ ОДИН ОЧЕНЬ ВАЖНЫЙ ФИЛОСОФСКИЙ И ТЕОРЕТИЧЕСКИЙ ВОПРОС: КАК ТОЧНО
СФОРМУЛИРОВАТЬ, ЧТО ИМЕННО МЫ ПОДРАЗУМЕВАЕМ ПОД
"СЛУЧАЙНЫМ ПОВЕДЕНИЕМ"? нУЖНО ПРЕДЛОЖИТЬ КОЛИЧЕСТВЕННОЕ ОПРЕДЕЛЕНИЕ
СЛУЧАЙНОГО ПОВЕДЕНИЯ. нЕ СЛЕДУЕТ ПОЛЬЗОВАТЬСЯ ПОНЯТИЯМИ, КОТОРЫХ
ПО-НАСТОЯЩЕМУ НЕ ПОНИМАЕШЬ, ТЕМ БОЛЕЕ ЧТО О СЛУЧАЙНЫХ ЧИСЛАХ МОЖНО
ВЫСКАЗАТЬ МНОГО НА ПЕРВЫЙ ВЗГЛЯД ПАРАДОКСАЛЬНЫХ УТВЕРЖДЕНИЙ.

мАТЕМАТИЧЕСКАЯ СТАТИСТИКА И ТЕОРИЯ ВЕРОЯТНОСТЕЙ ТЩАТЕЛЬНО ИЗБЕГАЮТ ОТВЕТА
НА НАШ ВОПРОС, ПОСКОЛЬКУ ЭТИ НАУКИ ВОЗДЕРЖИВАЮТСЯ ОТ АБСОЛЮТНЫХ
УТВЕРЖДЕНИЙ. вМЕСТО ЭТОГО РАССМАТРИВАЕТСЯ ВОПРОС О ТОМ, КАКУЮ
\emph{ВЕРОЯТНОСТЬ}  СЛЕДУЕТ ПРИПИСАТЬ ВЫСКАЗЫВАНИЯМ, СВЯЗАННЫМ СО
СЛУЧАЙНЫМИ ПОСЛЕДОВАТЕЛЬНОСТЯМИ НЕЗАВИСИМЫХ СОБЫТИЙ. аКСИОМЫ ТЕОРИИ
ВЕРОЯТНОСТЕЙ ПОЗВОЛЯЮТ БЕЗ ТРУДА
ВЫЧИСЛЯТЬ АБСТРАКТНЫЕ ВЕРОЯТНОСТИ, ОДНАКО ПРИ ЭТОМ ОСТАЕТСЯ НЕЯСНЫМ, ЧТО
ЖЕ В ДЕЙСТВИТЕЛЬНОСТИ ОЗНАЧАЕТ ПОНЯТИЕ ВЕРОЯТНОСТИ, ИЛИ КАК ЭТО ПОНЯТИЕ
МОЖНО ОСМЫСЛЕННО ПРИЛОЖИТЬ К ЯВЛЕНИЯМ ОКРУЖАЮЩЕГО МИРА. р.~ФОН~мИЗЕС В
КНИГЕ "вЕРОЯТНОСТЬ, СТАТИСТИКА И ИСТИНА" (Probability, Statistics, and
Truth, Macmillan, 1957) ПОДРОБНО ОБСУЖДАЕТ ЭТО ПОЛОЖЕНИЕ И ВЫСКАЗЫВАЕТ ТАКУЮ
ТОЧКУ ЗРЕНИЯ, ЧТО ОПРЕДЕЛЕНИЕ ВЕРОЯТНОСТИ ЗАВИСИТ ОТ ТОГО КАК ОПРЕДЕЛИТЬ
СЛУЧАЙНУЮ ПОСЛЕДОВАТЕЛЬНОСТЬ.

пРИВЕДЕМ ДВА ОПИСАНИЯ ПОНЯТИЯ СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ, НЕДАВНО
ПРЕДЛОЖЕННЫЕ ДВУМЯ АВТОРАМИ.
{\medskip\narrower
{\sl д.~X.~лЕМЕР (1951 Г.):\/} "сЛУЧАЙНАЯ ПОСЛЕДОВАТЕЛЬНОСТЬ ЕСТЬ НЕКОЕ
РАСПЛЫВЧАТОЕ ПОНЯТИЕ, ВОПЛОЩАЮЩЕЕ ИДЕЮ ПОСЛЕДОВАТЕЛЬНОСТИ, В КОТОРОЙ
КАЖДЫЙ ЧЛЕН НЕПРЕДСКАЗУЕМ ДЛЯ
%% 159
НЕПОСВЯЩЕННОГО И ЭЛЕМЕНТЫ КОТОРОЙ УДОВЛЕТВОРЯЮТ РЯДУ ТРАДИЦИОННЫХ СРЕДИ
СТАТИСТИКОВ КРИТЕРИЕВ, В ИЗВЕСТНОЙ СТЕПЕНИ ЗАВИСЯЩИХ ОТ ТОГО, ДЛЯ КАКИХ
ПРИМЕНЕНИЙ СЛУЖИТ ЭТА ПОСЛЕДОВАТЕЛЬНОСТЬ".

{\sl дЖ.~н.~фРЭНКЛИН (1962~Г.):\/} "пОСЛЕДОВАТЕЛЬНОСТЬ~(1) СЛУЧАЙНА, ЕСЛИ
ОНА ОБЛАДАЕТ ЛЮБЫМ СВОЙСТВОМ, КОТОРЫМ ОБЛАДАЮТ ВСЕ БЕСКОНЕЧНЫЕ
ПОСЛЕДОВАТЕЛЬНОСТИ НЕЗАВИСИМЫХ ВЫБОРОК СЛУЧАЙНЫХ ПЕРЕМЕННЫХ ИЗ
РАВНОМЕРНОГО РАСПРЕДЕЛЕНИЯ"
\medskip}

оПРЕДЕЛЕНИЕ фРЭНКЛИНА СУЩЕСТВЕННО ОБОБЩАЕТ ОПРЕДЕЛЕНИЕ лЕМЕРА, ПОСКОЛЬКУ
ОНО ТРЕБУЕТ, ЧТОБЫ ПОСЛЕДОВАТЕЛЬНОСТЬ УДОВЛЕТВОРЯЛА \emph{ВСЕМ}
СТАТИСТИЧЕСКИМ КРИТЕРИЯМ. еГО ОПРЕДЕЛЕНИЕ НЕ ЯВЛЯЕТСЯ АБСОЛЮТНО ТОЧНЫМ, И
СКОРО МЫ УБЕДИМСЯ В ТОМ, ЧТО РАЗУМНАЯ ЕГО ИНТЕРПРЕТАЦИЯ ПРИВОДИТ К
ОТРИЦАНИЮ СУЩЕСТВОВАНИЯ ТАКОГО ОБоЕКТА, КАК СЛУЧАЙНАЯ
ПОСЛЕДОВАТЕЛЬНОСТЬ! тАКИМ ОБРАЗОМ, ОНО СЛИШКОМ ОГРАНИЧИТЕЛЬНО, ПОЭТОМУ
ПОПЫТАЕМСЯ УТОЧНИТЬ \emph{ОПРЕДЕЛЕНИЕ лЕМЕРА.} мЫ ХОТИМ ПОЛУЧИТЬ
ОТНОСИТЕЛЬНО КОРОТКИЙ ПЕРЕЧЕНЬ МАТЕМАТИЧЕСКИХ СВОЙСТВ, КАЖДОЕ ИЗ КОТОРЫХ
НЕ ПРОТИВОРЕЧИТ НАШЕМУ ИНТУИТИВНОМУ ПРЕДСТАВЛЕНИЮ О
СЛУЧАЙНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ. кРОМЕ ТОГО, ЭТОТ ПЕРЕЧЕНЬ ДОЛЖЕН БЫТЬ
ДОСТАТОЧНО ПОЛНЫМ ДЛЯ ТОГО, ЧТОБЫ \emph{ЛЮБУЮ} ПОСЛЕДОВАТЕЛЬНОСТЬ,
ОБЛАДАЮЩУЮ ПЕРЕЧИСЛЕННЫМИ СВОЙСТВАМИ, МОЖНО БЫЛО БЫ ОТНЕСТИ К "СЛУЧАЙНЫМ".
тО, ЧТО МЫ РАЗРАБОТАЕМ В НАСТОЯЩЕМ РАЗДЕЛЕ, БУДЕТ, ПО-ВИДИМОМУ,
УДОВЛЕТВОРИТЕЛЬНЫМ, С ТОЧКИ ЗРЕНИЯ ПРИВЕДЕННЫХ ВЫШЕ СООБРАЖЕНИЙ,
ОПРЕДЕЛЕНИЕМ СЛУЧАЙНОСТИ, ХОТЯ ПРИ ЭТОМ ОСТАНУТСЯ БЕЗ ОТВЕТА МНОГИЕ
ИНТЕРЕСНЫЕ ВОПРОСЫ.

пУСТЬ~$u$ И~$v$---ДЕЙСТВИТЕЛЬНЫЕ ЧИСЛА, $0\le u < v \le 1$.
еСЛИ~$U$---СЛУЧАЙНАЯ ВЕЛИЧИНА, РАВНОМЕРНО РАСПРЕДЕЛЕННАЯ МЕЖДУ~$0$ И~$1$, ТО
ВЕРОЯТНОСТЬ ТОГО, ЧТО~$u\le U < v$, РАВНА~$v-u$. нАПРИМЕР, ЕСЛИ~$u=1/3$
И~$v=2/3$, ВЕРОЯТНОСТЬ ТОГО, ЧТО~$1/3\le U < 2/3$, РАВНА~$1/3$. кАК
ОБОБЩИТЬ ЭТО СВОЙСТВО НА СЛУЧАЙ БЕСКОНЕЧНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ~$U_0$,
$U_1$, $U_2$,~\dots? оЧЕВИДНЫЙ ОТВЕТ СОСТОИТ В ТОМ, ЧТО ЕСЛИ СОСЧИТАТЬ,
СКОЛЬКО РАЗ $U_n$~ПОПАДАЕТ В ИНТЕРВАЛ МЕЖДУ~$u$ И~$v$, ТО СРЕДНЕЕ ЧИСЛО
ПОПАДАНИЙ ДОЛЖНО БЫТЬ РАВНО ВЕЛИЧИНЕ~$v-u$. аНАЛОГИЧНЫМ ОБРАЗОМ ВВОДИЛОСЬ
ИНТУИТИВНОЕ ПОНЯТИЕ ВЕРОЯТНОСТИ: ОНО ОСНОВЫВАЛОСЬ НА ЧАСТОТЕ
ПОЯВЛЕНИЯ СОБЫТИЯ. еСЛИ БЫТЬ БОЛЕЕ ТОЧНЫМ, ОБОЗНАЧИМ ЧЕРЕЗ~$\nu(n)$
ЧИСЛО ЗНАЧЕНИЙ~$j$, $0\le j < n$, ТАКИХ, ЧТО~$u\le U_j < v$. мЫ ХОТИМ,
ЧТОБЫ ОТНОШЕНИЕ~$\nu(n)/n$ СТРЕМИЛОСЬ К~$v-u$ ПРИ СТРЕМЛЕНИИ~$n$ К БЕСКОНЕЧНОСТИ:
$$
\lim_{n\to\infty} \nu(n)/n=v-u.
\eqno(2)
$$
еСЛИ ЭТО УСЛОВИЕ УДОВЛЕТВОРЯЕТСЯ ПРИ ЛЮБОМ ВЫБОРЕ~$u$ И~$v$,
ПОСЛЕДОВАТЕЛЬНОСТЬ БУДЕМ НАЗЫВАТЬ \dfn{РАВНОМЕРНО РАСПРЕДЕЛЕННОЙ.}

оБОЗНАЧИМ ЧЕРЕЗ~$S(n)$ НЕКОТОРОЕ УТВЕРЖДЕНИЕ ОТНОСИТЕЛЬНО ЦЕЛОГО ЧИСЛА~$n$
И ПОСЛЕДОВАТЕЛЬНОСТИ~$U_1$, $U_2$,~$\ldots\,$. нАПРИМЕР,
%% 160
$S(n)$~МОЖЕТ БЫТЬ ВЫСКАЗАННЫМ ВЫШЕ УТВЕРЖДЕНИЕМ: "$u\le U_n < v$". мОЖНО
ОБОБЩИТЬ РАССУЖДЕНИЯ, ПРИВЕДЕННЫЕ В ПРЕДЫДУЩЕМ АБЗАЦЕ, И ОПРЕДЕЛИТЬ
"ВЕРОЯТНОСТЬ ТОГО, ЧТО $S(n)$~ИСТИННО" ПО ОТНОШЕНИЮ К ОПРЕДЕЛЕННОЙ
БЕСКОНЕЧНОЙ ПОСЛЕДОВАТЕЛЬНОСТИ. пУСТЬ~$\nu(n)$---ЧИСЛО ЗНАЧЕНИЙ~$j$, $0\le j <n$,
ТАКИХ, ЧТО~$S(j)$~ИСТИННО.

\proclaim оПРЕДЕЛЕНИЕ~A. гОВОРЯТ, ЧТО~$\Pr (S(n))=\lambda$,
ЕСЛИ~$\lim_{n\to\infty} \nu(n)/n=\lambda$. (в СЛОВЕСНОЙ ФОРМЕ "ВЕРОЯТНОСТЬ
ТОГО, ЧТО $S(n)$~ИСТИННО, РАВНА~$\lambda$, ЕСЛИ ПРЕДЕЛ~$\nu(n)/n$ ПРИ~$n$,
СТРЕМЯЩЕМСЯ К БЕСКОНЕЧНОСТИ, ЕСТЬ~$\lambda$".)

пОЛЬЗУЯСЬ ЭТИМ ОПРЕДЕЛЕНИЕМ, МОЖНО СКАЗАТЬ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ~$U_0$,
$U_1$,~\dots{} РАВНОМЕРНО РАСПРЕДЕЛЕНА В ТОМ И ТОЛЬКО ТОМ СЛУЧАЕ,
ЕСЛИ~$\Pr(u\le U_n < v)=v-u$ ДЛЯ ВСЕХ ДЕЙСТВИТЕЛЬНЫХ~$u$, $v$, ТАКИХ,
ЧТО~$0\le u < v \le 1$.

пОСЛЕДОВАТЕЛЬНОСТЬ МОЖЕТ БЫТЬ РАВНОМЕРНО РАСПРЕДЕЛЕННОЙ, НО НЕ СЛУЧАЙНОЙ.
еСЛИ, НАПРИМЕР, $U_0$, $U_1$,~\dots{} И~$V_0$, $V_1$,~\dots---ДВЕ РАВНОМЕРНО
РАСПРЕДЕЛЕННЫЕ ПОСЛЕДОВАТЕЛЬНОСТИ, ТО НЕТРУДНО ПОКАЗАТЬ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ
$$
W_0, W_1, W_2, W_3, \ldots = {1\over 2}U_0, {1\over 2}+{1\over 2}V_0,
{1\over2}U_1, {1\over2}+{1\over2}V_1,\ldots
\eqno(3)
$$
ТАКЖЕ РАВНОМЕРНО РАСПРЕДЕЛЕНА, ПОСКОЛЬКУ ПОСЛЕДОВАТЕЛЬНОСТЬ~${1\over2}U_0$,
${1\over 2}U_1$,~\dots{} РАВНОМЕРНО РАСПРЕДЕЛЕНА МЕЖДУ~$0$ И~$1/2$, А
ЧЕРЕДУЮЩАЯСЯ С НЕЙ ПОСЛЕДОВАТЕЛЬНОСТЬ~${1\over 2}+{1\over 2}V_0$,
${1\over 2}+{1\over 2}V_1$,~\dots{} РАВНОМЕРНО РАСПРЕДЕЛЕНА МЕЖДУ~$1/2$ И~$1$.
в ПОСЛЕДОВАТЕЛЬНОСТИ~$W$ ЗА ВЕЛИЧИНОЙ, МЕНЬШЕЙ~$1/2$, ВСЕГДА СЛЕДУЕТ
ВЕЛИЧИНА, БОЛЬШАЯ~$1/2$, И ОБРАТНО, ТАК ЧТО ЭТА ПОСЛЕДОВАТЕЛЬНОСТЬ НЕ
ЯВЛЯЕТСЯ СЛУЧАЙНОЙ НИ В КАКОМ РАЗУМНОМ СМЫСЛЕ. нАМ НУЖНО СВОЙСТВО
БОЛЕЕ СИЛЬНОЕ, ЧЕМ РАВНОМЕРНАЯ РАСПРЕДЕЛЕННОСТЬ.

пРИМЕР, ПРИВЕДЕННЫЙ В ПРЕДЫДУЩЕМ АБЗАЦЕ, ПРИВОДИТ К ЕСТЕСТВЕННОМУ
ОБОБЩЕНИЮ СВОЙСТВА РАВНОМЕРНОЙ РАСПРЕДЕЛЕННОСТИ, А ИМЕННО К РАССМОТРЕНИЮ
ПАР СОСЕДНИХ ЭЛЕМЕНТОВ ПОСЛЕДОВАТЕЛЬНОСТИ. мОЖНО ПОТРЕБОВАТЬ, ЧТОБЫ ДЛЯ
ЛЮБЫХ ЧЕТЫРЕХ ЧИСЕЛ~$u_1$, $v_1$, $u_2$, $v_2$, ТАКИХ, ЧТО~$0\le u_1 < v_1 \le 1$,
$0\le u_2 < v_2 \le 1$,  ПОСЛЕДОВАТЕЛЬНОСТЬ УДОВЛЕТВОРЯЛА ТРЕБОВАНИЮ
$$
\Pr(u_1\le U_n < v_1 \rand u_2\le U_{n+1}<v_2)=(v_1-u_1)(v_2-u_2).
\eqno(4)
$$
бОЛЕЕ ТОГО, ДЛЯ ЛЮБОГО ПОЛОЖИТЕЛЬНОГО ЦЕЛОГО ЧИСЛА~$k$ МОЖНО
ВВЕСТИ ПОНЯТИЕ \dfn{$k\hbox{-РАСПРЕДЕЛЕННОЙ}$} ПОСЛЕДОВАТЕЛЬНОСТИ.

\proclaim оПРЕДЕЛЕНИЕ~B. гОВОРЯТ, ЧТО ПОСЛЕДОВАТЕЛЬНОСТЬ~(1)
$k\hbox{-pacnpeДЕЛЕНА}$, ЕСЛИ
$$
\Pr(u_1\le U_n < v_1, \ldots, u_k\le U_{n+k-1}<v_k)=(v_1-u_1)\ldots(v_k-u_k)
\eqno(5)
$$
ДЛЯ ЛЮБЫХ ДЕЙСТВИТЕЛЬНЫХ ЧИСЕЛ~$u_j$, $v_j$, ТАКИХ, ЧТО~$0\le u_j<v_j\le 1$
ПРИ~$1 \le j \le k$.

%% 161
\bye