Two-type annihilating systems on the complete and star graph

David Sivakoff; Grayson York; Irina Cristali; Matthew Junge; Remy Kassem; Yufeng Jiang

REVIEW 2 major objections 2 minor 29 references

Two-type annihilating systems on the complete and star graph

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

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

Pith's one-line read Two-type annihilating systems on complete and star graphs survive asymptotically longer than their one-type counterparts, with sharp bounds on the star graph for every speed bias.

desk verdict Solid finite-graph results for two-type annihilation, with localized proof errors that don't threaten the main theorems. read the letter →

arxiv 1908.03218 v4 pith:SYHYQNWJ submitted 2019-08-08 math.PR

Irina Cristali , Yufeng Jiang , Matthew Junge , Remy Kassem , David Sivakoff , Grayson York This is my paper · ORCID

classification math.PR MSC 60K3505C8160J10

keywords annihilatingparticlesystemstwo-typeextinctiontimecompletegraphstarrandomwalkscouponcollectorasymmetricspeeds

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

This paper asks how long red and blue particles take to annihilate each other on two finite graphs, the complete graph on 2n vertices and the star graph with 2n leaves plus one core, when each step samples a random particle to walk and opposite colors annihilate on contact. Its central claim is that a two-type system survives asymptotically longer than the one-type system, because like-colored particles cluster and create safe sites. On the complete graph the expected extinction time is shown to be at least 2n log n, twice the one-type baseline, and at most 20n(log n)^2/log log n. On the star graph the results are sharper: with symmetric speeds the excess over 2n is between c√n and C√n log n, and with asymmetric speeds the leading coefficient is identified up to universal constants, growing like log(1/(1-p)) as the speed bias p approaches 1. The p=1 case, where red particles are immobile, has an exact distributional formula.

What carries the argument

The load-bearing object is the accounting identity in Lemma 7, A_t = 2n - t + C_t + 2M_t, where A_t is the number of surviving particles, C_t the number at the core, and M_t the number of times a core particle is sampled and moves to a leaf without annihilating. The identity converts extinction-time questions into estimates of core occupancy and non-annihilating core exits; those are then controlled by couplings to simple random walks for the symmetric case and to a coupon-collector process for p near 1.

What would settle it

Run the p=1 star process for n = $10^{2}$, $10^{3}$, $10^{4}$ and compare the empirical distribution of the extinction time against 2∑_{i=1}^n X(i/2n); a systematic deviation would falsify Theorem 6 and the master formula behind it. Alternatively, for a fixed p close to 1, measure $ET^{2}$_p(S_{2n})/n for increasing n and check that the coefficient lies between approximately 4 and 12 times log(1/(1-p)), as Theorem 5 requires; an empirical coefficient outside that window at large n would refute the asymptotics.

Watch

Extended reading notes

Core claim

The paper establishes that for all p in [1/2,1] the two-type extinction time $T^{2}$_p(K_{2n}) on the complete graph stochastically dominates a sum of geometric random variables, giving E $T^{2}$_p(K_{2n}) ≥ 2n log n, while a site-capacity argument gives E $T^{2}$_p(K_{2n}) ≤ 20n(log n)^2/log log n. Since the one-type extinction time on the complete graph is n log n + γn + Θ(1), the two-type process survives at least twice as long asymptotically. On the star graph, the master formula A_t = 2n - t + C_t + 2M_t yields, for p = 1/2, that E $T^{2}$_{1/2}(S_{2n}) - 2n has order between √n and √n log n; for p ∈ (1/2,1), the leading coefficient lies between 2 + (2p-1)/2 and 2/(1-p); and as p ↑ 1 the coefficient grows like log(1/(1-p)) with universal constants. The limiting p=1 case is equal in distribution to 2∑_{i=1}^n X(i/2n), so its expectation is 4n log n + 4γn + Θ(1).

Load-bearing premise

The star-graph theorems all rest on Lemma 7's identity A_t = 2n - t + C_t + 2M_t, which assumes the particle count is determined exactly by elapsed time, the number of particles at the core, and the number of non-annihilating core exits; if collisions could occur without changing those three quantities, the identity and the bounds built on it would fail.

Editorial extensions

If this is right

