TY - JOUR

T1 - Binary decompositions of probability densities and random-bit simulation

AU - Nekrutkin, Vladimir

PY - 2020/6/1

Y1 - 2020/6/1

N2 - This paper is devoted to random-bit simulation of probability densities, supported on [ 0, 1[ {[0,1]}. The term "random-bit" means that the source of randomness for simulation is a sequence of symmetrical Bernoulli trials. In contrast to the pioneer paper [D. E. Knuth and A. C. Yao, The complexity of nonuniform random number generation, Algorithms and Complexity, Academic Press, New York 1976, 357-428], the proposed method demands the knowledge of the probability density under simulation, and not the values of the corresponding distribution function. The method is based on the so-called binary decomposition of the density and comes down to simulation of a special discrete distribution to get several principal bits of output, while further bits of output are produced by "flipping a coin". The complexity of the method is studied and several examples are presented.

AB - This paper is devoted to random-bit simulation of probability densities, supported on [ 0, 1[ {[0,1]}. The term "random-bit" means that the source of randomness for simulation is a sequence of symmetrical Bernoulli trials. In contrast to the pioneer paper [D. E. Knuth and A. C. Yao, The complexity of nonuniform random number generation, Algorithms and Complexity, Academic Press, New York 1976, 357-428], the proposed method demands the knowledge of the probability density under simulation, and not the values of the corresponding distribution function. The method is based on the so-called binary decomposition of the density and comes down to simulation of a special discrete distribution to get several principal bits of output, while further bits of output are produced by "flipping a coin". The complexity of the method is studied and several examples are presented.

KW - complexity of simulation

KW - Random-bit simulation

KW - COMPLEXITY

UR - http://www.scopus.com/inward/record.url?scp=85083643081&partnerID=8YFLogxK

U2 - 10.1515/mcma-2020-2063

DO - 10.1515/mcma-2020-2063

M3 - Article

AN - SCOPUS:85083643081

VL - 26

SP - 163

EP - 169

JO - Monte Carlo Methods and Applications

JF - Monte Carlo Methods and Applications

SN - 0929-9629

IS - 2

ER -