Revision as of 16:15, 7 December 2024 edit Citation bot (talk \| contribs) Bots 5,871,244 edits Altered url. URLs might have been anonymized. \| Use this bot. Report bugs. \| #UCB_CommandLine ← Previous edit		Revision as of 10:20, 30 December 2024 edit undo 2a01:599:607:58c4:5c65:f467:5055:aece (talk) →Operation: Fixed typo Tags: Reverted Mobile edit Mobile web edit Next edit →
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\|~~die~~dice]] 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