Concentration of Broadcast Models on Trees

Christopher Shriver

REVIEW 1 major objections 4 minor 18 references

Concentration of Broadcast Models on Trees

T0 review · 1 major / 4 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 single descendant-weighted sum controls concentration on tree-indexed Markov measures.

desk verdict A genuine new concentration inequality for Markov measures on trees, with a proof that is largely sound and one explicitly fixable technical gap; worth sending to a serious referee. read the letter →

arxiv 1908.08121 v1 pith:EYQLQCML submitted 2019-08-21 math.PR

Christopher Shriver This is my paper · ORCID

classification math.PR MSC 60E1560J0505C0582B20

keywords concentrationofmeasureMarkovmeasuresontreesbroadcastmodelsLévyfamiliestransportation-entropyinequalitiesdescendantgeneratingfunctionIsingmodelphasetransition

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

A broadcast model on a tree passes a value from each node to its children through random kernels, and this paper asks how strongly such a process concentrates: how close Lipschitz functions of the whole configuration must be to their mean. The paper proves that concentration is governed by one number, built from the tree's descendant counts and the kernels' Lipschitz constant, and that the resulting bound recovers the classical product and chain inequalities as special cases. This yields a concrete condition, in terms of the tree's growth rate and the kernels' contraction, for a sequence of depth-k marginals to form a normal Lévy family. The proof is an induction over the depth of the tree, with a descendant generating function supplying the weights at each level.

What carries the argument

The central object is the descendant generating function $\delta(v)=\sum_{r\ge0}|D_r(v)|b^r$, which satisfies the recurrence $\delta(v)=1+b\sum_{w:\pi(w)=v}\delta(w)$ and whose $\ell^2$ norm is $\Delta$. The proof inducts on the depth of the tree, using $\delta$ to assign weights to the leaves of each level so that the conditional product of the one-step transition kernels becomes a weighted Hamming space; a standard bounded-differences lemma then bounds the exponential moment at each level. A classical equivalence between transportation-entropy inequalities and exponential moment bounds converts the result into the transport form, and estimates comparing sums of $b^{d(v,w)}$ with $\Delta^2$ link the bound to the tree's growth rates.

What would settle it

Take a depth-2 tree with a root and two children, choose two distinct $b$-Lipschitz binary kernels with the same Lipschitz constant, and compute $\int e^{n\lambda f}\,d\nu$ for a 1-Lipschitz function such as the normalized density of ones. If this ever exceeds $e^{\lambda^2\Delta^2/8}$, Theorem 1 is false. Equivalently, one could search for a counterexample to the weighted bounded-differences bound for products of non-identical marginals, which would break the induction even if the final inequality happens to hold.

Watch

Extended reading notes

Core claim

For any finite tree $T$ with $n$ vertices and any $b$-Lipschitz Markov measure $\nu$ indexed by $T$, the paper proves that every 1-Lipschitz function $f$ with mean zero satisfies the exponential moment bound $$\int $e^{{n\lambda f}}$\,d\nu \le e^{\$lambda^{2}$ \$\Delta$^2 / 8},$$ where $\Delta$ is the $\ell^2$ norm of the descendant generating function $$\delta(v) = \sum_{r\ge 0} |D_r(v)| b^r,$$ with $D_r(v)$ the set of descendants of $v$ at distance $r$. Equivalently, the transportation-entropy inequality $$\bar d(\mu,\nu) \le \frac{\$\Delta$}{n} \sqrt{\frac{1}{2}D(\mu\|\nu)}$$ holds for all probability measures $\mu$. From this the paper derives tail bounds of the form $2e^{-2n^2\varepsilon^2/\Delta^2}$, recovering McDiarmid's inequality when $b=0$ and Marton's inequality when the tree is a path. It then uses estimates on $\Delta$ to locate a phase transition: for subperiodic trees, a sequence of depth-$k$ marginals is a normal Lévy family exactly when $b^2 \mathrm{gr}\,T < 1$, and for the Ising model this threshold is shown to be intrinsic rather than an artifact of the method.

Load-bearing premise

The induction step applies a weighted bounded-differences inequality to a product of one-step transition kernels whose marginals are not identically distributed and depend on the conditioning parent value, while the lemma as stated covers only identical product measures; no separate proof of that extension is provided.

Editorial extensions

If this is right

