OctoInformBeta

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

Lemma 3.2: Disjointness and path recovery survive, with a quantitative loss of spread

Successful reductions halve the level capacities.

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

For a tree with set labels on its arcs, sampling a set WW asks how much of each path’s label union can be removed while retaining control of the outgoing label distributions.

A finite probability law ν\nu on a finite set BB is a family of real weights satisfying (1). νb≥0(b∈B),∑b∈Bνb=1.\nu_b\geq 0\quad(b\in B),\qquad \sum_{b\in B}\nu_b=1.(1)✦ A finite probability law ν\nu on BB has full support if νb>0\nu_b>0 for every b∈Bb\in B.✦

A probability tree 𝒯\mathcal T on a ground set XX, with kk levels, is a rooted tree whose leaves all have depth kk, whose outgoing arcs at each internal node have a finite index set BB with a full support probability law ν\nu, and whose arc labels AbA_b are finite subsets of XX.✦ A tree with zero levels is a single leaf. A full path PP of 𝒯\mathcal T is a complete history of branch choices from the root to a leaf; the leaf has one empty history.✦ The path label union U(P)U(P) of a full path PP of 𝒯\mathcal T is the set in (2). U(P)=⋃arcs b of PAb.U(P)=\bigcup_{\text{arcs }b\text{ of }P} A_b.(2)✦

Level capacities m1,…,mkm_1,\ldots,m_k for 𝒯\mathcal T are upper bounds on the sizes of its arc labels, as in (3). |Ab|≤mjfor every outgoing arc at every node at level j.|A_b|\leq m_j \qquad\text{for every outgoing arc at every node at level }j.(3)✦ Levels are numbered 1,…,k1,\ldots,k here; the library’s declarations number them from zero. The tree 𝒯\mathcal T is disjoint if the arc labels on each full path are pairwise disjoint.✦ A sequence of real numbers α1,…,αk\alpha_1,\ldots,\alpha_k is a sequence of level spread parameters for the probability tree 𝒯\mathcal T on XX if, at every node at level jj, the probability that its outgoing label contains any prescribed subset of XX is at most αj\alpha_j raised to the cardinality of that subset.✦

For a finite ground set XX and real ρ\rho, the Bernoulli subset weight bρ(W)b_\rho(W) of W⊆XW\subseteq X is given by (4). bρ(W)=∏x∈Wρ∏x∈X\W(1−ρ).b_\rho(W)=\prod_{x\in W}\rho\prod_{x\in X\setminus W}(1-\rho).(4)✦ For ρ∈[0,1]\rho\in[0,1], the Bernoulli law μρ\mu_\rho includes each element of XX independently with probability ρ\rho; its event probabilities are given by (5). μρ(ℰ)=∑W∈ℰbρ(W)(ℰ⊆2X).\mu_\rho(\mathcal E)=\sum_{W\in\mathcal E}b_\rho(W) \qquad\bigl(\mathcal E\subseteq 2^X\bigr).(5)✦

Good Samples and Reduction

Fix ρ\rho, a sequence mm and a finite set W⊆XW\subseteq X. At a node at level jj, write sbs_b for the mass of successful target assignments to branch bb determined by its outgoing law, label family and parameters ρ,mj,W\rho,m_j,W. A subtree 𝒮\mathcal S starting at level jj is good for these parameters if it is a leaf, or if its children 𝒮b\mathcal S_b satisfy the condition in (6); write 𝖦j(𝒮;W)\mathsf G_j(\mathcal S;W) for this property. 𝖦j(𝒮;W)⇔∑b:𝖦j+1(𝒮b;W)sb≥1−e−mj(𝒮 an internal node).\mathsf G_j(\mathcal S;W)\quad\Longleftrightarrow\quad \sum_{b:\,\mathsf G_{j+1}(\mathcal S_b;W)}s_b\geq 1-e^{-m_j} \qquad(\mathcal S\text{ an internal node}).(6)✦

