Alias method

In computing, the alias method is a family of efficient algorithms for sampling from a discrete probability distribution, due to A. J. Walker.^[1][2] The algorithms typically use or preprocessing time, after which random values can be drawn from the distribution in time.^[3]

Internally, the algorithm builds two tables, a probability table and an alias table. To generate a random outcome, a fair die is rolled to determine an index into the probability table. Based on the probability stored at that index, a biased coin is then flipped, and the outcome of the flip is used to determine which result to output.^[4]

There are cases in which the alias method is not optimal in rolls of the die. Consider the case where there are two choices with equal probability, and we have a die with 256 sides. The alias method could be performed with one throw of the die. However, the roll of the die could be used to make 8 independent selections between two choices using the binary representation of the numbers from 0 to 255. Another case is when there are a million different choices, but one of the choices has a probability of 99.99%. The alias method would require several rolls of the 256 side die. The table method described by Marsaglia et al. is more efficient.^[5]

Literature

Knuth, Art of Computer Programming, Vol 2: Seminumerical Algorithms: Sect. 3.4.1.

Implementations

• http://www.keithschwarz.com/darts-dice-coins/ Keith Schwarz: Detailed explanation, numerically stable version of Vose's algorithm, and link to Java implementation
• http://apps.jcns.fz-juelich.de/ransampl Joachim Wuttke: Implementation as a small C library.
• http://oroboro.com/non-uniform-random-numbers Rafael Baptista's Implementation in C++
• https://github.com/argh/hacks/tree/master/non-uniform-distributions Roger Gonzalez' implementation in JavaScript

References