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

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

Методы выборки, основанные на неравномерном распределении, обычно используют способность генератора псевдослучайных чисел порождать числа 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).

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

$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» (Распределения случайных чисел) с процедурами выборки согласно более чем двадцати различных распределений.

Литература

• 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