On the mixing time of simple random walk on the super critical percolation cluster

Itaï Benjamini, Elchanan Mossel

Abstract

We study the robustness under perturbations of mixing times by analyzing random walks in percolation clusters inside boxes in $\mathbb{Z}^d$. We show that for $d \geq 2$ and $p > p_c(\mathbb{Z}^d)$, the mixing time of a simple random walk on the largest cluster inside $\{-n,...,n\}^d$ is $\Theta(n^2)$. This demonstrates that the mixing time is robust up to a constant factor.

Introduction

A fundamental question in probability and graph theory concerns the robustness of stochastic processes: how does a random walk's behavior change when the underlying graph structure is perturbed? In their 2002 paper, Itai Benjamini and Elchanan Mossel address this by examining the mixing time of a simple random walk on a supercritical percolation cluster.

On a standard $d$-dimensional integer lattice $\mathbb{Z}^d$ restricted to a box of side length $n$, the mixing time—the time required for the walk to reach its stationary distribution—is known to scale as $\Theta(n^2)$. This reflects the diffusive nature of the walk. However, if edges are removed randomly, the resulting geometry becomes significantly more complex. Benjamini and Mossel prove that despite these structural irregularities, the fundamental scaling of the mixing time remains unchanged.

The Percolation Model

The authors consider Bernoulli bond percolation on $\mathbb{Z}^d$. In this model, each edge of the lattice is independently retained with probability $p$ and removed with probability $1-p$. When $p$ exceeds the critical threshold $p_c(\mathbb{Z}^d)$, a unique infinite connected component (the supercritical cluster) emerges.

When restricted to a finite box $B_n = \{-n, \dots, n\}^d$, the "largest cluster" is the intersection of this infinite component with the box. This cluster is characterized by a "messy" geometry, containing holes, dead ends, and narrow bottlenecks. A priori, one might expect these bottlenecks to trap a random walker, leading to a significant increase in mixing time. Benjamini and Mossel set out to prove that, despite this messy geometry, the mixing time remains fundamentally the same order of magnitude as the original grid.

Methodological Framework

To rigorously bound the mixing time, the authors employ several sophisticated mathematical techniques from Markov chain theory and percolation:

1. Continuous-Time Analysis

To avoid complications arising from the bipartite nature of the lattice (periodicity), the authors analyze the walk in continuous time. This ensures that the walk converges to a unique stationary distribution without oscillating between sets of nodes.

2. Conductance and the Lovász-Kannan Bound

A standard approach to bounding mixing times involves the Cheeger constant ($\phi$), which measures the conductance of the graph. While Cheeger's inequality provides a bound, it is often too loose for complex random geometries. Benjamini and Mossel instead utilize a more refined tool developed by Lovász and Kannan. This method examines "average conductance" across different scales, allowing for a much tighter bound of $\Theta(n^2)$.

3. Renormalization and Isoperimetry

The proof relies on showing that the percolation cluster satisfies specific isoperimetric inequalities. Using renormalization, the authors "zoom out" to show that on a sufficiently large scale, the irregular cluster behaves like a well-behaved lattice. This allows them to prove that no "hidden" bottlenecks exist that are large enough to trap the walk for more than $\Theta(n^2)$ steps.

Key Results

The primary contribution of the paper is the proof that for $d \geq 2$ and $p > p_c$, the mixing time $\tau_1$ on the largest cluster in a box of side $n$ is $\Theta(n^2)$ asymptotically almost surely.

Additional findings include:

  • Cheeger Constant Scaling: The Cheeger constant $\phi$ of the cluster scales as $\Theta(n^{-1})$, identical to the scaling of the original unperturbed grid.
  • Structural Stability: The results demonstrate the "stability" of diffusive parameters under percolation. The random walk effectively "feels" the boundaries of the box before it is significantly delayed by the internal vacancies of the cluster.

Discussion and Future Directions

The robustness of the $\Theta(n^2)$ scaling suggests that the global transport properties of the lattice are preserved in the supercritical phase. However, several questions remain:

  • Criticality: At the critical point $p = p_c$, the cluster becomes fractal-like and "spindly." In this regime, the mixing time is expected to be sub-diffusive (slower than $n^2$).
  • Constant Factors: While the order of magnitude is $\Theta(n^2)$, the constant factor is a function of $p$. The behavior of this constant as $p \to p_c$ remains a subject of interest.
  • Cover Time: The authors suggest that for $d \geq 3$, the cover time (the time to visit every node) on the cluster is $\Theta(n^d \log^2 n)$, which is slightly slower than the $\Theta(n^d \log n)$ observed on the full grid.

This work laid the groundwork for understanding how random environments affect the efficiency of stochastic algorithms and physical diffusion processes.

Summary updated

Abstract

We study the robustness under perturbations of mixing times, by studying mixing times of random walks in percolation clusters inside boxes in $\Z^d$. We show that for $d \geq 2$ and $p > p_c(\Z^d)$, the mixing time of simple random walk on the largest cluster inside $\{-n,...,n\}^d$ is $Θ(n^2)$ - thus the mixing time is robust up to constant factor.
BibTeX
@inproceedings{benjamini2003mixing,
  author = {Itaï Benjamini and Elchanan Mossel},
  title = {{On the mixing time of simple random walk on the super critical percolation cluster}},
  booktitle = {Probability},
  year = {2003},
  doi = {10.1007/s00440-002-0246-y},
}

Loading related content...

Figure