The Library
Extending the Bernoulli Factory to a dice enterprise
Tools
Morina, Giulio (2021) Extending the Bernoulli Factory to a dice enterprise. PhD thesis, University of Warwick.
|
PDF
WRAP_Theses_Morina_2021.pdf - Submitted Version - Requires a PDF viewer. Download (1230Kb) | Preview |
Official URL: http://webcat.warwick.ac.uk/record=b3684276
Abstract
The Bernoulli Factory problem consists of finding an algorithm that tosses an f(p)-coin, i.e. a coin that lands heads with probability f(p) for a given function f, when p is unknown and the only source of randomness is given by a p-coin that can be tossed as many times as needed. This problem has been extensively studied and has found several applications in a variety of fields. In the present thesis we first propose novel methodologies for the construction of Bernoulli Factories algorithms that are applicable for a wide variety of functions f(p). The main idea is to rephrase the original problem as constructing an unbiased estimator for f(p) that is in [0; 1] almost surely { a deed we propose to solve via debiasing techniques. We also formally study a multivariate extension of the problem, named Dice En- terprise, that considers a more general setting where the sole source of randomness is given by an m-sided die and the aim is to roll v-sided dice, where the probability of rolling each face is a given function of the probabilities associated with the given m-sided die. We extend most of the current available theoretical results for Bernoulli Factories to this generic case. In particular, we characterise the class of functions for which a Dice Enterprise exists, provide an implementable algorithm based on polynomial approximations, and characterise functions that can admit a Dice Enterprise with a fast simulation. We also present a constructive way to build an efficient Dice Enterprise when the function of interest is a rational function with coefficients in R. This construction uses techniques that have not been previously applied in this setting. We rephrase 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. We provide a comprehensive analysis of the running time of this new methodology.
Item Type: | Thesis (PhD) | ||||
---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics | ||||
Library of Congress Subject Headings (LCSH): | Probabilities, Distribution (Probability theory), Binomial distribution, Bernoulli numbers, Algorithms, Approximation theory, Markov processes, Martingales (Mathematics) | ||||
Official Date: | January 2021 | ||||
Dates: |
|
||||
Institution: | University of Warwick | ||||
Theses Department: | Department of Statistics | ||||
Thesis Type: | PhD | ||||
Publication Status: | Unpublished | ||||
Supervisor(s)/Advisor: | Łatuszyński, Krzysztof ; Cameron, Ewan | ||||
Format of File: | |||||
Extent: | vi, 137 leaves | ||||
Language: | eng |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year