×

Simulating events of unknown probabilities via reverse time martingales. (English) Zbl 1236.60044

A framework for simulating events of unknown probabilities is developed in the paper. The proposed approach is based on random sequences. Two specific examples are considered. The first is concerned with the exact simulation of non-linear diffusions. A general framework and algorithms for the solution for this kind of problem are presented. A reverse time martingale/unbiased estimator formulation of the Nacu-Peres algorithm which gives a new perspective on the Bernoulli factory problem is presented. The authors identify the coefficients of the lower and upper polynomial envelopes as random variables of desired properties and implementing the algorithm using a single \(U(0,1)\)-auxiliary random variable. They do not need to identify subsets of \([0,1]\) strings and thus avoid algorithmic difficulties of the original version. The martingale approach also simplifies the proof of validity of the Nacu-Peres algorithm. In the special case when \(f(p)\) has an alternating series expansion with decreasing coefficients, the martingale approach results in new, very efficient algorithms. In particular they can be used to obtain unbiased sequential estimators of a parameter of interest that is not necessarily in \([0, 1]\). The second example is concerned with the well-known Bernoulli factory problem of obtaining an \(f(p)\)-coin given a sequence \(X_i\), \(i=1,2,\dots\) of independent tosses of a \(p\)-coin (with known \(f\) and unknown \(p\)). The authors are deriving the exact algorithm for diffusions as a specific application of the Bernoulli factory for alternating series expansions. The here developed algorithms are straightforward to implement and thus allow for effective simulation of desired events of probability. These results are linked to existence and construction of unbiased estimators.

MSC:

60G42 Martingales with discrete parameter
65C60 Computational problems in statistics (MSC2010)
PDFBibTeX XMLCite
Full Text: DOI arXiv Link

References:

[1] Assmussen, Stationarity detection in the initial transient problem, ACM Trans Model Comput Simul 2 pp 130– (1992) · Zbl 0842.68106
[2] Asmussen, Stochastic simulation: Algorithms and analysis (2007) · Zbl 1126.65001
[3] Beskos, Exact simulation of diffusions, Ann Appl Probab 15 pp 2422– (2005) · Zbl 1101.60060
[4] Beskos, Retrospective exact simulation of diffusion sample paths with applications, Bernoulli 12 pp 1077– (2006) · Zbl 1129.60073
[5] Beskos, A factorisation of diffusion measure and finite sample path constructions, Methodol Comput Appl Probab 10 pp 85– (2008) · Zbl 1152.65013
[6] Beskos, Exact and computationally efficient likelihood-based estimation for discreetly observed diffusion processes (with discussion), J Royal Stat Soc B 68 pp 333– (2006) · Zbl 1100.62079
[7] Devroye, Non-uniform random variable generation (1986)
[8] Henderson, Non-existence of a class of variate generation schemes, Oper Res Lett 31 pp 83– (2003) · Zbl 1034.65002
[9] Holtz, New coins from old, smoothly, ArXiv e-prints (2010)
[10] Keane, A Bernoulli factory, ACM Trans Model Comput Simul (TOMACS) 4 pp 213– (1994) · Zbl 0844.60008
[11] Kloeden, Numerical solution of stochastic differential equations (1992) · Zbl 0359.60081
[12] Mossel, New coins from old: Computing with unknown bias, Combinatorica 25 pp 707– (2005) · Zbl 1099.68052
[13] Nacu, Fast simulation of new coins from old, Ann Appl Probab 15 pp 93– (2005) · Zbl 1072.65007
[14] Øksendal, Stochastic differential equations: An introduction with applications (1998) · Zbl 0897.60056
[15] Papaspiliopoulos, Retrospective Markov chain Monte Carlo for Dirichlet process hierarchical models, Biometrika 95 pp 169– (2008) · Zbl 1437.62576
[16] Peres, Iterating von Neumann’s procedure for extracting random bits, Ann Stat 20 pp 590– (1992) · Zbl 0754.60040
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.