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. Walker. That is, it returns integer values  according to some arbitrary discrete 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  (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 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.

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, 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 .  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 techniques arithmetic we can approach the limit given by the binary entropy function.

Literature
 Donald Knuth, The Art of Computer Programming, 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

Pseudorandom number generators