pith. machine review for the scientific record. sign in

arxiv: 2605.06511 · v1 · submitted 2026-05-07 · 🧮 math.PR · cs.DM

Recognition: unknown

Logarithmic Mixing of Random Walks on Dynamical Random Cluster Models

Andreas Galanis, Leslie Ann Goldberg, Xandru Mifsud

Pith reviewed 2026-05-08 06:02 UTC · model grok-4.3

classification 🧮 math.PR cs.DM
keywords random walksmixing timesrandom-cluster modelsdynamical random graphsGlauber dynamicssubcritical percolationcoupling arguments
0
0 comments X

The pith

Random walks on dynamical random-cluster graphs mix in Θ(log n) time when edge updates are at least order log n.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that the mixing time of a random walk coupled with a dynamical random-cluster environment on a random regular graph is Θ(log n) in continuous time, provided the edge update rate μ is at least ε log n for any ε>0 and the parameters are subcritical. This matches the known mixing time for the walk on a static graph, indicating no slowdown from the dynamics. A reader would care as it shows dynamic network changes can be harmless to exploration if they occur frequently enough. The argument uses couplings to handle the strong dependencies arising from global connectivity in the edge updates.

Core claim

In the subcritical regime p < p_u(q,d) on random d-regular graphs, for any ε>0 and q≥1, the joint mixing time is Θ(log n) whenever μ≥ε log n. The evolving environment does not slow down mixing in this regime. The proof is based on a coupling argument that uses path-count techniques to overcome the dependencies in the edge dynamics by controlling the structure of the environment along typical trajectories.

What carries the argument

Coupling argument with path-count techniques to control dependencies between the random walk and the global connectivity of the evolving environment.

If this is right

  • The mixing time of the joint process equals that of the static random walk.
  • It holds for all q ≥ 1 in the subcritical regime.
  • μ needs to be at least linear in log n to achieve this.
  • The result is specific to continuous-time dynamics.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • If the update rate drops below order log n, the dependencies may cause slower mixing.
  • Similar path-counting methods could apply to other Glauber-based dynamic environments.
  • The robustness to dynamics suggests logarithmic mixing persists in many fluctuating network models.

Load-bearing premise

That the system parameters are subcritical so that the environment's Glauber dynamics mixes quickly and path counting can control the walk-environment dependencies.

What would settle it

Finding that the mixing time grows faster than any constant times log n for some sequence of n with μ = ε log n and subcritical p would disprove the claim.

Figures

Figures reproduced from arXiv: 2605.06511 by Andreas Galanis, Leslie Ann Goldberg, Xandru Mifsud.

Figure 1
Figure 1. Figure 1: Illustration of the paths on Tj reaching k-roots which are also in the set S. The ball radius logd−1 log n highlighted in blue illustrates that at suitable depths every vertex is a k-root. Furthermore, the vertices highlighted by × are not in S. Lemma 10. With probability 1 − on(1) over G ∼ G(d, n), for all vertices u, all h, i ∈ N such that R/10 ≤ h ≤ R/5, and all i ≤ R/5, there are at least d − 2 neighbo… view at source ↗
read the original abstract

We study random walks on dynamically evolving graphs, where the environment is given by a time-dependent subset of the edges of an underlying graph. Concretely, following the recently introduced framework of Lelli and Stauffer, we consider a random walk interacting with a dynamical random-cluster environment, in which edges are updated with rate $\mu>0$ according to Glauber dynamics with parameters $p$ and $q$, and the walker moves at rate 1 but may only traverse edges that are present at the time of the move. This setting introduces strong dependencies between the walk and the environment, as edge-update probabilities depend on the global connectivity structure. We focus on the case where the underlying graph is a random $d$-regular graph and the parameters lie in the subcritical regime $p < p_{\mathrm{u}}(q, d)$ where it is known that the Glauber dynamics mixes quickly. Our main result is to show that for any $\varepsilon >0$ and all $q \ge 1$, for all $p$ in the subcritical regime, the mixing time of the joint process is $\Theta(\log n)$ (in continuous time) whenever $\mu\geq \varepsilon \log n$. This matches the mixing time of the simple random walk on a static random regular graph, showing that in this regime the evolving environment does not slow down mixing. Our proof is based on a coupling argument that uses path-count techniques to overcome the dependencies in the edge dynamics by controlling the structure of the environment along typical trajectories.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 3 minor

