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

DOI10.1017/S0269964800005192zbMath0978.62013MaRDI QIDQ4950714

James Allen Fill

Publication date: 4 February 2002

Published in: Probability in the Engineering and Informational Sciences (Search for Journal in Brave)

zbMATH Keywords

Markov chain Monte Carlofinite populationtime reversalmixing timesexhaustively sampling

Mathematics Subject Classification ID

Sampling theory, sample surveys (62D05) Numerical analysis or methods applied to Markov chains (65C40)

Related Items

A short history of Markov chain Monte Carlo: Subjective recollections from incomplete data ⋮ Unnamed Item ⋮ An interruptible algorithm for perfect sampling via Markov chains

Cites Work

• Unnamed Item
• Limits and rates of convergence for the distribution of search cost under the move-to-front rule
• Strong stationary times via a new form of duality
• Strong uniform times and finite random walks
• An exact formula for the move-to-front rule for self-organizing lists
• Shuffling Cards and Stopping Times
• An Efficient Method for Weighted Sampling without Replacement
• Efficient Calculation of Expected Miss Ratios in the Independent Reference Model
• Analysis of Top To Random Shuffles
• The general birthday problem
• The stationary distribution of an interesting Markov chain
• Inequalities: theory of majorization and its applications