Alias method

In computing, the alias method is a family of efficient algorithms for sampling from a discrete probability distribution, published in 1974 by Alastair J.

[4] More concretely, the algorithm operates as follows: An alternative formulation of the probability table, proposed by Marsaglia et al.[5] as the square histogram method, avoids the computation of y by instead checking the condition x < Vi = (Ui + i − 1)/n in the third step.

The distribution may be padded with additional probabilities pi = 0 to increase n to a convenient value, such as a power of two.

Vose[3]: 974  points out that floating-point rounding errors may cause the guarantee referred to in step 1 to be violated.

Doing this optimally turns out to be NP hard,[5]: 6  but a greedy algorithm comes reasonably close: rob from the richest and give to the poorest.

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.

A circle on the left has 5 lines to 5 boxes in a column labeled "Acceptance". The first and second box are solid and each have the number 1 in them. The second box is half full and has the number 0.5 in it. The fourth box is solid with a 1 and the fifth box is three quarters full with a 0.75. Each box has an arrow from the filled region to its index, i.e., the first box points to a 1, the second box to a two, etc. There is a second column of five boxes labeled "Alias", each corresponding to one of the first boxes. Three are empty, but the third has a 2 in it and the fifth has a 1 in it. There is an arrow from the empty part of the third box in the first column to the third box in the second column and similarly for the fifth boxes.
A diagram of an alias table that represents the probability distribution〈0.25, 0.3, 0.1, 0.2, 0.15〉