Archive for April, 2006
More on the alias method
Posted by prxq in Lisp, Mathematics, Programming on April 23, 2006
It turns out that, as pointed out by Jens Axel Søgaard, the method I wrote about a few days ago is the alias method by Walker, as found in D. Knuth’s TAOCP, but with a modification by R. A. Kronmal and A. V. Peterson. Their contribution, it seems, was the algorithm to rearrange the intervals in O(N) operations.
In any case, there is a very good and complete textbook, nowadays available freely on the net, where all these things are explained, disected, and thoroughly overengineered in every good sense of the word. The book is “Non-Uniform Random Variate Generation”, by Luc Devroye (thanks to Brad Lucier for mailing me this great link).
Below you’ll find some additional notes about the method, prompted by reading part of the book, and a link to an updated version of the CL code. (For simplicity, I will write as if in the context of my first post).
Slime 2.0
Posted by prxq in Lisp, Programming on April 20, 2006
A new version of slime has been released. See here, or download it directly as a gzipped tar archive or as a zip file.
The Alias Method
Posted by prxq in Lisp, Mathematics, Programming on April 17, 2006
Some days ago, there was some discussion in #lisp about how to program a random variable with nontrivial probability distribution. That is, given values x1,…,xn, and probabilities p1,…,pn, how to write a function that randomly returns one of those values with the corresponding probability each time it is called.
It turns out this problem has a beautiful, simple, and efficient solution called the alias method (R. A. Kronmal and A. V. Peterson. On the alias method for generating random variables from a discrete distribution. The American Statistician, 33:214–218, 1979.), that requires only one call to the random number generator. While I haven’t read any complete explanation of it (only the one in R. A. Kronmal, A. V. Peterson, The alias and alias-rejection-mixture methods for generating random variables from probability distributions. Proc. 1979 Winter Simulation Conference (ed. H.J. Highland et al.) 269–280, 1979, which isn’t complete), I think it is highly unlikely that it is different from the method I describe below.
An Common Lisp implementation can be found here.
First post
Posted by prxq in Uncategorized on April 13, 2006
At last, I have a blog. I thought about one for a long time, but somehow never moved beyond the early planning phase. About two weeks ago I decided to go ahead with it, and, after taking all the little decissions that go with that step, here it is.
So, what have we here? a nice empty blog, and no content yet. And by the look of things, it will stay that way over easter.