Hostname: page-component-586b7cd67f-g8jcs Total loading time: 0 Render date: 2024-11-28T17:24:02.744Z Has data issue: false hasContentIssue false
  • English
  • Français

The Move-to-Front Rule: A Case Study for two Perfect Sampling Algorithms

Published online by Cambridge University Press:  27 July 2009

James Allen Fill
James Allen Fill
Affiliation:
Department of Mathematical Sciences, The Johns Hopkins University, Baltimore, Maryland 21218–2682
Get access Rights & Permissions [Opens in a new window]

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.

Type
Research Article
Information
Probability in the Engineering and Informational Sciences , Volume 12 , Issue 3 , July 1998 , pp. 283 - 302
Copyright
Copyright © Cambridge University Press 1998

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

1.Aldous, D. & Diaconis, P. (1986). Shuffling cards and stopping times. American Mathematical Monthly 93: 333–348.CrossRefGoogle Scholar
2.Aldous, D. & Diaconis, P. (1987). Strong uniform times and finite random walks. Advances in Applied Mathematics 8: 69–97.CrossRefGoogle Scholar
3.Aldous, D. & Fill, J.A. (1998). Reversible Markov chains and random walks on graphs. (Book in preparation. First draft of manuscript available via http://stat-www.berkeley.edu/users/aldous.)Google Scholar
4.Björner, A. (1984). Orderings of Coxeter groups. In Contemporary mathematics. Vol. 34: Combinatorics and algebra. Providence, RI: American Mathematical Society, pp. 175–195.Google Scholar
5.Diaconis, P. (1988). Group representations in probability and statistics. Hayward, CA: Institute of Mathematical Statistics.CrossRefGoogle Scholar
6.Diaconis, P. (1993). Analysis of some weighted mixing schemes. [Unpublished manuscript]Google Scholar
7.Diaconis, P. & Fill, J.A. (1990). Strong stationary times via a new form of duality. Annals of Probability 18: 1483–1522.CrossRefGoogle Scholar
8.Diaconis, P., Fill, J.A., & Pitman, J. (1992). Analysis of top to random shuffles. Combinatorics, Probability & Computing 1: 135–155.CrossRefGoogle Scholar
9.Fagin, R. & Price, T.G. (1978). Efficient calculation of expected miss ratios in the independent reference model. SIAM Journal of Computing 7: 288–297.CrossRefGoogle Scholar
10.Fill, J.A. (1996). An exact formula for the move-to-front rule for self-organizing lists. Journal of Theoretical Probability 9: 113–160.CrossRefGoogle Scholar
11.Fill, J.A. (1997). Limits and rates of convergence for the distribution of search cost under the move-to-front rule. Theoretical Computer Science 164 (1996): 185–206.CrossRefGoogle Scholar
12.Fill, J.A. (1998). An interruptible algorithm for perfect sampling via Markov chains. Annals of Applied Probability 1.Google Scholar
13.Fill, J.A. and Hoist, L. (1996). On the distribution of search cost for the move-to-front rule. Random Structures and Algorithms 8: 179–186.3.0.CO;2-V>CrossRefGoogle Scholar
14.Fill, J.A. and Machida, M. (1996). Duality relations for Markov chains on partially ordered state spaces. [Unpublished notes.]Google Scholar
15.Hendricks, W.J. (1972). The stationary distribution of an interesting Markov chain. Journal of Applied Probability 9: 231–233.CrossRefGoogle Scholar
16.Hildebrand, M.V. (1993). The birthday problem (a notice). American Mathematical Monthly 100: 643.Google Scholar
17.Holst, L. (1995). The general birthday problem. Random Structures and Algorithms 6: 201–208.CrossRefGoogle Scholar
18.Knuth, D.E. (1981). The art of computer programming. Vol. 2: Seminumerical algorithms. Reading, MA: Addison-Wesley.Google Scholar
19.Marshall, A.W. & Olkin, I. (1979). Inequalities: Theory of majorization and its applications. New York: Academic Press.Google Scholar
20.Propp, J.G. & Wilson, D.B. (1996). Exact sampling with coupled Markov chains and applications to statistical mechanics. Random Structures and Algorithms 9: 223–252.3.0.CO;2-O>CrossRefGoogle Scholar
21.Wong, C.K. & Easton, M.C. (1980). An efficient method for weighted sampling without replacement. SIAM Journal of Computing 9: 111–113.CrossRefGoogle Scholar