a) Будет введено максимум Л записей (мы никогда не достигнем конца файла, пока не эыберем п элементов).

b) Выборка полностью беспристрастна. В частности, вероятность того, что любой заданный элемент выбран, как, например, последний элемент файла, равна n/N.

Утверждение (Ь) справедливо несмотря на то, что выбран (t + 1)-й элемент не с вероятностью n/N, ас вероятностью, заданной в (1)! Это послужило причиной некоторой неразберихи в опубликованной литературе. Может ли читатель объяснить это кажущееся противоречие?

(Замечание. Используя алгоритм S, следует позаботиться о наличии различных источников случайных чисел U при каждом выполнении программы во избежание зависимости между выборками, полученными в разные дни. Это можно сделать, например, выбирая каждый раз различные значения Xq в линейном конгруэнтном методе. Начальному значению Хо может быть присвоено число месяца в день выполнения программы или последнее случайное число X, которое генерировалось при предыдущем прогоне программы.)

Обычно мы не проходим все N записей. В самом деле, так как указанное выше утверждение (Ь) гласит, что последняя запись выбирается с вероятностью n/N, вероятность того, что работа алгоритма завершится до выбора последней записи, точно равна (1 - n/N). Среднее число рассмотренных записей, когда п = 2. приблизительно равно 7V; общие формулы даны в упр. 5 и 6.

Алгоритм S и другие подобные методы обсуждаются в работе Ч. Т. Фана, Мервина Э. Мюллера и Ивана Резуха (С. Т. Fan, Mervin Е. Muller, and Ivan Rezucha, J. Amer. Stat. Assoc. 57 (1962), 387-402). Независимо этот метод был открыт Т. Г. Джонсом (Т. С. Jones, САСМ 5 (1962), 343).

Если значение N заранее неизвестно, то возникают трудности, поскольку знание точного значения N является решающим для выполнения алгоритма S. Допустим, необходимо случайно выбрать п записей из файла, если точно неизвестно, сколько записей в настоящее время содержится в этом файле. Можно сначала пересчитать все записи, а затем перейти к выбору п записей, но лучше так выбрать т > п начальных записей на первом проходе, чтобы т было намного меньше N. Тогда на втором проходе "нужно будет рассмотреть только т записей. Искусство состоит, конечно, в том, чтобы при подобном выборе в результате получить истинную случайную выборку из исходного файла.

Так как заранее неизвестно, когда завершится ввод, "модель" случайной выборки из записей следует хранить на входе при первом просмотре, чтобы всегда быть готовым к его окончанию. При чтении файла мы строим "резервуар", содержащий только записи, которые образуют предварительные выборки. Первые п записей всегда будут входить в резервуар. Когда (t + 1)-я запись введена для t > п, в памяти формируется таблица п индексов записей, которые были выбраны среди первых t записей. Проблемой является сохранение этого состояния с t, увеличенным на единицу, т. е. поиск новой случайной выборки среди t+1 имеющихся известных сейчас записей. Нетрудно видеть, что новую запись следует включить в выборку с вероятностью n/{t + 1); при этом она заменит случайный элемент предьщущей выборки.

Итак, описанную работу выполняет следующий алгоритм.

Алгоритм R {Резервуар выбора). Выбрать случайно п записей из файла неизвестного размера > п, п > О задано. Дополнительный файл назовем резервуаром, содержащим все записи, которые являются кандидатами для окончательной выборки. Алгоритм использует таблицу различных индексов I[j] для 1 < j < п, каждый из которых указывает на одну из записей в резервуаре.

R1. [Инициализация.] Введем первые п записей и скопируем их в резервуар. Присвоим j для 1 < j < п и присвоим t <- тп <- п. (Если файл б>дет выборкой, имеющей меньше п записей, то, конечно, необходимо будет прервать выполнение алгоритма и сообщить о неблагоприятном исходе. В алгоритме индексы /[1], ..., 1[п] указьшают записи в текущей выборке; т является размерностью резервуара, at - номером входных записей, рассмотренных до сих пор.)

R2. [Конец файла?] Если записей на ввод больше нет, то перейти к шагу R6.

R3. [Генерирование и проверка.] Увеличить t на 1, затем генерировать случайное целое число М между 1 и < (включительно). Если М > п, перейти к шагу R5.

R4. [Увеличить резервуар.] Копировать следующую запись входного файла в резервуар, увеличить m на 1 и присвоить 1[М] f- т. (Запись, предварительно указанная как 1[М], за.меняется в выборке новой записью.) Возврат к шагу R2.

R5. [Пропустить.] Пропустить следующую запись входного файла (не включать ее в резервуар) и возвратиться к шагу R2.

R6. [Следующий просмотр.] Упорядочить индексы / таблицы входов так, чтобы /[1] < • • • < 1[п], затем тщательно разобрать резервуар, копируя записи с этими индексами в выходной файл, который фиксирует окончательный выбор.

