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

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

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

Исторически сложилось так, что основные методы выборки псевдослучайных чисел были разработаны для моделирования методом Монте-Карло в Манхэттенском проекте ; ^{[ необходима цитата ]} они были впервые опубликованы Джоном фон Нейманом в начале 1950-х годов. ^[1]

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

Для дискретного распределения вероятностей с конечным числом индексов n, при котором функция массы вероятности f принимает ненулевые значения, основной алгоритм выборки прост. Интервал [0, 1) делится на n интервалов [0,  f (1)), [ f (1),  f (1) +  f (2)), ... Ширина интервала i равна вероятности  f. ( i ). Рисуют равномерно распределенное псевдослучайное число X и ищут индекс 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 ).

Это можно сделать по разным алгоритмам:

• Линейный поиск , время вычислений линейно от  n .
• Двоичный поиск , время вычислений идет с log  n .
• Индексированный поиск , ^[2] также называемый метод CutPoint . ^[3]
• Метод псевдонима , время вычислений постоянно, с использованием некоторых предварительно вычисленных таблиц.
• Есть и другие методы, которые требуют постоянного времени. ^[4]

Непрерывное распространение [ править ]

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

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

Общие методы создания коррелированных выборок (часто необходимо для распределений необычной формы или большой размерности):

• Цепь Маркова Монте-Карло , общий принцип
• Алгоритм Метрополиса – Гастингса
• Выборка Гиббса
• Выборка срезов
• Цепь Маркова с обратимым скачком Монте-Карло , когда количество измерений не фиксировано (например, при оценке модели смеси и одновременной оценке количества компонентов смеси)
• Фильтры частиц , когда наблюдаемые данные связаны в цепь Маркова и должны обрабатываться последовательно.

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

• Преобразование Бокса – Мюллера
• Полярный метод Марсальи

Для создания распределения Пуассона :

• См. Распределение Пуассона # Генерация случайных величин с распределением Пуассона

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

В научной библиотеке GNU есть раздел под названием «Распределения случайных чисел» с процедурами выборки из более чем двадцати различных распределений.

Сноски [ править ]

Литература [ править ]

• Деврой, Л. (1986) Генерация неоднородной случайной величины . Нью-Йорк: Спрингер
• Фишман, GS (1996) Монте-Карло. Концепции, алгоритмы и приложения . Нью-Йорк: Спрингер
• Hörmann, W .; Дж. Лейдольд, Дж. Дерфлингер (2004, 2011) Автоматическая генерация неоднородной случайной величины . Берлин: Springer.
• Knuth, DE (1997) Искусство программирования , Vol. 2 Получисловые алгоритмы , Глава 3.4.1 (3-е издание).
• Рипли, Б.Д. (1987) Стохастическое моделирование . Вайли.