The double CFTP method
Luc Devroye, Lancelot F. James · ACM Transactions on Modeling and Computer Simulation · 2011
We consider the problem of the exact simulation of random variablesZthat satisfy the distributional identityZ=LVY+ (1-V)Z, whereV∈ [0,1] andYare independent, and =Ldenotes equality in distribution. Equivalently,Zis the limit of a Markov chain driven by that map. We give an algorithm that can be automated under the condition that we have a source capable of generating independent copies ofY, and thatVhas a density that can be evaluated in a black-box format. The method uses a doubling trick for inducing coalescence in coupling from the past. Applications include exact samplers for many Dirichlet means, some two-parameter Poisson--Dirichlet means, and a host of other distributions related to occupation times of Bessel bridges that can be described by stochastic fixed point equations.