Pith. sign in

REVIEW 2 major objections 2 minor 19 references

Large deviation principle for friendship-biases in Galton--Watson trees

T0 review · 2 major / 2 minor · reviewed 2026-06-26 · grok-4.3

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

Pith's one-line read Infinite Galton-Watson trees obey a large deviation principle for the fractions of friendship-bias types observed along random downward paths.

desk verdict The paper sets up an LDP for friendship-bias type fractions along paths in GW trees and works out the binary case numerically, but the rate function as described looks like it applies Sanov directly without adjusting for the Markov chain induced by size-biasing. read the letter →

arxiv 2606.17381 v1 pith:BB6Q2KV3 submitted 2026-06-16 math.PR

Frank den Hollander , Azadeh Parvaneh This is my paper · ORCID
classification math.PR
keywords largedeviationprincipleGalton-Watsontreefriendshipbiasbranchingprocessrandompathrelativeentropyratefunctionempiricalfractions
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 establishes a large deviation principle for the empirical fractions of vertices classified by their friendship bias in an infinite Galton-Watson tree. The bias of a vertex measures how its degree compares to the average degree of its neighbors, and vertices are typed negative, zero, or positive accordingly. Along a random path of branching depth l, the vector of type fractions satisfies an LDP with speed l whose rate function is obtained by minimizing relative entropy subject to a linear constraint induced by the branching structure. A reader would care because this provides a precise asymptotic description of the probability of atypical local degree patterns in random trees, which model many networked systems.

What carries the argument

The empirical type measure along the random downward path, whose large deviations are controlled by a relative-entropy minimization problem under the linear constraint coming from the offspring distribution and the definition of friendship bias.

What would settle it

Numerical computation of the empirical distribution of the type triple for large l in simulated binary Galton-Watson trees should match the exponential decay rate predicted by the variational formula; any systematic mismatch for moderate l would indicate the claim is false.

Watch

Extended reading notes

Core claim

In an infinite rooted Galton-Watson tree with i.i.d. offspring distribution, the fractions f_l^χ of vertices of each friendship-bias type χ along a uniform random downward path of length l obey a large deviation principle as l tends to infinity. The speed is l and the rate function is given by a variational formula that minimizes the relative entropy of the path measure with respect to the natural branching measure, subject to a linear constraint that encodes the type frequencies. The result is derived first for binary branching, where the rate function admits qualitative analysis and numerical evaluation.

Load-bearing premise

The offspring numbers at different vertices are independent and identically distributed, and the tree is conditioned to survive forever while the downward path is sampled uniformly among all paths of length l.

Editorial extensions

If this is right

  • For binary branching the rate function possesses identifiable qualitative properties that permit its numerical computation.
  • The same variational approach applies to offspring distributions beyond the binary case.
  • Large deviation principles hold for the joint type vectors observed on any fixed finite number of random downward paths.
  • The framework supplies the first quantitative large-deviation control on vertex-type statistics inside branching trees.

Reading between the lines

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

  • If the rate function is strictly convex, the typical type vector concentrates exponentially fast around its mean value.
  • The variational problem may simplify to a closed form when the offspring law is deterministic.
  • The same large-deviation technique could be applied to other additive path functionals such as total degree or cumulative bias.
  • Replacing the single random path by a breadth-first search would yield analogous results for local sampling in tree networks.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 2 minor

Summary. The paper establishes a large deviation principle (LDP) with speed l for the empirical type fractions (f_l^χ)_{χ∈S} of friendship-bias types along a uniform random downward path of branching depth l in an infinite rooted Galton-Watson tree (conditioned to be infinite). The rate function is given by a variational formula that minimizes relative entropy subject to a linear constraint; the analysis specializes to binary branching, identifies qualitative properties of the rate function, and shows how it can be computed numerically. The setup assumes i.i.d. offspring distributions and uses the standard spine decomposition for the downward path.