Any $b$-Lipschitz broadcast model on a finite tree satisfies the tail bound $\nu\{|f-\int f\,d\nu|>\varepsilon\}\le 2e^{-2n^2\varepsilon^2/\Delta^2}$, so Lipschitz observables concentrate at speed $n/\Delta$.
For a sequence of finite trees, $\Delta_k=o(|V_k|)$ makes the measures a Lévy family and $\Delta_k=O(\sqrt{|V_k|})$ makes them a normal Lévy family; bounded-degree infinite trees enter the latter regime when $b^2\max\mathrm{gr}\,T<1$ and leave it when $b^2\,\mathrm{gr}\,T>1$.
For the Ising broadcast model with flip probability $p$, where $b=1-2p$, the depth-$k$ marginals fail to form a normal Lévy family exactly when $\Delta_k$ is not $O(\sqrt{|V_k|})$, so the phase transition in concentration quality is genuine.
The universal constant in the theorem cannot be smaller than $\Delta\sqrt{(1-b^2)/2}$, so the bound is close to optimal in the worst case.

Reading between the lines

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

The same induction may extend to Bayesian networks with multiple sources and to concentration of the marginal on the leaves, as the paper itself suggests.
A direct testable extension is to compute the quantity $G(T)$ defined in Section 1.1.1 for non-subperiodic trees; if $G(T)=\max\mathrm{gr}\,T$ for such trees, the phase transition threshold $b^2\max\mathrm{gr}\,T=1$ would be universal.
Because the transportation-entropy form carries explicit constants, it could be converted into modified logarithmic Sobolev inequalities for tree-indexed Gibbs measures, giving a route to functional inequalities not explored in the paper.

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

Two things to know. First, this paper proves a real concentration theorem for Markov measures indexed by trees, not a repackaging of known results. Theorem 1 gives an exponential moment bound with a constant Delta built from descendant generating functions, and from it you get the equivalent transportation-entropy inequality and tail bounds. It recovers Marton's inequality for Markov chains and McDiarmid's inequality for product measures as special cases. That alone is a solid contribution to the concentration-of-measure literature. Second, the paper does something genuinely useful with the theorem: it derives conditions on the tree growth rate and the contraction parameter b under which depth-k marginals form a normal Levy family. For subperiodic trees, b^2 grT < 1 marks the phase transition for the growth of Delta_k, and the Ising model analysis (Theorems 4 and 5) shows the bound is close to sharp. The comparison with Kontorovich-Ramanan and Chazottes et al. in Section 6 is careful and fair, not a strawman.

The soft spot the reader flagged is real but not fatal. Proposition 16 is stated for i.i.d. product measures p^n, while the induction in Theorem 1 applies it to a product of distinct, y-dependent marginals q_w(.|y_{pi(w)}). I read the proof of Proposition 16; it never uses the fact that the marginals are identical. Hoeffding's lemma is applied to the residual function under a single marginal, and the induction hypothesis is applied to g/L under the first n-1 coordinates. Replacing p^n by a tensor product of distinct measures changes nothing, and the y-dependence is handled pointwise. So this is a genuine mismatch between statement and use, but a two-sentence remark would close it. The paper should say that the proposition extends verbatim to non-identical product measures; as written, it's a gap in presentation, not a hidden flaw in the central argument.

Two smaller things. Corollary 20 in Section 6 is stated without proof, but it is only used for comparison with prior work and is not load-bearing. And the phase-transition range for non-subperiodic trees between (maxgrT)^{-1/2} and (grT)^{-1/2} is left open; the author says so explicitly and shows only numerical evidence for the conjectured location. That is honest.

The citation pattern is fine, and the paper is self-contained. This is a paper for people working on concentration of measure, graphical models, or information flow on trees. It deserves a serious referee: the main theorem is new, the proof is mostly checkable, and the open points are clearly stated. I would send it out.

Referee Report

1 major / 4 minor

Summary. The paper proves a concentration inequality for Markov measures indexed by finite trees. For a finite tree T with n vertices and a b-Lipschitz broadcast model ν on a Polish metric space H of diameter at most 1, Theorem 1 asserts that every 1-Lipschitz f : H^V → R with mean zero satisfies ∫ e^{nλ f} dν ≤ e^{λ²Δ²/8}, where Δ is defined explicitly from b and the tree's descendant generating function. By the Bobkov–Götze equivalence this also yields a transportation-entropy inequality. The paper then derives tail bounds, gives growth-rate criteria for sequences of depth-k marginals to form (normal) Lévy families (Theorem 3), proves a near-optimality lower bound for the Ising model (Theorem 4), and establishes a phase transition for normal Lévy behavior in the Ising case (Theorem 5). The proof of the main theorem is an induction on tree depth, using a weighted McDiarmid-type exponential moment bound (Proposition 16).

