Главная  Полное построение алгоритма 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [ 103 ] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

лых чисел, сгенерированных при выборе М чисел из 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



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [91] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [ 103 ] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

0.1244