K Latuszynski, I Kosmidis, O Papaspiliopoulos and GO Roberts
Simulating Events of Unknown Probabilities via Reverse Time Martingales
Date: June 2009
Abstract: Assume that one aims to simulate an event of unknown probabilitys 2 (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 (, , , , , and also  and ) 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  as a specific instance of the generic framework developed here. In the case of the Bernoulli factory, our work others a statistical understanding of the Nacu-Peres algorithm for f(p) = minf2p; 1 􀀀 2"g (which is central to the general question, c.f. ) and allows for its immediate implementation that avoids algorithmic diffculties 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.