Skip to content Skip to navigation
University of Warwick
  • Study
  • |
  • Research
  • |
  • Business
  • |
  • Alumni
  • |
  • News
  • |
  • About

University of Warwick
Publications service & WRAP

Highlight your research

  • WRAP
    • Home
    • Search WRAP
    • Browse by Warwick Author
    • Browse WRAP by Year
    • Browse WRAP by Subject
    • Browse WRAP by Department
    • Browse WRAP by Funder
    • Browse Theses by Department
  • Publications Service
    • Home
    • Search Publications Service
    • Browse by Warwick Author
    • Browse Publications service by Year
    • Browse Publications service by Subject
    • Browse Publications service by Department
    • Browse Publications service by Funder
  • Help & Advice
University of Warwick

The Library

  • Login
  • Admin

From the Bernoulli factory to a dice enterprise via perfect sampling of Markov chains

Tools
- Tools
+ Tools

Morina, Giulio, Latuszynski, Krzysztof, Nayar, Piotr and Wendland, Alex (2022) From the Bernoulli factory to a dice enterprise via perfect sampling of Markov chains. Annals of Applied Probability, 32 (1). pp. 327-359. doi:10.1214/21-AAP1679 ISSN 1050-5164.

[img]
Preview
PDF
WRAP-from-Bernoulli-factory-dice-enterprise-via-perfect-sampling-Markov-chains-Latuszynski-2021.pdf - Accepted Version - Requires a PDF viewer.

Download (585Kb) | Preview
Official URL: https://doi.org/10.1214/21-AAP1679

Request Changes to record.

Abstract

Given a p-coin that lands heads with unknown probability p, we wish to produce an f(p)-coin for a given function f:(0,1)→(0,1). This problem is commonly known as the Bernoulli factory and results on its solvability and complexity have been obtained in (ACM Trans. Model. Comput. Simul. 4 (1994) 213–219; Ann. Appl. Probab. 15 (2005) 93–115). Nevertheless, generic ways to design a practical Bernoulli factory for a given function f exist only in a few special cases. We present a constructive way to build an efficient Bernoulli factory when f(p) is a rational function with coefficients in R. Moreover, we extend the Bernoulli factory problem to a more general setting where we have access to an m-sided die and we wish to roll a v-sided one; that is, we consider rational functions between open probability simplices. Our construction consists of rephrasing the original problem as simulating from the stationary distribution of a certain class of Markov chains—a task that we show can be achieved using perfect simulation techniques with the original m-sided die as the only source of randomness. In the Bernoulli factory case, the number of tosses needed by the algorithm has exponential tails and its expected value can be bounded uniformly in p. En route to optimizing the algorithm we show a fact of independent interest: every finite, integer valued, random variable will eventually become log-concave after convolving with enough Bernoulli trials.

Item Type: Journal Article
Subjects: Q Science > QA Mathematics
Divisions: Faculty of Science, Engineering and Medicine > Science > Mathematics
Faculty of Science, Engineering and Medicine > Science > Statistics
Library of Congress Subject Headings (LCSH): Bernoulli numbers, Markov processes, Perfect simulation (Statistics)
Journal or Publication Title: Annals of Applied Probability
Publisher: Institute of Mathematical Statistics
ISSN: 1050-5164
Official Date: February 2022
Dates:
DateEvent
February 2022Published
8 March 2022Available
8 March 2021Accepted
Volume: 32
Number: 1
Page Range: pp. 327-359
DOI: 10.1214/21-AAP1679
Status: Peer Reviewed
Publication Status: Published
Reuse Statement (publisher, data, author rights):
Access rights to Published version: Open Access (Creative Commons)
Date of first compliant deposit: 12 March 2021
Date of first compliant Open Access: 24 March 2022
Related URLs:
  • Publisher
Open Access Version:
  • ArXiv

Request changes or add full text files to a record

Repository staff actions (login required)

View Item View Item

Downloads

Downloads per month over past year

View more statistics

twitter

Email us: wrap@warwick.ac.uk
Contact Details
About Us