Revision as of 10:20, 30 December 2024 edit 2a01:599:607:58c4:5c65:f467:5055:aece (talk) →Operation: Fixed typo Tags: Reverted Mobile edit Mobile web edit ← Previous edit		Latest revision as of 01:14, 31 December 2024 edit undo Tamfang (talk \| contribs) Extended confirmed users, Pending changes reviewers, Rollbackers 59,063 edits Undid gf revision 1266160024 by 2A01:599:607:58C4:5C65:F467:5055:AECE (talk)— not an error Tag: Undo
Line 4: ==Operation== Internally, the algorithm consults two tables, a ''[[probability]] [[Table (information)\|table]]'' {{mvar\|U<sub>i</sub>}} and an ''alias table'' {{mvar\|K<sub>i</sub>}} (for {{math\|1 ≤ ''i'' ≤ ''n''}}). To generate a random outcome, a fair [[dice\|~~dice~~die]] is rolled to determine an index {{mvar\|i}} into the two tables. A [[biased coin]] is then flipped, choosing a result of {{mvar\|i}} with probability {{mvar\|U<sub>i</sub>}}, or {{mvar\|K<sub>i</sub>}} otherwise (probability {{math\|1 − ''U<sub>i</sub>''}}).<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:

Alias method: Difference between revisions