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. That is, it returns integer values according to some arbitrary probability distribution. 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 table and an alias table . To generate a random outcome, a fair diсe is rolled to determine an index into the two tables. Based on the probability stored at that index, a biased coin is then flipped, and the outcome of the flip is used to choose between a result of and.
More concretely, the algorithm operates as follows:
  1. Generate a uniform random variate.
  2. Let and.
  3. If, return. This is the biased coin flip.
  4. Otherwise, return.
An alternative formulation of the probability table, proposed by Marsaglia et. al. as the “square histogram” method, uses the condition in the third step instead of computing.

Table generation

The distribution may be padded with additional probabilities to increase to a convenient value, such as a power of two.
To generate the table, first initialize. While doing this, divide the table entries into three categories:
If, the corresponding value will never be consulted and is unimportant, but a value of is sensible.
As long as not all table entries are exactly full, repeat the following steps:
  1. Arbitrarily choose an overfull entry and an underfull entry.
  2. Allocate the unused space in entry to outcome, by setting.
  3. Remove the allocated space from entry by changing.
  4. Entry is now exactly full.
  5. Assign entry to the appropriate category based on the new value of.
Each iteration moves at least one entry to the “exactly full” category, 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 Alias structure is not unique.
As the lookup procedure is slightly faster if , one goal during table generation is to maximize the sum of the. Doing this optimally turns out to be NP hard, but a greedy algorithm 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 and is not needed. Generating is a waste of time. For example if, then a 32-bit random variate could be used to make 32 choices, 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 techniques arithmetic we can approach the limit given by the binary entropy function.

Literature