Pith. sign in

REVIEW 2 major objections 3 minor 1 cited by

The friendship paradox for trees

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

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

Pith's one-line read Every finite tree is significant for the friendship paradox: with a branching point, positive-bias vertices outnumber negative-bias vertices by at least $1+\sum_{u:d_u\ge3}(d_u-2)$, and only three-vertex paths deviate.

desk verdict Theorem 1.2(a) is false; the finite-tree lower bound collapses on a simple counterexample, so the paper needs major revision, though the infinite-tree results look salvageable. read the letter →

arxiv 2505.21774 v2 pith:X457Y5PQ submitted 2025-05-27 math.PR

Rajat Subhra Hazra , Frank den Hollander , Nelly Litvak , Azadeh Parvaneh This is my paper
classification math.PR MSC 05C8060C05
keywords friendshipparadoxtreesGalton-Watsonsignificancefriendship-biasvertex-typedensitiessize-biaseddistributionedgecorrelations
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 asks whether the friendship paradox—the observation that, on average, your friends have more friends than you do—is not just an average statement but a majority statement on trees. It proves that every finite tree is significant: the number of vertices whose neighbours' average degree exceeds their own is at least the number of vertices where the opposite happens, and if the tree has a vertex of degree at least three, the surplus is at least $1 + \sum_{u: d_u \ge 3}(d_u - 2)$. The only finite trees that are not strictly significant are paths, where the surplus is 1 for three vertices and 0 otherwise. For infinite random trees grown by a Galton-Watson process, the paper derives almost-sure formulas for the densities of positive, neutral, and negative vertices, and shows that which type dominates depends on the offspring distribution; it also computes edge-type densities and gives a sufficient condition for positive vertices to be negatively correlated along edges. These results apply because trees appear as the local limits of large sparse networks, so they identify when the paradox is a genuine majority phenomenon in such networks.

What carries the argument

The central identity is the expression for a vertex's type in terms of one generation's offspring numbers. On a rooted tree, if $u$ has $k$ children, then its degree is $k+1$; its parent has $\tilde{X}$ children in total under the size-biased distribution, and its children together account for $S_k+k$ neighbour-degrees, so the friendship-bias reduces to $(\tilde{X}+S_k-k(k+1))/(k+1)$, and the sign of this quantity fixes the type. For finite trees, the proof uses an exploration construction: starting from a branching point, subtrees are grown in sweeps, and each sweep adds at least as many positive as negative vertices, because leaves are always positive and the only negative vertices produced by paths come in pairs after a positive vertex. For infinite trees, the generation sizes form a Galton-Watson process, and a classical almost-sure convergence theorem for branching processes lets the densities be read off from the per-generation expectation of the sign of the central quantity, reducing the problem to one-vertex calculations. The size-biased distribution appears because the parent of a uniformly chosen vertex is a vertex with degree proportional to its degree.

What would settle it

For finite trees, a counterexample would be any tree with a vertex of degree at least three for which a direct count gives $N_n^+ < N_n^-$; exhaustive enumeration of all trees up to, say, ten vertices would settle this decisively, and the star with $d$ leaves confirms the predicted surplus $d-1$. For infinite trees, simulate a Galton-Watson tree with $p_1=0.4$ and $p_a=0.6$ for large $a$: the paper's Example 1.5 predicts that the fraction of positive vertices converges almost surely to a value close to $0.4$, so a persistent positive density near or above $0.5$ would falsify the density formula.

Watch

Extended reading notes

Core claim