Significance. If correct, the result is a genuine and natural extension of Marton's transportation-entropy inequality and McDiarmid's inequality to tree-indexed Markov processes. The constant Δ is constructed explicitly from the tree and the contraction parameter b, with no hidden free parameters, and Theorem 3 gives concrete, falsifiable growth-rate criteria that match known reconstruction thresholds in the regular-tree case. Theorem 4 independently demonstrates near-optimality of the constant via an exact variance computation for the Ising model, and Theorem 5 shows that the qualitative phase transition is real rather than an artifact of the bound. The central induction is detailed and self-contained, and there is no circularity: the main results are derived from explicit recurrences, and the optimality statement is an independent computation. The main formal gap, concerning the scope of Proposition 16, is localized and repairable.

major comments (1)

[Section 2.4 and Section 3 (Proof of Theorem 1)] Proposition 16 is stated only for an i.i.d. product measure p^n, but in the induction step of Theorem 1 it is applied to the conditional product ∏_{w∈L_k} q_w(·|y_{π(w)}), whose marginals are generally distinct and depend on y. This is a genuine mismatch between statement and use, and because the exponential moment bound at each level of the induction depends on this application, the proof is incomplete as written. The gap is readily repairable: the induction proof of Proposition 16 never uses identity of the marginals, and replacing p^n by ⊗_{i=1}^n μ_i, with μ_i possibly depending on a conditioning variable, changes nothing provided the mean-zero and 1-Lipschitz properties are checked pointwise. The proposition should be restated in this generality and the application in Section 3 should cite it explicitly.

minor comments (4)

[Section 6, Corollary 20] The two displayed claims of Corollary 20 are nontrivial and are asserted without proof, with the text saying the proofs are omitted for brevity. Since Corollary 20 is used to compare Theorem 1 with the inequalities of Kontorovich–Ramanan and Chazottes et al., the proofs should be included or the claims should be moved to an appendix with full arguments.
[Section 1, definition of normal Lévy family] There is a typo in the definition: 'postive constants' should read 'positive constants'.
[Section 4.2, proof of Theorem 3] The argument uses operator norms of Q on 𝓁²(V) for an infinite tree, but Lemma 9 defines Q on the vector space R^V. The proof should state explicitly that Q is viewed as a bounded operator on 𝓁²(V) under the bounded-degree assumption, or otherwise justify the norm computation.
[Theorem 3 statement] The statement should say explicitly that T is an infinite locally finite rooted tree, since the proof of the first part uses lim_{k→∞} |V_k| = ∞.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the main inequality is derived from explicit recurrences and standard lemmas, with no fitted parameters or load-bearing self-citations.

full rationale

The paper's central object Δ is defined constructively from the tree and the contraction parameter b via the descendant generating function δ(v)=Σ_r |D_r(v)| b^r, and Theorem 1 is proved by induction on tree depth using Hoeffding's lemma, the weighted McDiarmid-type Proposition 16, and the Bobkov–Götze equivalence. None of these steps assumes the theorem being proved; the induction hypothesis is applied only to smaller trees, and the vertex-level bound accumulates the δ-weights through the tree recurrence. The optimality result Theorem 4 is an independent variance computation for the Ising magnetization (Proposition 18), and Theorem 5 likewise derives a necessity statement from variance bounds; these are not re-uses of the target exponential moment bound. The paper contains no fitting step and no author self-citations that carry the argument. The only caveat is that Proposition 16 is stated for product measures p^n while Section 3 applies it to the conditional product ∏_w q_w(·|y_parent(w)) with possibly distinct, y-dependent marginals; but the proof of Proposition 16 never uses identity of the marginals and the Hoeffding step is applied pointwise in y, so this is a statement-hypothesis mismatch rather than circularity. Corollary 20's omitted proofs are not used to prove Theorem 1. Hence no circular step is exhibited.

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

The central claim rests on standard results in probability and on the explicit definition of the descendant generating function; there are no free parameters fitted to data and no invented entities.

