3 ms·
Yes, you can use an inverse CDF to implement a fairly efficient generator for pretty much any probability distribution. (I'm sure there's some pathological, an
by xscott 5y ago
Yes, you can use an inverse CDF to implement a fairly efficient generator for pretty much any probability distribution. (I'm sure there's some pathological, and uncommon, counterexample.) It's just a small/quick lookup table, and you can interpolate if you need extra resolution.
- tommiegannert 5y agoIsn't the problem that the normal distribution doesn't have an (inverse) CDF in closed form? So even the most common non-uniform distribution becomes a pathological example. https://en.wikipedia.org/wiki/Probit https://en.wikipedia.org/wiki/Probit
- klipt 5y agoYou can approximate it and throw away some samples to get the true distribution. See https://en.wikipedia.org/wiki/Ziggurat_algorithm https://en.wikipedia.org/wiki/Ziggurat_algorithm for one method which I believe statistical languages like R currently use to generate normal random variables.
- xscott 5y agoNope, that's not a problem. You don't need a closed form and simple equation to build the lookup table (inverse CDF). Use whatever expensive and iterative functions you want to build it. For the normal distribution, you can use a bisection on the math.h erf() function to invert it. This is expensive, but you're only going to do it to make your lookup table once. Build that table to reasonably fit in your cache, and then use your uniform pseudo random integers to peak into that table. As I mentioned above, you can interpolate between values in the table if you need more resolution. There are other tricks for specific distributions, but the technique is very general.