GENERATION OF DISCRETE-DISTRIBUTIONS FROM BIASED COINS

Authors
ABRAHAMS J
Citation
J. Abrahams, GENERATION OF DISCRETE-DISTRIBUTIONS FROM BIASED COINS, IEEE transactions on information theory, 42(5), 1996, pp. 1541-1546
Citations number
11
Categorie Soggetti
Information Science & Library Science","Engineering, Eletrical & Electronic
Journal title
IEEE transactions on information theory → ACNP
ISSN journal
00189448
Volume
42
Issue
5
Year of publication
1996
Pages
1541 - 1546
Database
ISI
SICI code
0018-9448(1996)42:5<1541:GODFBC>2.0.ZU;2-F
Abstract
The procedure of Knuth and Yao to simulate random numbers with specifi ed distribution by parsing sequences of fair coin tosses is generalize d 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 cl osely related to the code trees arising in Karp's optimal variable-len gth coding algorithm for code symbols of unequal cost.