Binary decompositions of probability densities and random-bit simulation

Nekrutkin Vladimir ()
Additional contact information
Nekrutkin Vladimir: St. Petersburg State University, 7/9 Universitetskaya nab., St. Petersburg, 199034, Russia

Monte Carlo Methods and Applications, 2020, vol. 26, issue 2, 163-169

Abstract: 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.

Keywords: Random-bit simulation; complexity of simulation (search for similar items in EconPapers)
Date: 2020
References: View complete reference list from CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1515/mcma-2020-2063 (text/html)
For access to full text, subscription to the journal or payment for the individual article is required.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:bpj:mcmeap:v:26:y:2020:i:2:p:163-169:n:5

Ordering information: This journal article can be ordered from
https://www.degruyter.com/journal/key/mcma/html

DOI: 10.1515/mcma-2020-2063

Access Statistics for this article

Monte Carlo Methods and Applications is currently edited by Karl K. Sabelfeld

More articles in Monte Carlo Methods and Applications from De Gruyter
Bibliographic data for series maintained by Peter Golla ().