On the complete graph, the expected extinction time of the two-type system is at least twice the one-type time, so like-colored clustering genuinely slows neutralization on dense graphs.
On the star graph with symmetric speeds, the extinction time exceeds 2n by a term of order between √n and √n log n, whereas the one-type correction is only logarithmic, making clustering at the core visible in the second-order term.
For asymmetric speeds with p ∈ (1/2,1), the leading coefficient of the star-graph extinction time is strictly larger than in the symmetric case, with explicit universal bounds in p.
As the speed bias approaches 1, the star-graph extinction time grows like log(1/(1-p)) n, with the leading constant pinned between 4 and 12; the conjectured sharp constant is 4.
When p=1 the extinction time on the star graph has an exact distributional identity, 2∑_{i=1}^n X(i/2n), giving expectation 4n log n + 4γn + Θ(1).

Reading between the lines

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

The logarithmic gap between the complete-graph upper and lower bounds suggests the true order may be n log n with a coefficient of 2; a sharper upper bound of O(n log n) would confirm that the complete graph's two-type system is only twice as slow as the one-type system.
The master formula's structure suggests the same core-versus-leaves bookkeeping could transfer to any graph with a distinguished hub and many leaves, such as split graphs or trees with small diameter, where similar √n or log(1/(1-p)) corrections might appear.
The coupon-collector interpretation for p near 1 indicates that the bottleneck is blue particles visiting every initially red leaf, so the sharp constant may depend only on the sampling bias and not on finer graph structure; this could be tested by replacing the star's leaves with a regular tree and comparing coefficients.

Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Desk Editor's Note

read the letter

You should know this paper before the next seminar: it is the first systematic study of two-type annihilation times on finite graphs, and it delivers real results. For the complete graph it shows the two-type extinction time is at least 2n log n, twice the one-type time, with an upper bound of n log^2 n/log log n. For the star graph the picture is sharper: symmetric speeds give a second-order term between sqrt(n) and sqrt(n) log n, and asymmetric speeds give leading constants matching up to constants, via a coupon-collector mechanism for p near 1. The p=1 case gives an exact distributional identity. The master formula in Lemma 7, A_t = 2n - t + C_t + 2M_t, is a neat tool and it checks out by induction; the lower-bound coupling to random walks and the coupon-collector arguments are fresh.

