{"id":"0e211124-1529-449a-954b-645337e4b2a7","arxiv_id":"1908.07616","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"In the Tree Builder Random Walk, odd growth periods force ballistic transience, while even growth periods yield null recurrence under slow-growth environments and trapping under fast-growth environments.","lead":"A random walk that grows new branches only every few steps shows sharply different fates depending on whether the growth interval is odd or even: odd intervals make the walker drift away at constant speed, while even intervals make it return slowly or get trapped in a small region. The paper proves this split rigorously for a large class of random growth rates, settling a conjecture from earlier work.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.1's event-(c) transfer of condition (R) to the subtree rooted at z is the load-bearing unproved step; the ballisticity criterion collapses if it fails.","rationale":"The reader's weakest assumption identifies the same load-bearing step: Lemma 4.1's transfer of (R) to the subtree rooted at z. This is the correct point to stress, because Proposition 4.2 has no other source of a positive drift: conditions (R) and (L) alone give opposite bounds on hitting +r and -r, and event (c) must be shown small by an additional structural argument. The paper explicitly says 'It is possible to show...', so this is an admitted omission rather than a contradiction. Independent support exists: the analogous step is proven in [12] for s=1 and Bernoulli growth, and the parity-correction Lemma 4.6 suggests the mechanism is likely to extend. For that reason I do not see grounds to reject or to declare the result unverdictable; the appropriate verdict is the original CONDITIONAL, pending a completed proof of Lemma 4.1 and, secondarily, of the coupling in Proposition 2.2 and the induction in Lemma 4.7. I also note that the alleged false statement in Lemma 2.4 appears to be a typesetting artifact: the plain-text '1/4 log' should read 1/(4 log(1+...)), and with that reading the proof's choice of small epsilon is consistent.","tokens_in":38645,"tokens_out":33761,"duration_ms":331637,"concrete_test":"Write out the missing coupling for Lemma 4.1 in the simplest nontrivial case: s=3, xi i.i.d. Bernoulli(1/2), and T a path of length 2r rooted at its endpoint. Let z be the midpoint and X the far endpoint, and set the time horizon T=exp{r^alpha}. Prove the identity P(no visit to z and no distance-r gain within T) = P_{subtree}(no reach distance 2r from z within T) by induction on T, exhibiting the pathwise bijection between excursions that do not visit z and walks on the subtree. Then verify that condition (R) applies to the random subtree state at sigma_k with the environment shifted by sigma_k. If the identity or the uniform applicability of (R) fails for any k, Lemma 4.1 is false; if both go through, the proof gap is closed and Theorem 1.3 stands.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The ballisticity proof of Theorem 1.3 is funneled through Proposition 4.2, and Proposition 4.2 through Lemma 4.1. In Lemma 4.1 the event (c) -- neither decreasing by r nor increasing by r within exp{r^alpha} steps -- is the only part not controlled directly by conditions (L) and (R). The proof sketch asserts, with no derivation, that the probability of (c) equals the probability that a TBRW on the subtree hung from the ancestor z fails to reach distance 2r from z, and then invokes (R). That transfer is doing real work: it changes the distinguished root from the original root to z, restricts the tree to the descendant subtree, and uses the process after the random stopping time sigma_k with the shifted environment. None of these ingredients is present in the statement of (R), and the sentence 'It is possible to show...' is the only justification. If the equality or the uniform applicability of (R) after the shift fails, the lower bound on the conditional probability of a rightward r-jump in (4.1) is unsupported, and the coupling to a positively drifted random walk in Proposition 4.2 has no basis. The same unproved transfer reappears in Lemma 4.7 when the 'consecutive successes' are applied to starting times of previous successes. This is a genuine proof gap in the central claim, though the mechanism is plausible and likely repairable.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies the Tree Builder Random Walk (TBRW), a walk on a rooted tree that grows by attaching a random number of leaves to the walker's current location every s steps. The main results are: for s even, under the growth condition (S) every vertex is recurrent, while under the independent heavy-growth condition (I) the walker is eventually trapped, and if (S) and (UE) hold then the recurrence is null; for s odd, the walker is ballistic under (UE) alone, proving a conjecture from [11] and generalizing the Bernoulli-growth ballisticity result of [12]. The proof strategy is to introduce a Generalized Loop Process to control hitting times of distant vertices, to use martingale and Doob-decomposition arguments for the even case, and to establish a general ballisticity criterion based on conditions (R) and (L), then to verify these conditions by bootstrapping a sequence of growth conditions (R)_M.","tokens_in":39016,"tokens_out":5632,"duration_ms":57004,"significance":"If the technical gaps are repaired, the paper makes a substantial contribution: Theorem 1.3 resolves the transience conjecture for odd s under a natural uniform ellipticity assumption, and the even-s results give a sharp-looking dichotomy between recurrence and trapping. The ballisticity criterion in Proposition 4.2 is a useful abstraction that could apply beyond the specific model. The paper also has a clean structure: the environment conditions (UE), (S), (I), and (M)_r are stated independently of the theorems and are not calibrated to the conclusions, which is a genuine strength. The main weaknesses are that three load-bearing arguments are omitted, sketched, or contain a quantitative error, so the current version is not fully justified as it stands.","major_comments":[{"comment":"The proof of Lemma 2.4 asserts that one can choose epsilon sufficiently small so that c1 = (1/4)log(1+epsilon*kappa/s) is greater than 1/3. For fixed s and kappa the largest possible value is c1* = (1/4)log(1+kappa/s), so the claim requires kappa/s > exp(4/3)-1; for example kappa=0.1 and s=2 give c1* approximately 0.012, far below 1/3. When this inequality fails, the displayed second summation diverges and the argument as written does not establish that E(eta_z) is infinite. The conclusion may be repairable with a different choice of K or a more refined tail estimate, but the present proof contains a concrete quantitative error.","section":"Section 2, Lemma 2.4"},{"comment":"The coupling between the TBRW and the Generalized Loop Process is stated as a Proposition but its proof is omitted, with a reference to Proposition 4.4 of [12]. This coupling is load-bearing: it is used in Corollary 2.3, Lemma 2.4, and ultimately in the verification of condition (L). Because the current setting allows arbitrary s and environments that may add more than one leaf at a time, the adaptation is not a purely cosmetic change of a parameter. A proof, or at least a detailed statement of how the argument in [12] transfers, should be included.","section":"Section 2, Proposition 2.2"},{"comment":"The treatment of event (c) in the proof sketch is the main gap in the ballisticity proof. The text says 'It is possible to show' that the probability that the walker neither advances nor retreats by r within exp{r^alpha} steps equals the probability that a TBRW on the subtree hung from the ancestor z fails to reach distance 2r from z, and then invokes condition (R). This transfer is not a direct consequence of (R) as stated: it changes the distinguished root from the original root to z, restricts the tree to the descendant subtree, and applies to the process after the random stopping time sigma_k with the shifted environment. None of these ingredients is present in the statement of (R). Without a proof of this equality or of a uniform applicability of (R) after the shift, the lower bound in (4.1) is unsupported, and the coupling in Lemma 4.1 and hence Proposition 4.2 collapse. The same unproved transfer is reused in Lemma 4.7, so this is a load-bearing step for Theorem 1.3.","section":"Section 4.1, Lemma 4.1"},{"comment":"Lemma 4.7, which is the iteration step from (R)_M to (R)_{M+1/2}, is presented only as a sketch and refers to Proposition 3.4 of [12] for details. In particular, the estimate for mu^k in the proof contains an 'essentially' line involving terms of order (log log n)^2 and o((log log n)^2) inside an exponent that must be compared with n^{1/4}. This comparison is not fully derived, and the application of Lemma 4.4 to indicators indexed by consecutive successes requires a rigorous check of the conditional-probability lower bounds after each success. Since Lemma 4.7 is essential for establishing condition (R), the proof needs to be completed in the manuscript.","section":"Section 4.2.4, Lemma 4.7"}],"minor_comments":[{"comment":"The displayed lower bound has a typesetting problem: the expression 'kappa1 2 floor((s+1)/2)' should presumably read kappa times 2^{-floor((s+1)/2)}, and the sentence 'Repeating this bouncing back argument on the leafs' should say 'leaves'.","section":"Section 4.2.2, Lemma 4.3"},{"comment":"The notation (M)_r is used for the moment condition, but later in Section 4 the conditions (R)_M and (R)M appear with inconsistent typography. The subscript notation should be unified throughout.","section":"Section 1.2"},{"comment":"The bound c(T_sk) <= c(T0) + sum_{i=0}^k 1{X_{ik} is a quasi-star} is asserted without proof. A one-sentence justification would help, since the argument depends on the distinction between adding leaves to a quasi-star and to a non-quasi-star vertex.","section":"Section 3, proof of Theorem 1.1(ii)"}],"recommendation":"major_revision","confidential_remarks":"The manuscript depends heavily on the authors' own previous paper [12] for three central arguments: Proposition 2.2 is stated without proof, Lemma 4.1 contains an asserted transfer of condition (R), and Lemma 4.7 is only sketched. Given that these are load-bearing for the main theorems and that Lemma 2.4 contains a quantitative error, I would advise the editor to require the authors to make these steps fully self-contained before acceptance. The citation of [12] is appropriate, but the dependence should not replace the proof in this paper. The paper's scope fits the journal well, and the overall direction is promising."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague — this one is worth your time, with a caveat. The TBRW model is a natural unifying framework: it reduces to NRRW and BGRW, and the paper proves a clean classification. If s is odd, under an independent environment with uniformly positive growth probability ((UE)), the walker is ballistic; this settles the conjecture from [11] and generalizes the Bernoulli case of [12]. If s is even, slow growth ((S)) gives null recurrence and fast growth ((I)) gives trapping. That is a genuinely nice dichotomy, and Theorem 3.4 adds a fine look at exit times in the i.i.d. case.\n\nThe math is mostly clever and the results are believable, but the written proofs are not complete. Three concrete issues. First, Lemma 2.4 contains a false claim: it says c1 = (1/4) log(1+εκ/s) can be made > 1/3 by choosing ε small, but c1 is increasing in ε and even at ε=1 the maximum is (1/4) log(1+κ/s) < 1/3 for all allowed κ and s. The proof uses c1 > 1/3 to make a sum converge; as written, the lower bound it derives is useless. This is a repairable numerical slip, but it is in a paper claiming rigor. Second, Proposition 2.2, the coupling between TBRW and the generalized loop process that everything downstream leans on, has its proof omitted with a reference to [12]. That is fine for a minor variant, but here it is central. Third—and this is the load-bearing one—Lemma 4.1's event (c) transfers condition (R) from the full tree to the subtree rooted at the ancestor z via a sentence 'It is possible to show...' with no derivation. This transfer changes the root and restricts the tree after a random stopping time, none of which is in the statement of (R). If it fails, the right-biased coupling in Proposition 4.2 and hence Theorem 1.3 collapses. The mechanism is plausible and likely repairable, but as written it is a genuine gap. Lemma 4.7 is also only sketched, though that is less worrying because it follows the pattern of [12].\n\nBottom line: the paper deserves a serious referee, and I would send it out rather than desk-reject. But I would make the authors complete the missing proofs before publication. The classification is likely correct; the current write-up does not quite establish it.","headline":"Plausible and significant classification for a natural unifying model, but the written proofs have a few load-bearing gaps, so treat as conditional pending completion.","tokens_in":39517,"tokens_out":4069,"would_cite":true,"duration_ms":568125,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["60K37"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves a clean dichotomy: for odd growth period s the Tree Builder Random Walk is ballistic under uniform ellipticity, while for even s it is null recurrent or trapped.","keywords":["Tree Builder Random Walk","random environment","random trees","ballisticity","recurrence","transience","trapping","uniform ellipticity"],"falsifier":"Simulate or construct a TBRW with s odd and independent ξ_n with P(ξ_n≥1) bounded below; if for some finite rooted tree the walker's distance from the root divided by n has liminf 0 on a positive-probability event, Theorem 1.3 is false. A less drastic check is to test, for a process satisfying (R) and (L), the conditional inequality inf P(Δ d_{k+1}=r | F_k) ≥ 1/(2(1+ε)) used to couple with the right-biased walk.","tokens_in":38402,"feed_emoji":"🌳","tokens_out":6182,"duration_ms":62285,"temperature":0.7,"pith_summary":"This paper studies a walk on a tree that grows only at times that are multiples of a fixed parameter s, with the new leaves attached to wherever the walker is standing. The main claim is that parity of s decides the long-run behavior: if s is odd and the random environment adds at least one leaf with probability bounded away from zero, the walker is ballistic, meaning its distance from the root grows at least linearly with time. If s is even, the same uniformity produces no ballisticity: under a slow-growth condition the walk is null recurrent, and under an opposite heavy-growth condition it gets trapped in a finite neighborhood of some random vertex. A sympathetic reader should care because this settles a conjecture from the no-restart random-walk model and extends a known ballisticity result for Bernoulli growth to arbitrary growth periods and general elliptic environments.","feed_headline":"Odd growth period makes a tree-growing walker ballistic","feed_subtitle":"Settles a conjecture: with bounded-below growth probability, distance from root grows linearly for odd s.","key_machinery":"The central object is the TBRW process itself, a Markov chain when the environment $\\xi$ is independent. The proof of ballisticity is carried by two conditions, $(R)$ and $(L)$: $(R)$ says that with probability at least $1-\\varepsilon/2$ the walker reaches distance $2r$ from the root within $\\exp\\{r^\\alpha\\}$ steps, and $(L)$ says that the probability of climbing back $r$ steps within that window is at most $1/2-\\varepsilon$. Lemma 4.1 turns these into a stochastic domination of the rescaled distance by a $\\frac{1}{2(1+\\varepsilon)}$-right-biased simple random walk. The auxiliary Generalized Loop Process, a path with loops added to the current vertex, supplies the stretched-exponential hitting-time upper bounds that yield $(L)$; the parity-correction lemma (Lemma 4.6) is the key local estimate that lets an odd-period walker push a new leaf forward with uniform probability, bootstrapping $(R)_{1/2}$ to $(R)_{M+1/2}$.","core_discovery":"At the paper's core is Theorem 1.3: for a $(\\xi,s)$-TBRW with $s$ odd and an independent environment satisfying $\\inf_n P(\\xi_n\\ge 1)>0$, the walker is ballistic, meaning $\\liminf_n \\operatorname{dist}_{T_n}(X_n,\\mathrm{root})/n \\ge c$ almost surely for a positive constant $c$. The proof works through a general criterion: if a tree-building walk has a large enough chance to push the tree forward by $r$ in $\\exp\\{r^\\alpha\\}$ steps (condition $(R)$) and a small enough chance to climb back $r$ in the same window (condition $(L)$), then its distance from the root, observed at suitable stopping times, stochastically dominates a right-biased simple random walk; the law of large numbers then gives positive speed. For even $s$ the paper proves a dichotomy instead: condition $(S)$ implies recurrence and, together with uniform ellipticity, null recurrence; condition $(I)$ implies almost sure trapping, so the walker eventually bounces forever between a vertex and its neighbours.","pith_inferences":["Because the paper's $(R)+(L)$ criterion is stated abstractly, the same coupling could be tried on other self-interacting walks; the TBRW is only one instance.","A natural extension the authors only ask about: replacing uniform ellipticity by a slowly decaying probability $P(\\xi_n\\ge 1)\\to 0$ might produce zero-speed transient or positive-recurrent regimes between ballistic and trapped.","Example 6.1 suggests that for infinite initial trees with growing vertex degrees the even-$s$ trap regime can disappear; characterizing such trees would be a direct next step."],"forward_implications":["For odd $s$ and uniformly elliptic independent environments, the walker is transient with positive speed, settling the odd-$s$ transient conjecture for the No Restart Random Walk.","For even $s$, a slowly growing environment (condition $(S)$) forces every vertex eventually added to the tree to be recurrent, and with $(UE)$ the recurrence is null rather than positive.","For even $s$, an environment with very fast growth (condition $(I)$) causes almost sure trapping: the walker eventually stays in a finite set and the height of the tree stops growing.","Under $(UE)$ alone, the hitting time of a vertex at distance at least $\\ell_0$ has infinite expectation, so the TBRW is never positive recurrent in any regime covered by the paper's assumptions.","For odd $s$ and $(UE)$, the height of the generated tree grows linearly; for even $s$ with $(S)$ and $(UE)$, the height still diverges to infinity almost surely."],"supporting_citations":[{"why":"Introduces the No Restart Random Walk, proves transience for s=1, formulates the odd-s conjecture, and supplies the parity/self-loop perspective for even s.","marker":"[11]"},{"why":"Provides the Bernoulli Growth Random Walk ballisticity proof, the loop process construction, conditions (R)/(L), and the key lemmas adapted here.","marker":"[12]"},{"why":"Supplies the martingale convergence theorem (5.3.1) used to prove that under condition (S) the walker crosses the self-loop infinitely often.","marker":"[7]"},{"why":"Moderate deviation principle for i.i.d. variables used in Theorem 3.4(i*) to handle the critical case k = E(ξ1).","marker":"[10]"},{"why":"Baum-Katz convergence-rate result used to bound moments of the random time M_delta, giving the Θ(ℓ) exit-time upper bound in Theorem 3.4(ii).","marker":"[2]"}],"fun_headline_variants":["Odd growth periods make tree walker ballistic—even ones, recurrent or trapped","For a tree builder, odd steps force escape; even steps either stall or trap","Ballistic with odd s, recurrent or trapped with even s: the split","Odd s: tree walker speeds away; even s: it circles or gets stuck"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The ballisticity argument depends on an unproved transfer: condition (R) on the whole tree is assumed to hold on the subtree rooted at the walker's current position, and the proof says only that this is possible to show.","fun_headline_variants_meta":{"raw":{"variants":["Odd growth periods make tree walker ballistic—even ones, recurrent or trapped","For a tree builder, odd steps force escape; even steps either stall or trap","Ballistic with odd s, recurrent or trapped with even s: the split","Odd s: tree walker speeds away; even s: it circles or gets stuck"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000882,"raw_usage":{"total_tokens":3795,"prompt_tokens":915,"completion_tokens":2880,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":531,"completion_tokens_details":{"reasoning_tokens":2794}},"tokens_in":531,"tokens_out":2880,"duration_ms":25092,"temperature":1.0,"reasoning_tokens":2794,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T12:01:45.572900+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Simulate or construct a TBRW with s odd and independent ξ_n with P(ξ_n≥1) bounded below; if for some finite rooted tree the walker's distance from the root divided by n has liminf 0 on a positive-probability event, Theorem 1.3 is false. A less drastic check is to test, for a process satisfying (R) and (L), the conditional inequality inf P(Δ d_{k+1}=r | F_k) ≥ 1/(2(1+ε)) used to couple with the right-biased walk.","supporting_citations":[{"cited_title":"Figueiredo, G","cited_arxiv_id":null,"evidence_quote":"Introduces the No Restart Random Walk, proves transience for s=1, formulates the odd-s conjecture, and supplies the parity/self-loop perspective for even s."},{"cited_title":"Figueiredo, G","cited_arxiv_id":null,"evidence_quote":"Provides the Bernoulli Growth Random Walk ballisticity proof, the loop process construction, conditions (R)/(L), and the key lemmas adapted here."},{"cited_title":"Durrett: Probability: Theory and Examples , 4th ed., Cambridge University Press, (2010)","cited_arxiv_id":null,"evidence_quote":"Supplies the martingale convergence theorem (5.3.1) used to prove that under condition (S) the walker crosses the self-loop infinitely often."},{"cited_title":"Eichelsbacher, M","cited_arxiv_id":null,"evidence_quote":"Moderate deviation principle for i.i.d. variables used in Theorem 3.4(i*) to handle the critical case k = E(ξ1)."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"Baum-Katz convergence-rate result used to bound moments of the random time M_delta, giving the Θ(ℓ) exit-time upper bound in Theorem 3.4(ii)."}],"review_version":1}