Rerooting multi-type branching trees: the infinite spine case

Benedikt Stufler

REVIEW 2 major objections 5 minor 1 cited by

Rerooting multi-type branching trees: the infinite spine case

T0 review · 2 major / 5 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 A conditioned multi-type Galton–Watson tree rerooted at a random vertex converges locally to a multi-type sin-tree, with the spine's type composition governed by offspring means.

desk verdict Theorem 1 overstates what the proof shows: convergence is only established for fringes at type-κ ancestors, not for the full local topology, which undermines the general statement and the irreducible applications. read the letter →

arxiv 1908.04843 v2 pith:Y4EM2TKT submitted 2019-08-13 math.PR math.CO

Benedikt Stufler This is my paper · ORCID

classification math.PRmath.CO MSC 60J8060F0505C05

keywords multi-typeGalton-Watsontreesfringedistributionslocalconvergencesin-treererootingconditionedbranchingprocessessesqui-type

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 proves that if you condition a multi-type Galton–Watson tree to be large in a mild way, pick a vertex uniformly at random, and inspect the finite neighborhoods around it, the picture stabilizes: the rerooted tree converges in the local sense to an infinite tree with a single infinite path running backwards from the marked vertex. The main theorems identify the limit for a type whose offspring mean is exactly 2, for types that appear only finitely often along that path, and for mixtures of types. Four applications give explicit limit laws for sesqui-type trees (two-type trees in which only one type branches), reducible critical trees, regular critical irreducible trees, and irreducible trees conditioned by typed population vectors. The paper's central message is that one object, the multi-type sin-tree, organizes the local geometry of a random vertex across these models.

What carries the argument