The soft spots are localized but real. Lemma 13's displayed closed form (12) is algebraically incorrect: for C=4 it evaluates negative while the integral is positive. The bound is still true, but the formula needs fixing. Lemma 10 states ED_{2n} ~ sqrt(2n/pi), but its own sum formula 1 + sum binom(2k,k)/4^k gives the constant 2/sqrt(pi), not sqrt(2/pi). Again the theorem is unaffected because only the order matters. More substantively, Lemma 18's concentration step is not justified as printed: the variance bound Var(V') <= (1-p)n and Chebyshev give P(...) = O(1/((1-p)n)), not 3/n. The final upper bound in Lemma 19 only needs O(1/n) with the constant allowed to depend on p, so this is repairable—I read it as a genuine typos rather than a crack in the argument—but the proof as written has a gap.

None of these affect the main qualitative claims. I'd send this to a serious referee, with the request that they check the constants in Section 5.2 and the two asymptotic statements. The paper introduces a quantity worth having and handles it honestly. If you work on interacting particle systems, finite graphs, or even coupon-collector variants, it is worth a slot in your reading group.

Referee Report

2 major / 2 minor

Summary. The paper introduces a discrete-time two-type annihilating particle system on the complete graph K_{2n} and the star graph S_{2n}, with equal initial numbers of red and blue particles and with blue selected with probability p≥1/2. It compares the extinction time T_p^2(G) with the one-type extinction time T^1(G). The main quantitative claims are: Theorem 2 gives 2n log n ≤ ET_p^2(K_{2n}) ≤ O(n(log n)^2/log log n); Theorem 3 gives ET_{1/2}^2(S_{2n}) = 2n + Θ(√n) up to a logarithmic factor in the upper bound; Theorems 4 and 5 bound the p∈(1/2,1) regime in terms of log(1/(1-p)); and Theorem 6 gives an exact distributional identity for p=1. The proofs are built around the master formula A_t = 2n - t + C_t + 2M_t, couplings to random walks, and coupon-collector estimates.

Significance. If the results stand after the repairs below, this is a useful and apparently novel contribution: it initiates the study of extinction times for two-type annihilating systems on finite graphs and identifies clustering as the reason the two-type system survives asymptotically longer than the one-type system. The proof strategy is self-contained and mostly transparent: the master formula is verified by induction, the p=1 result is an exact distributional identity, and the stochastic bounds use explicit geometric and coupon-collector arguments rather than fitted parameters. The paper also states open problems and conjectures that give the work additional value.

major comments (2)

[§5.2, Lemma 18] The proof bounds Var(V′) ≤ (1−p)n and then asserts P(V′ ≥ (1−p)n) ≤ 3/n. Chebyshev's inequality gives P(|V′−EV′| ≥ (1−p)n/2) ≤ 4 Var(V′)/((1−p)^2 n^2) ≤ 4/((1−p)n), which is not ≤ 3/n for any p∈[1/2,1); indeed 4/(1−p) > 3, so the printed variance bound cannot yield 3/n. This is load-bearing for the upper bound in Theorem 5 through Lemma 19. The gap is repairable: since Lemma 19 only needs an O(1/n) bound, replace the asserted 3/n by 4/((1−p)n) and adjust the subsequent 4/n estimate in Lemma 19 accordingly; the resulting error is O_p(1) and does not affect the leading constant in Theorem 5. The statements of Lemmas 18 and 19 should be corrected in the revision.
[§4.1, Lemma 10] The claimed asymptotics ED_{2n} ∼ √(2n/π) is inconsistent with the displayed identity ED_{2n} = 1 + ∑_{k=1}^{n-1} 2^{-2k} binom(2k,k). Stirling gives 2^{-2k} binom(2k,k) ∼ 1/√(πk), so the sum is ∼ 2√(n/π). Theorem 3(i) uses the lemma to obtain the constant (32π)^{-1/2}; the corrected value gives a larger constant, so the theorem remains true, but the printed lemma and the sentence 'Integrating ... gives the claimed asymptotic formula' must be fixed.

minor comments (2)

[§4, Lemma 13] Equation (12) is algebraically incorrect: for C=4 the printed expression is negative while the integral is approximately 1.80. The conclusion of the lemma is still true, for instance by bounding √(2n−x) ≤ √(2n) and integrating x^{-1} dx over [1,2n]; the closed form should be corrected or replaced by this simpler estimate.
[Throughout] There are several typographical and OCR artifacts in the text, including 'throug h-' in the abstract and 'Micha/suppress l' in the bibliography; a careful proofreading pass is needed.

Circularity Check

0 steps flagged · score 0.0 of 10

Self-contained proof chain; no fitted inputs or load-bearing self-citations.

full rationale

The paper's derivation chain is self-contained and does not reduce any target result to its own input. The one-type baseline (Proposition 1) is computed by decomposing extinction times into sums of independent geometric random variables. The two-type lower bounds (Theorem 2(1), Theorem 3(i), Theorem 4 lower, Theorem 5 lower) use either stochastic domination by geometrics or the master formula A_t = 2n - t + C_t + 2M_t (Lemma 7), which is proved by induction over all collision and non-collision transitions at the core. The upper bounds (Theorem 2(2), Theorem 3(ii), Theorem 4 upper, Theorem 5 upper, Lemma 19) are coupling and coupon-collector estimates with explicit constants; no parameter is fitted to the quantity being predicted. Theorem 6 is an exact distributional calculation: Lemma 7 at t = T gives T = 2n + 2M, and M is written as a sum of independent (X(i/2n) - 1) geometrics because each non-annihilating core escape before annihilation has success probability i/2n. No target distribution is assumed as an input. The citation to [DGJ+17] near Theorem 6 is contextual ("the setting in [DGJ+17]") and no load-bearing result is imported from it; the distributional identity is proved in the present paper. Background citations to Arratia, Bramson-Lebowitz, and others are used only for comparison and motivation. The issues noted by scrutiny (Lemma 18's printed Chebyshev bound is numerically too weak as stated, Lemma 10's claimed asymptotic √(2n/π) conflicts with its own displayed sum formula, and Lemma 13's equation (12) is algebraically suspect) are correctness or bookkeeping concerns, not circularity: they do not define the conclusions into the hypotheses, and repairing them would not change the structural derivation. Consequently there is no significant circularity.

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

No free parameters, fitted values, or invented entities. The paper introduces no new stochastic objects beyond the process under study; all constants are explicit universal constants.

assumptions (5)