On the paper's own terms, the central discovery is that the friendship paradox has a deterministic majority form on finite trees and a computable, distribution-dependent form on infinite Galton-Watson trees. For a finite tree $T_n$, define the friendship-bias of vertex $u$ as $\Delta_{u,n} = d_u^{-1}\sum_{v\sim u} d_v - d_u$; $u$ is positive, neutral, or negative according as $\Delta_{u,n}$ is $>0$, $=0$, or $<0$. Theorem 1.2 states that if $T_n$ has a vertex with $d_u \ge 3$, then $N_n^+ - N_n^- \ge 1 + \sum_{u: d_u\ge 3}(d_u-2)>0$, and that a path of $n$ vertices has $N_n^+ - N_n^- = \mathbf{1}_{\{n=3\}}$. For an infinite Galton-Watson tree with offspring distribution satisfying $p_0=0$, $p_1<1$, and $\sum_k (k\log k)p_k<\infty$, the paper proves that the densities $f^\chi$ of positive, neutral, and negative vertices exist almost surely and are given by $f^\chi = \sum_{k\ge 0} p_k P(\operatorname{sign}(\tilde{X}+S_k-k(k+1))=\chi)$, where $\tilde{X}$ is drawn from the size-biased offspring distribution and $S_k$ is the sum of $k$ independent offspring counts. Example 1.5 shows that $f^+ - f^-$ can be positive or negative depending on the offspring distribution, so infinite Galton-Watson trees are not always significant. Theorem 1.6 gives the analogous almost-sure formulas for the densities of directed edges of each pair of vertex types, and Theorem 1.8 gives a monotonicity condition under which positive vertices are negatively correlated along edges, with examples in both correlation directions.

Load-bearing premise

The limiting density results for infinite trees assume the offspring distribution has no zero-offspring vertices, is not deterministic one-child, and has finite $k\log k$ moment; if any of these fail, the almost-sure formulas are not proven.

Editorial extensions

If this is right

  • Every finite tree with a branching point has strictly more positive than negative vertices, with surplus at least $1 + \sum_{u: d_u \ge 3}(d_u - 2)$.
  • A path is the only finite tree that can fail strict significance, and among paths only the three-vertex path has a positive surplus, exactly 1.
  • In infinite Galton-Watson trees satisfying condition (1.2), the almost-sure densities of positive, neutral, and negative vertices are given by explicit formulas, and both $f^+>f^-$ and $f^+<f^-$ occur for suitable offspring distributions.
  • The almost-sure densities of all directed edge-type pairs exist and are given by explicit formulas; under the monotonicity condition (1.4), positive vertices are negatively correlated along edges, while Example 1.9(c) exhibits positive correlation.

Reading between the lines

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

  • The paper leaves implicit a practical consequence: in a large sparse network whose local structure is a Galton-Watson tree, the fraction of negative-bias vertices can be estimated directly from the degree distribution using Theorem 1.4, without simulating the whole network.
  • The finite-tree exploration argument suggests a natural conjecture for graphs that are locally tree-like but contain cycles: the majority property may survive until short cycles become abundant, and configuration-model graphs provide the testing ground.
  • The edge-density formulas give the coupling parameters needed to compare the sign process with independent percolation on the same tree, which could settle the authors' open question of whether positively correlated positive vertices percolate.
  • The paper's numerical finding that condition (1.4) fails for Poisson offspring in an intermediate mean-degree window suggests negative correlation of positive vertices is a small-degree phenomenon; locating the precise crossover is a concrete next step.
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 the friendship paradox on trees by classifying vertices according to the sign of the friendship-bias Delta_u = (average degree of neighbours) - d_u. For finite trees, Theorem 1.2 claims that every tree containing a vertex of degree at least 3 is strictly significant, with the quantitative lower bound N_+ - N_- >= 1 + sum_{d_u >= 3}(d_u - 2), and gives the exact count for paths. For infinite Galton-Watson trees satisfying condition (1.2), Theorem 1.4 gives almost-sure formulas for the densities of positive, neutral and negative vertices, Theorem 1.6 gives the analogous edge-type densities, and Theorem 1.8 provides a sufficient condition for negative correlation between positive parents and positive children, with Examples 1.5 and 1.9 illustrating regimes of significance and correlation.

Significance. The infinite-tree results are valuable in conception: the density formulas in Theorems 1.4 and 1.6 are explicit, algorithmically implementable, and derived with standard tools (Kesten-Stigum theorem, strong laws of large numbers, size-biased offspring distributions). The paper also honestly reports numerical limitations of Theorem 1.8. However, the finite-tree theorem that is advertised in the abstract and in Section 1.3 as a main contribution is false as stated. The explicit counterexample below shows that the claimed lower bound can fail, and the proof error in Section 2.2 is not cosmetic. Because the central finite-tree claim is load-bearing for the paper's message and is not correct, the manuscript cannot be accepted in its current form.

