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.