Pith. sign in

REVIEW 2 major objections 3 minor 2 cited by

Collisions of random walks on comb graphs with a planar base

T0 review · 2 major / 3 minor · reviewed 2026-08-05 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves the phase transition for collisions of two random walks on Z^2 combs: teeth growing like log^gamma produce infinitely many collisions exactly when gamma is at most 1.

desk verdict Answers an explicit open question with real new results; the Borel-Cantelli partition gap is genuine but looks repairable. read the letter →

arxiv 2508.19814 v1 pith:CE34G3VW submitted 2025-08-27 math.PR

Umberto De Ambroggio , Maximilian Nitzschner , Carlo Scali This is my paper · ORCID
classification math.PR MSC 60J1005C8160J35
keywords randomwalkscollisionscombgraphsheatkernelphasetransitionGreencriterionpercolationplanar
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper aims to pin down when two independent simple random walks on a comb graph—a planar base with vertical teeth whose length grows with distance from the origin—keep colliding or stop colliding. It proves a phase transition governed by how fast the teeth grow. On a base of Z^2 with teeth of length log^gamma(radius), walks started together collide infinitely often almost surely exactly when gamma is at most 1, and only finitely often when gamma is larger than 1; this answers a question left open by Barlow, Peres, and Sousi. The same transition is established for pre-fractal planar bases, at exponent beta minus alpha, and for typical supercritical Bernoulli percolation clusters in Z^2, again at gamma equals 1. The proof's workhorse is a sharp heat-kernel upper bound on the comb, obtained by concentrating on the time the walk spends in vertical excursions between horizontal steps.

What carries the argument

The heat-kernel bound on the comb is the key object. The walk's horizontal steps are interleaved with vertical excursions whose lengths are governed by the tooth profile. Lemma 4.4 bounds the diagonal heat kernel by showing that, in the time window [t/2, t], the number of returns to the starting tooth is controlled by the horizontal component, a random walk on Z^2. A concentration argument on the number of horizontal steps (events A and B) plus an occupation-time estimate reduce the return count to a truncated Green kernel on Z^2, which is O(1). From this diagonal bound, off-diagonal estimates and a two-scale comparison (short time versus long time) yield the sharp on-diagonal-to-off-diagona

What would settle it

Check the coverage claim: in Section 4.4 (and Section 3.1), the sets Qtilde_{k,ell} with ell in {2, 4, ..., 2^{j0}} are said to exhaust the vertex set, but they do not contain (u,0) or tooth heights above 2 ell/3. One can directly test whether the omitted sets still satisfy summable collision probabilities using the paper's own heat-kernel bounds; if that sum diverges, the finite-collision claim would need a different proof.

Watch

Extended reading notes

Core claim

The central claim is Theorem 4.1: on Comb(Z^2, f_gamma) with f_gamma(z) = floor(log^gamma(||z||_inf or 1)), two independent simple random walks started from the same vertex collide infinitely often almost surely if gamma is at most 1, and collide only finitely often almost surely if gamma is larger than 1. The infinite-collision side was known; the paper's new contribution is the finite side for gamma greater than 1, which requires proving the heat kernel from the origin to a vertex at sup-norm distance k is at most c/t for t at least k^2 log^gamma(k) and at most c/(k^2 log^gamma(k)) for smaller t. This tuned bound makes the expected number of collisions in concentric shells summable, so Bor

Load-bearing premise

The Borel-Cantelli argument in Theorem 4.1 and Theorem 3.2 relies on the claim that the regions Qtilde_{k,ell} cover every vertex of the comb; in fact height-0 vertices and the top third of each tooth are omitted, so unless those omitted regions are separately controlled, the summed probabilities do not by themselves prove finitely many collisions.

Editorial extensions