For ρ>0\rho>0, positive integer parameters mjm_j and a sample WW such that 𝖦1(𝒯;W)\mathsf G_1(\mathcal T;W) holds, the reduced tree ℛρ,m,W(𝒯)\mathcal R_{\rho,m,W}(\mathcal T) is the tree obtained recursively by retaining branches with good children and positive successful target mass, using the law and labels in (7), and reducing their children; a leaf remains a leaf. νb′=sb∑c:𝖦j+1(𝒮c;W)sc,Ab′=Ab\Won retained branches at level j.\nu'_b= \frac{s_b}{\displaystyle\sum_{c:\,\mathsf G_{j+1}(\mathcal S_c;W)}s_c}, \qquad A'_b=A_b\setminus W \qquad\text{on retained branches at level }j.(7)✦

The Claim

Theorem 1 (Lemma 3.2). Let 𝒯\mathcal T be a probability tree on XX with k≥0k\geq0 levels, let ρ>0\rho>0, and let m1,…,mkm_1,\ldots,m_k be positive integers. For every finite W⊆XW\subseteq X such that 𝖦1(𝒯;W)\mathsf G_1(\mathcal T;W) holds, put 𝒯′=ℛρ,m,W(𝒯)\mathcal T'=\mathcal R_{\rho,m,W}(\mathcal T). Then (8) holds. 𝒯′ has level capacities (⌊mj2⌋)j=1k.\mathcal T'\text{ has level capacities } \left(\left\lfloor\frac{m_j}{2}\right\rfloor\right)_{j=1}^k.(8)✦ If 𝒯\mathcal T is disjoint, then (9) holds. 𝒯′ is disjoint.\mathcal T'\text{ is disjoint}.(9)✦ If αj≥0\alpha_j\geq0 for every level and 𝒯\mathcal T has level spread parameters αj\alpha_j, then (10) holds. 𝒯′ has level spread parameters (αj1−e−mj)j=1k.\mathcal T'\text{ has level spread parameters } \left(\frac{\alpha_j}{1-e^{-m_j}}\right)_{j=1}^k.(10)✦ Path recovery is expressed by (11). For every full path Q of 𝒯′,there is a full path P of 𝒯 with U(P)⊆W∪U(Q).\text{For every full path }Q\text{ of }\mathcal T',\quad \text{there is a full path }P\text{ of }\mathcal T \text{ with }U(P)\subseteq W\cup U(Q).(11)✦

Suppose further that XX is finite, ρ<1\rho<1, and 𝒯\mathcal T is disjoint with level capacities mjm_j and nonnegative level spread parameters αj\alpha_j. Assume αj/ρ≤e−50\alpha_j/\rho\leq e^{-50} at each level and mj+1≥16mjm_{j+1}\geq16m_j at every pair of successive levels. The probability bounds are (12) and (13). μρ({W:𝖦1(𝒯;W)})≥34.\mu_\rho\bigl(\{W:\mathsf G_1(\mathcal T;W)\}\bigr)\geq\frac34.(12)✦ μρ({W:¬𝖦1(𝒯;W)})<14.\mu_\rho\bigl(\{W:\neg\mathsf G_1(\mathcal T;W)\}\bigr)<\frac14.(13)✦

In the paper, the result reads: for a disjoint probability tree 𝒯\mathcal T with k≥1k\geq1 levels, positive integer capacities mjm_j satisfying mj+1≥16mjm_{j+1}\geq16m_j, and level spread parameters 0<αj≤a0<\alpha_j\leq a with ρ=e50a<1\rho=e^{50}a<1, a deterministic procedure given W∼μρW\sim\mu_\rho succeeds with probability at least 3/43/4 and returns a disjoint tree 𝒯′\mathcal T' with the same levels, level capacities ⌊mj/2⌋\lfloor m_j/2\rfloor and level spread parameters αj/(1−e−mj)\alpha_j/(1-e^{-m_j}), such that every full path QQ of 𝒯′\mathcal T' recovers a full path PP of 𝒯\mathcal T satisfying U(P)⊆W∪U(Q)U(P)\subseteq W\cup U(Q).

What Is Checked

The probability assertions concern independent subsets of a finite ground set and disjoint probability trees satisfying the stated capacity, spread and growth hypotheses, while the deterministic assertions concern the recursive reduction of a good tree with positive integer parameters mjm_j and ρ>0\rho>0.