major comments (2)
  1. [Section 1.3, Theorem 1.2(a)] Theorem 1.2(a) is false. Let T be the tree with vertices r, a, b, c, a1, a2 and edges ra, rb, rc, aa1, aa2. The degrees are d_r = d_a = 3 and d_b = d_c = d_a1 = d_a2 = 1. Direct computation gives Delta_b = Delta_c = Delta_a1 = Delta_a2 = 2 and Delta_r = Delta_a = -4/3, so N_+ - N_- = 4 - 2 = 2. The right-hand side of (1.1) is 1 + (3-2) + (3-2) = 3. Thus the stated lower bound is violated. This is not a borderline example: the discrepancy is a full unit, and it arises from exactly the transition that the proof in Section 2.2 mishandles.
  2. [Section 2.2, Case 1] The update formula in Case 1 is incorrect. When a branching point u that was positive in T_{n_{j-1}} becomes negative in T_{n_j} after adding its d_u - 1 children, the net change in N_+ - N_- is (d_u - 1) - 1 - 1 = d_u - 3: the new children contribute +(d_u - 1), u is removed from N_+ (contributing -1), and u is added to N_- (contributing -1). The displayed formula in the paper, N_+^{n_j} - N_-^{n_j} = N_+^{n_{j-1}} - N_-^{n_{j-1}} + d_u - 1 - 1{u is neutral in T_{n_j}}, omits the second -1 for the case where u becomes negative, and the subsequent inequality with d_u - 2 is therefore invalid. The counterexample above realizes exactly this transition at vertex a: after adding its two children, a changes from positive to negative, and the increment is 0 rather than the claimed at least d_u - 2 = 1.
minor comments (3)
  1. [Section 3.2, Example 1.5] Several conditional-probability formulas in Example 1.5, such as "1 - q q / mu", lack parentheses and are typeset ambiguously; they should read e.g. (1-q) q / mu. This makes the displayed computations hard to verify.
  2. [Section 1.4.1] There is a typo: "esspecially" should be "especially".
  3. [References] Reference [8] is cited as "Probability Theory and Related Fields (2025)" without volume or article number; please provide full publication data if available.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the tree theorems are derived from the offspring distribution and explicit counting arguments, with self-citations used only for background and terminology.

full rationale

The paper's derivation chain is self-contained. Theorem 1.2 is proved by an explicit exploration construction that tracks increments of N+_n - N-_n; whether or not the argument is fully correct, it does not assume the desired lower bound as an input. The infinite-tree results in Theorems 1.4 and 1.6 are derived from the offspring distribution p through size-biased distributions, generation sums, the strong law of large numbers, and the Kesten-Stigum theorem. The formulas for f^chi and f^chitilde-chi are obtained by computing expected contributions per vertex/edge and then passing to almost-sure densities; no parameter is fitted to data and no predicted quantity is defined in terms of the quantity it is claimed to explain. Theorem 1.8 is conditional on an explicitly stated monotonicity hypothesis (1.4), and Example 1.9 computes f++ and f+ directly from p, so there is no hidden importation of the conclusion. The authors' earlier works [8] and [9] are cited for the notion of significance, background on sparse random graphs, and the multi-level friendship paradox, but none of the new theorems relies on those citations as a load-bearing premise. The external probabilistic tools used (Kesten-Stigum, SLLN, local convergence to Galton-Watson trees) are standard and independent of the paper's claims. The skeptical counterexample raised against Theorem 1.2(a), if valid, concerns mathematical correctness of a proof step, not circularity: it does not show that the theorem reduces to its own assumptions by definition or by a fitted parameter. Accordingly, the paper receives a circularity score of 0.

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

All results are derived from the definition of friendship-bias and standard branching-process tools. The only external inputs are the offspring distribution p and the standard theorems listed above. No fitted parameters or ad hoc postulates are introduced.

