Alias method: Difference between revisions

Revision as of 05:56, 2 December 2019

Revision as of 23:14, 22 December 2019

Line 44:

Another case arises when the probabilities are strongly unbalanced, so many {{math|''U_i'' ≈ 0}}. For example if {{math|1=''p''₁ = 0.999}} and {{math|1=''p''₂ = 0.001}}, then the great majority of the time, only a few random bits are required to determine that case 1 applies.

In such cases, the table method described by Marsaglia et al.<ref name=marsaglia/>{{Rp|1–4}} is more efficient. If we make many choices with the same probability we can on average require much less than one unbiased random bit. Using [[Arithmeticarithmetic coding]] techniques arithmetic we can approach the limit given by the [[Binarybinary entropy function]].

==Literature==