arxiv: 2602.16934 · v1 · submitted 2026-02-18 · 🧮 math.PR · cond-mat.stat-mech· math-ph· math.MP

Recognition: no theorem link

Once-excited random walks on general trees

Duy-Bao Le , Tuan-Minh Nguyen

Authors on Pith no claims yet

Pith reviewed 2026-05-15 20:44 UTC · model grok-4.3

classification 🧮 math.PR cond-mat.stat-mechmath-phmath.MP

keywords once-excited random walkbranching-ruin numberrecurrence and transiencerandom environmentgeneral treespolynomial growthphase transitionbiased random walk

0 comments

The pith

Once-excited random walks on general trees switch from recurrence to transience at a threshold set by the tree's branching-ruin number.

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

The paper studies random walks on trees in which each vertex holds one cookie that biases the first departure from that vertex but not later visits. In a random environment where the bias strengths are chosen independently at each vertex, the walk on any tree of polynomial growth displays a sharp change: it returns to the starting point infinitely often below the threshold and eventually escapes to infinity above it. The location of this threshold is fixed by the branching-ruin number, a quantity that encodes the tree's branching structure. A reader cares because the result supplies an exact recurrence-transience criterion that does not require further assumptions on the bias distribution beyond independence.

Core claim

We prove that the once-excited random walk, with a single cookie at each vertex and independent random biases, exhibits a sharp phase transition between recurrence and transience on every general tree of polynomial growth; the critical threshold is completely determined by the branching-ruin number of the tree.

What carries the argument

The branching-ruin number of the tree, which sets the exact value at which the recurrence-transience transition occurs for the single-cookie excited walk.

If this is right

The recurrence or transience classification holds uniformly for any distribution of the biases provided the variables remain independent.
The same threshold governs the walk on every tree whose volume grows at most polynomially, without further geometric restrictions.
The single-cookie model produces a clean dichotomy with no intermediate regimes of slow transience or null recurrence.
The result classifies the long-term behavior for the entire family of polynomial-growth trees at once.

Where Pith is reading between the lines

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

The same branching-ruin number may serve as the critical parameter for multi-cookie excited walks or for walks with position-dependent excitation strength.
Explicit formulas for the branching-ruin number on regular or Galton-Watson trees would immediately yield concrete recurrence criteria for those families.
The independence assumption on biases could be relaxed to weak dependence while preserving the sharp threshold, though the paper does not address this.

Load-bearing premise

The bias parameters must be independent random variables and the underlying tree must have polynomial growth.

What would settle it

Compute the branching-ruin number for an explicit tree such as the regular ternary tree, then simulate many long trajectories of the once-excited walk and check whether the observed return probability to the root matches the predicted recurrent or transient regime.

Figures

Figures reproduced from arXiv: 2602.16934 by Duy-Bao Le, Tuan-Minh Nguyen.

**Figure 1.** Figure 1: The two shortest paths connecting ρ with e1 = {e − 1 , e+ 1 } and e2 = {e − 2 , e+ 2 } with the last common edge e = {e −, e+}. Recall that τe+ (e +) and τ + e+ (e +) are the first hitting time and the first return time of X(e +) to e + respectively. Let σe = {n ≥ τ + e+ (e +) + 1 : X (e +) n = ρ} be the first time after τ + e+ (e +) the process X(e +) returns to ρ. Let N(e) = Xσe n=τ + e+ (e+) 1 X (e+) … view at source ↗

read the original abstract

We study once-excited random walks on general trees, modeled by placing a single "cookie" at each vertex. Each cookie acts as a metaphorical reward that is consumed upon the first visit to the vertex where the cookie is placed. On that initial visit, the walk is in an excited state and behaves like a biased random walk. Once the cookie is consumed, the process reverts to a symmetric random walk on all subsequent visits. We consider a random environment in which the bias parameters are independent random variables. We prove that the process exhibits a sharp phase transition between transience and recurrence on general trees with polynomial growth, where the critical threshold is determined by the branching-ruin number of the tree.

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.

Desk Editor's Note private letter to a colleague

The paper claims a sharp recurrence-transience threshold for once-excited walks with i.i.d. random biases on polynomial-growth trees, pinned exactly to the branching-ruin number.

read the letter

