Speeding up the FMMR perfect sampling algorithm: A case study revisited

From MaRDI portal



Abstract: In a previous paper by the second author,two Markov chain Monte Carlo perfect sampling algorithms -- one called coupling from the past (CFTP) and the other (FMMR) based on rejection sampling -- are compared using as a case study the move-to-front (MTF) self-organizing list chain. Here we revisit that case study and, in particular, exploit the dependence of FMMR on the user-chosen initial state. We give a stochastic monotonicity result for the running time of FMMR applied to MTF and thus identify the initial state that gives the stochastically smallest running time; by contrast, the initial state used in the previous study gives the stochastically largest running time. By changing from worst choice to best choice of initial state we achieve remarkable speedup of FMMR for MTF; for example, we reduce the running time (as measured in Markov chain steps) from exponential in the length n of the list nearly down to n when the items in the list are requested according to a geometric distribution. For this same example, the running time for CFTP grows exponentially in n.


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.











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)