Hostname: page-component-745bb68f8f-mzp66 Total loading time: 0 Render date: 2025-02-06T22:19:29.502Z Has data issue: false hasContentIssue false
  • English
  • Français

Intersection Conductance and Canonical Alternating Paths: Methods for General Finite Markov Chains

Published online by Cambridge University Press:  13 June 2014

RAVI MONTENEGRO
RAVI MONTENEGRO*
Affiliation:
Department of Mathematical Sciences, University of Massachusetts Lowell, Lowell, MA 01854, USA (e-mail: ravi_montenegro@uml.edu)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

We extend the conductance and canonical paths methods to the setting of general finite Markov chains, including non-reversible non-lazy walks. The new path method is used to show that a known bound for the mixing time of a lazy walk on a Cayley graph with a symmetric generating set also applies to the non-lazy non-symmetric case, often even when there is no holding probability.

Keywords

60J10
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 23 , Issue 4 , July 2014 , pp. 585 - 606
Copyright
Copyright © Cambridge University Press 2014 

References

[1]Babai, L. (1991) Local expansion of vertex-transitive graphs and random generation in finite groups. Proc. 23rd Annual ACM Symposium on Theory of Computing: STOC 1991, pp. 164–174.CrossRefGoogle Scholar
[2]Diaconis, P. and Fill, J. (1990) Strong stationary times via a new form of duality. Ann. Probab. 18 1483–1522.Google Scholar
[3]Diaconis, P. and Saloff-Coste, L. (1993) Comparison theorems for reversible Markov chains. Ann. Appl. Probab. 3 696–730.Google Scholar
[4]Diaconis, P. and Stroock, D. (1991) Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probab. 1 36–61.Google Scholar
[5]Dyer, M., Goldberg, L., Jerrum, M. and Martin, R. (2006) Markov chain comparison. Probab. Surv. 3 89–111.Google Scholar
[6]Fill, J. (1991) Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process. Ann. Appl. Probab. 1 62–87.Google Scholar
[7]Greenhill, C. (2013) Making Markov chains less lazy. arXiv:1203.6668Google Scholar
[8]Jerrum, M. and Sinclair, A. (1988) Conductance and the rapid mixing property for Markov chains: The approximation of the permanent resolved. In Proc. 20th Annual ACM Symposium on Theory of Computing: STOC 1988, pp. 235–243.CrossRefGoogle Scholar
[9]Kannan, R., Lovász, L. and Montenegro, R. (2006) Blocking conductance and mixing in random walks. Combin. Probab. Comput. 15 541–570.CrossRefGoogle Scholar
[10]Lawler, G. and Sokal, A. (1988) Bounds on the l 2 spectrum for Markov chains and Markov processes: A generalization of Cheeger's inequality. Trans. Amer. Math. Soc. 309 557–580.Google Scholar
[11]Mihail, M. (1989) Conductance and convergence of Markov chains: A combinatorial treatment of expanders. In 30th Annual Symposium on Foundations of Computer Science, pp. 526–531.Google Scholar
[12]Montenegro, R. and Tetali, P. (2006) Mathematical Aspects of Mixing Times in Markov Chains, Vol. 1:3 of Foundations and Trends in Theoretical Computer Science, NOW Publishers.Google Scholar
[13]Morris, B. and Peres, Y. (2005) Evolving sets, mixing and heat kernel bounds. Probab. Theory Rel. Fields 133 245–266.Google Scholar
[14]Sinclair, A. (1992) Improved bounds for mixing rates of Markov chains and multicommodity flow. Combin. Probab. Comput. 1 351–370.CrossRefGoogle Scholar