More Web Proxy on the site http://driver.im/

research-article

Rapidly Mixing Markov Chains with Applications in Computer Science and Physics

Author:

Dana RandallAuthors Info & Claims

Computing in Science and Engineering, Volume 8, Issue 2

Pages 30 - 41

https://doi.org/10.1109/MCSE.2006.30

Published: 01 March 2006 Publication History

Abstract

Monte Carlo algorithms often depend on Markov chains to sample from very large data sets. A key ingredient in the design of an efficient Markov chain is determining rigorous bounds on how quickly the chain "mixes," or converges, to its stationary distribution. This survey provides an overview of several useful techniques.

References

[1]

M.R. Jerrum and A.J. Sinclair, "The Markov Chain Monte Carlo Method: An Approach to Approximate Counting and Integration," Approximation Algorithms for NP-Hard Problems, D.S. Hochbaum, ed., PWS Publishing, 1997, pp. 482–520.

Digital Library

[2]

R. Kannan, "Markov Chains and Polynomial Time Algorithms," Proc. 35th IEEE Symp. Foundations of Computer Science, IEEE CS Press, 1994, pp. 656–671.

[3]

L. Lovász and P. Winkler, "Mixing Times," Microsurveys in Discrete Probability, vol. 41, DIMACS Series in Discrete Mathematical and Theoretical Computer Science, D. Aldous and J. Propp, eds., Am. Mathematical Soc., 1998, pp. 85–134.

[4]

A.J. Sinclair, "Convergence Rates for Monte Carlo Experiments," Numerical Methods for Polymeric Systems, S.G. Whittington, ed., IMA Volumes in Mathematics and Its Applications, Am. Mathematical Soc., 1997, pp. 1–18.

[5]

M.E. Dyer, A. Frieze, and R. Kannan, "A Random Polynomial Time Algorithm for Approximating the Volume of a Convex Body," Proc. 24th ACM Symp. Theory of Computing, ACM Press, 1992, pp. 26–38.

[6]

A.J. Sinclair, Algorithms for Random Generation and Counting: A Markov Chain Approach, Birkhauser, 1993.

Digital Library

[7]

M.R. Jerrum, A.J. Sinclair, and E. Vigoda, "A Polynomial-Time Approximation Algorithm for the Permanent of a Matrix with Non-Negative Entries," Proc. 33rd ACM Symp. Theory of Computing, ACM Press, 2001, pp. 712–721.

Digital Library

[8]

Theoretical Computer Science, vol. 8, 1979, pp. 189–201.

[9]

Theoretical Computer Science, vol. 43, 1986, pp. 169–188.

[10]

J. Mathematical Physics, vol. 4, 1963, pp. 294–307.

[11]

J. Chemical Physics, vol. 21, 1953, pp. 1087–1092.

[12]

Computing in Science & Eng., vol. 2, no. 1, 2000, pp. 65–69.

Digital Library

[13]

D. Aldous and J. Fill, "Reversible Markov Chains and Random Walks on Graphs," in preparation, 2005;

[14]

A. Broder, "Generating Random Spanning Trees," Proc. 30th IEEE Symp. Foundations of Computer Science, IEEE CS Press, 1989, pp. 442–447.

[15]

D. Aldous, "Random Walks on Finite Groups and Rapidly Mixing Markov Chains," Seminaire de Probabilites XVII, Lecture Notes in Mathematics, vol. 986, 1981/82, pp. 243–297.

[16]

R. Bubley and M. Dyer, "Faster Random Generation of Linear Extensions," Discrete Mathematics, vol. 201, 1999, pp. 81–88.

Digital Library

[17]

M. Dyer and C. Greenhill, "A More Rapidly Mixing Markov Chain for Graph Colorings," Random Structures and Algorithms, vol. 13, 1998, pp. 285–317.

Digital Library

[18]

M.R. Jerrum, "A Very Simple Algorithm for Estimating the Number of k-Colorings of a Low-Degree Graph," Random Structures and Algorithms, vol. 7, 1995, pp. 157–165.

[19]

M. Luby, D. Randall, and A.J. Sinclair, "Markov Chains for Planar Lattice Structures," SIAM J. Computing, vol. 31, 2001, pp. 167–192.

