Simulating events of unknown probabilities via reverse time martingales

DOI10.1002/RSA.20333zbMATH Open1236.60044arXiv0907.4018OpenAlexW2142828514MaRDI QIDQ5198664FDOQ5198664

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)

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.

Full work available at URL: https://arxiv.org/abs/0907.4018

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

zbMATH Keywords

computational problems in statisticsretrospective samplingBernoulli factorymartingales with discrete parameterunbiased simulation

Mathematics Subject Classification ID

Martingales with discrete parameter (60G42)

Cites Work

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

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
• Statistical inference for stochastic differential equations
• Exact simulation for multivariate Itô diffusions
• 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
• Nearly optimal Bernoulli factories for linear functions
• CLTs and asymptotic variance of time-sampled Markov chains
• Exact sampling for intractable probability distributions via a Bernoulli factory

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)