Alias method: Difference between revisions

Revision as of 20:46, 22 June 2024

Latest revision as of 01:14, 31 December 2024

(3 intermediate revisions by 3 users not shown)

Line 4:

==Operation==

Internally, the algorithm consults two tables, a ''[[probability]] [[Table (information)|table]]'' {{mvar|U_i}} and an ''alias table'' {{mvar|K_i}} (for {{math|1 ≤ ''i'' ≤ ''n''}}). To generate a random outcome, a fair [[dice|die]] is rolled to determine an index {{mvar|i}} into the two tables. Based on the probability stored at that index, aA [[biased coin]] is then flipped, andchoosing thea outcomeresult of the{{mvar|i}} flipwith is used to choose between a result ofprobability {{mvar|U_i}}, andor {{mvar|K_i}} otherwise (probability {{math|1 − ''U_i''}}).<ref>{{cite web |url=http://www.keithschwarz.com/darts-dice-coins/ |title=Darts, Dice, and Coins: Sampling from a Discrete Distribution |date=29 December 2011 |website=KeithSchwarz.com |access-date=2011-12-27}}</ref>

More concretely, the algorithm operates as follows:

Line 13:

# 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 |url=https://www.researchgate.net/publication/5142858_Fast_Generation_of_Discrete_Random_Variables/fulltext/0e5fcf01f0c404bcbfaaa888/Fast-Generation-of-Discrete-Random-Variables.pdf5142858}}</ref> as the '''square histogram method''', avoids the computation of {{mvar|y}} by instead checking the condition {{math|1=''x'' &lt; &nbsp;''V_i''}} in the third step (where {{math|1=''V_i'' = &nbsp;(''U_i'' &nbsp;+ &nbsp;''i'' &nbsp;− &nbsp;1)/''n''}}) in the third step.

==Table generation==