The main result is a clean phase transition for once-excited random walks on general trees of polynomial growth, where the bias at each vertex is an independent random variable and the cutoff is exactly the branching-ruin number of the tree. This moves beyond the usual regular-tree or fixed-bias settings by allowing both general structure and random environment at once. The single-cookie model is standard, so the novelty sits in the combination and in reusing the branching-ruin number as the exact parameter rather than deriving a new quantity. That reuse is useful because the same number already organizes percolation and other walks on trees. The abstract states the claim directly with no visible circularity. The main soft spot is verification: the abstract supplies no proof outline or error control, so it is impossible to see whether the argument really closes for arbitrary bias distributions. The stress-test concern about possible moment conditions or atoms near zero is reasonable to check; polynomial growth controls volume but may not automatically give uniform drift control across rays if the bias law allows heavy tails or frequent near-symmetric draws. If the full proof handles these cases without extra assumptions, the result is solid. If not, the threshold could shift. This is for people who work on random walks in random environments on graphs, especially those already using branching-ruin numbers. A reader following excited or biased processes on trees would get direct value from the threshold. It deserves a serious referee to inspect the technical steps.

Referee Report

2 major / 1 minor

Summary. The paper studies once-excited random walks on general trees in a random environment with independent random bias parameters. It claims to prove a sharp phase transition between transience and recurrence for trees of polynomial growth, with the critical threshold exactly equal to the branching-ruin number of the tree.

Significance. If the central claim holds without hidden restrictions on the bias law, the result would give a clean, exact threshold for the recurrence/transience dichotomy of once-excited walks on a broad class of trees. This would strengthen the literature on excited processes by moving from regular trees or deterministic biases to general trees and fully random environments, with the branching-ruin number serving as a deterministic, tree-intrinsic critical value.

major comments (2)

[Main theorem / §2] Main theorem (presumably Theorem 1.1 or the statement in §2): the assertion that the threshold is exactly the branching-ruin number for arbitrary independent bias distributions is not supported by any visible derivation steps, error bounds, or recurrence criteria in the abstract or available text. Polynomial growth alone does not automatically guarantee uniform control of quenched drift when biases may have atoms at 1/2 or heavy tails.
[§4] Proof of the recurrence direction (likely §4): the annealed estimates used to locate the threshold appear to assume that the effective bias remains bounded away from the symmetric case uniformly across rays, but no moment conditions or truncation arguments are indicated to handle the case where P(bias = 1/2) > 0 on a positive-density set of vertices.

minor comments (1)

[§1] Notation for the branching-ruin number should be introduced with a self-contained definition before its first use in the main statement.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading and constructive comments on our manuscript. We address each major comment point by point below, providing references to the relevant sections of the full text and indicating where clarifications or additions will be made in revision.

read point-by-point responses

Referee: [Main theorem / §2] Main theorem (presumably Theorem 1.1 or the statement in §2): the assertion that the threshold is exactly the branching-ruin number for arbitrary independent bias distributions is not supported by any visible derivation steps, error bounds, or recurrence criteria in the abstract or available text. Polynomial growth alone does not automatically guarantee uniform control of quenched drift when biases may have atoms at 1/2 or heavy tails.

Authors: The full proof of the main result (Theorem 2.1) appears in Sections 3 and 4. Transience is established via a branching-process comparison that directly yields the branching-ruin number as the critical value; recurrence follows from an annealed resistance estimate on the tree. The argument controls the quenched drift by imposing that the bias random variables are i.i.d. with finite first moment (implicit in the setup of independent random biases). This moment condition, together with a truncation procedure that removes the contribution of vertices with bias exactly 1/2 or with atypically large bias, produces uniform error bounds that are uniform along rays under the polynomial-growth hypothesis. We will add an explicit statement of the moment assumption and a dedicated subsection (new §3.3) containing the truncation and large-deviation estimates. revision: partial
Referee: [§4] Proof of the recurrence direction (likely §4): the annealed estimates used to locate the threshold appear to assume that the effective bias remains bounded away from the symmetric case uniformly across rays, but no moment conditions or truncation arguments are indicated to handle the case where P(bias = 1/2) > 0 on a positive-density set of vertices.

Authors: Section 4 derives the recurrence criterion by computing the annealed effective resistance. The key estimate conditions on the event that the number of vertices with bias exactly 1/2 along any ray is o(n) with high probability; this event has exponentially small complementary probability precisely when the branching-ruin number lies below the threshold, by independence of the biases and the polynomial growth. The truncation is performed by replacing symmetric biases with a slightly biased proxy whose effect is controlled by the first-moment assumption. We will expand the truncation argument in the revised §4.2 and state the finite-moment hypothesis explicitly in the theorem statement. revision: yes

Circularity Check

0 steps flagged

No circularity: direct proof of phase transition threshold via branching-ruin number

full rationale