If this is right

  • For Comb(Z^2, f_gamma), two walks starting together meet infinitely often almost surely if gamma is at most 1, and only finitely many times if gamma is larger than 1.
  • The same gamma equals 1 phase transition holds when the base is a typical supercritical Bernoulli percolation cluster in Z^2 containing the origin.
  • For pre-fractal bases satisfying the stated volume and resistance conditions, the phase transition occurs at tooth-growth exponent gamma equal to beta minus alpha.
  • The Green-kernel criterion of Barlow, Peres, and Sousi is sharp at leading order for these planar bases: it predicts the exact transition exponent, and the heat-kernel analysis shows the crossover where the criterion stops being effective.
  • By the zero-one law, the infinite or finite collision property holds from every starting vertex once it holds from one vertex.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • The concentration method around vertical excursions looks transferable to any recurrent planar base whose heat kernel is approximately 1/t on relevant scales; the paper does not claim this full generality.
  • The stated exhaustion of the vertex set by the regions Qtilde in Section 4.4 (and 3.1) omits height-zero base vertices and the top third of each tooth. The paper's own heat-kernel bounds appear to make the omitted regions summable, so the proof could be repaired by adding them, but the coverage claim needs correction or augmentation.
  • For the pre-fractal base, the critical exponent beta minus alpha is exactly the exponent appearing in the resistance scaling, suggesting that the collision threshold is governed by resistance growth rather than volume growth; this may be a general principle worth testing on other recurrent planar graphs.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

2 major / 3 minor

Summary. The paper studies collisions of two independent simple random walks on comb graphs Comb(\tilde G, f) with a planar base. The main results are phase transitions for the number of collisions: for Comb(Z^2, f_γ) with f_γ(z)=⌊log^γ(||z||_∞∨1)⌋, infinitely many collisions occur for γ≤1 and only finitely many for γ>1, answering a question of Barlow, Peres, and Sousi; analogous transitions are proved for polynomial profiles on fractal-like bases and for logarithmic profiles over supercritical percolation clusters. The finite-collision proofs rest on new heat-kernel upper bounds, most notably Proposition 4.2 for Comb(Z^2, f_γ), combined with a Borel-Cantelli argument over space-time regions.

Significance. If correct, the paper resolves a natural open question and gives the first finite-collision examples over planar base graphs with logarithmic tooth profiles. The heat-kernel estimates in Section 4 are a substantial technical contribution and appear, for the most part, carefully derived. The paper is clearly written and makes good use of prior work (Barlow–Peres–Sousi, Barlow, Abe) without obvious circularity. However, the Borel-Cantelli partition used to conclude the finite-collision property does not cover the vertex set as claimed; this is a load-bearing gap, though it appears repairable with the paper's own estimates. A second, smaller gap concerns the application of Lemma 4.10 in Lemma 4.8 to vertices on teeth.

major comments (2)
  1. [§4.4 (and §3.1)] The assertion that the sets \tilde Q_{k,ℓ} exhaust V is false. For \tilde Q_{k,ℓ} = {(u,h): ||u||_∞=k, ℓ/3≤h≤2ℓ/3} with ℓ∈{2,4,...,2^{j0}} and 2^{j0}≥log^γ(k), the union over ℓ covers, in each tooth, only heights in [2/3, 2^{j0+1}/3]. Hence h=0 is never included, and for many k an interval near the top (and near the bottom) is omitted whenever log^γ(k) > 2^{j0+1}/3 or 2^{j0}/3 > 2/3. Consequently ∑ P_0(\tilde Z_{k,ℓ}>0)<∞ does not rule out infinitely many collisions at base vertices or in the omitted tooth segments, and the appeal to [5, Cor. 2.3] is not justified. The same defect appears in §3.1, where \tilde Q_{k,ℓ} = {(u,h): u∈A_k, ℓ/3≤h≤2ℓ/3} with 2^{j0}≥k^γ, so base vertices and positive fractions of each tooth are again uncovered. The proof must either enlarge the partition or add a separate summability argument for these regions; the paper's own bounds in Lemmas 3.7–3.8 and 4.7–4.
  2. [§4.3, Lemma 4.8] In the proof of Lemma 4.8, the second term after the first display is bounded using 'Lemma 4.10 to the second term'. However, Lemma 4.10 is stated and proved only for vertices x=(z,0) on the base, whereas the second term involves P_y(X_{t-s}=x) with x=(z,h) for h≥0 and y on the boundary of B(0,k/2). No on-diagonal or off-diagonal upper bound for vertices at positive height on a tooth is proved (Lemma 4.4 covers only base vertices). This leaves the short-time bound of Proposition 4.2 without a complete proof as written. The gap is likely fixable by extending Lemma 4.4 to arbitrary (z,h) or by giving a separate off-diagonal estimate, but the current derivation is not self-contained.