Алгоритм R предложен Аланом Дж. Вотерманом .(Alan G. Waterman). Читатель при желании может выполнить упр. 9, используя эти операции.

Если записи достаточно короткие, конечно, излишне помещать их в резервуар. п записей текущего файла можно постоянно хранить в памяти, и алгоритм станет более простым (см. упр. 10).

Относительно алгоритма R возникает естественный вопрос: "Какова предполагаемая размерность резервуара?". В упр. 11 показано, что среднее значение т точно равно п(1 4- Hjv - Я„), т. е. приблизительно п(1 + ln(7V/n)). Так, если N/n = 1000, в резервуаре будет содержаться лишь около 1/125 целых записей исходного файла.

Заметим, что алгорит.мы S и R можно применять, чтобы получать выборки для различных независимых классов одновре.менно. Например, если есть большой файл фамилий и адресов постоянных жителей США, можно случайным образом сделать выборку точно 10 жителей из каждого из 50 штатов, не просматривая 50 раз файл и не выполняя первую сортировку файла по штатам.

Возможно значительное улучшение алгоритмов S и R, когда n/N мало. Скажите, сколько записей можно пропустить, вместо того чтобы решать, пропускать ли каждую запись, если генерируется единственная случайная величина? (См. упр. 8.)

Проблема выборки может быть рассмотрена как вычисление случайного сочетания в соответствии с обычным определением сочетания N поп (см. раздел 1.2.6). Рассмотрим задачу вычисления случайной перестановки t объектов. Назовем ее

задачей перемешивания (тасования), так как, например, тасование колоды карт является ничем иным, как ее случайной перестановкой.

Достаточно легко убедить любого игрока в карты, что традиционная процедура тасования карт ужасно несовершенна. Нет надежды получить таким методом каждую из t\ перестановок с примерно равными вероятностями. Рассказывают, что знаток игры в бридж использует это обстоятельство, когда принимает решение, стоит ли ему блефовать. По крайней мере семь "перемешиваний" колоды из 52 карт происходит с вероятностью, примерно равной 10% от вероятности получить эти перемешивания при равномерном распределении, в то время как 14 случайных перемешиваний имеют вероятность появления, примерно равную вероятности их получения при равномерном распределении [см. Aldous and Diaconis, АММ 93 (1986), 333-348].

Если t мало, можно получить случайную перестановку очень быстро, генерируя случайное целое число между 1 и t\. Например, когда t = 4, случайного чиста между 1 и 24 достаточно, чтобы выбрать случайную перестановку из таблицы всех возможностей. Но для больших t необходимо быть более осторожным, если требуется, чтобы каждая перестановка была равновероятной, так как t\ намного больше точности отдельного случайного числа.

Подходящая процедура перемешивания может быть получена с помощью уже упоминаемого алгоритма 3.3.2Р, который дает простое соответствие между каждой из t\ возможных перестановок и последовательностью чисел (ci, сг,.. ,c-i) с О < < j- Можно легко получить такое множество случайных чисел, и это соответствие можно использовать для получения случайных перестановок.

Алгоритм Р (Перемешивание). Пусть Al, Аг, ..., Xi - множество t чисел для перемешивания.

Р1. [Инициализация.] Присвоить j i- t.

Р2. [Генерирование U.] Генерировать случайное число U, равномерно распределенное между О и 1.

РЗ. [Замена.] Присвоить к +- \ jU\ + 1. (Сейчас к - случайное целое число между 1 и у. В упр. 3.4.1-3 объясняется, что деление на j не следует использовать для вычисления к.) Заменим Х -н Xj.

Р4. [Уменьшение j.] Уменьшить j на 1. Если j > 1, возвратиться к шагу Р2.

Впервые этот алгоритм опубликовали Р. А. Фишер и Ф. Яте (R. А. Fisher and F. Yates, Statistical Tables (London, 1938), Example 12) на обычном языке, a P. Дурстенфелд - на языке компьютерном (R. Durstenfeld, САСМ 7 (1964), 420). Чтобы просто генерировать случайную перестановку {!,...,t} вместо перемешивания заданной последовательности (Х\,... ,Xi), можно избежать операции замены А Xj, выполнив увеличение j от 1 до t и присвоив Xj +- Xk, Xk j [см. D. Е. Knuth, ТЬе Stanford GraphBase (New York: ACM Press, 1994), 104].

P. Салфи (R. Salfi, COMPSTAT 1974 (Vienna, 1974), 28-35) указал, что алгоритм P не имеет возможности генерировать более т различных перестановок, когда мы получаем равномерно распределенные Uj из линейной конгруэнтной последовательности по модулю т или используем рекуррентное соотношение U„+i - f(Un),