Mixing time for random walk on supercritical dynamical percolation

DOI10.1007/S00440-019-00927-ZzbMATH Open1444.60084arXiv1707.07632OpenAlexW2964303558MaRDI QIDQ2174662FDOQ2174662

Authors: Yuval Peres, Perla Sousi, Jeffrey E. Steif 

Publication date: 21 April 2020

Published in: Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete (Search for Journal in Brave)

Abstract: We consider dynamical percolation on the $d$-dimensional discrete torus of side length $n$, $mathbb{Z}_n^d$, where each edge refreshes its status at rate $mu=m{u}_{n}le1/2$ to be open with probability $p$. We study random walk on the torus, where the walker moves at rate $1/(2d)$ along each open edge. In earlier work of two of the authors with A. Stauffer, it was shown that in the subcritical case $p<p_c(mathbb{Z}^d)$, the (annealed) mixing time of the walk is $Theta(n^2/mu)$, and it was conjectured that in the supercritical case $p>p_c(mathbb{Z}^d)$, the mixing time is $Theta(n^2+1/mu)$; here the implied constants depend only on $d$ and $p$. We prove a quenched (and hence annealed) version of this conjecture up to a poly-logarithmic factor under the assumption $heta(p)>1/2$. Our proof is based on percolation results (e.g., the Grimmett-Marstrand Theorem) and an analysis of the volume-biased evolving set process; the key point is that typically, the evolving set has a substantial intersection with the giant percolation cluster at many times. This allows us to use precise isoperimetric properties of the cluster (due to G. Pete) to infer rapid growth of the evolving set, which in turn yields the upper bound on the mixing time.

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

Recommendations

• On the mixing time of a simple random walk on the super critical percolation cluster
• Random walks on dynamical percolation: mixing times, mean squared displacement and hitting times
• The mixing time of a random walk on a long-range percolation cluster in pre-Sierpinski gasket
• Mixing times of random walks on dynamic configuration models
• Pseudo-mixing Time of Random Walks
• Quenched exit times for random walk on dynamical percolation
• Regularity of the time constant for a supercritical Bernoulli percolation
• Superdiffusion in decoupled continuous time random walks
• Random walks on supercritical percolation clusters

zbMATH Keywords

random walkmixing timesstopping timesdynamical percolation

Mathematics Subject Classification ID

Interacting random processes; statistical mechanics type models; percolation theory (60K35) Processes in random environments (60K37)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Percolation
• Strong stationary times via a new form of duality
• A note on percolation on \(\mathbb Z^d\): isoperimetric profile via exponential cluster repulsion
• Isoperimetry and heat kernel decay on percolation clusters.
• Evolving sets, mixing and heat kernel bounds
• Random walks on dynamical percolation: mixing times, mean squared displacement and hitting times
• Quenched invariance principle for random walks with time-dependent ergodic degenerate weights
• Limit theory for random walks in degenerate time-dependent random environments
• Quenched exit times for random walk on dynamical percolation

Cited In (17)

• An invariance principle for one-dimensional random walks in degenerate dynamical random environments
• Cover times for random walk on dynamical percolation
• Mixing time of random walk on dynamical random cluster
• Mixing time of near-critical random graphs
• Title not available (Why is that?)
• Quenched exit times for random walk on dynamical percolation
• Mixing time trichotomy in regenerating dynamic digraphs
• Cutoff for random walk on dynamical Erdős-Rényi graph
• Pseudo-mixing Time of Random Walks
• Biased random walk on dynamical percolation
• Random Walks on Randomly Evolving Graphs
• Mixing times for the mean-field Blume-Capel model via aggregate path coupling
• Random walks on dynamical percolation: mixing times, mean squared displacement and hitting times
• Collisions of random walks in dynamic random environments
• On the mixing time of a simple random walk on the super critical percolation cluster
• A comparison principle for random walk on dynamical percolation
• Linking the mixing times of random walks on static and dynamic random graphs

This page was built for publication: Mixing time for random walk on supercritical dynamical percolation

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