OctoInformBeta

OpenAI preprint, September 2026 · §3. Covering a tree

§3 (proof of Lemma 3.2): fixed-input potentials and outside dependence: For positive parameters, with locality under disjointness and expectation bounds under level spread conditions

Bad probability trees have large potentials.

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

A fixed occupied set WW determines which local resampling choices succeed at each node of a probability tree. The associated potential assigns a real value to every subtree.

Let XX be a ground set, and let W⊆XW\subseteq X be finite. A finite probability law ν\nu on a finite set BB consists of weights νb≥0\nu_b\geq0 with ∑b∈Bνb=1\sum_{b\in B}\nu_b=1✦; it has full support if every νb\nu_b is positive.✦ A probability tree 𝒯\mathcal T on XX is either a leaf, of depth zero, or a node with a finite branch set BB, a full-support law ν\nu, finite arc labels Ab⊆XA_b\subseteq X, and children 𝒯b\mathcal T_b of a common depth.✦

A probability tree 𝒯\mathcal T on XX has disjoint path labels if the arc labels on every full path of 𝒯\mathcal T are pairwise disjoint.✦ Level capacities m1,m2,…m_1,m_2,\ldots for a probability tree 𝒯\mathcal T on XX form a sequence such that every arc label leaving level ss has cardinality at most msm_s, where the root is at level one.✦ A probability tree 𝒯\mathcal T on XX satisfies the level spread condition with parameters a1,a2,…a_1,a_2,\ldots if, at every node of level ss, the total weight of labels containing any fixed finite subset of XX is at most asa_s raised to the cardinality of that subset.✦ The declarations index these levels from zero.

Local Masses and Potentials