Significance. If the derivation of the rate function is correct, the result supplies the first LDP for vertex-type empirical measures along paths in GW trees and demonstrates that the linear constraint can encode the friendship-bias definition. This could serve as a template for LDPs on other path functionals in branching processes, though the numerical accessibility for binary branching is a modest practical contribution.

major comments (2)
  1. [Abstract] Abstract and the variational formula (presumably §3 or §4): the claimed rate function minimizes ordinary relative entropy (Sanov-type) subject to a linear constraint. However, the sequence of types χ along the random downward path is a Markov chain whose transitions are governed by the size-biased offspring law and the friendship-bias definition (each vertex on the spine has size-biased degree). The large-deviation rate for the empirical measure of a Markov chain is the Donsker–Varadhan specific relative entropy rate, not the i.i.d. KL divergence; the linear constraint alone does not automatically replace the transition kernel. This appears load-bearing for the identification of the rate function.
  2. [Abstract] The abstract states that the offspring distribution is i.i.d. across vertices and the downward path is chosen uniformly; the spine decomposition then induces dependence. No verification is visible that the variational problem correctly recovers the Markov rate (e.g., via explicit computation of the transition kernel or comparison with the Donsker–Varadhan functional).
minor comments (2)
  1. The abstract mentions “we briefly indicate how to proceed for more general branching,” but no explicit statement of the required changes to the linear constraint or the state space appears.
  2. Notation for the set S = {−,0,+} and the fractions f_l^χ is introduced without a preliminary display equation; a displayed definition would improve readability.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for their careful reading and constructive comments. The major concerns correctly identify that the type sequence along the spine is Markovian and that explicit verification against the Donsker-Varadhan rate is required. We respond point-by-point below and will incorporate the necessary clarifications and computations.

read point-by-point responses

  1. Referee: [Abstract] Abstract and the variational formula (presumably §3 or §4): the claimed rate function minimizes ordinary relative entropy (Sanov-type) subject to a linear constraint. However, the sequence of types χ along the random downward path is a Markov chain whose transitions are governed by the size-biased offspring law and the friendship-bias definition (each vertex on the spine has size-biased degree). The large-deviation rate for the empirical measure of a Markov chain is the Donsker–Varadhan specific relative entropy rate, not the i.i.d. KL divergence; the linear constraint alone does not automatically replace the transition kernel. This appears load-bearing for the identification of the rate function.

    Authors: We agree that the sequence of friendship-bias types along the spine is a Markov chain whose transitions are determined by the size-biased offspring distribution and the type definition. Our variational formula was obtained by minimizing relative entropy subject to the linear constraint that encodes the friendship-bias condition; however, we recognize that this must be shown to coincide with the Donsker-Varadhan specific relative entropy rate of the underlying Markov chain. In the revised manuscript we will add an explicit derivation of the transition kernel on the type space S = {−,0,+} and prove that the proposed rate function equals the Donsker-Varadhan rate evaluated at the empirical measure. revision: yes

  2. Referee: [Abstract] The abstract states that the offspring distribution is i.i.d. across vertices and the downward path is chosen uniformly; the spine decomposition then induces dependence. No verification is visible that the variational problem correctly recovers the Markov rate (e.g., via explicit computation of the transition kernel or comparison with the Donsker–Varadhan functional).

    Authors: We acknowledge that the current version does not contain an explicit verification that the variational problem recovers the correct Markov-chain rate. We will insert a dedicated subsection that (i) computes the one-step transition probabilities of the type Markov chain under the size-biased law and the friendship-bias rule, and (ii) directly compares the resulting variational expression with the Donsker-Varadhan functional. The comparison will be carried out in full for the binary case that is the focus of the paper. revision: yes

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; derivation self-contained via standard LDP tools

full rationale

