OctoInformBeta

OpenAI preprint, September 2026 · §2. Resampling a spread family

§2 (setting): the planted union, posterior transition, and fragment: Posterior target weights and fragment recovery, with the exact density of the observed set

Resampling an indexed family through a planted union.

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

An indexed family of subsets can be sampled by adjoining one of its members to independent coordinate noise and then choosing a target from the observed union. The library defines this resampling experiment and the part of the target retained outside the noise.

Let XX and BB be finite sets, and let A=(Ab)b∈BA=(A_b)_{b\in B} be a family of subsets of XX. A finite probability law ν\nu on BB is a collection 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.✦ For a finite law λ\lambda on a finite set Ω\Omega and an event E⊆ΩE\subseteq\Omega, the event probability λ(E)\lambda(E) is the real number given by the sum in (2).✦ λ(E)=∑ω∈Eλω.\lambda(E)=\sum_{\omega\in E}\lambda_\omega.(2)

For a real parameter ρ\rho and a subset W⊆XW\subseteq X, the Bernoulli subset weight μρ(W)\mu_\rho(W) of WW is the real number given by the product in (3).✦ For 0≤ρ≤10\leq\rho\leq1, the product law μρ\mu_\rho on 2X2^X is the finite probability law that includes each coordinate independently with probability ρ\rho. μρ(W)=∏x∈X{ρ,x∈W,1−ρ,x∉W.\mu_\rho(W)=\prod_{x\in X} \begin{cases} \rho,&x\in W,\\ 1-\rho,&x\notin W. \end{cases}(3)

For a real parameter ρ\rho, a subset V⊆XV\subseteq X and an index b∈Bb\in B, the unnormalized target weight nρ(V,b)n_\rho(V,b) is the real number in (4), with the convention 0−1=00^{-1}=0.✦ nρ(V,b)={νb(ρ−1)|Ab|,Ab⊆V,0,Ab⊈V.n_\rho(V,b)= \begin{cases} \nu_b(\rho^{-1})^{|A_b|},&A_b\subseteq V,\\ 0,&A_b\nsubseteq V. \end{cases}(4)

The Claim

Definition 1. For a noise set W⊆XW\subseteq X and a source index c∈Bc\in B, the planted union Y(W,c)Y(W,c) is the subset of XX in (5).✦ Y(W,c)=W∪Ac.Y(W,c)=W\cup A_c.(5) The normalizing density Zρ(V)Z_\rho(V) of a subset V⊆XV\subseteq X is the sum in (6).✦ Zρ(V)=∑b∈Bnρ(V,b).Z_\rho(V)=\sum_{b\in B}n_\rho(V,b).(6) For a real parameter ρ\rho, a noise set W⊆XW\subseteq X and source and target indices c,b∈Bc,b\in B, the posterior target weight qW,c(b)q_{W,c}(b) is the real number in (7).✦ qW,c(b)={nρ(Y(W,c),b)Zρ(Y(W,c)),Zρ(Y(W,c))≠0,0,Zρ(Y(W,c))=0.q_{W,c}(b)= \begin{cases} \dfrac{n_\rho(Y(W,c),b)}{Z_\rho(Y(W,c))}, &Z_\rho(Y(W,c))\ne0,\\[6pt] 0,&Z_\rho(Y(W,c))=0. \end{cases}(7)✦ For a noise set W⊆XW\subseteq X, the source and target weight rW(c,b)r_W(c,b) of a pair (c,b)∈B×B(c,b)\in B\times B is the real number in (8).✦ rW(c,b)=νcqW,c(b).r_W(c,b)=\nu_c q_{W,c}(b).(8)

Suppose that ν\nu has full support and ρ>0\rho>0. The conditional resampling law RWR_W on B×BB\times B is the finite probability law with atom weights (9).✦ RW({(c,b)})=rW(c,b).R_W(\{(c,b)\})=r_W(c,b).(9)✦ For 0<ρ≤10<\rho\leq1, the joint resampling experiment ℙρ\mathbb P_\rho is the finite probability law on 2X×B×B2^X\times B\times B with atom weights (10).✦ ℙρ({(W,c,b)})=μρ(W)rW(c,b).\mathbb P_\rho(\{(W,c,b)\})=\mu_\rho(W)r_W(c,b).(10)

For every W⊆XW\subseteq X and b∈Bb\in B, the retained target fragment T(W,b)T(W,b) is the subset of XX defined by (11).✦ T(W,b)=Ab\W.T(W,b)=A_b\setminus W.(11)

Theorem 1. Let ν\nu be a finite probability law on BB, let ρ\rho be real, and let W⊆XW\subseteq X. Every pair (c,b)∈B×B(c,b)\in B\times B of positive source and target weight rW(c,b)>0r_W(c,b)>0 satisfies (12).✦ T(W,b)⊆Ac∩Ab.T(W,b)\subseteq A_c\cap A_b.(12)✦ For every target index b∈Bb\in B, recovery holds in the form (13).✦ Ab⊆W∪T(W,b).A_b\subseteq W\cup T(W,b).(13)✦ If ν\nu has full support and 0<ρ≤10<\rho\leq1, then every subset V⊆XV\subseteq X has observed mass (14) in the joint resampling experiment.✦ ℙρ({(W,c,b):Y(W,c)=V})=μρ(V)Zρ(V).\mathbb P_\rho\bigl(\{(W,c,b):Y(W,c)=V\}\bigr) =\mu_\rho(V)Z_\rho(V).(14)✦

What Is Checked

The joint experiment is stated over a family of subsets of a finite ground set, a full-support probability law on the finite index set, and 0<ρ≤10<\rho\leq1. For a full-support law ν\nu and ρ>0\rho>0, the source and target weights sum to one over all ordered pairs of indices, for every noise set W⊆XW\subseteq X.✦ ∑(c,b)∈B×BrW(c,b)=1.\sum_{(c,b)\in B\times B}r_W(c,b)=1.(15)