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

DOI10.1002/RSA.10096zbMATH Open1042.65014arXivmath/0205164OpenAlexW2141869115MaRDI QIDQ4446872

Robert P. Dobrow, James Allen Fill

Publication date: 3 February 2004

Published in: Random Structures \& Algorithms (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/math/0205164

zbMATH Keywords

monotonicitypartially ordered setseparationexact samplingrejection samplingcoupling from the pastperfect simulationrunning timestrong stationary timemove-to-front ruleMarkov Chain Monte Carlo methodFill's algorithmPropp-Wilson algorithmFMMR algorithm

Mathematics Subject Classification ID

Computational methods in Markov chains (60J22) Sampling theory, sample surveys (62D05) Monte Carlo methods (65C05) Numerical analysis or methods applied to Markov chains (65C40)

Cites Work

• Inequalities: theory of majorization and its applications

Related Items (1)

Double Happiness: Enhancing the Coupled Gains of L-lag Coupling via Control Variates

Recommendations

• Title not available (Why is that?) 👍 👎
• Widening and clustering techniques allowing the use of monotone CFTP algorithm 👍 👎
• Stopping tests for Markov chain Monte-Carlo methods 👍 👎
• Improving Monte Carlo Efficiency by Increasing Variance 👍 👎
• On Exact Simulation of Markov Random Fields Using Coupling from the Past 👍 👎

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)