The abstract and description present the LDP rate function as a variational problem minimizing relative entropy subject to a linear constraint on the empirical type frequencies along the downward path. No equations or steps are shown that define a quantity in terms of itself, rename a fitted parameter as a prediction, or rely on a load-bearing self-citation whose content reduces to the present claim. The setup invokes standard Galton-Watson conditioning and spine decomposition, then applies large-deviation principles; the resulting variational formula is not exhibited as equivalent to its inputs by construction. This is the normal case of an independent derivation.

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

Based on abstract only. The claim rests on the standard i.i.d. offspring assumption of Galton-Watson trees and on the existence of the infinite tree conditioned on non-extinction; no free parameters or invented entities are introduced in the abstract.

assumptions (1)
  • domain assumption Offspring distribution is i.i.d. across vertices (standard Galton-Watson assumption)
    Invoked when defining the random tree and the downward path.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Large deviation principle for friendship-biases in Galton--Watson trees." pith.science (2026). https://pith.science/paper/BB6Q2KV3

@misc{pith2026260617381,
  author       = {Pith},
  title        = {Pith review of: Large deviation principle for friendship-biases in Galton--Watson trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/BB6Q2KV3}},
  note         = {Machine review of arXiv:2606.17381}
}
abstract

In this paper we consider the friendship-bias of the vertices in an infinite rooted Galton--Watson tree. The friendship-bias of a vertex is the difference between the average degree of the neighbours of the vertex and the degree of the vertex itself. A vertex is said to be of type $\chi \in S$, with $S = \{-,0,+\}$, when its friendship-bias is, respectively, strictly negative, zero or strictly positive. We consider the fractions $f_l^\chi$ of vertices of type $\chi \in S$ along a random downward path up to branching depth $l \in \mathbb{N}$ and derive a large deviation principle (LDP) for the triple $(f_l^\chi)_{\chi \in S}$ as $l\to\infty$. The branching depth of a vertex counts the number of branchings that occur along the path that connects the vertex to the root of the tree. The rate in the LDP is $l$, while the rate function in the LDP is identified in terms of a variational formula minimising a relative entropy under a linear constraint. We focus on the case of binary branching, for which the rate function is already quite involved. We identify the qualitative properties of the rate function and show how it can be computed numerically. We briefly indicate how to proceed for more general branching and for vertex types along a tree consisting of a finite number of random downward paths. Our paper is the first to consider large deviations of vertex types.

Figures

Figures reproduced from arXiv: 2606.17381 by the authors.