minor comments (3)
  1. [§4.4 and §5] The definitions of \tilde Q_{k,ℓ} in §4.4 and of \tilde Q^μ_{k,ℓ} in §5 write '(u,ℓ) ∈ V' instead of '(u,h) ∈ V'; this is a typo that should be corrected.
  2. [Lemma 4.4] In the decomposition of the B^c term, the display reads '+ Ez[...]' where the first expectation is Ex; presumably this should be Ex throughout.
  3. [§3.1, Lemma 3.9] The lower bound E[Z_{k,ℓ}|\tilde Z_{k,ℓ}>0] ≥ cℓ is stated without the rounding details in the definition of the tooth heights; adding a sentence clarifying that ℓ/3 and 2ℓ/3 are interpreted up to integer parts would improve readability.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the central derivation is self-contained and uses prior results as lemmas; the flagged Borel-Cantelli coverage gap is a correctness issue, not a circularity.

full rationale

The paper's main derivation for the finite-collision half of Theorem 4.1 is self-contained. It proves heat-kernel upper bounds (Proposition 4.2, Lemma 4.4, Lemmas 4.7–4.8) from Markov-chain arguments, concentration estimates for tooth-excursion times (Proposition 4.6), and standard planar random-walk facts (Lemma 2.1, classical Green-kernel bounds). These estimates are then fed into a Borel-Cantelli summation via Lemma 4.11. None of these steps is defined in terms of the collision conclusion, and no fitted parameter is renamed as a prediction. The Green kernel criterion (2.4) and Corollary 2.3 from Barlow–Peres–Sousi [5] are used as genuine external lemmas, not as self-citations; the infinite-collision side γ ≤ 1 is explicitly attributed to [5] rather than presented as new. The only self-citation in the related-work section, [10], is not load-bearing. The reader's identified issue is a coverage gap in Section 4.4 (and Section 3.1): the sets \tilde Q_{k,ℓ} with ℓ ∈ {2,4,...,2^{j0}} do not actually exhaust the vertex set, because h=0 and heights above 2^{j0+1}/3 are omitted. The text asserts "the sets (\tilde Q_{k,ℓ})_{k,ℓ} with k ≥ 0 and ℓ ∈ L(k) exhaust the vertex set V of the infinite graph G," which is false as written. However, this is a correctness/completeness gap in the Borel-Cantelli partition, not circularity: the argument does not assume the conclusion, and the paper's own heat-kernel bounds appear capable of controlling the omitted regions. The circularity score is therefore low, reflecting only the presence of a repairable technical gap rather than any self-referential derivation.

Assumptions & free parameters 0 free parameters · 8 assumptions · 0 invented entities

The paper introduces no new entities and no fitted parameters. The constants gamma, alpha, beta are mathematical parameters in the theorem statements, not free parameters fitted to data. The central claims rest on standard probabilistic tools and imported results on fractals and percolation; the new work is proving heat kernel bounds for combs with slowly growing teeth.

assumptions (8)
  • domain assumption Volume regularity (VG): |B_tildeG(v,k)| is bounded between c k^alpha and C k^alpha with alpha in [1,2]
    Assumed in Theorem 3.2; standard for fractal graphs such as the Sierpiński gasket.
  • domain assumption Resistance regularity (RG): R_eff(u,v) is bounded between c d(u,v)^(beta-alpha) and C d(u,v)^(beta-alpha) with 2 <= beta <= alpha+1 and beta > alpha
    Assumed in Theorem 3.2; controls exit times and heat kernels of the base graph via the literature on strongly recurrent graphs.
  • domain assumption Supercritical Bernoulli bond percolation p>1/2 on Z^2, with unique infinite cluster C_infty conditioned to contain the origin
    Used in Section 5; standard in percolation theory.
  • standard math Quenched heat kernel bounds for supercritical percolation (Barlow [2], eq 5.9-5.11): p_n^{C_infty}(x,y) <= C/n for n >= vartheta_x or ||x-y||_1
    Imported from literature; used in Lemma 5.2 and Proposition 5.5.
  • standard math Effective resistance bounds for percolation clusters in boxes (Abe [1], Boivin-Rau [6], eq 5.3 and 5.5)
    Used to prove the infinite collision property and truncated Green function bounds for the percolation base.
  • standard math Green kernel criterion for infinite collisions (Barlow-Peres-Sousi [5, Theorem 3.1], eq 2.4)
    Used to prove the infinite collision side for all three base graph families.
  • standard math Occupation time estimate for Z^2 simple random walk: E[(U_t)^2] <= C log^4 t (Erdős-Taylor [15])
    Used in Lemma 2.1 and in the proof of Lemma 4.4 for the horizontal walk.
  • standard math Standard Markov chain tools: strong Markov property, Gambler's ruin, Chernoff bounds, Borel-Cantelli
    Used throughout the proofs.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Collisions of random walks on comb graphs with a planar base." pith.science (2026). https://pith.science/paper/CE34G3VW

