Generation of discrete distributions from biased coins |
| |
| Authors: | Abrahams J. |
| |
| Affiliation: | Math., Comput., & Inf. Sci., Office of Naval Res., Arlington, VA; |
| |
| Abstract: | The procedure of Knuth and Yao (1976) to simulate random numbers with specified distribution by parsing sequences of fair coin tosses is generalized to employ discrete distributions of particular form instead of fair coins. Each probability in these distributions is an integral power of some fixed value t. The parse tree for the simulation procedure is closely related to the code trees arising in Karp's optimal variable-length coding algorithm for code symbols of unequal cost |
| |
| Keywords: | |
|
|
