Alias method: Difference between revisions

Revision as of 13:54, 2 February 2019

Revision as of 19:06, 16 February 2019

Line 1:

In [[computing]], the '''alias method''' is a family of efficient [[algorithm]]s for [[pseudo-random number sampling|sampling from a discrete probability distribution]], due to A. J. Walker.<ref name=Walker1974>{{Cite journal |doi=10.1049/el:19740097 |title=New fast method for generating discrete random numbers with arbitrary frequency distributions |journal=Electronics Letters |volume=10 |issue=8 |pages=127 |date=April 1974 |last1=Walker |first1=A. J. }}</ref><ref name=Walker1977>{{Cite journal |doi=10.1145/355744.355749 |title=An Efficient Method for Generating Discrete Random Variables with General Distributions |journal=ACM Transactions on Mathematical Software |volume=3 |issue=3 |pages=253253–256 |date=September 1977 |last1=Walker |first1=A. J. }}</ref> That is, it returns integer values {{math |1 ≤ ''i'' ≤ ''n''}} according to some arbitrary probability distribution {{mvar|p_i}}. The algorithms typically use {{math|''O''(''n'' log ''n'')}} or {{math|''O''(''n'')}} preprocessing time, after which random values can be drawn from the distribution in {{math|''O''(1)}} time.<ref name=Vose>{{Cite journal |ref=harv |doi=10.1109/32.92917 |title=A linear algorithm for generating random numbers with a given distribution |journal=IEEE Transactions on Software Engineering |volume=17 |issue=9 |pages=972&ndash;975 |date=September 1991 |last1=Vose |first1=Michael D. |url=http://web.eecs.utk.edu/~vose/Publications/random.pdf |archive-url=https://web.archive.org/web/20131029203736/http://web.eecs.utk.edu/~vose/Publications/random.pdf |archive-date=2013-10-29|citeseerx=10.1.1.398.3339 }}</ref>

==Operation==

Line 11:

# Otherwise, return {{mvar|K_i}}.

An alternative formulation of the probability table, proposed by Marsaglia et. al.<ref name=marsaglia>{{Citation |first1=George |last1=Marsaglia |authorlink1=George Marsaglia |first2=Wai Wan |last2=Tsang |first3=Jingbo |last3=Wang |title=Fast Generation of Discrete Random Variables |url=http://www.jstatsoft.org/v11/i03 |journal=Journal of Statistical Software |date=2004-07-12 |volume=11 |issue=3 |pages=1–11 |doi=10.18637/jss.v011.i03 |doi-access=free |accessdate=2012-07-14}}</ref> as the “square histogram” method, uses the condition {{math|''x'' &lt; ''V_i''}} in the third step (where {{math|1=''V_i'' = (''U_i'' + ''i'' − 1)/''n''}}) instead of computing {{mvar|y}}.

==Table generation==