Alias Method
   HOME

TheInfoList



OR:

In
computing Computing is any goal-oriented activity requiring, benefiting from, or creating computer, computing machinery. It includes the study and experimentation of algorithmic processes, and the development of both computer hardware, hardware and softw ...
, the alias method is a family of efficient
algorithm In mathematics and computer science, an algorithm () is a finite sequence of Rigour#Mathematics, mathematically rigorous instructions, typically used to solve a class of specific Computational problem, problems or to perform a computation. Algo ...
s for sampling from a discrete probability distribution, published in 1974 by Alastair J. Walker. That is, it returns integer values according to some arbitrary
discrete probability distribution In probability theory and statistics, a probability distribution is a function that gives the probabilities of occurrence of possible events for an experiment. It is a mathematical description of a random phenomenon in terms of its sample spa ...
. The algorithms typically use or preprocessing time, after which random values can be drawn from the distribution in time.


Operation

Internally, the algorithm consults two tables, a ''
probability Probability is a branch of mathematics and statistics concerning events and numerical descriptions of how likely they are to occur. The probability of an event is a number between 0 and 1; the larger the probability, the more likely an e ...
table Table may refer to: * Table (database), how the table data arrangement is used within the databases * Table (furniture), a piece of furniture with a flat surface and one or more legs * Table (information), a data arrangement with rows and column ...
'' and an ''alias table'' (for ). To generate a random outcome, a fair die is rolled to determine an index into the two tables. A biased coin is then flipped, choosing a result of with probability , or otherwise (probability ). More concretely, the algorithm operates as follows: # Generate a
uniform A uniform is a variety of costume worn by members of an organization while usually participating in that organization's activity. Modern uniforms are most often worn by armed forces and paramilitary organizations such as police, emergency serv ...
random variate . # Let and . (This makes uniformly distributed on and uniformly distributed on .) # If , return . This is the biased coin flip. # Otherwise, return . An alternative formulation of the probability table, proposed by Marsaglia et al. as the square histogram method, avoids the computation of by instead checking the condition in the third step.


Table generation

The distribution may be padded with additional probabilities to increase to a convenient value, such as a
power of two A power of two is a number of the form where is an integer, that is, the result of exponentiation with number 2, two as the Base (exponentiation), base and integer  as the exponent. In the fast-growing hierarchy, is exactly equal to f_1^ ...
. To generate the two tables, first initialize . While doing this, divide the table entries into three categories: * The "overfull" group, where , * The "underfull" group, where and has not been initialized, and * The "exactly full" group, where or ''has'' been initialized. If , the corresponding value will never be consulted and is unimportant, but a value of is sensible. This also avoids problems if the probabilities are represented as fixed-point numbers which cannot represent exactly. As long as not all table entries are exactly full, repeat the following steps: # Arbitrarily choose an overfull entry and an underfull entry . (If one of these exists, the other must, as well.) # Allocate the unused space in entry to outcome , by setting . # Remove the allocated space from entry by changing . # Entry is now exactly full. # Assign entry to the appropriate category based on the new value of . Each iteration moves at least one entry to the "exactly full" category (and the last moves two), so the procedure is guaranteed to terminate after at most iterations. Each iteration can be done in time, so the table can be set up in time. Vose points out that floating-point rounding errors may cause the guarantee referred to in step 1 to be violated. If one category empties before the other, the remaining entries may have set to 1 with negligible error. The solution accounting for floating point is sometimes called the Walker-Vose method or the Vose alias method. Because of the arbitrary choice in step 1, the alias structure is not unique. As the lookup procedure is slightly faster if (because does not need to be consulted), one goal during table generation is to maximize the sum of the . Doing this optimally turns out to be
NP hard NP may refer to: Arts and entertainment * NP (novel), ''NP'' (novel), by Japanese author Banana Yoshimoto Organizations * Nashua-Plainfield Community School District, Iowa, United States * National Party (disambiguation), various political parti ...
, but a
greedy algorithm A greedy algorithm is any algorithm that follows the problem-solving heuristic of making the locally optimal choice at each stage. In many problems, a greedy strategy does not produce an optimal solution, but a greedy heuristic can yield locally ...
comes reasonably close: rob from the richest and give to the poorest. That is, at each step choose the largest and the smallest . Because this requires sorting the , it requires time.


Efficiency

Although the alias method is very efficient if generating a uniform deviate is itself fast, there are cases where it is far from optimal in terms of random bit usage. This is because it uses a full-precision random variate each time, even when only a few random bits are needed. One case arises when the probabilities are particularly well balanced, so many . For these values of , is not needed and generating is a waste of time. For example if , then a 32-bit random variate could be used to generate 32 outputs, but the alias method will only generate one. Another case arises when the probabilities are strongly unbalanced, so many . For example if and , then the great majority of the time, only a few random bits are required to determine that case 1 applies. In such cases, the table method described by Marsaglia et al. is more efficient. If we make many choices with the same probability we can on average require much less than one unbiased random bit. Using
arithmetic coding Arithmetic coding (AC) is a form of entropy encoding used in lossless data compression. Normally, a String (computer science), string of characters is represented using a fixed number of bits per character, as in the American Standard Code for In ...
techniques arithmetic we can approach the limit given by the
binary entropy function Binary may refer to: Science and technology Mathematics * Binary number, a representation of numbers using only two values (0 and 1) for each digit * Binary function, a function that takes two arguments * Binary operation, a mathematical op ...
.


Literature

*
Donald Knuth Donald Ervin Knuth ( ; born January 10, 1938) is an American computer scientist and mathematician. He is a professor emeritus at Stanford University. He is the 1974 recipient of the ACM Turing Award, informally considered the Nobel Prize of comp ...
, ''
The Art of Computer Programming ''The Art of Computer Programming'' (''TAOCP'') is a comprehensive multi-volume monograph written by the computer scientist Donald Knuth presenting programming algorithms and their analysis. it consists of published volumes 1, 2, 3, 4A, and 4 ...
'', Vol 2: Seminumerical Algorithms, section 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 * https://jugit.fz-juelich.de/mlz/ransampl Joachim Wuttke: Implementation as a small C library. * https://gist.github.com/0b5786e9bfc73e75eb8180b5400cd1f8 Liam Huang's Implementation in C++ * https://github.com/joseftw/jos.weightedresult/blob/develop/src/JOS.WeightedResult/AliasMethodVose.cs C# implementation of Vose's algorithm. * https://github.com/cdanek/KaimiraWeightedList C# implementation of Vose's algorithm without floating point instability.


References

{{reflist Pseudorandom number generators