assumptions (5)
  • standard math Kesten-Stigum theorem for Galton-Watson processes under the moment condition (1.2), giving Z_m / mu^m -> W_infty a.s.
    Used in the proof of Theorem 1.4 to establish almost-sure convergence of generation sizes; cited from [14].
  • standard math Strong law of large numbers for i.i.d. random variables applied to per-vertex type counts and per-vertex edge counts.
    Used in Theorems 1.4 and 1.6 to pass from expected values to almost-sure limits.
  • domain assumption Offspring counts of all vertices are i.i.d. with common distribution p, and the tree is rooted at a single vertex.
    This defines the Galton-Watson tree and is the base probabilistic model for all infinite-tree theorems.
  • domain assumption p0 = 0, p1 < 1, and sum_k (k log k) p_k < infinity (assumption (1.2)).
    These conditions ensure the tree is infinite and non-degenerate, and are needed for the Kesten-Stigum theorem. They appear in Theorem 1.4 and are used throughout the infinite-tree proofs.
  • standard math The size-biased distribution tilde p_k = k p_k / mu correctly describes the offspring count of the parent of a uniformly selected vertex.
    This Palm-calculus fact underlies the derivation of the density formulas for f^chi and f^{tilde chi chi}.

how reviews work

0 comments
Cite this review

Pith. "Pith review of The friendship paradox for trees." pith.science (2026). https://pith.science/paper/X457Y5PQ

@misc{pith2026250521774,
  author       = {Pith},
  title        = {Pith review of: The friendship paradox for trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/X457Y5PQ}},
  note         = {Machine review of arXiv:2505.21774}
}
read the original abstract

We analyse the friendship paradox on finite and infinite trees. In particular, we monitor the vertices for which the friendship-bias is positive, neutral and negative, respectively. For an arbitrary finite tree, we show that the number of positive vertices is at least as large as the number of negative vertices, a property we refer to as significance, and derive a lower bound in terms of the branching points in the tree. For an infinite Galton-Watson tree, we compute the densities of the positive and the negative vertices and show that either may dominate the other, depending on the offspring distribution. We also compute the densities of the edges having two given types of vertices at their ends, and give conditions in terms of the offspring distribution under which these types are positively or negatively correlated.

Figures

Figures reproduced from arXiv: 2505.21774 by the authors.

