Генерация неоднородной случайной величины

Неравномерная генерация случайных величин или выборка псевдослучайных чисел — это численная практика генерации псевдослучайных чисел (PRN), которые следуют заданному распределению вероятностей .Методы обычно основаны на наличии равномерно распределенного генератора PRN . Затем вычислительные алгоритмы используются для преобразования одной случайной величины X или часто нескольких таких переменных в новую случайную величину Y так, чтобы эти значения имели требуемое распределение.Первые методы были разработаны для моделирования Монте-Карло в Манхэттенском проекте , ^{[ нужна ссылка ]} опубликовано Джоном фон Нейманом в начале 1950-х годов. ^[1]

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

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

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

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

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

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

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

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

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

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

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

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

Библиотеки программного обеспечения

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

См. также

Сноски

^ Фон Нейман, Джон (1951). «Различные методы, используемые при работе со случайными цифрами» (PDF) . В Хаусхолдере, AS; Форсайт, GE; Джермонд, Х.Х. (ред.). Методы Монте-Карло . Серия Национального бюро стандартов по прикладной математике. Том. 12. Типография правительства США. стр. 36–38. Любой, кто рассматривает арифметические методы получения случайных цифр, конечно, находится в состоянии греха. Также в сети находится некачественный скан оригинальной публикации .
^ Рипли (1987) ^{[ нужна страница ]}
^ Фишман (1996) ^{[ нужна страница ]}
^ Фишман (1996) ^{[ нужна страница ]}
^ «Распределение случайных чисел — документация GSL 2.7» . Операционная система GNU и движение за свободное программное обеспечение . Проверено 18 августа 2022 г.

Литература

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

[1] Фон Нейман, Джон (1951). «Различные методы, используемые при работе со случайными цифрами» (PDF) . В Хаусхолдере, AS; Форсайт, GE; Джермонд, Х.Х. (ред.). Методы Монте-Карло . Серия Национального бюро стандартов по прикладной математике. Том. 12. Типография правительства США. стр. 36–38. Любой, кто рассматривает арифметические методы получения случайных цифр, конечно, находится в состоянии греха. Также в сети находится некачественный скан оригинальной публикации .

[2] Рипли (1987) ^{[ нужна страница ]}

[3] Фишман (1996) ^{[ нужна страница ]}

[4] Фишман (1996) ^{[ нужна страница ]}

[The_GNU_Operating_System_and_the_Free_Software_Movement-5] «Распределение случайных чисел — документация GSL 2.7» . Операционная система GNU и движение за свободное программное обеспечение . Проверено 18 августа 2022 г.

[1]

[2]

[3]

[4]

[5]