лых чисел, сгенерированных при выборе М чисел из N, то м-1

k=M-l

= 7V( - ,); =- (это Л-е гармоническое число).

Таким образом, E{T)=0{N logzN).

Нам желательно иметь алгоритм, гарантирующий извлечение точно М предметов при каждом испытании, но обладающий тем же свойством, что и первая описанная процедура: решение «принять / отвергнуть» достигается за один проход.

Предположим, что мы собираемся рассматривать (&-Ь1)-й предмет и что уже выбрано q предметов. Какое значение вероятности следует

приписать принятию этого предмета? Убедимся, что существует f")

способов выбрать М-q предметов из остающихся -k. Все способы следует рассматривать как равновероятные, и один должен иметь место, если мы в конце концов выберем М предметов. Аналогично,

если выбран (А-Ы)-й предмет, то существует способов вы-

брать M-q-1 предметов из -k-1 оставшихся. При всех способах выбора М предметов из N, когда q выбраны из k первых, в точности

(N-k-l\

[м-д-\)

N-k\ ~N - k М-

l-q)

ИЗ них выбирают (А+1)-й элемент. Мы утверждаем, что это та вероятность, которую следует приписать выбору {к+\)-то предмета.

Прежде чем принять это утверждение, сформулируем весь алгоритм извлечения выборки.

Algorithm SS (извлечение выборки) для извлечения несмещенной выборки lMN предметов из множества предметов. Шаг.О. [Инициализация] Set /(-«-0; and Q-«-0. (/(+1 указывает рассматриваемый предмет, а Q обозначает число уже выбранных предметов.) Шаг 1. [Цикл] Do through шаг 4 while Q<M od; and STOP.

Шаг 2. [Генерация случайного числа] Генерируется (с равномерным распределением) случайное число Y между О и 1.

Шаг 3. [Проверка: взять или отвергнуть] If (Л-K)Y<.M-Q then выбрать предмет К+1; and set Q--Q+l fi.

Шаг 4. [Увеличение К\ Set К<-К-\.

На первый взгляд вовсе не очевидно, что алгоритм SS выбирает в точности М предметов и что выборка будет несмещенной, т. е. что все предметы будут выбираться с равной вероятностью.

Теорема 6.3.1. Алгоритм SS выбирает точно М предметов.

Доказательство. Очевидно, что невозможно выбрать более М предметов, так как алгоритм прекращает работу, как только выбран М-й предмет.

На шаге 3, если уже выбрано q предметов и остается просмотреть только М-q предметов, то все остающиеся предметы будут выбраны. Таким образом, выбирается по меньшей мере М предметов. Следовательно, выбирается точно М предметов.

Теорема 6.3.2. Алгоритм SS выбирает каждый предмет несмещенным образом.

Рассмотрим {к+1)-й предмет. При любом испытании вероятность принятия этого предмета равна (M-q)/ {N-k), где q - число уже выбранных предметов. Значение q является случайной переменной, зависящей от выборов, сделанных при первых k пробах. Мы хотим показать, что при любых k, М и N среднее значение величины (M-q)/ {N-k) равно в точности M/N. Именно в этом смысле алгоритм SS является несмещенным.

Так как полное доказательство теоремы 6.3.2 слишком сложно, мы просто продемонстрируем его правильность для k=2.

Так как k=2, рассмотрим предмет 3. Следующая таблица возможных исходов для первых двух предметов не нуждается в пояснениях. Для указанных действий с первыми двумя предметами показаны значения q и вероятности выбора предмета 3.

Предмет 1

Предмет 2

Р (выбрать предмет 3)

Принять Принять Отвергнуть Отвергнуть

Принять Отвергнуть Принять Отвергнуть

2 1 1 О

(M-2)/(N-2) (M-l)/0V-2) (M-l)/(,V-2) M/(N-2)

Вероятность того, что q=2, равна

P{q = 2) = P (принять предмет 1) [Р (принять предмет 21 предмет 1 принят)] = М М-1 ~ N N-1 •

Аналогично мы можем вычислить остальную часть вероятностной

меры для q:

(Ч Ч- - Лул? -1~ N(N - \)

(Af-M)(Af-М-1) N(N - 1)

Убедитесь, что P{q2)+Piq=l)+Piq=0)=l. Среднее значение Р (принять предмет 3) равно

/сред(==3) = -Р(=2) + -Р(?=1) +

+ (9 = 0) = - дГ (проверьте это!).

Очевидно, что в худшем случае алгоритм SS просмотрит все предметы, прежде чем получит полную выборку из М предметов. В лучшем случае будет просмотрено только М предметов. В качестве упражнения попробуйте доказать, что среднее значение к, при котором алгоритм SS прекращает работу, равно

Ь -(+)

*сред .

Дадим еще один метод выбора М чисел из Л.

Algorithm SELECT (выбор) для извлечения несмещенной выборки lMN чисел из набора 1, 2, . . ., Л. Выбранные числа помещаются в массив SELECT (1),. . ., SELECT(М).

Шаг 0. [Инициализация] For / -t- 1 to do set ITEM (/) -t- 1 od;

set LAST N; and set L -t- L Шаг 1. [Повторение М раз] Do through шаг 4 while LM od; and

STOP.

Шаг 2. [Генерация случайного числа] Генерируется с равномерным распределением случайное число К между 1 и LAST.

Шаг 3. [Выбор следующего числа] Set SELECT (L) <-

ITEM (/С); set LL+1. Шаг 4. [Уменьшение размера выборки] Set ITEM (К) -t-

ITEM(LAST); and LAST LAST-1.

Рисунок 6.3.1 иллюстрирует применение алгоритма SELECT на примере выбора 5 чисел из 10.

Легко доказать, что алгоритм является несмещенным. Пусть Pi (к) - вероятность выбора t-ro числа на к-й итерации алгоритма SELECT. Тогда вероятность pt выбора числа i равна

Рг = S Pi (k), k=l