Summary. The manuscript proves that the mixing time of the joint process consisting of a continuous-time random walk and a dynamical random-cluster environment on a random d-regular graph is Θ(log n) whenever the edge-update rate satisfies μ ≥ ε log n for any ε > 0, the edge parameter p lies in the subcritical regime p < p_u(q, d), and q ≥ 1. The argument proceeds by constructing a coupling between two copies of the joint process and controlling the evolution of the environment along typical trajectories of the walker via path-counting estimates that exploit the rapid mixing of the underlying Glauber dynamics.

Significance. If the central claim holds, the result is significant because it supplies an explicit, parameter-free asymptotic mixing-time bound showing that sufficiently rapid environmental dynamics do not slow the walker relative to the static-graph case. The proof technique—coupling augmented by path counting to handle global dependencies—is a standard tool in the area but is applied here to a setting with strong walk-environment correlations; the manuscript derives the joint-process bound independently rather than reducing to fitted parameters.

minor comments (3)
  1. [Introduction / Main result] The statement of the main theorem (presumably Theorem 1.1 or equivalent) should include an explicit reference to the continuous-time normalization and the precise definition of the joint state space.
  2. [Proof of main theorem] In the coupling construction, the error term arising from the path-counting bound on atypical trajectories is stated to be o(1); an explicit quantitative estimate (e.g., O(1/log n) or better) would strengthen the presentation.
  3. [Model definition] Notation for the random-cluster measure and the Glauber update rates is introduced without a dedicated preliminary section; a short subsection collecting the standard definitions and the known subcritical mixing time for Glauber dynamics would improve readability.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for their positive assessment of the manuscript, accurate summary of the main result, and recommendation for minor revision. No specific major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity; derivation is self-contained

full rationale

The paper's central claim is a direct proof that the joint mixing time is Θ(log n) via an explicit coupling argument augmented by path-count techniques to control dependencies between the random walk and the dynamical random-cluster environment. This argument is constructed from first principles in the subcritical regime and does not reduce to any fitted parameter, self-definition, or load-bearing self-citation. It invokes the known fast mixing of Glauber dynamics on static subcritical random-cluster models as an external input (from prior literature, not the authors' own prior uniqueness theorems), then derives the new joint-process bound independently. No step equates a 'prediction' to its own inputs by construction, and the result is externally falsifiable against static-graph mixing times.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claim rests on standard mathematical facts about random regular graphs and known rapid mixing of Glauber dynamics below the uniqueness threshold; no numerical parameters are fitted to data and no new entities are postulated.

axioms (2)
  • domain assumption Glauber dynamics for the random-cluster model mixes in polynomial time when p < p_u(q, d).
    Invoked to ensure the environment reaches equilibrium fast enough that the walk sees a typical configuration along its trajectory.
  • standard math Random d-regular graphs admit sufficient expansion or path-counting bounds for coupling arguments.
    Used to control the probability that two coupled walks meet or that the environment along typical paths behaves predictably.

pith-pipeline@v0.9.0 · 5582 in / 1555 out tokens · 44676 ms · 2026-05-08T06:02:17.541539+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

