Hostname: page-component-78c5997874-t5tsf Total loading time: 0 Render date: 2024-11-15T19:40:39.819Z 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)
Get access Rights & Permissions [Opens in a new window]

Abstract

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 (). 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).

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

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. 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