@misc{pith2026250819814,
  author       = {Pith},
  title        = {Pith review of: Collisions of random walks on comb graphs with a planar base},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/CE34G3VW}},
  note         = {Machine review of arXiv:2508.19814}
}
abstract

In this article we study collisions of two independent random walks on comb graphs $\mathrm{Comb}(\tilde{G},f)$ for a large class of recurrent planar graphs $\tilde{G}$ and profile functions $f$, the latter governing the length of vertical segments (called "teeth") attached to vertices of the base graph $\tilde{G}$. We prove that the number of collisions of two random walks starting from the same site undergoes a phase transition depending on the growth of $f$. As a benchmark example, we show that for $\mathrm{Comb}(\mathbb{Z}^2,f_\gamma)$ with $f_\gamma(z) = \log^{\gamma}(\|z\|_\infty\vee 1)$ and $\|\cdot \|_\infty$ denoting the supremum norm, two independent random walks started at the origin collide finitely often almost surely if $\gamma > 1$, answering a question of Barlow, Peres, and Sousi, see arXiv:1003.3255, who established that infinitely many collisions occur almost surely if $\gamma \leq 1$. We furthermore establish phase transitions in the cases where the base graph $\tilde{G}$ is pre-fractal, or a typical realization of a supercritical cluster of planar Bernoulli bond percolation.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 2 Pith papers

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

  1. Collisions of random walks in unimodular random graphs: applications to the random geometric graph and long-range percolation

    math.PR 2026-07 accept novelty 6.5 of 10

    Under unimodularity plus Green-function integrability, transient random graphs have the finite collision property; this classifies voter-model stationary measures on Gilbert, Delaunay, Gabriel and long-range percolati...

  2. Infinite collisions of simple random walks on random recursive trees generated by Bernoulli sequences

    math.PR 2026-07 conditional novelty 5.5 of 10

    Random recursive trees generated by Bernoulli attachment almost surely have exactly one topological end and the infinite collision property for two independent simple random walks.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages · cited by 2 Pith papers

  1. [1]

    Y. Abe. Effective resistances for supercritical percolation clusters in boxes.Ann. Inst. Henri Poincaré Probab. Stat., 51(3):935–946, 2015

    work page 2015

  2. [2]

    Randomwalksonsupercriticalpercolationclusters

    M.Barlow. Randomwalksonsupercriticalpercolationclusters. Ann. Probab., 32(4):3024– 3084, 2004

    work page 2004

  3. [3]

    Random walks and heat kernels on graphs, volume438of London Mathematical Society Lecture Note Series

    M.Barlow. Random walks and heat kernels on graphs, volume438of London Mathematical Society Lecture Note Series. Cambridge University Press, Cambridge, 2017

    work page 2017

  4. [4]

    Barlow, T

    M. Barlow, T. Coulhon, and T. Kumagai. Characterization of sub-Gaussian heat kernel estimates on strongly recurrent graphs. Comm. Pure Appl. Math., 58(12):1642–1677, 2005

    work page 2005

  5. [5]

    Barlow, Y

    M. Barlow, Y. Peres, and P. Sousi. Collisions of random walks.Ann. Inst. Henri Poincaré Probab. Stat., 48(4):922–946, 2012

    work page 2012

  6. [6]

    Boivin and C

    D. Boivin and C. Rau. Existence of the harmonic measure for random walks on graphs and in random environments.J. Stat. Phys., 150(2):235–263, 2013

    work page 2013

  7. [7]

    D. Chen, B. Wei, and F. Zhang. A note on the finite collision property of random walks. Statist. Probab. Lett., 78(13):1742–1747, 2008

    work page 2008

  8. [8]

    Chen and D

    X. Chen and D. Chen. Two random walks on the open cluster ofZ2 meet infinitely often. Sci. China Math., 53(8):1971–1978, 2010

    work page 1971

