OctoInformBeta

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

Lemma 2.1: Change-of-measure estimates for observables outside a fixed target

An exponential bound for local resampling failure.

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 planted set can be resampled through its posterior label while retaining only the coordinates absent from a random background. Local failure concerns the normalizing density of this posterior law and the size of the retained fragment.

A finite probability law ww on a finite set Ω\Omega is a family of nonnegative weights wωw_\omega whose sum is one.✦ A finite probability law ww on Ω\Omega has full support when every weight wωw_\omega, for ω∈Ω\omega\in\Omega, is strictly positive.✦ For a finite probability law ww on Ω\Omega, the expectation 𝔼wg\mathbb E_w g of a real function gg on Ω\Omega and the probability ℙw(E)\mathbb P_w(E) of an event E⊆ΩE\subseteq\Omega are the weighted sums in (1). 𝔼wg=∑ω∈Ωwωg(ω),ℙw(E)=∑ω∈Ewω.\mathbb E_w g=\sum_{\omega\in\Omega}w_\omega g(\omega), \qquad \mathbb P_w(E)=\sum_{\omega\in E}w_\omega.(1)

Let XX be a finite ground set, BB a finite label set, (Ab)b∈B(A_b)_{b\in B} an indexed family of subsets of XX, and ν\nu a finite probability law on BB with weights νb\nu_b. For a real parameter aa, a finite probability law ν\nu on BB is aa-spread for an indexed family (Ab)b∈B(A_b)_{b\in B} of subsets of XX when every nonempty J⊆XJ\subseteq X satisfies (2). ∑b:J⊆Abνb≤a|J|(⌀≠J⊆X).\sum_{b:\,J\subseteq A_b}\nu_b\le a^{|J|} \qquad(\varnothing\ne J\subseteq X).(2)✦

For a subset WW of XX and a real parameter ρ\rho, the Bernoulli subset weight wρ(W)w_\rho(W) is the real number given by the product in (3). For 0≤ρ≤10\le\rho\le1, these weights form the law μρ\mu_\rho of independent coordinate inclusion with probability ρ\rho; the Bernoulli expectation of a real function ff on subsets of XX is its expectation with these weights. wρ(W)=∏x∈Wρ∏x∈X\W(1−ρ),𝔼μρf=∑W⊆Xwρ(W)f(W).w_\rho(W)=\prod_{x\in W}\rho\prod_{x\in X\setminus W}(1-\rho), \qquad \mathbb E_{\mu_\rho}f=\sum_{W\subseteq X}w_\rho(W)f(W).(3)

For a background W⊆XW\subseteq X, source c∈Bc\in B and target b∈Bb\in B, the planted union YY and retained fragment TT are the sets in (4). Y=W∪Ac,T=Ab\W.Y=W\cup A_c,\qquad T=A_b\setminus W.(4) For a label b∈Bb\in B and a set Y⊆XY\subseteq X, the unnormalized target weight rb(Y)r_b(Y) and normalizing density Z(Y)Z(Y) are the real numbers in (5), with the reciprocal at zero taken to be zero. rb(Y)={νb(ρ−1)|Ab|,Ab⊆Y,0,Ab⊈Y,Z(Y)=∑b∈Brb(Y).r_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}r_b(Y).(5) For a background W⊆XW\subseteq X and labels c,b∈Bc,b\in B, the posterior target weight qW(c,b)q_W(c,b) and source and target weight KW(c,b)K_W(c,b) are the real numbers in (6); a zero denominator gives posterior weight zero. qW(c,b)=rb(W∪Ac)Z(W∪Ac),KW(c,b)=νcqW(c,b).q_W(c,b)=\frac{r_b(W\cup A_c)}{Z(W\cup A_c)}, \qquad K_W(c,b)=\nu_c q_W(c,b).(6)

When ν\nu has full support and ρ>0\rho>0, the resampling transition law RWR_W is the finite probability law on B×BB\times B with masses KW(c,b)K_W(c,b).✦ For ν\nu with full support and 0<ρ≤10<\rho\le1, the joint resampling law ℙρ\mathbb P_\rho on triples (W,c,b)(W,c,b) is defined by (7). ℙρ(W,c,b)=wρ(W)KW(c,b).\mathbb P_\rho(W,c,b)=w_\rho(W)K_W(c,b).(7)✦

For a nonnegative integer mm, local success 𝒮m(W,c,b)\mathcal S_m(W,c,b) is the condition in (8). For a nonnegative integer mm, a background W⊆XW\subseteq X and labels c,b∈Bc,b\in B, local failure ℒm(W,c,b)\mathcal L_m(W,c,b) is the condition that local success 𝒮m(W,c,b)\mathcal S_m(W,c,b) does not hold.✦ 𝒮m(W,c,b)⇔Z(Y)≥e−10m and |T|≤⌊m/2⌋.\mathcal S_m(W,c,b)\quad\Longleftrightarrow\quad Z(Y)\ge e^{-10m}\ \text{ and }\ |T|\le\lfloor m/2\rfloor.(8)✦

