Я пытаюсь написать симуляцию Монте-Карло. В моем моделировании мне нужно генерировать много случайных величин из дискретного распределения вероятностей.
У меня есть закрытое решение для дистрибутива, и оно имеет конечную поддержку; однако это не стандартный дистрибутив. Я знаю, что я мог бы нарисовать равномерную [0,1) случайную переменную и сравнить ее с CDF, чтобы получить случайную переменную из моего распределения, но параметры в распределениях всегда меняются. Использование этого метода слишком медленно.
Поэтому я думаю, что мой вопрос состоит из двух частей:
Существует ли метод / алгоритм для быстрой генерации конечных, дискретных случайных величин без использования CDF?
Есть ли модуль Python и / или библиотека C ++, которая уже имеет эту функциональность?
Принятие \ Нестабильность:
Найти функцию, которая всегда выше, чем в PDF. Генерация 2 случайных вариаций. Первый вы масштабируете, чтобы вычислить значение, второй вы используете, чтобы решить, принять или отклонить выбор. Промойте и повторяйте, пока не примете значение.
Извините, я не могу быть более конкретным, но я давно этого не делал ..
Это стандартный алгоритм, но я бы лично реализовал его с нуля, поэтому я не знаю ни о каких реализациях.
Действительно, принятие / отклонение — это путь, если вы аналитически знаете свой pdf. Давайте назовем это f (x). Найдите pdf g (x) такой, что существует постоянная c, такая, что cg (x)> f (x), и такая, что вы знаете, как имитировать переменную с помощью pdf g (x) — например, во время работы с распределением с конечной поддержкой, форма будет делать: g (x) = 1 / (размер вашего домена) по всему домену.
Затем нарисуйте пару (G, U), такую, что G моделируется с помощью pdf g (x), и U равномерно на [0, c.g (G)]. Тогда, если U < f (G), примите U в качестве переменной. В противном случае нарисуйте снова. U, который вы, наконец, примете, будет иметь f в виде pdf.
Обратите внимание, что постоянная c определяет эффективность метода. Чем меньше c, тем эффективнее вы будете — в основном вам понадобятся в среднем рисунки c, чтобы получить правильную переменную. Лучше получить функцию g достаточно просто (не забывайте, что вам нужно рисовать переменные, используя g в виде pdf), но будет наименьшее возможное c.
Если отклонение принятия также слишком неэффективно, вы также можете попробовать какой-нибудь метод Марковской цепочки MC, они генерируют последовательность выборок, каждая из которых зависит от предыдущей, поэтому, пропуская блоки из них, можно получить дополнительную выборку, получив более или менее независимый набор. Им нужен только PDF, или даже кратный. Обычно они работают с фиксированными дистрибутивами, но также могут быть адаптированы к медленно меняющимся.