Revision as of 20:58, 24 November 2018 edit Tamfang (talk \| contribs) Extended confirmed users, Pending changes reviewers, Rollbackers 59,063 edits m →Literature: fuller names, links ← Previous edit		Revision as of 13:54, 2 February 2019 edit undo Deacon Vorbis (talk \| contribs) Extended confirmed users, Rollbackers 23,589 edits →Operation: ugh Next edit →
Line 2: ==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 into the two tables. Based on the probability stored at that index, a [[biased coin]] is then flipped, and the outcome of the flip is used to choose between a result of {{mvar\|i}} and {{mvar\|K<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