domain assumption The discrete-time process is the embedded jump chain of a continuous-time annihilating random walk system.
Used in the introduction to motivate the model and the interpretation of p as a speed ratio; the theorems are stated for the discrete-time process and do not rely on this equivalence.
domain assumption In the one-type system at most one particle occupies each site.
Required for Proposition 1 to decompose T^1 into independent geometric phases; it follows from annihilation upon meeting.
standard math Standard random walk estimate ED_t ~ sqrt(2n/pi) for p=1/2.
Used in Theorem 3(i); proven within Lemma 10 using the martingale W_t^2 - t and Stirling's approximation.
standard math Chernoff and Chebyshev bounds for binomial and geometric random variables.
Used in Lemmas 16 and 18 to control large deviations in the coupon collector arguments.
standard math Wald's identity for random sums.
Used to convert the stochastic upper bound in Lemma 11 into the expectation bound in Theorem 3(ii) and Lemma 19.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Two-type annihilating systems on the complete and star graph." pith.science (2026). https://pith.science/paper/SYHYQNWJ

@misc{pith2026190803218,
  author       = {Pith},
  title        = {Pith review of: Two-type annihilating systems on the complete and star graph},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/SYHYQNWJ}},
  note         = {Machine review of arXiv:1908.03218}
}

read the original abstract

Red and blue particles are placed in equal proportion through-out either the complete or star graph and iteratively sampled to take simple random walk steps. Mutual annihilation occurs when particles with different colors meet. We compare the time it takes to extinguish every particle to the analogous time in the (simple to analyze) one-type setting. Additionally, we study the effect of asymmetric particle speeds.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 29 canonical work pages

[1]

Richard Arratia, Limiting point processes for rescalings of coalescing and annihilating random walks on Z ^d , The Annals of Probability (1981), 909--936

work page 1981
[2]

, Site recurrence for annihilating random walks on Z ^d , Ann. Probab. 11 (1983), no. 3, 706--713

work page 1983
[3]

Riti Bahl, Philip Barnet, Tobias Johnson, and Matthew Junge, Diffusion-limited annihilating systems and the increasing convex order, arXiv ID:2104.12797 (2021)

work page Pith review arXiv 2021
[4]

2, 183--196

Maury Bramson and David Griffeath, Asymptotics for interacting particle systems on Z ^d , Zeitschrift f \"u r Wahrscheinlichkeitstheorie und verwandte Gebiete 53 (1980), no. 2, 183--196

work page 1980
[5]

21, 2397

Maury Bramson and Joel L Lebowitz, Asymptotic behavior of densities in diffusion-dominated annihilation reactions, Physical review letters 61 (1988), no. 21, 2397

work page 1988
[6]

1, 88--94

, Asymptotic behavior of densities in diffusion dominated two-particle reactions, Physica A: Statistical Mechanics and its Applications 168 (1990), no. 1, 88--94

work page 1990
[7]

1-2, 297--372

, Asymptotic behavior of densities for two-particle annihilating random walks, Journal of statistical physics 62 (1991), no. 1-2, 297--372

work page 1991
[8]

, Spatial structure in diffusion-limited two-particle reactions, Ann. Appl. Probab. 11 (2001), no. 1, 121--181

work page 2001

Show all 29 references

[9]

4, 1748--1758

Colin Cooper, Robert Elsasser, Hirotaka Ono, and Tomasz Radzik, Coalescing random walks and voting on connected graphs, SIAM Journal on Discrete Mathematics 27 (2013), no. 4, 1748--1758

2013
[10]

399--410

Colin Cooper, Alan Frieze, and Tomasz Radzik, Multiple random walks and interacting particle systems, International Colloquium on Automata, Languages, and Programming, Springer, 2009, pp. 399--410

2009
[11]

Discrete Math

Colin Cooper, Alan Frieze, and Tomasz Radzik, Multiple random walks in random regular graphs, SIAM J. Discrete Math. 23 (2009), no. 4, 1738--1761

2009
[12]

4, 1333--1366

J Theodore Cox, Coalescing random walks and voter model consensus times on the torus in Z ^d , The Annals of Probability 17 (1989), no. 4, 1333--1366

1989
[13]

Cabezas, L

M. Cabezas, L. T. Rolla, and V. Sidoravicius, Non-equilibrium phase transitions: Activated random walks at criticality, Journal of Statistical Physics 155 (2014), no. 6, 1112--1125

2014
[14]

3, 587--615

, Recurrence and density decay for diffusion-limited annihilating systems, Probability Theory and Related Fields 170 (2018), no. 3, 587--615

2018
[15]

Damron , J

M. Damron , J. Gravner , M. Junge , H. Lyu , and D. Sivakoff , Parking on transitive unimodular graphs , ArXiv e-prints: 1710.10529. To appear in Annals of Applied Probability (2017)

2017 arXiv
[16]

49, Cambridge university press, 2019

Rick Durrett, Probability: theory and examples, vol. 49, Cambridge university press, 2019