Figure 1
Figure 1. A schematic tree illustrating linear points (white), branching points (dark gray), and branching￾linear points (light gray) in a tree with binary offspring law. The structure continues infinitely beyond the dotted nodes. The following lemma, which is proved in Section 3.1, characterises the possible types of vertices in T∞. See [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗
Figure 2
Figure 2. Numerical plots for p = 1 2 and x = 3 2 , x = 2, x = 5 2 , respectively. Left: Plot of s 7→ J(x, s). The height represents the value of J(x, s), the plane represents the simplex s = (s −, s0 , 1 − s − − s 0 ). Right: The dotted region is the effective domain of s 7→ J(x, s) in the simplex. Comments: (1) Since x ∗ = 2 when p = 1 2 , the middle left figure achieves a unique zero at s = (s −, s0 , s+) = ( 7 16 , 3 16 ,… view at source ↗
Figure 3
Figure 3. Same as in [PITH_FULL_IMAGE:figures/full_fig_p038_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

19 extracted references · 3 canonical work pages

  1. [1]

    Bansaye, J

    V. Bansaye, J. Berestycki, Large deviations for branching processes in random environment, Markov Processes and Related Fields 15 (2009), 493–524

    2009

  2. [2]

    Bansaye, C

    V. Bansaye, C. B¨ oinghoff, Upper large deviations for branching processes in random environ- ment with heavy tails, Electronic Journal of Probability 16 (2011), 1900–1933

    2011

  3. [3]

    Bhattacharya, N

    B. Bhattacharya, N. Gadhiwala, F. den Hollander, P.R. Jain, T. Subramanya, The triangle friendship paradox, 2025, https://arxiv.org/abs/2507.02627

    work page arXiv 2025

  4. [4]

    Bredon,Topology and Geometry, Springer, 1993

    G.E. Bredon,Topology and Geometry, Springer, 1993

    1993

  5. [5]

    Brezis,Functional Analysis, Sobolev Spaces and Partial Differential Equations, Springer, New York, 2011

    H. Brezis,Functional Analysis, Sobolev Spaces and Partial Differential Equations, Springer, New York, 2011

    2011

  6. [6]

    W. Bryc, D. Minda, S. Sethuraman, Large deviations for the leaves in some random trees, Advances in Applied Probability 41 (2009), 845–873

    2009

  7. [7]

    Dembo, N

    A. Dembo, N. Gantert, Y. Peres, O. Zeitouni, Large deviations for random walks on Galton– Watson trees: averaging and uncertainty, Probability Theory and Related Fields 122 (2002), 241–288

    2002

  8. [8]

    Dembo, P

    A. Dembo, P. M¨ orters, S. Sheffield, Large deviations of Markov chains indexed by random trees, Annales de l’Institut Henri Poincare (B) Probability and Statistics 41 (2005), 971–996

    2005

Show all 19 references
  1. [9]

    Dembo, O

    A. Dembo, O. Zeitouni,Large Deviations Techniques and Applications, 2nd edition, Springer, New York, 1998

    1998

  2. [10]

    Dupuis, R.S

    P. Dupuis, R.S. Ellis,A Weak Convergence Approach to the Theory of Large Deviations, Wiley, New York, 1997

    1997

  3. [11]

    Grimmett, H

    G. Grimmett, H. Kesten, Random electrical networks on complete graphs, Journal of the London Mathematical Society 30 (1984), 171–192

    1984

  4. [12]

    Hazra, F

    R.S. Hazra, F. den Hollander, A. Parvaneh, The friendship paradox for sparse random graphs, Probability Theory and Related Fields, 2025, https://doi.org/10.1007/s00440-025-01365-w

    2025 doi

  5. [13]

    Hazra, F

    R.S. Hazra, F. den Hollander, A. Parvaneh, The multi-level friendship paradox for sparse random graphs, Stochastic Processes and their Applications 195 (2026), 104873

    2026

  6. [14]

    Hazra, F

    R.S. Hazra, F. den Hollander, N. Litvak, A. Parvaneh, The friendship paradox for trees, 2025, https://arxiv.org/abs/2505.21774

    2025

  7. [15]

    Hazra, E

    R.S. Hazra, E. Verbitskiy, The generalized friendship paradox for spectral centralities, Journal of Complex Networks 14 (2026), cnag001

    2026

  8. [16]

    van der Hofstad,Random Graphs and Complex Networks, Volume 1, Cambridge University Press, 2017

    R. van der Hofstad,Random Graphs and Complex Networks, Volume 1, Cambridge University Press, 2017

    2017

  9. [17]

    van der Hofstad,Random Graphs and Complex Networks, Volume 2, Cambridge University Press, 2024

    R. van der Hofstad,Random Graphs and Complex Networks, Volume 2, Cambridge University Press, 2024

    2024

  10. [18]

    den Hollander,Large Deviations, Volume 14, American Mathematical Society, 2000

    F. den Hollander,Large Deviations, Volume 14, American Mathematical Society, 2000. 36 Figure 2:Numerical plots forp= 1 2 andx= 3 2,x= 2,x= 5 2, respectively.Left: Plot ofs7→J(x, s). The height represents the value ofJ(x, s), the plane represents the simplexs= (s −, s0,1−s − −s...

    2000

  11. [19]

    2, i.e., the support does not depend onp

    Note that the right figures are the same as in Fig. 2, i.e., the support does not depend onp. 38

Pith tools

Reviewed June 26, 2026 · model on record in the stance chip above.