Long-Range Percolation Mixing Time

DOI10.1017/S0963548308008948MaRDI QIDQ3527537zbMATH OpenFDO

Authors Itai Benjamini, Noam Berger, Ariel Yadin

Publication date 29 September 2008

Published in Combinatorics, Probability and Computing (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0703872

zbMATH Keywords

random graphmixing timepercolation

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs arising in equilibrium statistical mechanics (82B20)

Abstract: We provide an estimate, sharp up to poly-logarithmic factors, of the asymptotically almost sure mixing time of the graph created by long-range percolation on the cycle of length N (Z/NZ). While it is known that the almost sure diameter drops from linear to poly-logarithmic as the exponent s decreases below 2, the almost sure mixing time drops from N^2 only to N^(s-1) (up to poly-logarithmic factors).

Recommendations

• The mixing time of a random walk on a long-range percolation cluster in pre-Sierpinski gasket
• Random walks on the random graph
• Critical random graphs: Diameter and mixing time
• Mixing time for the random walk on the range of the random walk on tori
• Random walks on dynamical percolation: mixing times, mean squared displacement and hitting times

Cites work

• Geometric bounds for eigenvalues of Markov chains
• On the Edge-Expansion of Graphs
• On the mixing time of a simple random walk on the super critical percolation cluster
• On the scaling of the chemical distance in long-range percolation models
• The diameter of long-range percolation clusters on finite cycles

Cited in

(14)

• Transience and anchored isoperimetric dimension of supercritical percolation clusters
• Simple random walk on long range percolation clusters. I: Heat kernel bounds
• Simple random walk on long-range percolation clusters. II: Scaling limits
• Scale-free percolation mixing time
• Multiple phase transitions in long-range first-passage percolation on square lattices
• Heat kernel estimates for strongly recurrent random walk on random media
• The diameter of a long-range percolation cluster on pre-Sierpinski gasket
• Mixing time for the random walk on the range of the random walk on tori
• Arithmetic oscillations of the chemical distance in long-range percolation on \(\mathbb{Z}^d\)
• Graph diameter in long-range percolation
• Recurrence and transience of symmetric random walks with long-range jumps
• The mixing time of a random walk on a long-range percolation cluster in pre-Sierpinski gasket
• Behavior of the distance exponent for \(\frac{1}{|x-y|^{2d}}\) long-range percolation
• Polynomial lower bound on the effective resistance for the one-dimensional critical long-range percolation

This page was built for publication: Long-Range Percolation Mixing Time

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3527537)