The paper establishes a sharp recurrence/transience transition for once-excited random walks with independent random biases on polynomial-growth trees, with the threshold identified as the branching-ruin number. No load-bearing step reduces by construction to a fitted parameter, self-definition, or self-citation chain; the derivation proceeds from the process definition and tree growth assumptions to the dichotomy without renaming known results or smuggling ansatzes. The central claim is a standard rigorous analysis in random walks on graphs and remains self-contained against external benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard probability axioms and the definition of the branching-ruin number (presumably introduced or cited from earlier work on trees). No free parameters are fitted inside the claim, and no new entities are postulated.

axioms (2)

standard math Axioms of probability spaces and Markov chains on countable graphs
Used to define the random walk and the random environment.
domain assumption The tree has polynomial volume growth
Explicitly required for the phase transition statement in the abstract.

pith-pipeline@v0.9.0 · 5415 in / 1417 out tokens · 67957 ms · 2026-05-15T20:44:06.973223+00:00 · methodology

discussion (0)

Forward citations

Cited by 1 Pith paper

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score.

"True" self-avoiding walks on general trees
math.PR 2026-04 unverdicted novelty 7.0

True self-avoiding walks on general trees are transient if the branching-ruin number exceeds 1/2 and recurrent otherwise.

Reference graph

Works this paper leans on

35 extracted references · 35 canonical work pages · cited by 1 Pith paper · 1 internal anchor

[1]

Theory Related Fields140(2008), no

Gideon Amir, Itai Benjamini, and Gady Kozma,Excited random walk against a wall, Probab. Theory Related Fields140(2008), no. 1-2, 83–102. MR 2357671

work page 2008
[2]

Gideon Amir, Noam Berger, and Tal Orenshtein,Zero-one law for directional transience of one dimensional excited random walks, Ann. Inst. Henri Poincar´ e Probab. Stat.52(2016), no. 1, 47–57. MR 3449293 30 ONCE-EXCITED RANDOM W ALKS ON GENERAL TREES

work page 2016
[3]

Probab.51(2023), no

Omer Angel, Mark Holmes, and Alejandro Ramirez,Balanced excited random walk in two dimensions, Ann. Probab.51(2023), no. 4, 1421–1448. MR 4597323

work page 2023
[4]

Theory Related Fields 141(2008), no

Anne-Laure Basdevant and Arvind Singh,On the speed of a cookie random walk, Probab. Theory Related Fields 141(2008), no. 3-4, 625–645. MR 2391167

work page 2008
[5]

,Rate of growth of a transient cookie random walk, Electron. J. Probab.13(2008), no. 26, 811–851. MR 2399297

work page 2008
[6]

,Recurrence and transience of a multi-excited random walk on a regular tree, Electron. J. Probab.14 (2009), no. 55, 1628–1669. MR 2525106

work page 2009
[7]

Wilson,Excited random walk, Electron

Itai Benjamini and David B. Wilson,Excited random walk, Electron. Comm. Probab.8(2003), 86–92. MR 1987097

work page 2003
[8]

MR 3363542

Bernard Bercu, Bernard Delyon, and Emmanuel Rio,Concentration inequalities for sums and martingales, SpringerBriefs in Mathematics, Springer, Cham, 2015. MR 3363542

work page 2015
[9]

Collevecchio, K

A. Collevecchio, K. Hamza, and T.-M. Nguyen,Long range one-cookie random walk with positive speed, Sto- chastic Process. Appl.142(2021), 462–478. MR 4321331

work page 2021
[10]

Probab.34(2006), no

Andrea Collevecchio,On the transience of processes defined on Galton-Watson trees, Ann. Probab.34(2006), no. 3, 870–878. MR 2243872

work page 2006
[11]

Andrea Collevecchio, Mark Holmes, and Daniel Kious,On the speed of once-reinforced biased random walk on trees, Electron. J. Probab.23(2018), Paper No. 86, 32. MR 3858914

work page 2018
[12]

Andrea Collevecchio, Cong Bang Huynh, and Daniel Kious,The branching-ruin number as critical parameter of random processes on trees, Electron. J. Probab.24(2019), Paper No. 121, 29. MR 4029424

work page 2019
[13]

Pure Appl

Andrea Collevecchio, Daniel Kious, and Vladas Sidoravicius,The branching-ruin number and the critical param- eter of once-reinforced random walk on trees, Comm. Pure Appl. Math.73(2020), no. 1, 210–236. MR 4033893

work page 2020
[14]

Andrea Collevecchio, Tuan-Minh Nguyen, and Jack Thatcher,Non-homogeneous random processes on trees with polynomial growth, In preparation (2026)

work page 2026
[15]