Show all 23 references
  1. [9]

    Chen and D

    X. Chen and D. Chen. Some sufficient conditions for infinite collisions of simple random walks on a wedge comb.Electron. J. Probab., 16:no. 49, 1341–1355, 2011

    2011

  2. [10]

    Croydon and Umberto De Ambroggio

    David A. Croydon and Umberto De Ambroggio. Triple collisions on a comb graph.To appear in Electron. J. Probab., 2024+

    2024

  3. [11]

    Dembo, Y

    A. Dembo, Y. Peres, J. Rosen, and A. Zeitouni. Thick points for planar brownian motion and the Erdős-Taylor conjecture on random walk.Acta Math., 186(239):270, 2001

    2001

  4. [12]

    Devulder

    A. Devulder. Infinitely many collisions between a recurrent simple random walk and arbitrary many transient random walks in a subballistic random environment.Electron. Comm. Probab., 30:1–11, 2025

    2025

  5. [13]

    Devulder, N

    A. Devulder, N. Gantert, and F. Pène. Collisions of several walkers in recurrent random environments. Electron. J. Probab., 23:Paper No. 90, 34, 2018

    2018

  6. [14]

    Devulder, N

    A. Devulder, N. Gantert, and F. Pène. Arbitrary many walkers meet infinitely often in a subballistic random environment.Electron. J. Probab., 24:Paper No. 100, 25, 2019

    2019

  7. [15]

    Erdős and S

    P. Erdős and S. J. Taylor. Some problems concerning the structure of random walk paths. Acta Math. Acad. Sci. Hungar, 11:137–162, 1960

    1960

  8. [16]

    Grimmett.Percolation

    G. Grimmett.Percolation. Springer, 1999

    1999

  9. [17]

    Halberstam and T

    N. Halberstam and T. Hutchcroft. Collisions of random walks in dynamic random envi- ronments. Electron. J. Probab., 27:Paper No. 8, 18, 2022

    2022

  10. [18]

    Hutchcroft and Y

    T. Hutchcroft and Y. Peres. Collisions of random walks in reversible random graphs. Electron. Commun. Probab., 20:no. 63, 6, 2015

    2015

  11. [19]

    Krishnapur and Y

    M. Krishnapur and Y. Peres. Recurrent graphs where two independent random walks collide finitely often.Electron. Comm. Probab., 9:72–81, 2004

    2004

  12. [20]

    Coupling from the past

    D. A. Levin and Y. Peres.Markov chains and mixing times. American Mathematical Society, Providence, RI,2017. Secondedition, WithcontributionsbyElizabethL.Wilmer, With a chapter on “Coupling from the past” by James G. Propp and David B. Wilson

    2017

  13. [21]

    Lyons and Y

    R. Lyons and Y. Peres.Probability on trees and networks, volume 42 ofCambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, New York, 2016. COLLISIONS OF RANDOM W ALKS ON COMB GRAPHS WITH A PLANAR BASE 41

    2016

  14. [22]

    Sapozhnikov

    A. Sapozhnikov. Random walks on infinite percolation clusters in models with long-range correlations. Ann. Probab., 45(3):1842–1898, 2017

    2017

  15. [23]

    Watanabe

    S. Watanabe. Infinite collision property for the three-dimensional uniform spanning tree. Int. J. Math. Ind., 15:Paper No. 2350005, 10, 2023. Department of Mathematics, National University of Singapore Current address: 10 Lower Kent Ridge Road, National University of Singapore...

    2023

Pith tools

Reviewed August 5, 2026 · model on record in the stance chip above.