Digital Library

[20]

M.E. Dyer and A. Frieze, "Randomly Colouring Graphs with Lower Bounds on Girth and Maximum Degree," Proc. 42nd Symp. Foundations of Computer Science, 2001, pp. 579–587.

Digital Library

[21]

M.E. Dyer et al., "An Extension of Path Coupling and Its Application to the Glauber Dynamics for Graph Colorings," SIAM J. Computing, vol. 30, 2001, pp. 1962–1975.

Digital Library

[22]

M. Molloy, "The Glauber Dynamics on Colorings of a Graph with High Girth and Maximum Degree," Proc. 34th ACM Symp. Theory of Computing, ACM Press, 2002, pp. 91–98.

Digital Library

[23]

T.P. Hayes and E. Vigoda, "A Non-Markovian Coupling for Randomly Sampling Colorings," Proc. 44th IEEE Symp. Foundations of Computing, IEEE Press, 2003.

Digital Library

[24]

Information and Computation, vol. 82, 1989, pp. 93–133.

[25]

A.J. Sinclair, "Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow," Combinatorics, Probability and Computing, vol. 1, 1992, pp. 351–370.

[26]

P. Diaconis and L. Saloff-Coste, "Comparison Theorems for Reversible Markov Chains," Annals of Applied Probability, vol. 3, 1993, pp. 696–730.

[27]

D. Randall and P. Tetali, "Analyzing Glauber Dynamics by Comparison of Markov Chains," J. Mathematical Physics, vol41, 2000, pp. 1598–1615.

[28]

N. Madras and D. Randall, "Markov Chain Decomposition for Convergence Rate Analysis," Annals of Applied Probability, vol. 12, 2002, pp. 581–606.

[29]

R.A. Martin and D. Randall, "Sampling Adsorbing Staircase Walks Using a New Markov Chain Decomposition Method," Proc. 41st IEEE Symp. Foundations of Computer Science, IEEE CS Press, 2000, pp. 492–502.

Digital Library

[30]

M.R. Jerrum et al., "Elementary Bounds on Poincaré and Log-Sobolev Constants for Decomposable Markov Chains," Annals of Applied Probability, 2004, pp. 1741–1765.

[31]

C. Cooper et al., "Mixing Properties of the Swendsen-Wang Process on the Complete Graph and Narrow Grids," J. Mathematical Physics, vol. 41, 2000, pp. 1499–1527.

[32]

D. Randall, "Decomposition Methods and Sampling Circuits in the Cartesian Lattice," Proc. 5th Symp. Mathematical Foundations of Computer Science, LNCS 1256, J. Sgall, A. Pultr, and P. Kolman, eds., Springer-Verlag, 2001, pp. 72–84.

Digital Library

[33]

M.R. Jerrum and A.J. Sinclair, "Polynomial-Time Approximation Algorithms for the Ising Model," SIAM J. Computing, vol. 22, 1993, pp. 1087–1116.

Digital Library

[34]

D. Randall and D.B. Wilson, "Sampling Spin Configurations of an Ising System," Proc. 10th ACM/SIAM Symp. Discrete Algorithms, ACM Press, 1999, pp. 959–960.

Digital Library

Cited By

Zhang YBucklew MElkind E(2023)Max Markov chainProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/639(5758-5767)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/639
Ghosh S(2023)Cutoff phenomenon for the warp-transpose top with random shuffleJournal of Algebraic Combinatorics: An International Journal10.1007/s10801-023-01271-158:3(775-809)Online publication date: 29-Sep-2023
https://dl.acm.org/doi/10.1007/s10801-023-01271-1
Chang HLee CLuo ZSang HZhou QKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Rapidly mixing multiple-try metropolis algorithms for model selection problemsProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3602144(25842-25855)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3602144
Show More Cited By

Index Terms

Recommendations

A Randomized Quasi-Monte Carlo Simulation Method for Markov Chains

We introduce and study a randomized quasi-Monte Carlo method for the simulation of Markov chains up to a random (and possibly unbounded) stopping time. The method simulates n copies of the chain in parallel, using a (d+1)-dimensional, highly uniform ...
Deterministic Random Walks for Rapidly Mixing Chains