assumptions (5)

standard math Bobkov-Gotze equivalence: a transportation-entropy inequality is equivalent to an exponential moment bound for mean-zero 1-Lipschitz functions.
Invoked as Theorem 13 and used to pass between the two forms of the main result.
standard math Hoeffding's lemma for bounded mean-zero functions.
Used as Lemma 15 in the base case and in Proposition 16.
standard math Monge-Kantorovich-Rubinstein duality for the transportation metric on a bounded Polish space.
Used in the proof of Theorem 1 to bound oscillations of conditional expectations.
domain assumption The transition kernels are uniformly b-Lipschitz with respect to the transportation metric.
This is the contraction condition defining the class of Markov measures covered by Theorem 1.
domain assumption The state space H is Polish with diameter at most 1.
The diameter bound normalizes the Hamming metric; a general bounded space can be rescaled.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Concentration of Broadcast Models on Trees." pith.science (2026). https://pith.science/paper/EYQLQCML

@misc{pith2026190808121,
  author       = {Pith},
  title        = {Pith review of: Concentration of Broadcast Models on Trees},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EYQLQCML}},
  note         = {Machine review of arXiv:1908.08121}
}

abstract

An inequality of K. Marton shows that the joint distribution of a Markov chain with uniformly contracting transition kernels exhibits concentration. We prove an analogous inequality for broadcast models on finite trees. We use this inequality to develop a condition for the sequence of depth-$k$ marginals of a broadcast model on a rooted infinite tree to form a normal L\'{e}vy family in terms of the Lipschitz constants of the transition kernels and the growth rate of the tree.

Figures

Figures reproduced from arXiv: 1908.08121 by the authors.

**Figure 1.** Comparison of growth rate of ∆k for different values of b, where on the left T is the “3-1 tree” defined in Section 2.1 and pictured in [PITH_FULL_IMAGE:figures/full_fig_p006_1.png] view at source ↗

**Figure 2.** The first few levels of the 3-1 tree, which satisfies gr T = 2 and maxgr T = 3. children of v are those vertices in the set π −1 (v) = {w ∈ V : π(w) = v}. A vertex with no children is called a leaf. We denote the set of descendants in the rth generation after v by Dr(v) := {w ∈ V : v ≤ w, d(v, w) = r} = (π r ) −1 (v). The upper growth rate and the maximum local growth rate of T are defined by gr T := lim sup r→∞ |Dr… view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

[1]

Markov Chains Indexed by Trees.The Annals of Probability, 22(1):219– 243, 1994

Itai Benjamini and Yuval Peres. Markov Chains Indexed by Trees.The Annals of Probability, 22(1):219– 243, 1994

work page 1994
[2]

Exponential Integrability and Transportation Cost Related to Logarithmic Sobolev Inequalities

S.G Bobkov and F G¨ otze. Exponential Integrability and Transportation Cost Related to Logarithmic Sobolev Inequalities. Journal of Functional Analysis , 163(1):1–28, April 1999

work page 1999
[3]

J. R. Chazottes, P. Collet, C. K¨ ulske, and F. Redig. Concentration inequalities for random ﬁelds via coupling. Probability Theory and Related Fields , 137(1-2):201–225, November 2006

work page 2006
[4]

T. M. Cover and Joy A. Thomas. Elements of Information Theory . Wiley-Interscience, Hoboken, N.J, 2nd ed edition, 2006. OCLC: ocm59879802

work page 2006
[5]

Large Deviations Techniques and Applications, volume 38 of Stochastic Modelling and Applied Probability

Amir Dembo and Ofer Zeitouni. Large Deviations Techniques and Applications, volume 38 of Stochastic Modelling and Applied Probability . Springer Berlin Heidelberg, Berlin, Heidelberg, 2010

work page 2010
[6]

Real Analysis and Probability

Richard M Dudley. Real Analysis and Probability . Cambridge University Press, Cambridge, 2004. OCLC: 740992059

work page 2004
[7]

Schulman

William Evans, Claire Kenyon, Yuval Peres, and Leonard J. Schulman. Broadcasting on trees and the Ising model. The Annals of Applied Probability , 10(2):410–433, May 2000

work page 2000
[8]

Probability Inequalities for Sums of Bounded Random Variables

Wassily Hoeﬀding. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association , 58(301):13, March 1963

work page 1963

