Title :
Interval algorithm for random number generation
Author :
Te Sun Hao ; Hoshi, Mamoru
Author_Institution :
Sch. of Inf. Syst., Univ. of Electro-Commun., Tokyo, Japan
fDate :
3/1/1997 12:00:00 AM
Abstract :
The problem of generating a random number with an arbitrary probability distribution by using a general biased M-coin is studied. An efficient and very simple algorithm based on the successive refinement of partitions of the unit interval (0, 1), which we call the interval algorithm, is proposed. A fairly tight evaluation on the efficiency is given. Generalizations of the interval algorithm to the following cases are investigated: (1) output sequence is independent and identically distributed (i.i.d.); (2) output sequence is Markov; (3) input sequence is Markov; (4) input sequence and output sequence are both subject to arbitrary stochastic processes
Keywords :
Markov processes; arithmetic codes; deterministic algorithms; entropy; probability; random number generation; Markov sequence; arbitrary probability distribution; arbitrary stochastic processes; deterministic algorithm; efficiency; general biased M-coin; i.i.d sequence; independent and identically distributed sequence; input sequence; interval algorithm; output sequence; random number generation; unit interval; upper bound; Arithmetic; Entropy; Markov processes; Partitioning algorithms; Probability distribution; Random number generation; Stochastic processes; Sun; Tellurium; Upper bound;
Journal_Title :
Information Theory, IEEE Transactions on
