Alias method: Difference between revisions

Revision as of 13:51, 13 April 2021

Revision as of 23:23, 24 September 2021

Line 7:

# Generate a [[Uniform distribution (continuous)|uniform]] random variate {{math|0 ≤ ''x'' < 1}}.

# Let {{math|1=''i'' = ⌊''nx''⌋ + 1}} and {{math|1=''y'' = ''nx'' + 1 − ''i''}}. (This makes {{math|''i''}} uniformly distributed on {{math|{1, 2, …..., ''n''} }} and {{math|''y''}} uniformly distributed on {{math|[0, 1)}}.)

# If {{math|''y'' < ''U_i''}}, return {{mvar|i}}. This is the biased coin flip.

# 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 |author-link1=George Marsaglia |first2=Wai Wan |last2=Tsang |first3=Jingbo |last3=Wang |title=Fast Generation of Discrete Random Variables |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 }}</ref> as the “square"square histogram”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==

Line 17:

To generate the table, first initialize {{math|1=''U_i'' = ''np_i''}}. While doing this, divide the table entries into three categories:

* The “overfull”"overfull" group, where {{math|''U_i'' > 1}},

* The “underfull”"underfull" group, where {{math|''U_i'' &lt; 1}} and {{mvar|K_i}} has not been initialized, and

* The “exactly"exactly full”full" group, where {{math|1=''U_i'' = 1}} or {{mvar|K_i}} ''has'' been initialized.

If {{math|1=''U_i'' = 1}}, the corresponding value {{mvar|K_i}} will never be consulted and is unimportant, but a value of {{math|1=''K_i'' = ''i''}} is sensible.

Line 30:

# Assign entry {{mvar|i}} to the appropriate category based on the new value of {{mvar|U_i}}.

Each iteration moves at least one entry to the “exactly"exactly full”full" category (and the last moves two), so the procedure is guaranteed to terminate after at most {{math|''n''−1}} iterations. Each iteration can be done in {{math|''O''(1)}} time, so the table can be set up in {{math|''O''(''n'')}} time.

Vose<ref name=Vose/>{{Rp|974}} 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 {{mvar|U_i}} set to 1 with negligible error. The solution accounting for floating point is sometimes called the '''Walker-Vose method''' or the '''Vose alias method'''.

Line 50:

==Implementations==

* http://www.keithschwarz.com/darts-dice-coins/ Keith Schwarz: Detailed explanation, numerically stable version of Vose’sVose's algorithm, and link to Java implementation

* http://apps.jcns.fz-juelich.de/ransampl Joachim Wuttke: Implementation as a small C library.

*https://gist.github.com/0b5786e9bfc73e75eb8180b5400cd1f8 Liam Huang's Implementation in C++