Show all 18 references

[9]

John D. Hunter. Matplotlib: A 2D Graphics Environment. Computing in Science & Engineering , 9(3):90–95, 2007

2007
[10]

Obtaining Measure Concentration from Markov Contraction

Aryeh Kontorovich. Obtaining Measure Concentration from Markov Contraction. Markov Processes and Related Fields , 18(4):613–638, 2012

2012
[11]

Concentration inequalities for dependent random variables via the martingale method

Leonid (Aryeh) Kontorovich and Kavita Ramanan. Concentration inequalities for dependent random variables via the martingale method. The Annals of Probability , 36(6):2126–2158, November 2008

2008
[12]

The Concentration of Measure Phenomenon

Michel Ledoux. The Concentration of Measure Phenomenon . Number 89 in Mathematical Surveys and Monographs. American Math. Soc, Providence, RI, 2001. OCLC: 846496936

2001
[13]

Random Walks and Percolation on Trees

Russell Lyons. Random Walks and Percolation on Trees. The Annals of Probability , 18(3):931–958, 1990

1990
[14]

Russell Lyons and Y. Peres. Probability on Trees and Networks . Cambridge Series in Statistical and Probabilistic Mathematics. Cambridge University Press, New York NY, 2016

2016
[15]

K. Marton. Bounding ¯d-distance by informational divergence: a method to prove measure concentra- tion. The Annals of Probability , 24(2):857–866, 1996

1996
[16]

Concentration

Colin McDiarmid. Concentration. In Michel Habib, Colin McDiarmid, Jorge Ramirez-Alfonsin, and Bruce Reed, editors, Probabilistic Methods for Algorithmic Discrete Mathematics , pages 195–248. Springer Berlin Heidelberg, Berlin, Heidelberg, 1998

1998
[17]

Information ﬂow on trees

Yuval Peres and Elchanan Mossel. Information ﬂow on trees. The Annals of Applied Probability , 13(3):817–844, August 2003

2003
[18]

The NumPy Array: A Structure for Eﬃcient Numerical Computation

St´ efan van der Walt, S Chris Colbert, and Ga¨ el Varoquaux. The NumPy Array: A Structure for Eﬃcient Numerical Computation. Computing in Science & Engineering , 13(2):22–30, March 2011

2011

Pith tools

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

[1] [1]

Markov Chains Indexed by Trees.The Annals of Probability, 22(1):219– 243, 1994

Itai Benjamini and Yuval Peres. Markov Chains Indexed by Trees.The Annals of Probability, 22(1):219– 243, 1994

work page 1994

[2] [2]

Exponential Integrability and Transportation Cost Related to Logarithmic Sobolev Inequalities

S.G Bobkov and F G¨ otze. Exponential Integrability and Transportation Cost Related to Logarithmic Sobolev Inequalities. Journal of Functional Analysis , 163(1):1–28, April 1999

work page 1999

[3] [3]

J. R. Chazottes, P. Collet, C. K¨ ulske, and F. Redig. Concentration inequalities for random ﬁelds via coupling. Probability Theory and Related Fields , 137(1-2):201–225, November 2006

work page 2006

[4] [4]

T. M. Cover and Joy A. Thomas. Elements of Information Theory . Wiley-Interscience, Hoboken, N.J, 2nd ed edition, 2006. OCLC: ocm59879802

work page 2006

[5] [5]

Large Deviations Techniques and Applications, volume 38 of Stochastic Modelling and Applied Probability

Amir Dembo and Ofer Zeitouni. Large Deviations Techniques and Applications, volume 38 of Stochastic Modelling and Applied Probability . Springer Berlin Heidelberg, Berlin, Heidelberg, 2010

work page 2010

[6] [6]

Real Analysis and Probability

Richard M Dudley. Real Analysis and Probability . Cambridge University Press, Cambridge, 2004. OCLC: 740992059

work page 2004

[7] [7]

Schulman

William Evans, Claire Kenyon, Yuval Peres, and Leonard J. Schulman. Broadcasting on trees and the Ising model. The Annals of Applied Probability , 10(2):410–433, May 2000

work page 2000

[8] [8]

Probability Inequalities for Sums of Bounded Random Variables

Wassily Hoeﬀding. Probability Inequalities for Sums of Bounded Random Variables. Journal of the American Statistical Association , 58(301):13, March 1963

work page 1963