Is there a way to generate a random variate from a non-standard distribution without computing CDF?

0
votes

I'm trying to write a Monte Carlo simulation. In my simulation I need to generate many random variates from a discrete probability distribution.

I do have a closed-form solution for the distribution and it has finite support; however, it is not a standard distribution. I am aware that I could draw a uniform[0,1) random variate and compare it to the CDF get a random variate from my distribution, but the parameters in the distributions are always changing. Using this method is too slow.

So I guess my question has two parts:

  1. Is there a method/algorithm to quickly generate finite, discrete random variates without using the CDF?

  2. Is there a Python module and/or a C++ library which already has this functionality?

3
c++pythonalgorithmrandommontecarlo
Try std::discrete_distribution. – Kerrek SB
Doesn't that require you to know the distribution? – thang
if you have a closed-form solution, is there any chance you could invert it? – ev-br

3 Answers

0
votes

Acceptance\Rejection: Find a function that is always higher than the pdf. Generate 2 Random variates. The first one you scale to calculate the value, the second you use to decide whether to accept or reject the choice. Rinse and repeat until you accept a value. Sorry I can't be more specific, but I haven't done it for a while.. Its a standard algorithm, but I'd personally implement it from scratch, so I'm not aware of any implementations.

0
votes

Indeed acceptance/rejection is the way to go if you know analytically your pdf. Let's call it f(x). Find a pdf g(x) such that there exist a constant c, such that c.g(x) > f(x), and such that you know how to simulate a variable with pdf g(x) - For example, as you work with a distribution with a finite support, a uniform will do: g(x) = 1/(size of your domain) over the domain.

Then draw a couple (G, U) such that G is simulated with pdf g(x), and U is uniform on [0, c.g(G)]. Then, if U < f(G), accept U as your variable. Otherwise draw again. The U you will finally accept will have f as a pdf.

Note that the constant c determines the efficiency of the method. The smaller c, the most efficient you will be - basically you will need on average c drawings to get the right variable. Better get a function g simple enough (don't forget you need to draw variables using g as a pdf) but will the smallest possible c.

0
votes

If acceptance rejection is also too inefficient you could also try some Markov Chain MC method, they generate a sequence of samples each one dependent on the previous one, so by skipping blocks of them one can subsample obtaining a more or less independent set. They only need the PDF, or even just a multiple of it. Usually they work with fixed distributions, but can also be adapted to slowly changing ones.