Simulating events of unknown probabilities via reverse time martingales

DOI10.1002/RSA.20333MaRDI QIDQ5198664zbMATH OpenOpenAlexFDO

Authors Krzysztof Łatuszyński, Ioannis Kosmidis, Omiros Papaspiliopoulos, Gareth O. Roberts

Publication date 9 August 2011

Published in Random Structures \& Algorithms (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0907.4018, http://wrap.warwick.ac.uk/41524/1/WRAP-simulating-events-unknown-probabilities-reverse-time-martingales-Kosmidis-2010.pdf

zbMATH Keywords

computational problems in statisticsretrospective samplingBernoulli factorymartingales with discrete parameterunbiased simulation

Mathematics Subject Classification ID

Martingales with discrete parameter (60G42)

Abstract: Assume that one aims to simulate an event of unknown probability $sin(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, second, the celebrated Bernoulli factory problem of generating an $f(p)-$coin given a sequence $X_1,X_2,\mathrm{...}$ 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 cite{BeskosRobertsEA1} 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)=min2p,1-2varepsilon$ (which is central to the general question) and allows for its immediate implementation that avoids algorithmic difficulties of the original version.

Recommendations

• Unbiased simulation of rare events in continuous time
• A Bernoulli factory
• Optimal linear Bernoulli factories for small mean problems
• From the Bernoulli factory to a dice enterprise via perfect sampling of Markov chains
• Fast simulation of new coins from old

Cites work

• A Bernoulli factory
• A factorisation of diffusion measure and finite sample path constructions
• Exact and Computationally Efficient Likelihood-Based Estimation for Discretely Observed Diffusion Processes (with Discussion)
• Exact simulation of diffusions
• Fast simulation of new coins from old
• Iterating von Neumann's procedure for extracting random bits
• New coins from old: Computing with unknown bias
• Nonexistence of a class of variate generation schemes.
• Retrospective Markov chain Monte Carlo methods for Dirichlet process hierarchical models
• Retrospective exact simulation of diffusion sample paths with applications
• Stationarity detection in the initial transient problem
• Stochastic differential equations. An introduction with applications.
• Stochastic simulation: Algorithms and analysis
• The numerical solution of stochastic differential equations

Cited in

(16)

• Optimal linear Bernoulli factories for small mean problems
• On nonnegative unbiased estimators
• Bernoulli factories and duality in Wright-Fisher and Allen-Cahn models of population genetics
• From the Bernoulli factory to a dice enterprise via perfect sampling of Markov chains
• An asymptotically optimal Bernoulli factory for certain functions that can be expressed as power series
• Bayesian computation: a summary of the current state, and samples backwards and forwards
• Exact simulation for multivariate Itô diffusions
• Statistical inference for stochastic differential equations
• Exact Bayesian Inference for Diffusion-Driven Cox Processes
• Bernoulli factory: the \(2\mathtt{p}\)-coin problem
• The computational cost of blocking for sampling discretely observed diffusions
• Combinatorial Bernoulli factories
• Barker's algorithm for Bayesian inference with intractable likelihoods
• CLTs and asymptotic variance of time-sampled Markov chains
• Exact sampling for intractable probability distributions via a Bernoulli factory
• Nearly optimal Bernoulli factories for linear functions

This page was built for publication: Simulating events of unknown probabilities via reverse time martingales

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5198664)