The Move-to-Front Rule: A Case Study for two Perfect Sampling Algorithms
- 27 July 1998
- journal article
- research article
- Published by Cambridge University Press (CUP) in Probability in the Engineering and Informational Sciences
- Vol. 12 (3) , 283-302
- https://doi.org/10.1017/s0269964800005192
Abstract
The elementary problem of exhaustively sampling a finite population without replacement is used as a nonreversible test case for comparing two recently proposed MCMC algorithms for perfect sampling, one based on backward coupling and the other on strong stationary duality. The backward coupling algorithm runs faster in this case, but the duality-based algorithm is unbiased for user impatience. An interesting by-product of the analysis is a new and simple stochastic interpretation of a mixing-time result for the move-to-front rule.Keywords
This publication has 14 references indexed in Scilit:
- Limits and rates of convergence for the distribution of search cost under the move-to-front ruleTheoretical Computer Science, 1996
- Exact sampling with coupled Markov chains and applications to statistical mechanicsRandom Structures & Algorithms, 1996
- On the distribution of search cost for the move-to-front ruleRandom Structures & Algorithms, 1996
- An exact formula for the move-to-front rule for self-organizing listsJournal of Theoretical Probability, 1996
- The general birthday problemRandom Structures & Algorithms, 1995
- Analysis of Top To Random ShufflesCombinatorics, Probability and Computing, 1992
- Strong uniform times and finite random walksAdvances in Applied Mathematics, 1987
- Shuffling Cards and Stopping TimesThe American Mathematical Monthly, 1986
- Shuffling Cards and Stopping TimesThe American Mathematical Monthly, 1986
- Efficient Calculation of Expected Miss Ratios in the Independent Reference ModelSIAM Journal on Computing, 1978