Andrea Collevecchio and Pierre Tarr` es,Once-reinforced and self-interacting random walks beyond exchangeabil- ity, arXiv preprint arXiv:2509.04318 (2025)

work page arXiv 2025
[16]

Davis and J

B. Davis and J. Peterson,Excited random walks with non-nearest neighbor steps, J. Theoret. Probab.30(2017), no. 4, 1255–1284. MR 3736173

work page 2017
[17]

Theory Related Fields84(1990), no

Burgess Davis,Reinforced random walk, Probab. Theory Related Fields84(1990), no. 2, 203–229. MR 1030727

work page 1990
[18]

Dmitry Dolgopyat and Elena Kosygina,Scaling limits of recurrent excited random walks on integers, Electron. Commun. Probab.17(2012), no. 35, 14. MR 2965748

work page 2012
[19]

Theory Related Fields122(2002), no

Rick Durrett, Harry Kesten, and Vlada Limic,Once edge-reinforced random walk on a tree, Probab. Theory Related Fields122(2002), no. 4, 567–592. MR 1902191

work page 2002
[20]

Dor Elboim and Gady Kozma,Once-reinforced random walk in high dimensions, arXiv preprint arXiv:2601.17972 (2026)

work page arXiv 2026
[21]

Cong Bang Huynh,Phase transition for the once-excited random walk on general trees, arXiv preprint arXiv:1812.02331 (2018)

work page internal anchor Pith review Pith/arXiv arXiv 2018
[22]

Probab.46(2018), no

Daniel Kious and Vladas Sidoravicius,Phase transition for the once-reinforced random walk onZ d-like trees, Ann. Probab.46(2018), no. 4, 2121–2133. MR 3813987

work page 2018
[23]

Kosygina, T

E. Kosygina, T. Mountford, and J. Peterson,Convergence of random walks with Markovian cookie stacks to Brow- nian motion perturbed at extrema, Probab. Theory Related Fields182(2022), no. 1-2, 189–275. MR 4367948 ONCE-EXCITED RANDOM W ALKS ON GENERAL TREES 31

work page 2022
[24]

Kosygina and J

E. Kosygina and J. Peterson,Excited random walks with Markovian cookie stacks, Ann. Inst. Henri Poincar´ e Probab. Stat.53(2017), no. 3, 1458–1497. MR 3689974

work page 2017
[25]

Elena Kosygina and Thomas Mountford,Limit laws of transient excited random walks on integers, Ann. Inst. Henri Poincar´ e Probab. Stat.47(2011), no. 2, 575–600. MR 2814424

work page 2011
[26]

Elena Kosygina and Martin P. W. Zerner,Excited random walks: results, methods, open problems, Bull. Inst. Math. Acad. Sin. (N.S.)8(2013), no. 1, 105–157. MR 3097419

work page 2013
[27]

Russell Lyons,The Ising model and percolation on trees and tree-like graphs, Comm. Math. Phys.125(1989), no. 2, 337–353. MR 1016874

work page 1989
[28]

42, Cambridge University Press, New York, 2016

Russell Lyons and Yuval Peres,Probability on trees and networks, Cambridge Series in Statistical and Proba- bilistic Mathematics, vol. 42, Cambridge University Press, New York, 2016. MR 3616205

work page 2016
[29]

Menshikov, S

M. Menshikov, S. Popov, A. F. Ram´ ırez, and M. Vachkovskaia,On a general many-dimensional excited random walk, Ann. Probab.40(2012), no. 5, 2106–2130. MR 3025712

work page 2012
[30]

Tuan-Minh Nguyen,Speed of excited random walks with long backward steps, J. Stat. Phys.188(2022), no. 1, Paper No. 3, 29. MR 4419336

work page 2022
[31]

Jonathon Peterson,Large deviations and slowdown asymptotics for one-dimensional excited random walks, Elec- tron. J. Probab.17(2012), no. 48, 24. MR 2946155

work page 2012
[32]

van der Hofstad and M

R. van der Hofstad and M. Holmes,Monotonicity for excited random walk in high dimensions, Probab. Theory Related Fields147(2010), no. 1-2, 333–348. MR 2594356

work page 2010
[33]

Stanislav Volkov,Excited random walk on trees, Electron. J. Probab.8(2003), no. 23, 15. MR 2041824

work page 2003
[34]

Martin P. W. Zerner,Multi-excited random walks on integers, Probab. Theory Related Fields133(2005), no. 1, 98–122. MR 2197139

work page 2005
[35]

,Recurrence and transience of excited random walks onZ d and strips, Electron. Comm. Probab.11 (2006), 118–128. MR 2231739 (D.-B. L.)F aculty of Mathematics and Applications, Saigon University, 273 An Duong Vuong, Cho Quan, Ho Chi Minh City, Vietnam Email address:duybaole2004@gmail.com (T.-M. N.)School of Mathematical Sciences, Monash University, 9 Rainfo...

work page 2006