Hostname: page-component-74656f9884-8r8nv Total loading time: 0 Render date: 2026-11-07T10:10:31.858Z Has data issue: false hasContentIssue false
  • English
  • Français

Long-Range Percolation Mixing Time

Published online by Cambridge University Press:  01 July 2008

ITAI BENJAMINI ,
NOAM BERGER  and
ARIEL YADIN
ITAI BENJAMINI
Affiliation:
Weizmann Institute of Science, Rehovot 76100, Israel (e-mail: itai.benjamini@weizmann.ac.il, ariel.yadin@weizmann.ac.il)
NOAM BERGER
Affiliation:
Mathematics Department, UCLA, Los Angeles, CA 90095-1555, USA (e-mail: berger@math.ucla.edu)
ARIEL YADIN
Affiliation:
Weizmann Institute of Science, Rehovot 76100, Israel (e-mail: itai.benjamini@weizmann.ac.il, ariel.yadin@weizmann.ac.il)
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 provide an estimate, sharp up to poly-logarithmic factors, of the asymptotic almost sure mixing time of the graph created by long-range percolation on the cycle of length N ($\Integer/N\Integer$). While it is known that the asymptotic almost sure diameter drops from linear to poly-logarithmic as the exponent s decreases below 2 [4, 9], the asymptotic almost sure mixing time drops from N2 only to Ns-1 (up to poly-logarithmic factors).

Information

Type
Paper
Information
Combinatorics, Probability and Computing , Volume 17 , Issue 4 , July 2008 , pp. 487 - 494
Copyright
© Cambridge University Press 2008

References

[1]Aldous, D. and Fill, J. (2000) Reversible Markov Chains and Random Walks on Graphs. Book in preparation. www.stat.berkeley.edu/~aldous.Google Scholar
[2]Alon, N. (1997) On the edge expansion of graphs. Combin. Probab. Comput. 6 145–152.CrossRefGoogle Scholar
[3]Alon, N. and Spencer, J. H. (2000) The Probabilistic Method, Wiley.CrossRefGoogle Scholar
[4]Benjamini, I. and Berger, N. (2001) The diameter of long-range percolation clusters on finite cycles. Random Struct. Alg. 19 102–111. arXiv:math.PR/0012070CrossRefGoogle Scholar
[5]Benjamini, I., Kesten, H., Peres, Y. and Schramm, O. (2004) Geometry of the uniform spanning forest: Phase transitions in dimensions 4,8,12,. . .. Ann. of Math. 160 465–491.CrossRefGoogle Scholar
[6]Benjamini, I., Kozma, G. and Wormald, N. (2006) The mixing time of the giant component of a random graph. arXiv:math.PR/0610459.Google Scholar
[7]Benjamini, I., Lyons, R., Peres, Y. and Schramm, O. (2001) Uniform spanning forests. Ann. Probab. 29 1–65.CrossRefGoogle Scholar
[8]Benjamini, I. and Mossel, E. (2003) On the mixing time of a simple random walk on the super critical percolation cluster. Probab. Theory Rel. Fields 125 408–420.Google Scholar
[9]Biskup, M. (2004) On the scaling of the chemical distance in long-range percolation models. Ann. Probab. 32 2938–2977.CrossRefGoogle Scholar
[10]Biskup, M. Graph diameter in long-range percolation. Preprint. http://www.math.ucla.edu/~biskup.Google Scholar
[11]Diaconis, P. and Stroock, D. (1991) Geometric bounds for eigenvalues of Markov chains. Ann. Appl. Probab. 1 36–61.CrossRefGoogle Scholar
[12]Doyle, P. G. and Laurie Snell, J. (2000) Random Walks and Electric Networks, Carus Mathematical Monographs. arXiv:math.PR/0001057.Google Scholar
[13]Fountoulakis, N. and Reed, B. (2006) On the evolution of the mixing rate. arXiv:math.PR/0701474Google Scholar
[14]Kleinberg, J. (2006) Complex networks and decentralized search algorithms. To appear in Proc. International Congress of Mathematicians (ICM).Google Scholar
[15]Lyons, R. and Peres, Y. (2005) Probability on Trees and Networks. Book in preparation. http://mypage.iu.edu/~rdlyons/prbtree/prbtree.html.Google Scholar
[16]Mihail, M., Papadimitriou, C. H. and Saberi, A. (2003) On certain connectivity properties of the internet topology. In FOCS 2003. http://www.cs.berkeley.edu/~christos.Google Scholar
[17]Sinclair, A. (1992) Improved bounds for mixing rates of Markov chains and multicommodity flow. Combin. Probab. Comput. 1 351–370.Google Scholar