Fix a node with branch law ν\nu and labels AbA_b, and a real parameter ρ\rho. For a source cc, the planted union is Y=W∪AcY=W\cup A_c.✦ At a node with branch set BB, law ν\nu and labels AbA_b, the unnormalized target weight nb(Y)n_b(Y) for a branch b∈Bb\in B and the normalizing density Z(Y)Z(Y) are the real numbers in (1); quotients with zero denominator are set to zero. nb(Y)={νb(ρ−1)|Ab|,Ab⊆Y,0,Ab⊈Y,Z(Y)=∑b∈Bnb(Y).n_b(Y)= \begin{cases} \nu_b(\rho^{-1})^{|A_b|},& A_b\subseteq Y,\\ 0,& A_b\nsubseteq Y, \end{cases} \qquad Z(Y)=\sum_{b\in B}n_b(Y).(1) The conditional target weight qW(b∣c)q_W(b\mid c) and the source and target weight rW(c,b)r_W(c,b) are the weights in (2). qW(b∣c)=nb(W∪Ac)Z(W∪Ac),rW(c,b)=νcqW(b∣c).q_W(b\mid c)=\frac{n_b(W\cup A_c)}{Z(W\cup A_c)}, \qquad r_W(c,b)=\nu_c q_W(b\mid c).(2)

For an integer capacity m≥0m\geq0, local success 𝒮(W;c,b)\mathcal S(W;c,b) means the condition in (3), with retained fragment T=Ab\WT=A_b\setminus W; local failure ℱ(W;c,b)\mathcal F(W;c,b) is its complement.✦ Z(W∪Ac)≥e−10m,|T|≤⌊m/2⌋.Z(W\cup A_c)\geq e^{-10m}, \qquad |T|\leq\lfloor m/2\rfloor.(3)✦ For a real parameter pp, use the outgoing law and labels at a node vv of level ss with ρ=p\rho=p and m=msm=m_s. The local failure mass dv(W)d_v(W) at a node vv for an occupied set WW is the sum of source and target weights over local failures in (4). dv(W)=∑b∈B∑c∈Bℱ(W;c,b)rW(c,b).d_v(W)=\sum_{b\in B}\sum_{\substack{c\in B\\\mathcal F(W;c,b)}}r_W(c,b).(4)✦ The successful target mass tvb(W)t_{vb}(W) at a node vv for a target branch bb and an occupied set WW is the sum of source and target weights over local successes with target bb in (5). tvb(W)=∑c∈B𝒮(W;c,b)rW(c,b).t_{vb}(W)=\sum_{\substack{c\in B\\\mathcal S(W;c,b)}}r_W(c,b).(5)✦

For a node vv of a probability tree on XX, the fixed-input tree potential DvD_v is the real-valued function on finite occupied sets W⊆XW\subseteq X defined recursively by (6), where bb also denotes the corresponding child. Dv(W)={0,v is a leaf,ems(dv(W)+∑b∈Btvb(W)Db(W)),v is at level s and branches.D_v(W)= \begin{cases} 0,&v\text{ is a leaf},\\ e^{m_s}\bigl(d_v(W)+\sum_{b\in B}t_{vb}(W)D_b(W)\bigr), &v\text{ is at level }s\text{ and branches}. \end{cases}(6)✦ For the capacity sequence 𝒎\mathbf m with entries m1,m2,…m_1,m_2,\ldots, a leaf is good for (p,𝒎,W)(p,\mathbf m,W). A branching node vv at level ss of a probability tree is good for (p,𝒎,W)(p,\mathbf m,W) if it satisfies (7); a node of the tree is bad for these parameters if it is not good. ∑b∈Bb is good for (p,𝒎,W)tvb(W)≥1−e−ms.\sum_{\substack{b\in B\\b\text{ is good for }(p,\mathbf m,W)}}t_{vb}(W) \geq1-e^{-m_s}.(7)✦

A function ff on finite subsets of XX depends only on coordinates outside a finite set AA if f(W)=f(V)f(W)=f(V) whenever W\A=V\AW\setminus A=V\setminus A.✦

The potential envelope Es,kE_{s,k} for kk remaining levels, starting at level ss, is the number defined by (8). Es,0=0,Es,k+1=e−8ms+e12msEs+1,k.E_{s,0}=0,\qquad E_{s,k+1}=e^{-8m_s}+e^{12m_s}E_{s+1,k}.(8)✦

For finite XX, the Bernoulli subset weight wρ(W)w_\rho(W) and Bernoulli expectation 𝔼ρf\mathbb E_\rho f are given by (9). For 0≤ρ≤10\leq\rho\leq1, μρ\mu_\rho includes coordinates independently with probability ρ\rho, and 𝔼ρ\mathbb E_\rho is expectation under μρ\mu_\rho. wρ(W)=∏x∈X{ρ,x∈W,1−ρ,x∉W,𝔼ρf=∑W⊆Xwρ(W)f(W).w_\rho(W)=\prod_{x\in X} \begin{cases}\rho,&x\in W,\\1-\rho,&x\notin W,\end{cases} \qquad \mathbb E_\rho f=\sum_{W\subseteq X}w_\rho(W)f(W).(9)

The Claim

Theorem 1. Let p>0p>0, let 𝒎\mathbf m be a sequence of nonnegative integer capacities, and let W⊆XW\subseteq X be finite. A bad probability tree with root rr satisfies (10). Dr(W)>1.D_r(W)>1.(10)✦ Let the parameter be real and let the capacities be any sequence. At a branching node of a probability tree with disjoint path labels, each child potential depends only on coordinates outside its incoming label, as stated in (11) for every branch bb and finite W,VW,V. Db(W)=Db(V)whenever W\Ab=V\Ab.D_b(W)=D_b(V)\qquad \text{whenever }W\setminus A_b=V\setminus A_b.(11)✦ Suppose now that XX is finite, 0<p<10<p<1, and 𝒯\mathcal T has depth dd, disjoint path labels, level capacities 𝒎\mathbf m, and level spread parameters 𝒂\mathbf a. If ms≥1m_s\geq1, as≥0a_s\geq0, and as/p≤e−50a_s/p\leq e^{-50} for every 1≤s≤d1\leq s\leq d, its root potential satisfies (12). 𝔼μpDr(W)≤E1,d.\mathbb E_{\mu_p}D_r(W)\leq E_{1,d}.(12)✦

In the paper, the result reads: with outgoing capacity msm_s, local failure mass dv(W)d_v(W) and local non-failure mass tvb(W)t_{vb}(W) with target bb, leaves have Dv=0D_v=0 and branching nodes have Dv=(dv+∑btvbDb)/e−msD_v=(d_v+\sum_b t_{vb}D_b)/e^{-m_s}, bad nodes have Dv>1D_v>1, disjointness makes DbD_b depend only on WW outside AbA_b, and 𝔼Dv≤e−8ms+e12ms∑bνb𝔼Db\mathbb E D_v\leq e^{-8m_s}+e^{12m_s}\sum_b\nu_b\mathbb E D_b, with geometric capacity growth giving 𝔼Dr<1/4\mathbb E D_r<1/4.

What Is Checked

The bad-tree assertion is stated over finite subsets of an arbitrary ground set and a positive parameter; locality is stated over disjoint probability trees for any real parameter; the expectation bound is stated over a finite ground set with the level capacity and spread hypotheses in the theorem.