Speeding up the FMMR perfect sampling algorithm: A case study revisited
In the Markov chain Monte Carlo method one is interested in obtaining a sample from a distribution \(\pi \) from which it is computationally difficult to simulate directly. One constructs a Markov chain whose stationary distribution is \(\pi \) and after running the chain ``a long time takes an outcome as an observation from \(\pi \). There are two algorithms based on different ideas: coupling from the past (CFTP) and the rejection sampling (FMMR). These two algorithms were compared in a case study the move-to-front (MTF) self-organizing list chain by \textit{J. A. Fill} [Probab. Eng. Inf. Sci. 12, 283--302 (1998; Zbl 0978.62013)]. The present paper gives a stochastic monotonicity result for the running time of FMMR applied to MTF and identifies the initial state which gives the stochastically smallest running time. It turns out that in case of optimal initial state the worst-case running time for FMMR equals the best-case running time for CFTP. The goal is to illustrate how the good choice of starting state for FMMR can improve its performance. One recommands to experiment with a wide variety of initial states before carrying out the bulk of simulations.
- Widening and clustering techniques allowing the use of monotone CFTP algorithm
- On Exact Simulation of Markov Random Fields Using Coupling from the Past
- scientific article; zbMATH DE number 1559585
- Stopping tests for Markov chain Monte-Carlo methods
- Improving Monte Carlo Efficiency by Increasing Variance
This page was built for publication: Speeding up the FMMR perfect sampling algorithm: A case study revisited
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4446872)