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

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

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

${\displaystyle 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