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

Перейти к навигацииПерейти к поиску

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

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

Примечания

  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