Name
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, tile running time for CFTP grows exponentially in n. |
Year | DOI | Venue |
|---|---|---|
2003 | 10.1002/rsa.10096 | Random Struct. Algorithms |
Keywords | Field | DocType |
exact sampling,markov chain monte carlo,best choice,case study,markov chain step,. perfect simulation,previous study,self-organizing list chain,rejection sampling,strong stationary time,propp{wilson algorithm,markov chain,running time,monotonicity,coupling from the past,initial state,separation,length n,perfect sampling algorithm,fmmr perfect sampling algorithm,fmmr algorithm,fill's algorithm,user-chosen initial state,par- tially ordered set.,move-to-front rule,partially ordered set,self organization,geometric distribution | Rejection sampling,Monotonic function,Combinatorics,Exponential function,Markov chain Monte Carlo,Coupling from the past,Markov chain,Algorithm,Geometric distribution,Mathematics,Speedup | Journal |
Volume | Issue | ISSN |
23 | 4 | 1042-9832 |
Citations | PageRank | References |
0 | 0.34 | 7 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robert P. Dobrow | 1 | 35 | 5.28 |
| James Allen Fill | 2 | 253 | 40.88 |