The rotor-router model is a deterministic process analogous to a simple random walk on a graph, and the discrepancy of token configurations between the rotor-router model and its corresponding random walk has been investigated in some contexts. Motivated by ...
Rapidly Mixing Markov Chains for Sampling Contingency Tables with a Constant Number of Rows
FOCS '02: Proceedings of the 43rd Symposium on Foundations of Computer Science

We consider the problem of sampling almost uniformly from the set of contingency tables with given row and column sums, when the number of rows is a constant. Cryan and Dyer [3] have recently given a fully polynomial randomized approximation scheme (...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Computing in Science and Engineering

Computing in Science and Engineering Volume 8, Issue 2

March 2006

87 pages

ISSN:1521-9615

Issue’s Table of Contents

Copyright © 2006.

Publisher

IEEE Educational Activities Department

United States

Publication History

Published: 01 March 2006

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

15
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Zhang YBucklew MElkind E(2023)Max Markov chainProceedings of the Thirty-Second International Joint Conference on Artificial Intelligence10.24963/ijcai.2023/639(5758-5767)Online publication date: 19-Aug-2023
https://dl.acm.org/doi/10.24963/ijcai.2023/639
Ghosh S(2023)Cutoff phenomenon for the warp-transpose top with random shuffleJournal of Algebraic Combinatorics: An International Journal10.1007/s10801-023-01271-158:3(775-809)Online publication date: 29-Sep-2023
https://dl.acm.org/doi/10.1007/s10801-023-01271-1
Chang HLee CLuo ZSang HZhou QKoyejo SMohamed SAgarwal ABelgrave DCho KOh A(2022)Rapidly mixing multiple-try metropolis algorithms for model selection problemsProceedings of the 36th International Conference on Neural Information Processing Systems10.5555/3600270.3602144(25842-25855)Online publication date: 28-Nov-2022
https://dl.acm.org/doi/10.5555/3600270.3602144
Zhou LJia CZhang J(2020)Information-aware Message Passing Neural Networks for Graph Node ClassificationProceedings of the 2020 3rd International Conference on Signal Processing and Machine Learning10.1145/3432291.3432294(68-72)Online publication date: 22-Oct-2020
https://dl.acm.org/doi/10.1145/3432291.3432294
Wang ZLing C(2019)Lattice Gaussian Sampling by Markov Chain Monte CarloIEEE Transactions on Information Theory10.1109/TIT.2019.290149765:6(3630-3645)Online publication date: 1-Jun-2019
https://dl.acm.org/doi/10.1109/TIT.2019.2901497
Wang ZLing C(2018)On the Geometric Ergodicity of Metropolis-Hastings Algorithms for Lattice Gaussian SamplingIEEE Transactions on Information Theory10.1109/TIT.2017.274250964:2(738-751)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1109/TIT.2017.2742509
Abbas HFainekos GSankaranarayanan SIvančić FGupta A(2013)Probabilistic Temporal Logic Falsification of Cyber-Physical SystemsACM Transactions on Embedded Computing Systems10.1145/2465787.246579712:2s(1-30)Online publication date: 1-May-2013
https://dl.acm.org/doi/10.1145/2465787.2465797
Ghaderi JSrikant R(2013)The impact of access probabilities on the delay performance of Q-CSMA algorithms in wireless networksIEEE/ACM Transactions on Networking10.1109/TNET.2012.221596421:4(1063-1075)Online publication date: 1-Aug-2013
https://dl.acm.org/doi/10.1109/TNET.2012.2215964
Bordewich MKang R(2011)Rapid mixing of subset Glauber dynamics on graphs of bounded tree-widthProceedings of the 38th international colloquim conference on Automata, languages and programming - Volume Part I10.5555/2027127.2027184(533-544)Online publication date: 4-Jul-2011
https://dl.acm.org/doi/10.5555/2027127.2027184
Vandin FUpfal ERaphael B(2011)De novo discovery of mutated driver pathways in cancerProceedings of the 15th Annual international conference on Research in computational molecular biology10.5555/1987587.1987631(499-500)Online publication date: 28-Mar-2011
https://dl.acm.org/doi/10.5555/1987587.1987631
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents