pith. sign in

arxiv: 2605.18712 · v1 · pith:HG3XZNRNnew · submitted 2026-05-18 · 🧮 math.PR · math.CO

Faster random walks via infrequent steering

Boris Bukh , Quentin Dubroff This is my paper

Pith reviewed 2026-05-20 07:43 UTC · model grok-4.3

classification 🧮 math.PR math.CO
keywords random walkscover timegraph decompositionsteeringbounded degreeMarkov chainsprobabilistic exploration
0
0 comments X

The pith

Steering random walks at small probability covers bounded-degree graphs in n to the 1 plus little-o of 1 steps.

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

The paper shows that random walks on graphs become much faster when a small fixed probability epsilon lets the walker steer its next step instead of picking a neighbor uniformly at random. For any graph whose maximum degree is bounded by a constant, there exists a steering rule that makes the walk visit every vertex in n to the power 1 plus little-o of 1 steps, with high probability. This is faster than the cover time of ordinary random walks on many graphs. The proof rests on first splitting the graph into pieces of small diameter so that the occasional steering choices can be used efficiently. Readers care because the result gives a concrete way to make a basic probabilistic process explore large networks with only rare external help.

Core claim

We show that in graphs of bounded degree, there is a way to steer the random walk so that, when at each step there is a small probability epsilon of choosing the next neighbor via steering rather than at random, the walk visits every vertex in n^{1+o(1)} steps with high probability. The key to this result is a decomposition of arbitrary graphs into small-diameter pieces that enables effective steering.

What carries the argument

A decomposition of arbitrary graphs into small-diameter pieces that enables effective infrequent steering of the random walk.

Load-bearing premise

Arbitrary graphs of bounded degree admit a decomposition into small-diameter pieces that supports effective steering with only a small probability of intervention.

What would settle it

An explicit bounded-degree graph together with a proof that no steering rule with fixed small epsilon can achieve cover time n^{1+o(1)} on that graph.

read the original abstract

Random walks on graphs can be slow. To speed them up, imagine that at each step instead of choosing the neighbor at random, there is a small probability $\varepsilon>0$ that we can choose it. We show that in this case, at least for graphs of bounded degree, there is a way to steer the walk so that it visits every vertex in $n^{1+o(1)}$ steps with high probability. The key to this result is a way to decompose arbitrary graphs into small-diameter pieces.

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

2 major / 2 minor

Summary. The manuscript introduces infrequent steering for random walks on graphs: at each step, with small probability ε>0 the walker may choose its next neighbor instead of selecting uniformly at random. For graphs of bounded maximum degree the authors claim there exists a steering policy under which the walk covers every vertex in n^{1+o(1)} steps with high probability. The central technical device is a decomposition of an arbitrary graph into pieces of small diameter that permits effective steering within and between pieces.

Significance. If the claimed bound and its supporting decomposition are correct, the result would give a near-linear cover time for bounded-degree graphs, improving substantially on the worst-case Θ(n^3) cover time of the simple random walk. The decomposition technique itself may be reusable for other controlled random processes on graphs. The bounded-degree hypothesis is stated explicitly and the high-probability guarantee is the natural one for cover-time statements.

major comments (2)
  1. [Abstract] The abstract asserts the n^{1+o(1)} bound but supplies neither the explicit diameter bound on the pieces nor the dependence of the steering failure probability on that diameter; without these parameters it is impossible to verify that the o(1) term remains o(1) uniformly over all bounded-degree graphs.
  2. [Section 4 (Decomposition)] The decomposition is described only at the level of existence; the manuscript must exhibit a polynomial-time (or at least explicit) procedure that produces the small-diameter partition and prove that the resulting pieces admit a steering schedule whose total length is n^{1+o(1)}.
minor comments (2)
  1. [Introduction] Define the precise range of ε for which the result holds and state whether ε may depend on n or must be a fixed constant.
  2. [Theorem 1.1] Clarify whether the high-probability statement is with respect to the random walk or also with respect to the random choice of steering times.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments. We address the major comments point by point below.

read point-by-point responses

  1. Referee: [Abstract] The abstract asserts the n^{1+o(1)} bound but supplies neither the explicit diameter bound on the pieces nor the dependence of the steering failure probability on that diameter; without these parameters it is impossible to verify that the o(1) term remains o(1) uniformly over all bounded-degree graphs.

    Authors: We agree that the abstract would benefit from greater specificity on these parameters. Section 4 of the manuscript derives explicit bounds on the piece diameter and on the steering failure probability (which decays sufficiently rapidly with the diameter) that together ensure the o(1) term is uniform over the class of bounded-degree graphs. We will revise the abstract to state these parameters explicitly so that the uniformity claim can be verified directly from the abstract. revision: yes

  2. Referee: [Section 4 (Decomposition)] The decomposition is described only at the level of existence; the manuscript must exhibit a polynomial-time (or at least explicit) procedure that produces the small-diameter partition and prove that the resulting pieces admit a steering schedule whose total length is n^{1+o(1)}.

    Authors: We acknowledge that the current presentation of the decomposition emphasizes existence. The underlying construction is algorithmic and can be made fully explicit via an iterative center-selection procedure followed by breadth-first search layering to form the clusters. We will expand Section 4 to describe this polynomial-time procedure in detail and to prove that the resulting steering schedule across all pieces has total length n^{1+o(1)} with high probability. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper presents a cover-time result of n^{1+o(1)} steps for bounded-degree graphs under infrequent steering, derived from a decomposition of arbitrary graphs into small-diameter pieces that enables effective steering. No load-bearing steps reduce by construction to the target bound, no parameters are fitted to a subset and then relabeled as predictions, and no uniqueness theorems or ansatzes are imported via self-citation chains. The derivation is self-contained against the stated graph-theoretic technique and the bounded-degree restriction, with the abstract and described claims showing the bound following from the decomposition rather than being defined in terms of itself.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The result rests on standard assumptions about undirected graphs of bounded degree and the existence of a suitable decomposition into small-diameter pieces; no free parameters or new entities are introduced in the abstract.

axioms (1)
  • domain assumption The graphs under consideration are undirected, connected, and have bounded maximum degree.
    The result is explicitly stated to hold at least for graphs satisfying this condition.

pith-pipeline@v0.9.0 · 5594 in / 1251 out tokens · 166793 ms · 2026-05-20T07:43:51.608119+00:00 · methodology

discussion (0)

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

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

17 extracted references · 17 canonical work pages

  1. [1]

    Reversible Markov chains and random walks on graphs,

    David Aldous and James Allen Fill. Reversible Markov chains and random walks on graphs,

    work page

  2. [2]

    Unfinished monograph, recompiled 2014, available athttp://www.stat.berkeley.edu/ ~aldous/RWG/book.html

    work page 2014

  3. [3]

    Noga Alon, Chen Avin, Michal Kouck´ y, Gady Kozma, Zvi Lotker, and Mark R. Tuttle. Many random walks are faster than one.Combin. Probab. Comput., 20(4):481–502, 2011

    work page 2011

  4. [4]

    Non-backtracking random walks mix faster.Commun

    Noga Alon, Itai Benjamini, Eyal Lubetzky, and Sasha Sodin. Non-backtracking random walks mix faster.Commun. Contemp. Math., 9(4):585–603, 2007

    work page 2007

  5. [5]

    The power of choice in random walks: An empiri- cal study

    Chen Avin and Bhaskar Krishnamachari. The power of choice in random walks: An empiri- cal study. InProceedings of the 9th ACM international symposium on Modeling analysis and simulation of wireless and mobile systems, pages 219–228, 2006

    work page 2006

  6. [6]

    Broder, Anna R

    Yossi Azar, Andrei Z. Broder, Anna R. Karlin, Nathan Linial, and Steven Phillips. Biased random walks. InProceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, STOC ’92, pages 1–9, New York, NY, USA, 1992. Association for Computing Machinery

    work page 1992

  7. [7]

    Collective coin flipping, robust voting schemes and minima of banzhaf values

    Michael Ben-Or and Nathan Linial. Collective coin flipping, robust voting schemes and minima of banzhaf values. In26th Annual Symposium on Foundations of Computer Science (sfcs 1985), pages 408–416. IEEE, 1985

    work page 1985

  8. [8]

    Lifting Markov chains to speed up mixing

    Fang Chen, L´ aszl´ o Lov´ asz, and Igor Pak. Lifting Markov chains to speed up mixing. InAnnual ACM Symposium on Theory of Computing (Atlanta, GA, 1999), pages 275–281. ACM, New York, 1999

    work page 1999

  9. [9]

    American Mathematical Soc., 1984

    Peter G Doyle and J Laurie Snell.Random walks and electric networks, volume 22. American Mathematical Soc., 1984

    work page 1984

  10. [10]

    Speeding up random walk mixing by starting from a uniform vertex.Electron

    Alberto Espuny D´ ıaz, Patrick Morris, Guillem Perarnau, and Oriol Serra. Speeding up random walk mixing by starting from a uniform vertex.Electron. J. Probab., 29:Paper No. 26, 25, 2024

    work page 2024

  11. [11]

    A tight upper bound on the cover time for random walks on graphs.Random Structures Algorithms, 6(1):51–54, 1995

    Uriel Feige. A tight upper bound on the cover time for random walks on graphs.Random Structures Algorithms, 6(1):51–54, 1995

    work page 1995

  12. [12]

    Choice and bias in random walks

    Agelos Georgakopoulos, John Haslegrave, Thomas Sauerwald, and John Sylvester. Choice and bias in random walks. In11th Innovations in Theoretical Computer Science Conference (ITCS 2020), volume 76, pages 1–19. Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2020. 14

    work page 2020

  13. [13]

    The power of two choices for random walks.Combinatorics, Probability and Computing, 31(1):73–100, 2022

    Agelos Georgakopoulos, John Haslegrave, Thomas Sauerwald, and John Sylvester. The power of two choices for random walks.Combinatorics, Probability and Computing, 31(1):73–100, 2022

    work page 2022

  14. [14]

    Time dependent biased random walks

    John Haslegrave, Thomas Sauerwald, and John Sylvester. Time dependent biased random walks. ACM Transactions on Algorithms (TALG), 18(2):1–30, 2022

    work page 2022

  15. [15]

    Covering problems for Brownian motion on spheres.The Annals of Probability, pages 189–199, 1988

    Peter Matthews. Covering problems for Brownian motion on spheres.The Annals of Probability, pages 189–199, 1988

    work page 1988

  16. [16]

    Time-biased random walks and robustness of expanders

    Sam Olesker-Taylor, Thomas Sauerwald, and John Sylvester. Time-biased random walks and robustness of expanders. InProceedings of the 2026 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 2928–2941. SIAM, 2026

    work page 2026

  17. [17]

    Wilmer, David A

    Elizabeth L. Wilmer, David A. Levin, and Yuval Peres.Markov chains and mixing times. Amer- ican Mathematical Society, 2nd edition, 2017. 15

    work page 2017