OctoInformBeta

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

Theorem 3.1: A quantitative estimate for disjoint spread probability trees with geometrically growing positive capacities

Random subsets can cover a tree path.

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

Let XX be a finite ground set. A rooted tree whose arcs are labelled by subsets of XX gives a family of sets, one for each full path. A random subset W⊆XW\subseteq X covers a path when it contains every label along that path.

A finite probability law ν\nu on a finite set BB is a family of real weights νb\nu_b satisfying (1); it has full support if νb>0\nu_b>0 for every b∈Bb\in B.✦ ν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 probability tree TT of depth kk over XX is a finite rooted tree with all leaves at depth kk, in which each internal vertex has a finite set BB of outgoing branches, a probability law of full support on BB, and a label Ab⊆XA_b\subseteq X on each outgoing arc.✦ A probability tree of depth zero consists of a single leaf.✦

A full path PP in TT starts at the root and chooses one outgoing branch at each internal vertex until it reaches a leaf.✦ The label union U(P)U(P) of a full path PP in a probability tree TT over XX is the subset of XX defined by (2), where A1(P),…,Ak(P)A_1(P),\ldots,A_k(P) are the successive arc labels and the empty union equals ⌀\varnothing. U(P)=⋃i=1kAi(P).U(P)=\bigcup_{i=1}^{k}A_i(P).(2) The path covering event 𝒞T\mathcal C_T is the family of subsets of XX in (3). 𝒞T={W⊆X:there is a full path P in T with U(P)⊆W}.\mathcal C_T =\{W\subseteq X:\text{there is a full path $P$ in $T$ with }U(P)\subseteq W\}.(3)✦

For ρ∈[0,1]\rho\in[0,1], let μρ\mu_\rho be the probability law on subsets of XX under which coordinates are included independently with probability ρ\rho. Its mass at a subset WW and its probability of an event 𝒜\mathcal A are given by (4). μρ({W})=∏x∈X{ρ,x∈W,1−ρ,x∉W,μρ(𝒜)=∑W∈𝒜μρ({W}).\mu_\rho(\{W\})=\prod_{x\in X} \begin{cases} \rho,&x\in W,\\ 1-\rho,&x\notin W, \end{cases} \qquad \mu_\rho(\mathcal A)=\sum_{W\in\mathcal A}\mu_\rho(\{W\}).(4)

Disjointness, Capacities and Spread

A probability tree TT is disjoint if the arc labels on every full path are pairwise disjoint.✦ Level capacities ℓ1,…,ℓk\ell_1,\ldots,\ell_k for TT are nonnegative integers such that every arc label at level ii has cardinality at most ℓi\ell_i.✦ Levels are numbered from one here, while the declarations index them from zero.

For σ>0\sigma>0, an indexed family of labels (Ab)b∈B(A_b)_{b\in B} with probability law ν\nu is σ\sigma-spread if it satisfies (5). Level spread parameters σ1,…,σk\sigma_1,\ldots,\sigma_k for a probability tree TT of depth kk are numbers such that the outgoing labels at each vertex of depth i−1i-1, with that vertex’s probability law, are σi\sigma_i-spread.✦ ∑b∈BS⊆Abνb≤σ|S|for every S⊆X.\sum_{\substack{b\in B\\S\subseteq A_b}}\nu_b \leq \sigma^{|S|} \qquad\text{for every }S\subseteq X.(5) A probability tree TT is σ\sigma-spread when all its level spread parameters equal σ\sigma. Write log⁡2x=log⁡x/log⁡2\log_2 x=\log x/\log 2 for the base-two logarithm.

The Claim

Theorem 1. Let TT be a disjoint probability tree of positive depth kk over a finite ground set XX. Suppose that TT is σ\sigma-spread for some σ>0\sigma>0, and that it has positive integer level capacities ℓ1,…,ℓk\ell_1,\ldots,\ell_k satisfying 16ℓi≤ℓi+116\ell_i\leq\ell_{i+1} for 1≤i<k1\leq i<k. Then μρ(𝒞T)≥23,ρ=min⁡{1,16e50σ(1+log⁡2ℓk)}.\mu_\rho(\mathcal C_T)\geq\frac23, \qquad \rho=\min\{1,16e^{50}\sigma(1+\log_2\ell_k)\}.(6)✦

What Is Checked

The estimate (6) is stated over finite ground sets and probability trees of positive depth, with full support at every internal vertex, disjoint path labels, a common positive spread parameter, and positive level capacities growing by a factor of at least sixteen.