Hostname: page-component-586b7cd67f-dsjbd Total loading time: 0 Render date: 2024-11-21T23:49:46.828Z Has data issue: false hasContentIssue false
  • English
  • Français

Improved Bounds for Mixing Rates of Markov Chains and Multicommodity Flow

Published online by Cambridge University Press:  12 September 2008

Alistair Sinclair
Alistair Sinclair
Affiliation:
Department of Computer Science, University of Edinburgh, The King's Buildings, Edinburgh EH9 3JZ, Scotland
Get access Rights & Permissions [Opens in a new window]

Abstract

The paper is concerned with tools for the quantitative analysis of finite Markov chains whose states are combinatorial structures. Chains of this kind have algorithmic applications in many areas, including random sampling, approximate counting, statistical physics and combinatorial optimisation. The efficiency of the resulting algorithms depends crucially on the mixing rate of the chain, i.e., the time taken for it to reach its stationary or equilibrium distribution.

The paper presents a new upper bound on the mixing rate, based on the solution to a multicommodity flow problem in the Markov chain viewed as a graph. The bound gives sharper estimates for the mixing rate of several important complex Markov chains. As a result, improved bounds are obtained for the runtimes of randomised approximation algorithms for various problems, including computing the permanent of a 0–1 matrix, counting matchings in graphs, and computing the partition function of a ferromagnetic Ising system. Moreover, solutions to the multicommodity flow problem are shown to capture the mixing rate quite closely: thus, under fairly general conditions, a Markov chain is rapidly mixing if and only if it supports a flow of low cost.

Type
Research Article
Information
Combinatorics, Probability and Computing , Volume 1 , Issue 4 , December 1992 , pp. 351 - 370
Copyright
Copyright © Cambridge University Press 1992

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. (1982) Some inequalities for reversible Markov chains. Journal of the London Mathematical Society (2) 25 564–576.CrossRefGoogle Scholar
[2]Aldous, D. (1987) On the Markov chain simulation method for uniform combinatorial distributions and simulated annealing. Probability in the Engineering and Informational Sciences 1 33–46.CrossRefGoogle Scholar
[3]Alon, N. (1986) Eigenvalues and expanders. Combinatorica 6 83–96.CrossRefGoogle Scholar
[4]Alon, N. and Milman, V. D. (1985) λ1, isoperimetric inequalities for graphs and superconcentrators. Journal of Combinatorial Theory Series B 38 73–88.CrossRefGoogle Scholar
[5]Broder, A. Z. (1986) How hard is it to marry at random? (On the approximation of the permanent). Proceedings of the 18th ACM Symposium on Theory of Computing, 50–58. Erratum in Proceedings of the 20th ACM Symposium on Theory of Computing (1988) 551.CrossRefGoogle Scholar
[6]Dagum, P., Luby, M., Mihail, M. and Vazirani, U. V. (1988) Polytopes, permanents and graphs with large factors. Proceedings of the 29th IEEE Symposium on Foundations of Computer Science 412–421.CrossRefGoogle Scholar
[7]Diaconis, P. (1988) Group representations in probability and statistics, Lecture Notes Monograph Series Vol. 11, Institute of Mathematical Statistics, Hayward, California.CrossRefGoogle Scholar
[8]Diaconis, P., and Stroock, D. (1991) Geometric bounds for eigenvalues of Markov chains. Annals of Applied Probability 1 36–61.CrossRefGoogle Scholar
[9]Dyer, M., Frieze, A. and Kannan, R. (1989) A random polynomial time algorithm for approximating the volume of convex bodies. Proceedings of the 21st ACM Symposium on Theory of Computing 375–381.CrossRefGoogle Scholar
[10]Fill, J. Unpublished manuscript.Google Scholar
[11]Jerrum, M. R. and Sinclair, A. J. (1989) Approximating the permanent. SIAM Journal on Computing 18 1149–1178.CrossRefGoogle Scholar
[12]Jerrum, M. R. and Sinclair, A. J. (1990) Fast Uniform Generation of Regular Graphs. Theoretical Computer Science 73 91–100.CrossRefGoogle Scholar
[13]Jerrum, M. R. and Sinclair, A. J. (1993) Polynomial-time approximation algorithms for the Ising model, Technical Report CSR-1–90, Dept. of Computer Science, University of Edinburgh. (To appear in SIAM Journal on Computing, August 1993; Extended Abstract in Proceedings of the 17th International Colloquium on Automata, Languages and Programming (1990). Springer LNCS 443 462–475.)Google Scholar
[14]Karzanov, A. and Khachiyan, L. (1990) On the conductance of order Markov chains, Technical Report DCS 268, Rutgers University.Google Scholar
[15]Keilson, J. (1979) Markov chain models – rarity and exponentiality, Springer-Verlag, New York.CrossRefGoogle Scholar
[16]Lawler, G. F. and Sokal, A. D. (1988) Bounds on the L 2 spectrum for Markov chains and Markov processes: a generalization of Cheeger's inequality. Transactions of the American Mathematical Society 309 557–580.Google Scholar
[17]Leighton, T. and Rao, S. (1988) An approximate max-flow min-cut theorem for uniform multicommodity flow problems with applications to approximation algorithms. Proceedings of the 29th IEEE Symposium on Foundations of Computer Science 422–431.CrossRefGoogle Scholar
[18]Matula, D. W. and Shahrokhi, F. (1990) Sparsest cuts and bottlenecks in graphs. Discrete Applied Mathematics 27 113–123.CrossRefGoogle Scholar
[19]Mihail, M. (1989) Conductance and convergence of Markov chains: a combinatorial treatment of expanders. Proceedings of the 30th IEEE Symposium on Foundations of Computer Science 526–531.CrossRefGoogle Scholar
[20]Mihail, M. and Winkler, P. (1992) On the number of Eulerian orientations of a graph. Proceedings of the 3rd ACM-SIAM Symposium on Discrete Algorithms 138–145.Google Scholar
[21]Mohar, B. (1989) Isoperimetric numbers of graphs. Journal of Combinatorial Theory, Series B 47 274–291.CrossRefGoogle Scholar
[22]Shahrokhi, F. and Matula, D. W. (1990) The maximum concurrent flow problem. Journal of the ACM 37 318–334.CrossRefGoogle Scholar
[23]Sinclair, A. J. (1988) Algorithms for random generation and counting: a Markov chain approach, PhD Thesis, University of Edinburgh. (Revised version appeared as a monograph in the series Progress in Theoretical Computer Science, Birkhäuser, Boston, 1992.)CrossRefGoogle Scholar
[24]Sinclair, A. J. and Jerrum, M. R. (1989) Approximate counting, uniform generation and rapidly mixing Markov chains. Information and Computation 82 93–133.CrossRefGoogle Scholar