Figure 1
Figure 1. Four realisations of generations 0, . . . , 6 of an infinite rooted Galton-Watson tree with an offspring distribution that is Poisson(λ) with λ = 0.1, 0.5, 1, 2, respectively. Indicated are the locations of the positive (= red), neutral (= circle) and negative (= blue) vertices in the infinite tree. Negative vertices have a tendency to be adjacent to positive vertices. Smaller values of λ tend to produce a higher pr… view at source ↗
Figure 2
Figure 2. Plots of k 7→ f( ˜k, k, λ) = P( ˜k + Sk − k(k + 1) > 0) for ˜k ∈ {1, 2, 5, 8, 10} and λ ∈ {1.5, 2, 3, 7}. The function is non-increasing in k for all displayed values, except for λ = 7 and ˜k = 1, where a slight increase is observed from k = 1 to k = 2. 10 [PITH_FULL_IMAGE:figures/full_fig_p010_2.png] view at source ↗
Figure 3
Figure 3. Indicated in black is the subtree Tn2 of the full tree Tn. • Let j > 2. If nj−1 = n, then Theorem 1.2(a) is proved. Otherwise, go to the next step. Step j: Construct Tnj . We have j > 2, and Tnj−1 has been constructed. Take any leaf u ∈ V (Tnj−1 ) with a degree larger than 1 in Tn (like ϕ1, ϕ2, ϕ3 and ϕ5 in [PITH_FULL_IMAGE:figures/full_fig_p012_3.png] view at source ↗
Figures from the paper (1 more)
Figure 4
Figure 4. Figure 4: Indicated in black is the subtree Tn3 of the full tree Tn. 2.3 All finite trees are significant The above iterative construction has the property that the number of positive vertices is at least as large as the number of negative vertices, at every step j ≥ 1. Moreover…

Discussion (0). Sign in 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

  1. The Generalized Friendship Paradox for Eigenvectors

    math.PR 2026-07 conditional novelty 6.0 of 10

    For inhomogeneous Erdős–Rényi graphs generated by a continuous graphon, the empirical distribution of eigenvector friendship bias converges to the law of (ρ/K(U)−1)φ(U), where ρ and φ are the principal eigenvalue and ...

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages · cited by 1 Pith paper

  1. [1]

    Avrachenkov, N

    K. Avrachenkov, N. Litvak, L. Ostroumova Prokhorenkova, E. Suyargulova, Quick detection of high-degree entities in large directed networks, IEEE International Conference on Data Mining (2014), 20–29

    work page 2014

  2. [2]

    Britton, S

    T. Britton, S. Janson, A. Martin-L¨ of, Graphs with specified degree distributions, simple epi- demics, and local vaccination strategies, Advances in Applied Probability 39 (2007), 922–948

    work page 2007

  3. [3]

    Cao, S.M

    Y. Cao, S.M. Ross, The friendship paradox, Mathematical Scientist 41 (2016), 61–64

    work page 2016

  4. [4]

    Christakis, J.H

    N.A. Christakis, J.H. Fowler, Social network sensors for early detection of contagious out- breaks, PLoS ONE 5 (2010), e12948

    work page 2010

  5. [5]

    Cohen, S

    R. Cohen, S. Havlin, D. Ben-Avraham, Efficient immunization strategies for computer net- works and populations, Physical Review Letters 91 (2003), 247901

    work page 2003

  6. [6]

    Eom, H.-H

    Y.-H. Eom, H.-H. Jo, Generalized friendship paradox in complex networks: the case of scientific collaboration, Scientific Reports 4 (2014), 1–6

    work page 2014

  7. [7]

    Feld, Why your friends have more friends than you do, American Journal of Sociology 96 (1991), 1464–1477

    S. Feld, Why your friends have more friends than you do, American Journal of Sociology 96 (1991), 1464–1477. 23

    work page 1991

  8. [8]

    Hazra, F

    R.S. Hazra, F. den Hollander, A. Parvaneh, The friendship paradox for sparse random graphs, Probability Theory and Related Fields (2025)

    work page 2025

Show all 18 references
  1. [9]

    Hazra, F

    R.S. Hazra, F. den Hollander, A. Parvaneh, The multi-level friendship paradox for sparse random graphs, (2025) arXiv:2502.17724[math.PR]

    2025

  2. [10]

    Hodas, F

    N. Hodas, F. Kooti, K. Lerman, Friendship paradox redux: your friends are more interesting than you, Proceedings of the International AAAI Conference on Web and Social Media 7 (2013), 225–233

    2013

  3. [11]

    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

  4. [12]

    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

  5. [13]

    Jackson, The friendship paradox and systematic biases in perceptions and social norms, Journal of Political Economy 127 (2019), 777–818

    M.O. Jackson, The friendship paradox and systematic biases in perceptions and social norms, Journal of Political Economy 127 (2019), 777–818

    2019

  6. [14]

    Kesten, B.P

    H. Kesten, B.P. Stigum, Limit theorems for decomposable multi-dimensional Galton-Watson processes, Journal of Mathematical Analysis and Applications 17 (1967), 309–338

    1967

  7. [15]

    Krishnamurthy, B

    V. Krishnamurthy, B. Nettasinghe, Information diffusion in social networks: friendship para- dox based models and statistical inference, Modeling, Stochastic Control, Optimization, and Applications 164 (2019), 369–406

    2019

  8. [16]

    majority illusion

    K. Lerman, X. Yan, X.-Z. Wu, The “majority illusion” in social networks, PLoS ONE 11 (2016), e0147617

    2016

  9. [17]

    L. Page, S. Brin, R. Motwani, T. Winograd, The PageRank citation ranking: bringing order to the web, The Web Conference (1999)

    1999

  10. [18]

    Rosenblatt, J.A

    S.F. Rosenblatt, J.A. Jeffrey, G.R. Gauthier, L. H´ ebert-Dufresne, Immunization strategies in networks with missing data, PLoS Computational Biology 16 (2020), e1007897. 24

    2020

Pith tools

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