CODEWITHSUNDEEP
randomprobabilitydistributed
carnun
carnun

Reputation: 21

Pseudorandom Number Generation with Specific Non-Uniform Distributions

I'm writing a program that simulates various random walks (with differing distributions). At each timestep, I need randomly generated, two dimensional step distances and angles from the distribution of the random walk. I'm hoping someone can check my understanding of how to generate these random numbers.

As I understand it I can use Inverse Transform Sampling as follows:

If f(x) is the pdf of our random walk that has a non-uniform distribution, and y is a random number from a uniform distribution. Then if we let f(x) = y and solve to find x then we have a random number from the non-uniform distribution.

Is this a feasible solution?

Upvotes: 2

Views: 253

Answers (2)

Samsdram
Samsdram

Reputation: 1635

You are close, but not quite. Every probability density function (pdf) has a corresponding cumulative density function (cdf). An important property about CDF(x) is that they are always between 0 and 1. Because it is relatively easy to draw a random number between 0 and 1, we can use that to work our way backwards to the distribution. So changing the word pdf to CDF in your question makes the statement correct.

As an aside for this to make sense computationally you need to find an easy to calculate inverse of the CDF. One way to do this is to fit a polynomial approximation to the CDF and find the inverse of that function. There are more advanced techniques for simulating probability distributions with messy distributions. See this book chapter for the details.

Upvotes: 0

Aniko
Aniko

Reputation: 18864

Not quite. The function that needs to be inverted is not f(x), the pdf, but F(x)=P(X<=x)=int_{-inf}^{x}f(t)dt, the cdf. The good thing is that F is monotone, so actually has a unique inverse (unlike f).

There are multiple other ways of generating random numbers according to a given distribution. For example, if the cdf F is difficult to compute or to invert, rejection sampling can be a good option if f is easy to compute.

Upvotes: 2

Related Questions