Alias method

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〉

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.[1][2] That is, it returns integer values 1 ≤ i ≤ n according to some arbitrary discrete probability distribution pi. The algorithms typically use O(n log n) or O(n) preprocessing time, after which random values can be drawn from the distribution in O(1) time.[3]

  1. ^ Walker, A. J. (18 April 1974). "New fast method for generating discrete random numbers with arbitrary frequency distributions". Electronics Letters. 10 (8): 127–128. Bibcode:1974ElL....10..127W. doi:10.1049/el:19740097.
  2. ^ Walker, Alastair J. (September 1977). "An Efficient Method for Generating Discrete Random Variables with General Distributions". ACM Transactions on Mathematical Software. 3 (3): 253–256. doi:10.1145/355744.355749. S2CID 4522588.
  3. ^ Vose, Michael D. (September 1991). "A linear algorithm for generating random numbers with a given distribution" (PDF). IEEE Transactions on Software Engineering. 17 (9): 972–975. CiteSeerX 10.1.1.398.3339. doi:10.1109/32.92917. Archived from the original (PDF) on 2013-10-29.