17 extracted references · 1 canonical work pages

  1. [1]

    Biased random walk on dynamical percolation.The Annals of Probability, 52(6), November 2024

    Sebastian Andres, Nina Gantert, Dominik Schmid, and Perla Sousi. Biased random walk on dynamical percolation.The Annals of Probability, 52(6), November 2024

    2024

  2. [2]

    The voter model on random regular graphs with random rewiring, 2025

    Luca Avena, Rangel Baldasso, Rajat Subhra Hazra, Frank den Hollander, and Matteo Quattropani. The voter model on random regular graphs with random rewiring, 2025. arXiv:2501.08703

    work page arXiv 2025

  3. [3]

    Mixing times of random walks on dynamic configuration models.The Annals of Applied Probability, 28(4):1977– 2002, 2018

    Luca Avena, Hakan G ¨uldas ¸, Remco van der Hofstad, and Frank den Hollander. Mixing times of random walks on dynamic configuration models.The Annals of Applied Probability, 28(4):1977– 2002, 2018

    1977

  4. [4]

    Random walks on dy- namic configuration models: A trichotomy.Stochastic Processes and their Applications, 129(9):3360– 3375, 2019

    Luca Avena, Hakan G ¨uldas ¸, Remco van der Hofstad, and Frank den Hollander. Random walks on dy- namic configuration models: A trichotomy.Stochastic Processes and their Applications, 129(9):3360– 3375, 2019

    2019

  5. [5]

    Mixing of fast random walks on dynamic random permutations.Probability Theory and Related Fields, Apr 2025

    Luca Avena, Remco van der Hofstad, Frank den Hollander, and Oliver Nagy. Mixing of fast random walks on dynamic random permutations.Probability Theory and Related Fields, Apr 2025

    2025

  6. [6]

    Limit theory for random walks in degenerate time- dependent random environments.Journal of Functional Analysis, 274(4):985–1046, 2018

    Marek Biskup and Pierre-Franc ¸ois Rodriguez. Limit theory for random walks in degenerate time- dependent random environments.Journal of Functional Analysis, 274(4):985–1046, 2018

    2018

  7. [7]

    Random-Cluster Dynamics on Random Regular Graphs in Tree Uniqueness.Communications in Mathematical Physics, 386(2):1243–1287, 2021

    Antonio Blanca and Reza Gheissari. Random-Cluster Dynamics on Random Regular Graphs in Tree Uniqueness.Communications in Mathematical Physics, 386(2):1243–1287, 2021

    2021

  8. [8]

    Random walks on randomly evolving graphs

    Leran Cai, Thomas Sauerwald, and Luca Zanetti. Random walks on randomly evolving graphs. In Andrea Werneck Richa and Christian Scheideler, editors,Structural Information and Communication Complexity, pages 111–128, 2020

    2020

  9. [9]

    A comparison principle for random walk on dynamical percolation

    Jonathan Hermon and Perla Sousi. A comparison principle for random walk on dynamical percolation. The Annals of Probability, 48(6), November 2020. 20

    2020

  10. [10]

    Exchangeable Pairs, Switchings, and Random Regular Graphs.The Electronic Journal of Combinatorics, 22(1), February 2015

    Tobias Johnson. Exchangeable Pairs, Switchings, and Random Regular Graphs.The Electronic Journal of Combinatorics, 22(1), February 2015

    2015

  11. [11]

    Mixing time of random walk on dynamical random cluster

    Andrea Lelli and Alexandre Stauffer. Mixing time of random walk on dynamical random cluster. Probability Theory and Related Fields, 189(3):981–1043, Aug 2024

    2024

  12. [12]

    Cutoff phenomena for random walks on random regular graphs.Duke Mathematical Journal, 153(3), June 2010

    Eyal Lubetzky and Allan Sly. Cutoff phenomena for random walks on random regular graphs.Duke Mathematical Journal, 153(3), June 2010

    2010

  13. [13]

    Yuval Peres, Perla Sousi, and Jeffrey E. Steif. Mixing time for random walk on supercritical dynamical percolation.Probability Theory and Related Fields, 176(3):809–849, Apr 2020

    2020

  14. [14]

    Yuval Peres, Alexandre Stauffer, and Jeffrey E. Steif. Random walks on dynamical percolation: mix- ing times, mean squared displacement and hitting times.Probability Theory and Related Fields, 162(3):487–530, Aug 2015

    2015

  15. [15]

    Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities

    Thomas Sauerwald and Luca Zanetti. Random Walks on Dynamic Graphs: Mixing Times, Hitting Times, and Return Probabilities. In Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi, editors,46th International Colloquium on Automata, Languages, and Programming (ICALP 2019), volume 132 ofLeibniz International Proceedings in Informatic...

    2019

  16. [16]

    Cutoff for random walk on dynamical Erd ˝os–R´enyi graph.Annales de l’Institut Henri Poincar´e, Probabilit´es et Statistiques, 56(4), November 2020

    Perla Sousi and Sam Thomas. Cutoff for random walk on dynamical Erd ˝os–R´enyi graph.Annales de l’Institut Henri Poincar´e, Probabilit´es et Statistiques, 56(4), November 2020

    2020

  17. [17]

    cut edge event

    Martin Wainwright.High-dimensional statistics: a non-asymptotic viewpoint. Cambridge series in statistical and probabilistic mathematics; 48. Cambridge University Press, 2019. A Detailed Chain Description We next formalise the full Markov chain that we study. For all positive integersdandn,G(d, n)denotes the family of (simple)d-regular graphs withnvertice...

    2019