Алгоритмы формирования случайной выборки

9. Алгоритмы формирования случайной выборки

9.1. Последовательное извлечение

Утверждение.

Следующая процедура отбора приводит к простой случайной выборке без возвращения:

· Извлечь первый элемент из совокупности N элементов с вероятностью равной 1/N;

· Извлечь второй элемент из оставшихся  элементов с вероятностью равной 1/().

...

· Извлечь n-ый элемент из оставшихся  элементов с вероятностью .

Комментарий:

Рекомендуемые материалы

Для практической реализации требуется n считываний файла, что имеет большие временные затраты при большом объеме файла (N).

9.2. Случайная сортировка

Следующая процедура отбора приводит к простой случайной выборке:

1. Каждой единице совокупности присвоить случайное число (реализацию) u  из равномерного распределения на отрезке [0,1]. Для этого можно воспользоваться генератором случайных чисел.

2. Ранжировать единицы в порядке убывания (или возрастания) присвоенных значений u.

3. Выбрать n первых единиц.

Доказательство.

Вероятность отбора выборки равна:

где  F(x) - функция распределения :

Поэтому

Комментарий :

- сортировка относительно долгая по времени при большом N;

- Однако этот метод позволяет делать несколько выборок без пересечения или с контролируемым пересечением списков единиц выборок.

9.3. Прямая реализация

1. Единицы совокупности, расположенные в случайном порядке или ранжированные по какому-либо признаку, пронумеровать значениями от 1 до N.

2. Получить n различных случайных чисел от 1 до N, в соответствии с законом равномерного распределения на {1,2, ..., N}.

3. Включить в выборку единицы с номерами, соответствующими значениям полученных случайных чисел.

Комментарий:

- требуется только одно считывание файла (в случае предварительного ранжирования полученных n случайных чисел);

- метод эффективен для небольших выборок;

- требует много времени для выборок большого объема (n).

9.4. Метод отбора-отказа

- независимые реализации случайной величины, полученные в соответствии с равномерным распределением на [0,1].

1. Если , то элемент k=1 извлекается, в противном случае - он пропускается.

2. Для k = 2, 3, ..., пусть j - число уже отобранных элементов (среди первых k-1 единиц).
Если , то элемент  отбирается, в противном случае - пропускается.

3. Процедура заканчивается, когда j = n.

Доказательство:

Покажем рекуррентно, что  

Значит:

Но доказательство недостаточное!

Комментарий:

требуется лишь одно считывание файла.

9.5. Актуализация выборки

Начинаем формирование выборки с n первых записей; затем этот первоначальный набор актуализируется, проверяя последовательно  оставшихся единиц.

Алгоритм

Для  :

1.Образовать случайное число u в промежутке от 0 до 1.

Если Вам понравилась эта лекция, то понравится и эта - 7 США в период президентства Эйзенхауэра 1952 - 1960.

2.Если : единица k вводится в выборку и заменяет уже существующую в ней единицу, определенную в результате равновероятностного извлечения среди n единиц выборки.

В противном случае, переходим к следующей единице.

Комментарий:

-не обязательно знать N заранее;

-требуется лишь одно считывание файла;

-отсутствует строгий критерий отбора заменяемых единиц.