Łatuszyński, Krzysztof, Kosmidis, Ioannis, Papaspiliopoulos, Omiros and Roberts, Gareth O. (2009) Simulating events of unknown probabilities via reverse time martingales. Working Paper. Coventry: University of Warwick. Centre for Research in Statistical Methodology. (Working papers).

Preview

PDF WRAP_Latuszynski_09-30w.pdf - Published Version - Requires a PDF viewer such as GSview, Xpdf or Adobe Acrobat Reader Download (416Kb)

Abstract

Assume that one aims to simulate an event of unknown probability s ∈ (0, 1) which is uniquely determined, however only its approximations can be obtained using a finite computational effort. Such settings are often encountered in statistical simulations. We consider two specific examples. First, the exact simulation of non-linear diffusions ([3]). Second, the celebrated Bernoulli factory problem ([10], [16], [13], [12], [9], and also [1] and [8]) of generating an f(p)-coin given a sequence X1,X2, ... of independent tosses of a p-coin (with known f and unknown p). We describe a general framework and provide algorithms where this kind of problems can be fitted and solved. The algorithms are straightforward to implement and thus allow for effective simulation of desired events of probability s: In the case of diffusions, we obtain the algorithm of [3] as a specific instance of the generic framework developed here. In the case of the Bernoulli factory, our work offers a statistical understanding of the Nacu-Peres algorithm for f(p) = min{2p; 1 - 2ε} (which is central to the general question, c.f. [13]) and allows for its immediate implementation that avoids algorithmic difficulties of the original version. In the general case we link our results to existence and construction of unbiased estimators. In particular we show how to construct unbiased estimators given sequences of under- and overestimating reverse time super- and submartingales.

Item Type:	Working or Discussion Paper (Working Paper)
Subjects:	Q Science > QA Mathematics
Divisions:	Faculty of Science > Statistics
Library of Congress Subject Headings (LCSH):	Martingales (Mathematics), Probabilities
Series Name:	Working papers
Publisher:	University of Warwick. Centre for Research in Statistical Methodology
Place of Publication:	Coventry
Date:	2009
Volume:	Volume 2009
Number:	Number 30
Number of Pages:	11
Status:	Not Peer Reviewed
Access rights to Published version:	Open Access
Funder:	Spain
Grant number:	MTM2008-06660 (Spain)
Version or Related Resource:	Published as: Łatuszyński, K., et al. (2011). Simulating events of unknown probabilities via reverse time martingales. Random Structures & Algorithms, 38(4), pp. 441-452. http://wrap.warwick.ac.uk/id/eprint/41524
Related URLs:	Related item in WRAP
References:	[1] S. Assmussen, P. W. Glynn and H. Thorisson. Stationarity Detection in the Initial Transient Problem. ACM Transactions on Modelling and Computer Simulation, 2(2):130-157, 1992. [2] S. Asmussen and P. W. Glynn Stochastic simulation: algorithms and anal- ysis. Springer, New York, 2007. [3] A. Beskos, G.O. Roberts. Exact Simulation of Diffusions. Ann. Appl. Probab. 15(4): 2422{2444, 2005. [4] A. Beskos, O. Papaspiliopoulos, G.O. Roberts. Retrospective Exact Simulation of Diffusion Sample Paths with Applications. Bernoulli 12: 1077{1098, 2006. [5] A. Beskos, O. Papaspiliopoulos, G.O. Roberts. A factorisation of diffusion measure and finite sample path constructions. Methodol. Comput. Appl. Probab. 10(1): 85{104, 2008. [6] A. Beskos, O. Papaspiliopoulos, G.O. Roberts, and P. Fearnhead. Exact and computationally efficient likelihood-based estimation for discretely observed diffusion processes (with discussion). Journal of the Royal Statistical Society: Series B (Statistical Methodology), 68(3):333-382, 2006. [7] L. Devroye. Nonumniform Random Variable Generation. Springer-Verlag, New York, 1986. [8] S.G. Henderson and P. W. Glynn. Nonexistance of a class of variate generation schemes. Operations Research Letters, 31: 83{89, 2003. [9] O. Holtz, F. Nazarov, and Y. Peres. New coins from old, smoothly. eprint arXiv: 0808.1936, 2008. [10] M.S. Keane and G.L. OBrien. A Bernoulli factory. ACM Transactions on Modeling and Computer Simulation (TOMACS), 4(2):213-219, 1994. [11] P.E. Kloeden and E.Platen. Numerical Solution of Stochastic Differential Equations, Springer-Verlag, 1995. [12] E. Mossel and Y. Peres. New coins from old: computing with unknown bias. Combinatorica, 25(6):707-724, 2005. [13] S. Nacu and Y. Peres. Fast simulation of new coins from old. Annals of Applied Probability, 15(1):93{115, 2005. [14] , B.K. ksendal. Stochastic Differential Equations: An Introduction With Applications, Springer-Verlag, 1998. [15] O. Papaspiliopoulos, G.O. Roberts. Retrospective Markov chain Monte Carlo for Dirichlet process hierarchical models. Biometrika, 95:169{186, 2008. [16] Y. Peres. Iterating von Neumann's procedure for extracting random bits. Annals of Statistics, 20(1): 590{597, 1992.
URI:	http://wrap.warwick.ac.uk/id/eprint/35218

Request changes to a record

Actions (login required)

View Item