0
$\begingroup$

Say I have a distribution, either described by a probability density function that is integrable and continuous, or by a set of discrete probabilities over a finite set of symbols.

I want to efficiently generate samples from this distribution. I don't care about references to other algorithms, I want to know if this idea is essentially correct, or how to improve it.

Here is how I currently do it for the discrete case :

  1. form the cumulative probability function ( defined at the ith symbol as the sum of all probabilities from the first symbol to the ith symbol ).
  2. Then, there is an interval, [0,max(CDF)] and it is trivial to output a IID random number anywhere in that interval using a regular PRNG.
  3. Since every symbol is now associated with an interval, we output the symbol in whose interval the IID number landed.

It seems completely obvious to me that the output sequence will have the characteristics of the given discrete distribution, and is optimal up to the original PRNG.

I want now to extend to the continuous case (this may be the Ziggurat algorithm, and if so, boy am I happy I jumped straight to that). But can we not simply integrate the PDF to get a CDF, again form the interval [0,max(CDF)] and again shoot IID randoms at this interval, and again, and this is the tricky part for me, associate each sample symbol (of which there are infinitely many) with an interval. Then output the sample symbol in whose interval the IID number landed.

So, my question is : how can I associate the sample symbols, with intervals? Presumably by discretizing (putting into buckets) the sample symbol interval, and giving anything in a bucket the same probability. The size of buckets could be worked out so as to, over the intended output stream length, not cause any detectable deviation from the underlying continuous distribution.

Also, I am doing this in JavaScript. It's a DIY so I am not interested in trusting or using someone else's code. But nor am I interested in spending 2 days on it. I'm asking here as I am not an expert in distributions, and I want to have the ideas corrected before I try to implement this.

$\endgroup$
  • $\begingroup$ Actually Ziggurat just sounds easier. Maybe I should just do that. I can't see anything wrong with the above idea...but if someone can make an answer about it I'm sure I will learn something. $\endgroup$ – Cris Stringfellow Mar 12 '13 at 5:34
  • $\begingroup$ I lost you in the middle right where you tried to characterize the "continuous case" in terms of "sample symbols" and "intervals." This sounds like a discrete distribution, not a continuous one. Perhaps you could clarify this by specifying how your distribution will be described and what output you are hoping to get in the continuous case. BTW, if your policy is not to "use someone else's code," yet you know you're not an expert, then you're really saying you think that your lack of expertise makes you better qualified than the experts to write correct code in this tricky situation. Good luck! $\endgroup$ – whuber Mar 12 '13 at 16:11
  • $\begingroup$ @whuber not really my meaning about the experts. Just that I like to make stuff in order to learn. Even if it breaks first. But actually what I am describing is just the inverted cumulative density function. I admit...it's a bit nastily worded...but sometimes that happens. $\endgroup$ – Cris Stringfellow Mar 12 '13 at 16:14
  • $\begingroup$ (I think all your readers will appreciate the motivation for learning and the benefits of writing your own code for comparison to the state of the art.) But then what is your question? If you're inverting a CDF, there are no symbols or intervals involved; that's what's confusing me--and will likely confuse other readers too. $\endgroup$ – whuber Mar 12 '13 at 16:17
  • 2
    $\begingroup$ How accurate do you need the inversion to be? What programming capabilities do you have? There are many, many algorithms for this, ranging from continued fraction approximations through numerical integration or even just interpolation in precomputed tables. You can get some sense of the nature of the techniques from stats.stackexchange.com/questions/7200, which discusses computing the Normal CDF; some of the links and references in those answers probably include methods to compute the inverse CDF, too. $\endgroup$ – whuber Mar 12 '13 at 16:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.