OctoInformBeta

OpenAI preprint, September 2026 · §6. The case of unbounded overlap scale · §6

Lemma 6.1 [Tree distance fluctuations]: If every cut of positive length has mass in [η,1−η][\eta,1-\eta], then 𝔼|d(X,Y)−d(X′,Y)|\mathbb{E}|d(X,Y)-d(X',Y)| is at least η3\eta^3 times the total length

Balanced laminar cuts bound cut distance fluctuations from below.

Hover over a blue or green term in the text, or a node in the graph, to find it in the other. Select it to read its declaration both in Lean and in words.

The Setting

Take a finite tree with vertex set VV, nonnegative lengths on its edges, its path distance dd, and a probability distribution pp on VV. Let XX, X′X' and YY be independent random vertices with law pp. The mean 𝔼|d(X,Y)−d(X′,Y)|\mathbb{E}\,|d(X,Y)-d(X',Y)| measures how much the distance from YY changes when XX is replaced by an independent copy X′X'. The question is how large it must be, compared with the total length of the tree, when every edge of positive length splits VV into two sides that both carry a substantial part of the mass of pp.

Root the tree at a vertex and give each edge the vertex set of the subtree below it. Any two of these sets are nested or disjoint, and d(x,y)d(x,y) is the total length of the edges whose set contains exactly one of xx and yy. The library states the lemma for any such family of subsets of VV with lengths on its members.

Laminar Families and Cut Distances

A family 𝒮\mathcal{S} of subsets of a finite set VV is laminar if any two of its members are nested or disjoint: A⊆B,B⊆AorA∩B=∅for all A,B∈𝒮.A\subseteq B,\quad B\subseteq A\quad\text{or}\quad A\cap B=\emptyset \qquad\text{for all } A,B\in\mathcal{S}.(1)✦

The indicator 𝟏C\mathbf{1}_C of a subset CC of VV is the function on VV equal to 11 on CC and to 00 off CC.✦

The cut distance of a family 𝒮\mathcal{S} of subsets of VV, with a real length ℓ(C)\ell(C) given to each subset CC of VV, is the function dd on pairs of points of VV given by d(x,y)=∑C∈𝒮ℓ(C)|𝟏C(x)−𝟏C(y)|.d(x,y)=\sum_{C\in\mathcal{S}}\ell(C)\,\bigl|\mathbf{1}_C(x)-\mathbf{1}_C(y)\bigr|.(2)✦ The members of 𝒮\mathcal{S} are called cuts.

The mass of a subset CC of VV under a real function bb on VV is b(C)=∑x∈Cb(x)b(C)=\sum_{x\in C}b(x).✦

The Claim

Theorem 1. Let 𝒮\mathcal{S} be a laminar family of subsets of a finite set VV, let ℓ\ell give each subset of VV a real length with ℓ(C)≥0\ell(C)\ge 0 for every C∈𝒮C\in\mathcal{S}, and let dd be the cut distance (2) of 𝒮\mathcal{S} with lengths ℓ\ell. Let pp be a probability distribution on VV and η≥0\eta\ge 0 a real number such that every cut C∈𝒮C\in\mathcal{S} of positive length has mass η≤p(C)≤1−η\eta\le p(C)\le 1-\eta. Then for independent random points XX, X′X', YY of VV with law pp, η3∑C∈𝒮ℓ(C)≤𝔼|d(X,Y)−d(X′,Y)|.\eta^3\sum_{C\in\mathcal{S}}\ell(C)\;\le\;\mathbb{E}\,\bigl|d(X,Y)-d(X',Y)\bigr|.(3)✦

In the paper, the result reads: if a finite tree has nonnegative edge lengths summing to Λ\Lambda, path pseudometric dd and a probability distribution pp on its vertices, and every edge of positive length separates two vertex sets each of pp-mass at least δ/2\delta/2, where 0<δ<10<\delta<1, then independent XX, X′X', YY of law pp satisfy 𝔼|d(X,Y)−d(X′,Y)|≥δ2Λ/(32(⌈16/δ⌉+1))\mathbb{E}\,|d(X,Y)-d(X',Y)|\ge \delta^2\Lambda/\bigl(32(\lceil 16/\delta\rceil+1)\bigr).

What Is Checked

The claim (3) is stated over a laminar family 𝒮\mathcal{S} of subsets of a finite set VV, lengths ℓ\ell nonnegative on its cuts, the cut distance (2) built from the indicators 𝟏C\mathbf{1}_C, and a probability distribution pp on VV through the masses p(C)p(C) of the cuts.