The central object is the multi-type sin-tree $\widehat T(\kappa)$: a rooted tree with a marked vertex $u_0$ and an infinite backwards-growing spine $u_0,u_1,\dots$, in which each spine vertex of type $\kappa$ carries an independent copy of the $\kappa$-size-biased stopped tree $\widehat T_\kappa$, and every other type-$\kappa$ leaf carries an independent copy of the ordinary conditioned tree $T(\kappa)$. The argument is carried by a concentration lemma for counts of extended fringe subtrees, meaning the marked subtrees spanned by a vertex and its ancestors: the conditioned tree is decomposed into a short random sequence of independent copies of $T_\kappa$, so a bounded-differences concentration inequality controls fluctuations of fringe-subtree counts, and Assumption (22) makes the summed tail vanish. The size-bias identity $P(\widehat T_\kappa=(T,u)) = P(T_\kappa=T)$, valid exactly when $E[\#_\kappa T_\kappa]=2$, is what makes the spine Markovian and converts type-$\kappa$ fringe counts into the sin-tree distribution.

What would settle it

Simulate a large sesqui-type tree conditioned on total size $n$ under a law satisfying $E[\xi]=1$ and finite covariance, and estimate the empirical probability that a uniformly chosen vertex has type 1 together with the distribution of the first few extended fringe subtrees up the spine; the theorem predicts a limit whose type-1 probability is $1/(1+E[\zeta])$ and whose spine-fringe frequencies are those of $\widehat T(1,\eta)$. A systematic discrepancy in these finite-$h$ statistics at large $n$ would refute the central claim.

Watch

Extended reading notes

Core claim

The central claim, stated as Equation (37) in Theorem 1, is that the conditional law $L((T_n,v_n^\kappa)\mid T_n)$ converges in probability to $L(\widehat T(\kappa))$, where $T_n$ is the conditioned multi-type Galton–Watson tree, $v_n^\kappa$ is a uniformly selected type-$\kappa$ vertex, and $\widehat T(\kappa)$ is the $\kappa$-biased multi-type sin-tree, provided $E[\#_\kappa T_\kappa]=2$ and Assumption (22) holds. Theorem 2 extends the limit to a type $\gamma$ that need not recur infinitely often on the spine, giving the modified sin-tree $\widehat T(\kappa,\gamma)$, and Theorem 3 mixes these limits when the rerooting vertex is drawn uniformly from a set of types, with mixing weights $p(\gamma)=E[\#_\gamma T_\kappa]$. In the applications, the limit for sesqui-type and reducible trees has one infinite-recurrence type and one finitely-recurring type, while regular critical irreducible trees and typed-population conditioned trees converge to mixtures $\widehat T(\eta)$ in which every type recurs infinitely often along the spine; in the irreducible cases the limit does not depend on the initial root type.

Load-bearing premise

The whole concentration argument rests on Assumption (22): the conditioning event defining $T_n$ must not be exponentially improbable relative to $\exp(-\epsilon s_n)$ for every $\epsilon>0$, while $s_n\to\infty$ and $P(\#_\kappa T_n\ge s_n)\to1$; if the conditioning event decays faster than this, the tail sums of the concentration inequality need not vanish and the local limit could fail.

Editorial extensions

If this is right

For critical sesqui-type trees conditioned on a total of $n$ vertices, a uniformly selected vertex sees the limit $\widehat T(1,\eta)$, where the marked vertex has type 1 with probability $1/(1+E[\zeta])$ and type 2 with probability $E[\zeta]/(1+E[\zeta])$; type 1 recurs infinitely often along the spine, while type 2 does not.
For reducible $d$-type trees with upper-triangular offspring, rerooting at a uniformly chosen vertex from any non-empty type subset $G_0$ yields the mixture $\widehat T(1,\eta)$, with $\eta$ drawn proportionally to $E[\#_i T^1]$.
For regular critical irreducible trees conditioned on a positive linear combination of type counts, the local limit is $\widehat T(\eta)$, independent of the root type chosen to start the conditioning; every type recurs infinitely often along the spine, and $\eta$ is proportional to the asymptotic type proportions $c_\gamma$.
For irreducible critical trees conditioned on an exact typed population vector $k(n)$ with $k(n)/\|k(n)\|_1\to a$, the local limit is $\widehat T(\eta)$ with $\eta$ proportional to $a$ restricted to the selected type subset.
In all four settings the convergence is quenched: the empirical distribution of local neighborhoods around a uniformly chosen vertex converges in probability to the stated sin-tree law, not merely in expectation over the random tree.

Reading between the lines

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

I infer that the mixture formula in Theorem 3 extends to any limiting type-proportion vector $w_\gamma$: if the empirical ratios $\#_\gamma T_n/\#_\kappa T_n$ converge to $w_\gamma$ (rather than specifically to $E[\#_\gamma T_\kappa]$), the same proof should give a limit in which the rerooted vertex has type $\gamma$ with probability proportional to $w_\gamma$.
I infer that the irreducibility of the limiting spine in the regular critical case is a fingerprint of the conditioning statistic: any conditioning that leaves the initial type influential should produce a limit that does depend on the starting type, so checking whether the first few spine-type frequencies match the left eigenvector of the mean matrix would test the 'forgetting' claim at a quantit
I infer that the same local-convergence scheme should apply to conditioning events with polynomially decaying probabilities, as long as the threshold sequence $s_n$ grows slowly enough for Assumption (22) to hold; the paper verifies the assumption case by case, but the mechanism itself is not tied to $n^{-3/2}$-type estimates.

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

Colleague,

The paper has a genuine gap that the reader's report didn't catch, and the stress-test note is right. Theorem 1 claims quenched convergence in the space X, whose metric compares fringes at every ancestor. The proof only establishes convergence for fringes at the h-th type-κ ancestor (Eq. 38). In the limit object T̂(κ), the immediate ancestors of the marked vertex lie inside the biased tree T̂κ and may have any type, so non-κ-root fringes have positive probability. The proof never controls their empirical frequencies. Eq. (38) is not equivalent to Eq. (37). The same problem propagates to Theorems 2–3 and the irreducible applications in §4.4–4.5.

That said, the core is not without value. Lemma 1's McDiarmid concentration for fringe counts of type-κ-rooted trees is clean, and the sin-tree construction is a sensible multi-type extension of Aldous. For the sesqui-type and reducible cases (Theorems 4 and 5), the gap may be benign because type-1 vertices have only type-1 parents, so the type-κ-ancestor fringes determine the full local limit. Those applications probably stand.

There is also a smaller unproved assertion in Lemma 3: the existence of a bounded truncation of (ξ,ζ) preserving E[ξ]=1 is used to identify d = m/D. The reader flagged it; it looks fixable but should be spelled out.

Net: the main theorems are not proven as stated, but the machinery is likely sufficient to repair them. A referee should be sent this and asked for a revised proof of full quenched convergence in X, or a restriction of the statements to settings where the parent of a random type-κ vertex is type-κ with high probability. I'd engage with it.

Referee Report

2 major / 5 minor

Summary. The paper develops a concentration inequality (Lemma 1) for counts of fringe subtrees in conditioned multi-type Galton-Watson trees and uses it to claim quenched local convergence of the tree rerooted at a uniformly chosen type-κ vertex to a multi-type version of Aldous' invariant sin-tree. Theorems 2 and 3 extend the result to non-recurring types and mixtures of types, and the applications cover sesqui-type, reducible, irreducible regular, and typed-population conditioned trees. The main proof route is: Lemma 1 gives convergence of empirical fringe counts for finite trees with root type κ; identity (36) converts these into counts of certain extended fringes; and the limiting probabilities are identified with the sin-tree construction.

Significance. If fully established, the paper would provide a unified and quite general local-limit theory for rerooted multi-type branching trees, with a clean main lemma and broad applications. Lemma 1 is a genuinely useful concentration statement, and the sin-tree construction for multi-type processes is natural. However, the central quenched-convergence claim is not proved for extended fringes whose root type differs from κ, and this gap affects most of the applications. The paper is likely correct in its conclusions, but the missing argument is substantial.

major comments (2)

[§3.2, Theorem 1 (Eqs. (37)-(38)); §2.2 (Eq. (10))]
[§3.3, Proposition 2]

minor comments (5)

[§4.2, after Eq. (70)]
[§3.2, Eq. (33); §3.3, Eq. (40); Remark 2]
[§4.2, Lemma 3]
[§4.1, Proposition 4]
[Introduction and general presentation]

Circularity Check

0 steps flagged · score 0.0 of 10

No circular reasoning found: the multi-type sin-tree limits are constructed directly from the offspring distribution and none of the paper's predictions reduce to fitted inputs or load-bearing self-citations.

full rationale

The paper's derivation chain is self-contained in the circularity sense. The limit objects T̂(κ), T̂(κ,γ), and the mixture T̂(κ,η) are defined explicitly from the offspring distribution via size-biasing identities (Eqs. (33), (35), (40)), and no parameter is fitted to the target convergence statement. Lemma 1 establishes concentration of rooted fringe counts N_T(T_n)/#κT_n toward P(T(κ)=T), and Eq. (36) is a combinatorial identity relating marked and unmarked fringe counts, not a definitional smuggling of the conclusion. The applications verify the hypotheses (22), (43), (49), (50) using external inputs such as [18], [10], and [4]; the author's own works [19], [21], [22] are cited for context, related monotype results, or provenance of material, not as the load-bearing justification for the main theorems. The skeptic's concern that Eq. (37) requires convergence of fringes at ancestors of arbitrary type while the proof only establishes convergence at type-κ ancestors is an omitted-proof/correctness issue, not a circularity: even if the gap is real, the claimed limit object is still independently defined from the model data, and the 'prediction' is not equivalent to its inputs by construction. Accordingly, no circular step is identified and the circularity score is 0.

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

The central theorems depend on a small set of standard probabilistic tools (McDiarmid, local CLT) and on domain-specific assumptions from prior literature (criticality, irreducibility, lattice properties). No free parameters are fitted to data. The only questionable item is the unproved existence of the bounded truncation ξ^(K) in Lemma 3.

assumptions (6)

standard math McDiarmid's inequality gives exponential tail bounds for functions of independent random variables that change by at most 1 in each coordinate.
Used in Lemma 1 (Equation (18)) to control ψ(Tα,Tκ_1,...,Tκ_𝓁) around its expectation; a minor coordinate-change condition is checked.
standard math Strengthened multidimensional local limit theorem for lattice distributions (Proposition 4, cited to Williamson-Rinehart and Spitzer).
The central asymptotic engine of Lemma 3; used to estimate P(S_𝓁 = y_n) uniformly in x with the additional factor R_n(x).
domain assumption The offspring distribution is critical in the κ-coordinate: E[#κTκ] = 2 (Equation (32)).
Defines the size-biased tree T̂κ and the sin-tree construction; without it the spine construction is not a probability distribution.
domain assumption For critical irreducible multitype Galton-Watson trees, [18, Prop. 2.1] supplies E[#γTγ]=2, finite exponential moments, and [18, Prop. 2.2] supplies lattice properties of |T|_ω.
Invoked in Theorems 6 and 7 to verify criticality and Assumption (22).
domain assumption Singularity analysis result [4, Thm. 28] gives n^{-3/2} asymptotics for bounded sesqui-type trees with exponential moments.
Used in Lemma 3 to identify the lattice constant d = m/D by comparison with the truncated distribution ξ^(K).
domain assumption Trees are a.s. finite and every type has positive probability to appear (Assumptions (11), (12)).
Global standing assumptions under which the depth-first representation and McDiarmid argument operate.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Rerooting multi-type branching trees: the infinite spine case." pith.science (2026). https://pith.science/paper/Y4EM2TKT

@misc{pith2026190804843,
  author       = {Pith},
  title        = {Pith review of: Rerooting multi-type branching trees: the infinite spine case},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/Y4EM2TKT}},
  note         = {Machine review of arXiv:1908.04843}
}

read the original abstract

We prove local convergence results of rerooted conditioned multi-type Galton--Watson trees. The limit objects are multitype variants of the random sin-tree constructed by Aldous (1991), and differ according to which types recur infinitely often along the backwards growing spine.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 1 Pith paper

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

Random punctured hyperbolic surfaces & the Brownian sphere
math.PR 2025-08 conditional novelty 8.0 of 10

Random Weil-Petersson punctured spheres converge, after fourth-root rescaling, to the Brownian sphere.

Reference graph

Works this paper leans on

30 extracted references · 29 canonical work pages · cited by 1 Pith paper

[1]

Abraham, J.-F

R. Abraham, J.-F. Delmas, and H. Guo. Critical multi-type Galton-Watson trees con- ditioned to be large. J. Theoret. Probab., 31(2):757–788, 2018

work page 2018
[2]

D. Aldous. Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab., 1(2):228–266, 1991

work page 1991
[3]

K. B. Athreya and P. E. Ney. Branching processes. Springer-Verlag, New York- Heidelberg, 1972. Die Grundlehren der mathematischen Wissenschaften, Band 196

work page 1972
[4]

J. P. Bell, S. N. Burris, and K. A. Yeats. Counting rooted trees: the universal law t(n) ∼Cρ−nn−3/2. Electron. J. Combin., 13(1):Research Paper 63, 64 pp. (electronic), 2006

work page 2006
[5]

de Raph´ elis

L. de Raph´ elis. Scaling limit of multitype galton–watson trees with inﬁnitely many types. Ann. Inst. H. Poincar´ e Probab. Statist., 53(1):200–225, 02 2017

work page 2017
[6]

Drmota and V

M. Drmota and V. Vatutin. Limiting distributions in branching processes with two types of particles. In Classical and modern branching processes (Minneapolis, MN, 1994), volume 84 of IMA Vol. Math. Appl. , pages 89–110. Springer, New York, 1997

work page 1994
[7]

F´ eray and I

V. F´ eray and I. Kortchemski. The geometry of random minimal factorizations of a long cycle via biconditioned bitype random trees. Annales Henri Lebesgue, 1:149–226, 2018

work page 2018
[8]

B. V. Gnedenko. On a local limit theorem of the theory of probability. Uspehi Matem. Nauk (N. S.) , 3(3(25)):187–194, 1948

work page 1948

Show all 30 references

[9]

Isp´ any and G

M. Isp´ any and G. Pap. Asymptotic behavior of critical primitive multi-type branching processes with immigration. Stoch. Anal. Appl., 32(5):727–741, 2014

2014
[10]

S. Janson. Simply generated trees, conditioned Galton-Watson trees, random allocations and condensation. Probab. Surv., 9:103–252, 2012

2012
[11]

Janson, O

S. Janson, O. Riordan, and L. Warnke. Sesqui-type branching processes. Stochastic Process. Appl., 128(11):3628–3655, 2018

2018
[12]

Miermont

G. Miermont. An invariance principle for random planar maps. In Fourth Colloquium on Mathematics and Computer Science Algorithms, Trees, Combinatorics and Proba- bilities, Discrete Math. Theor. Comput. Sci. Proc., AG, pages 39–57. Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2006

2006
[13]

Miermont

G. Miermont. Invariance principles for spatial multitype Galton-Watson trees. Ann. Inst. Henri Poincar´ e Probab. Stat., 44(6):1128–1161, 2008

2008
[14]

P´ enisson

S. P´ enisson. Beyond theQ-process: various ways of conditioning the multitype Galton- Watson process. ALEA Lat. Am. J. Probab. Math. Stat. , 13(1):223–237, 2016

2016
[15]

Riordan and L

O. Riordan and L. Warnke. The phase transition in bounded-size Achlioptas processes. arXiv:1704.08714, Apr. 2017

2017 arXiv
[16]

Rvacheva

E. Rvacheva. On the domains of attraction for multi-dimensional stable distributions. Uch. Zap. L’vov University , (29):5–54, 1954

1954
[17]

F. Spitzer. Principles of random walk . Springer-Verlag, New York-Heidelberg, second edition, 1976. Graduate Texts in Mathematics, Vol. 34

1976
[18]

Stephenson

R. Stephenson. Local convergence of large critical multi-type Galton-Watson trees and applications to random maps. J. Theoret. Probab., 31(1):159–205, 2018

2018
[19]

B. Stuﬂer. Random enriched trees with applications to random graphs. Electronic Journal of Combinatorics , 25(3), 2018

2018
[20]

B. Stuﬂer. Graphon convergence of random cographs. arXiv:1906.10355, Jun 2019

1906 arXiv
[21]

B. Stuﬂer. Local limits of large Galton–Watson trees rerooted at a random vertex. Ann. Inst. H. Poincar´ e Probab. Statist., 55(1):155–183, 02 2019

2019
[22]

B. Stuﬂer. Quenched local convergence of Boltzmann planar maps. Submitted, 2020+

2020
[23]

Tak´ acs

L. Tak´ acs. A generalization of the ballot problem and its application in the theory of queues. J. Amer. Statist. Assoc. , 57:327–337, 1962. Rerooting multi-type branching trees: the inﬁnite spine case 31

1962
[24]

Vatutin and V

V. Vatutin and V. Wachtel. Multi-type subcritical branching processes in a random environment. Advances in Applied Probability, 50(A):281–289, 2018

2018
[25]

V. A. Vatutin. The structure of the decomposable reduced branching processes. I. Finite-dimensional distributions. Theory Probab. Appl., 59(4):641–662, 2015

2015
[26]

V. A. Vatutin. The structure of decomposable reduced branching processes. II. Func- tional limit theorems. Theory Probab. Appl., 60(1):103–119, 2016

2016
[27]

V. A. Vatutin. A conditional functional limit theorem for decomposable branching processes with two types of particles. Mat. Zametki, 101(5):669–683, 2017

2017
[28]

V. A. Vatutin and E. E. Dyakonova. Decomposable branching processes with a ﬁxed extinction moment. Proc. Steklov Inst. Math. , 290(1):103–124, 2015. Published in Russian in Tr. Mat. Inst. Steklova 290 (2015), 114–135

2015
[29]

H. S. Wilf. generatingfunctionology. A K Peters, Ltd., Wellesley, MA, third edition, 2006

2006
[30]

J. A. Williamson and G. S. Rinehart. Remarks on the periodic behavior in time of sums of random variables. Teor. Verojatnost. i Primenen, 14:719–722, 1969

1969

Pith tools

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

[1] [1]

Abraham, J.-F

R. Abraham, J.-F. Delmas, and H. Guo. Critical multi-type Galton-Watson trees con- ditioned to be large. J. Theoret. Probab., 31(2):757–788, 2018

work page 2018

[2] [2]

D. Aldous. Asymptotic fringe distributions for general families of random trees. Ann. Appl. Probab., 1(2):228–266, 1991

work page 1991

[3] [3]

K. B. Athreya and P. E. Ney. Branching processes. Springer-Verlag, New York- Heidelberg, 1972. Die Grundlehren der mathematischen Wissenschaften, Band 196

work page 1972

[4] [4]

J. P. Bell, S. N. Burris, and K. A. Yeats. Counting rooted trees: the universal law t(n) ∼Cρ−nn−3/2. Electron. J. Combin., 13(1):Research Paper 63, 64 pp. (electronic), 2006

work page 2006

[5] [5]

de Raph´ elis

L. de Raph´ elis. Scaling limit of multitype galton–watson trees with inﬁnitely many types. Ann. Inst. H. Poincar´ e Probab. Statist., 53(1):200–225, 02 2017

work page 2017

[6] [6]

Drmota and V

M. Drmota and V. Vatutin. Limiting distributions in branching processes with two types of particles. In Classical and modern branching processes (Minneapolis, MN, 1994), volume 84 of IMA Vol. Math. Appl. , pages 89–110. Springer, New York, 1997

work page 1994

[7] [7]

F´ eray and I

V. F´ eray and I. Kortchemski. The geometry of random minimal factorizations of a long cycle via biconditioned bitype random trees. Annales Henri Lebesgue, 1:149–226, 2018

work page 2018

[8] [8]

B. V. Gnedenko. On a local limit theorem of the theory of probability. Uspehi Matem. Nauk (N. S.) , 3(3(25)):187–194, 1948

work page 1948