OctoInformBeta

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

§3 (setting): probability trees, disjoint paths, capacities, and spread: Full paths, level capacities and spread, with equivalent criteria for disjoint labels

Set choices along a probability tree.

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

Successive choices of finite subsets of a ground set XX may depend on earlier choices. A probability tree describes such choices with a prescribed number of steps.

A finite probability law ν\nu on a finite set BB is a family of real weights (νb)b∈B(\nu_b)_{b\in B} 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.✦

The Claim

Definition 1. A probability tree TT of depth dd over XX is a rooted tree whose leaves all have distance dd from its root rr.✦ At each internal vertex vv, the outgoing arcs are indexed by a finite set BvB_v, have finite labels Av,b⊆XA_{v,b}\subseteq X, and are assigned a probability law νv=(νv,b)b∈Bv\nu_v=(\nu_{v,b})_{b\in B_v} with full support. A tree of depth zero consists of a single leaf.

A full path PP of a probability tree TT is a choice of an outgoing arc at each successive vertex until a leaf is reached. Writing TbT_b for the child subtree reached by root arc bb, the set 𝒫(T)\mathcal P(T) of full paths has the recursive description (2); ()() denotes the empty path. 𝒫(T)={{()},d=0,⨆b∈Br{b}×𝒫(Tb),d>0.\mathcal P(T)= \begin{cases} \{()\}, & d=0,\\[2pt] \displaystyle\bigsqcup_{b\in B_r}\{b\}\times\mathcal P(T_b), & d>0. \end{cases}(2)✦ The path labels of P∈𝒫(T)P\in\mathcal P(T) form the ordered list (A1(P),…,Ad(P))(A_1(P),\ldots,A_d(P)), where Ai(P)A_i(P) is the label of its iith arc.✦ The path union U(P)U(P) is the finite subset of XX defined in (3), with the empty union equal to ⌀\varnothing. U(P)=⋃i=1dAi(P).U(P)=\bigcup_{i=1}^{d}A_i(P).(3)✦

For a probability tree TT rooted at rr, let 𝒱j\mathcal V_j be the set of vertices of TT at distance jj from rr. Arc levels are numbered 1,…,d1,\ldots,d here; the declarations number these levels from zero. For a sequence (mi)i≥1(m_i)_{i\geq1} of nonnegative integers, level capacities (mi)(m_i) for TT are upper bounds on label cardinalities as specified in (4). T has capacities (mi)⇔|Av,b|≤mi(1≤i≤d,v∈𝒱i−1,b∈Bv).\text{$T$ has capacities $(m_i)$} \quad\Longleftrightarrow\quad |A_{v,b}|\leq m_i \quad \bigl(1\leq i\leq d,\ v\in\mathcal V_{i-1},\ b\in B_v\bigr).(4)✦ Spread is a condition on the probabilities that an outgoing label contains a prescribed finite subset of XX. For a sequence (ai)i≥1(a_i)_{i\geq1} of real numbers, level spread (ai)(a_i) for TT requires this condition with parameter aia_i at every vertex at distance i−1i-1 from the root, as specified in (5). T has spread (ai)⇔(Av,b)b∈Bv is ai-spread under νvfor every 1≤i≤d and v∈𝒱i−1.\text{$T$ has spread $(a_i)$} \quad\Longleftrightarrow\quad \begin{gathered} \text{$(A_{v,b})_{b\in B_v}$ is $a_i$-spread under $\nu_v$}\\ \text{for every $1\leq i\leq d$ and $v\in\mathcal V_{i-1}$.} \end{gathered}(5)✦

A finite set W⊆XW\subseteq X covers TT when the condition in (6) holds. T is covered by W⇔there exists P∈𝒫(T) with U(P)⊆W.\text{$T$ is covered by $W$} \quad\Longleftrightarrow\quad \text{there exists $P\in\mathcal P(T)$ with $U(P)\subseteq W$.}(6)✦

A probability tree TT is recursively disjoint if every root arc label is disjoint from the union of all labels in its chosen child subtree, and each child subtree is recursively disjoint.✦ A leaf is recursively disjoint.

Theorem 1. Let TT be a probability tree of depth dd. Recursive disjointness and the criterion of path disjointness are related by (7). T is recursively disjoint⇔Ai(P)∩Aj(P)=⌀for every P∈𝒫(T) and 1≤i<j≤d.\text{$T$ is recursively disjoint} \quad\Longleftrightarrow\quad \begin{gathered} A_i(P)\cap A_j(P)=\varnothing\\ \text{for every $P\in\mathcal P(T)$ and $1\leq i<j\leq d$.} \end{gathered}(7)✦

What Is Checked

The definitions and the disjointness equivalence concern trees of a common finite depth, with finite subset labels over an arbitrary set XX and laws with full support on finite sets of outgoing arcs.