Mark Huber Publications

Perfect simulation with exponential tails
M. Huber, Random Structures and Algorithms, vol. 33 no. 1 (August 2008), pp.2943.

Abstract: Monte Carlo algorithms typically need to generate random variates from a probability distribution described by an unnormalized density or probability mass function. Perfect simulation algorithms generate random variates exactly from these distributions, but have a running time T that is itself an unbounded random variable. This article shows that commonly used protocols for creating perfect simulation algorithms, such as Coupling From the Past can be used in such a fashion that the running time is unlikely to be very much larger than the expected running time.

Keywords: Monte Carlo; perfect simulation; coupling from the past; noninterruptible algorithms


This site supported by NSF CAREER grant DMS-05-48153. Last update: 04 December 2009. Note: All downloads provided solely for use within the restrictions of the Fair Use Act, and all copyrights remain with their respective owners.