Выборка псевдослучайных чисел

Выборка псевдослучайных чисел — это практика генерации псевдослучайных чисел, распределенных согласно заданному вероятностному распределению. Базируется на численных методах.

Методы выборки, основанные на неравномерном распределении, обычно используют способность генератора псевдослучайных чисел порождать числа X, которые распределены равномерно. Затем применяется вычислительный алгоритм, который в результате манипуляций со случайной величиной X возвращает случайную величину Y, значения которой удовлетворяют заданному распределению.

Конечные дискретные распределенияПравить

Для дискретного распределения с конечным числом n значений случайной величины, в которых функция вероятности f принимает значения, отличные от нуля, базовый алгоритм выборки довольно прост. Интервал [0, 1) делится на n интервалов [0, f(1)), [f(1), f(1) + f(2)), … Длина интервала i равняется вероятности f(i). Предположим, кому-то дано равномерно распределенное число X, которому ставится в соответствие индекс i соответствующего интервала. Таким образом определенный индекс i будет иметь распределение f(i).

Формализовать сказанную мысль просто, используя (кумулятивную) функцию распределения

$\text{[math]}$ $\text{[math]}$ $F(i)=\sum _{j=1}^{i}f(j)$

Удобно задать F(0) = 0. Тогда n интервалов будут иметь вид [F(0), F(1)), [F(1), F(2)), …, [F(n − 1), F(n)). И тогда главной вычислительной задачей становится поиск такого i, для которого выполняется F(i − 1) ≤ X < F(i).

Поиск может быть произведен различными алгоритмами, например:

Линейный поиск с линейной вычислительной сложностью.
Бинарный поиск с логарифмической сложностью.
И прочие виды поисков.

Непрерывные распределенияПравить

Общие методы генерации независимых выборок:

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

Общие методы генерации коррелированных выборок (часто необходимы, например, в случае многомерных распределений):

Методы Монте-Карло по схеме марковской цепи, основной принцип
Алгоритм Метрополиса — Гастингса
Семплирование по Гиббсу
Выборка по уровням
Реверсивный алгоритм переходов Монте-Карло по схеме марковской цепи, когда размерность не фиксирована
Многочастичный фильтр, когда наблюдаемые данные связаны в цепь Маркова и должны быть обработаны последовательно

Для генерации согласно нормальному распределению:

Программные библиотекиПравить

GNU Scientific Library имеет раздел, озаглавленный «Random Number Distributions» (Распределения случайных чисел) с процедурами выборки согласно более чем двадцати различных распределений.^[1]

ПримечанияПравить

↑ GNU Scientific Library – Reference Manual: Random Number Distributions (неопр.). www.gnu.org. Дата обращения: 5 января 2018. Архивировано 9 января 2018 года.

ЛитератураПравить

Devroye, L. (1986) Non-Uniform Random Variate Generation. New York: Springer

Fishman, G.S. (1996) Monte Carlo. Concepts, Algorithms, and Applications. New York: Springer
Hörmann, W.; J Leydold, G Derflinger (2004,2011) Automatic Nonuniform Random Variate Generation. Berlin: Springer
Knuth, D.E. (1997) The Art of Computer Programming, Vol. 2 Seminumerical Algorithms, Chapter 3.4.1 (3rd edition)
Ripley, B.D. (1987) Stochastic Simulation. Wiley

[1] GNU Scientific Library – Reference Manual: Random Number Distributions (неопр.). www.gnu.org. Дата обращения: 5 января 2018. Архивировано 9 января 2018 года.

[1]