A function ff on subsets of XX depends only on coordinates outside D⊆XD\subseteq X when, for all subsets W,V⊆XW,V\subseteq X, f(W)=f(V)f(W)=f(V) whenever W\D=V\DW\setminus D=V\setminus D.✦ For a real cutoff δ\delta, the density cutoff target mass Cδ(W,b)C_\delta(W,b) is the sum in (9) over sources whose planted union has density at least δ\delta. Cδ(W,b)=∑c:Z(W∪Ac)≥δKW(c,b).C_\delta(W,b)= \sum_{c:\,Z(W\cup A_c)\ge\delta}K_W(c,b).(9)✦

The Claim

Theorem 1. For every real ρ\rho, nonnegative integer mm, background WW and labels c,bc,b, local failure has the real threshold description (10). ℒm(W,c,b)⇔Z(Y)<e−10m or |T|>m/2.\mathcal L_m(W,c,b)\quad\Longleftrightarrow\quad Z(Y)<e^{-10m}\ \text{ or }\ |T|>m/2.(10)✦

Suppose ν\nu has full support, 0<ρ<10<\rho<1, mm is a positive integer, |Ab|≤m|A_b|\le m for every b∈Bb\in B, and ν\nu is aa-spread with a≥0a\ge0 and a/ρ≤e−50a/\rho\le e^{-50}. Then the joint law satisfies (11) and (12). ℙρ(ℒm(W,c,b))≤e−9m.\mathbb P_\rho\bigl(\mathcal L_m(W,c,b)\bigr)\le e^{-9m}.(11)✦ ℙρ(Z(Y)<e−10m or |T|>m/2)≤e−9m.\mathbb P_\rho\bigl(Z(Y)<e^{-10m}\ \text{ or }\ |T|>m/2\bigr) \le e^{-9m}.(12)✦

Let 0<ρ≤10<\rho\le1, a≥0a\ge0, and let ν\nu be aa-spread with a/ρ≤e−50a/\rho\le e^{-50}. Fix b∈Bb\in B and a nonnegative integer mm with |Ab|≤m|A_b|\le m. For every nonnegative real function ff depending only on coordinates outside AbA_b, the cutoff estimate (13) holds. 𝔼μρ[Ce−10m(W,b)f(W)]≤e11mνb𝔼μρf.\mathbb E_{\mu_\rho}\!\left[C_{e^{-10m}}(W,b)f(W)\right] \le e^{11m}\nu_b\mathbb E_{\mu_\rho}f.(13)✦ When ν\nu has full support, the transition law also satisfies (14), where dd denotes its sampled target. 𝔼W∼μρ𝔼(c,d)∼RW[𝟏{d=b,Z(W∪Ac)≥e−10m}f(W)]≤e11mνb𝔼μρf.\mathbb E_{W\sim\mu_\rho} \mathbb E_{(c,d)\sim R_W}\!\left[ \mathbf 1_{\{d=b,\ Z(W\cup A_c)\ge e^{-10m}\}}f(W)\right] \le e^{11m}\nu_b\mathbb E_{\mu_\rho}f.(14)✦

In the paper, the result reads: for an aa-spread indexed law with |Ab|≤m|A_b|\le m for every label, a positive integer mm, 0<ρ<10<\rho<1 and a/ρ≤e−50a/\rho\le e^{-50}, draw W∼μρW\sim\mu_\rho independently of the source c∼νc\sim\nu and then take the specified posterior target dd, declare local failure when Z(Y)<e−10mZ(Y)<e^{-10m} or |T|>m/2|T|>m/2, with T=Ad\WT=A_d\setminus W, and obtain ℙ(local failure)≤e−9m\mathbb P(\text{local failure})\le e^{-9m} together with 𝔼[𝟏{d=b,Z(Y)≥e−10m}f(W)]≤e11mνb𝔼μρf\mathbb E[\mathbf 1_{\{d=b,\ Z(Y)\ge e^{-10m}\}}f(W)] \le e^{11m}\nu_b\mathbb E_{\mu_\rho}f for every fixed target bb and every nonnegative real ff depending only on W∩(X\Ab)W\cap(X\setminus A_b).

What Is Checked

The failure bounds are stated over the joint resampling law for a finite label law with full support and a finite indexed family under the spread, size and parameter hypotheses of (11); the size hypothesis in (13) concerns only its fixed target, and its parameter range includes m=0m=0 and ρ=1\rho=1.

For every ν\nu with full support, positive ρ\rho and background WW, the source and target weights satisfy the normalization identity (15). ∑(c,b)∈B×BKW(c,b)=1.\sum_{(c,b)\in B\times B}K_W(c,b)=1.(15)✦