In computing, the alias method is a family of efficient algorithms for sampling from a discrete probability distribution, due to A. J. Walker. The algorithms typically use or preprocessing time, after which random values can be drawn from the distribution in time.
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.
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.
Knuth, Art of Computer Programming, Vol 2: Seminumerical Algorithms: Sect. 3.4.1.
- 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++
- 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.
- 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.
- Vose, M. D. (1991). "A linear algorithm for generating random numbers with a given distribution". IEEE Transactions on Software Engineering 17 (9): 972–975. doi:10.1109/32.92917.
- Darts, Dice, and Coins: Sampling from a Discrete Distribution. KeithSchwarz.com. Retrieved on 2011-12-27.
- 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
|This statistics-related article is a stub. You can help Wikipedia by expanding it.|
|This computer science article is a stub. You can help Wikipedia by expanding it.|