2019
[17]

Erdos and P

P. Erdos and P. Ney, Some problems on random intervals and annihilating particles, Ann. Probab. 2 (1974), no. 5, 828--839

1974
[18]

1, 23--45

Christina Goldschmidt and Micha Przykucki, Parking on a random tree, Combinatorics, Probability and Computing 28 (2019), no. 1, 23--45

2019
[19]

Tobias Johnson , Matthew Junge , Hanbaek Lyu , and David Sivakoff , Particle density in diffusion-limited annihilating systems , arXiv e-prints (2020), arXiv:2005.06018

2020 arXiv
[20]

956--965

Varun Kanade, Frederik Mallmann-Trenn, and Thomas Sauerwald, On coalescence time in graphs: When is coalescing as fast as meeting?, Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SIAM, 2019, pp. 956--965

2019
[21]

Kang and S

K. Kang and S. Redner, Scaling approach for the kinetics of recombination processes, Phys. Rev. Lett. 52 (1984), 955--958

1984
[22]

Konheim and Benjamin Weiss, An occupancy discipline and applications, SIAM Journal on Applied Mathematics 14 (1966), no

Alan G. Konheim and Benjamin Weiss, An occupancy discipline and applications, SIAM Journal on Applied Mathematics 14 (1966), no. 6, 1266--1274

1966
[23]

Lee and John Cardy, Renormalization group study of the A+B 0 diffusion-limited reaction , Journal of Statistical Physics 80 (1995), no

Benjamin P. Lee and John Cardy, Renormalization group study of the A+B 0 diffusion-limited reaction , Journal of Statistical Physics 80 (1995), no. 5, 971--1007

1995
[24]

13, 1977, pp

J-C Lootgieter, Probl \`e mes de r \'e currence concernant des mouvements al \'e atoires de particules sur z avec destruction , Annales de l'IHP Probabilit \'e s et statistiques, vol. 13, 1977, pp. 127--139

1977
[25]

Marie-Louise Lackner and Alois Panholzer, Parking functions for mappings, Journal of Combinatorial Theory, Series A 142 (2016), 1--28

2016
[26]

1-2, 215--218

AA Ovchinnikov and Ya B Zeldovich, Role of density fluctuations in bimolecular reaction kinetics, Chemical Physics 28 (1978), no. 1-2, 215--218

1978
[27]

Micha Przykucki, Alexander Roberts, and Alex Scott, Parking on the integers, arXiv preprint arXiv:1907.09437 (2019)

2019 arXiv
[28]

Diane Schwartz, On hitting probabilities for an annihilating particle model, The Annals of Probability (1978), 398--403

1978
[29]

5, 2642--2647

Doug Toussaint and Frank Wilczek, Particle--antiparticle annihilation in diffusive motion, The Journal of Chemical Physics 78 (1983), no. 5, 2642--2647

1983

Pith tools

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

[1] [1]

Richard Arratia, Limiting point processes for rescalings of coalescing and annihilating random walks on Z ^d , The Annals of Probability (1981), 909--936

work page 1981

[2] [2]

, Site recurrence for annihilating random walks on Z ^d , Ann. Probab. 11 (1983), no. 3, 706--713

work page 1983

[3] [3]

Riti Bahl, Philip Barnet, Tobias Johnson, and Matthew Junge, Diffusion-limited annihilating systems and the increasing convex order, arXiv ID:2104.12797 (2021)

work page Pith review arXiv 2021

[4] [4]

2, 183--196

Maury Bramson and David Griffeath, Asymptotics for interacting particle systems on Z ^d , Zeitschrift f \"u r Wahrscheinlichkeitstheorie und verwandte Gebiete 53 (1980), no. 2, 183--196

work page 1980

[5] [5]

21, 2397

Maury Bramson and Joel L Lebowitz, Asymptotic behavior of densities in diffusion-dominated annihilation reactions, Physical review letters 61 (1988), no. 21, 2397

work page 1988

[6] [6]

1, 88--94

, Asymptotic behavior of densities in diffusion dominated two-particle reactions, Physica A: Statistical Mechanics and its Applications 168 (1990), no. 1, 88--94

work page 1990

[7] [7]

1-2, 297--372

, Asymptotic behavior of densities for two-particle annihilating random walks, Journal of statistical physics 62 (1991), no. 1-2, 297--372

work page 1991

[8] [8]

, Spatial structure in diffusion-limited two-particle reactions, Ann. Appl. Probab. 11 (2001), no. 1, 121--181

work page 2001