Content deleted Content added
m v1.41b - WP:WCW project (Link equal to linktext) |
No edit summary |
||
Line 41:
One case arises when the probabilities are particularly well balanced, so many {{math|1=''U<sub>i</sub>'' = 1}} and {{mvar|K<sub>i</sub>}} is not needed. Generating {{mvar|y}} is a waste of time. For example if {{math|1=''p''<sub>1</sub> = ''p''<sub>2</sub> = {{frac|1|2}}}}, then a 32-bit random variate {{mvar|x}} could be used to make 32 choices, but the alias method will only generate one.
Another case arises when the probabilities are strongly unbalanced, so many {{math|''U<sub>i</sub>'' ≈ 0}}. For example if {{math|1=''p''<sub>1</sub> = 0.999}} and {{math|1=''p''<sub>2</sub> = 0.001}}, then the great majority of the time, only a few random bits are required to determine that case 1 applies. If several choices are to be produced we can use much less than a uniform random bit. The limit is given by the “[[Binary entropy method]]”.
In such cases, the table method described by Marsaglia et al.<ref name=marsaglia/>{{Rp|1–4}} is more efficient.
| |||