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 $O(n \log n)$ or $O(n)$ preprocessing time, after which random values can be drawn from the distribution in $O(1)$ 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.

References

1. ^ Walker, A. J. (1974). "New fast method for generating discrete random numbers with arbitrary frequency distributions". Electronics Letters 10 (8): 127. doi:10.1049/el:19740097. edit
2. ^ Walker, A. J. (1977). "An Efficient Method for Generating Discrete Random Variables with General Distributions". ACM Transactions on Mathematical Software 3 (3): 253. doi:10.1145/355744.355749. edit
3. ^
4. ^ Darts, Dice, and Coins: Sampling from a Discrete Distribution. KeithSchwarz.com. Retrieved on 2011-12-27.
5. ^ George Marsaglia; Wai Wan Tsang; Jingbo Wang (2004-07-12), "Fast Generation of Discrete Random Variables", Journal of Statistical Software 11 (3): 1–11, retrieved 2012-07-14