Perfect simulation with exponential tails on the running time |
| |
Authors: | Mark Huber |
| |
Affiliation: | Department of Mathematics and ISDS, Duke University, Durham, NC 27713 |
| |
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. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 |
| |
Keywords: | Monte Carlo perfect simulation coupling from the past noninterruptible algorithms |
|
|