Monday, January 09, 2012

Generating random numbers following a given discrete probability distribution

I have never really thought very much about generating random numbers according to a precise discrete distribution, for example to simulate an unfair dice. In finance, we are generally interested in continuous distributions, where there is typically 2 ways: the inverse transform (usually computed in a numerical way), and the acceptance-rejection method (typically the ziggurat). The inverse transform is often preferred, because it's usable method for Quasi Monte-Carlo simulations while the acceptance rejection is not.

I would have thought about the simple way to generate random numbers according to a discrete distribution as first described here. But establishing a link with Huffman encoding is brilliant. Some better performing alternative (unrelated to Huffman) is offered there.

1 comment :

  1. the link to delicious is maybe broken (gives a 404 to me) but the original blog post is still there. Might maybe link there directly? I mean:
    http://blog.sigfpe.com/2012/01/lossless-decompression-and-generation.html

    ReplyDelete