OctoInformBeta

OpenAI preprint, September 2026 · §6. Adaptive exploration and the final contradiction

Lemma 6.1: Finite histories fix observed coordinates and retain Bernoulli parameters on the others

Finite exploration preserves pending connection promises.

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 pending coarse vertex comes with a finite graph in ℤ3\mathbb Z^3 and an event that the origin reaches its inner cube. Revealing its coarse block raises the question of how to describe the remaining random variables and the probabilities attached to the other pending vertices.

Let MM be the bond or site model on the nearest-neighbor lattice ℤ3\mathbb Z^3. Write eie_i for the positive unit vector in coordinate direction ii. A lattice bond (x,i)(x,i) has endpoints xx and x+eix+e_i; incidence with two vertices means that they are these endpoints in either order. The coordinate set EME_M is the set of lattice bonds for the bond model and ℤ3\mathbb Z^3 for the site model.✦ A configuration ω∈{0,1}EM\omega\in\{0,1\}^{E_M} assigns closed or open states to these coordinates.✦ Two lattice vertices are nearest neighbors when their difference is ±ei\pm e_i for some ii.✦ Open adjacency requires their joining bond to be open in the bond model, and both vertices to be open in the site model.✦ A vertex is available unconditionally for bonds and precisely when it is open for sites.✦

A finite lattice subgraph G=(VG,EG)G=(V_G,E_G) consists of finite sets of lattice vertices and bonds, with both endpoints of every bond in VGV_G.✦ The underlying simple graph of a finite lattice subgraph G=(VG,EG)G=(V_G,E_G) has vertex set VGV_G and adjacency given by endpoint incidence with a bond of EGE_G.✦ Write x↔Gyx\leftrightarrow_G y for connection by a finite open path in GG.✦ A bond path may have length zero at any vertex. In the site model, an open path requires all its vertices to be open, including the coincident endpoints of a path of length zero. The finite target connection event ℋG(o,T)\mathcal H_G(o,T) for a vertex o∈VGo\in V_G and a target set T⊆ℤ3T\subseteq\mathbb Z^3 is the set of configurations specified by ℋG(o,T)={ω:∃y∈T∩VG,o↔Gy}\mathcal H_G(o,T)=\{\omega:\exists y\in T\cap V_G,\ o\leftrightarrow_G y\}.✦ The graph variables ℰM(G)\mathcal E_M(G) are EGE_G for bonds and VGV_G for sites.✦

A lattice box B=[ℓ,u]∩ℤ3B=[\ell,u]\cap\mathbb Z^3 has coordinatewise ordered corners.✦ The vertices of a lattice box B=[ℓ,u]∩ℤ3B=[\ell,u]\cap\mathbb Z^3 are the integer triples with ℓi≤xi≤ui\ell_i\le x_i\le u_i in every coordinate, and the bonds of BB have both endpoints among those vertices. Write GBG_B for this finite lattice graph✦ and ℰM(B)=ℰM(GB)\mathcal E_M(B)=\mathcal E_M(G_B) for its variables.✦ A graph contains BB when it contains all these vertices and bonds.✦ For a lattice center cc and a coordinate radius bb, the cube Λb(c)\Lambda_b(c) is the box with corners c−(b,b,b)c-(b,b,b) and c+(b,b,b)c+(b,b,b).✦

Finite Histories

For a coordinate set EE and a parameter vector 𝒑=(pe)e∈E∈[0,1]E\boldsymbol p=(p_e)_{e\in E}\in[0,1]^E, let ℙ𝒑\mathbb P_{\boldsymbol p} be the independent Bernoulli product measure, with opening probability pep_e at coordinate ee.✦ The notation ℙq\mathbb P_q means the constant parameter vector pe=qp_e=q.

A finite pattern [ξ]J[\xi]_J is the event prescribing a configuration ξ\xi on a finite set J⊂EJ\subset E.✦ The pinned parameter vector 𝒑J,ξ\boldsymbol p^{J,\xi} fixes these coordinates to their prescribed states, as in (1).✦ [ξ]J={ω:ωe=ξe for every e∈J},peJ,ξ={ξe,e∈J,pe,e∉J.[\xi]_J=\{\omega:\omega_e=\xi_e\text{ for every }e\in J\}, \qquad p^{J,\xi}_e= \begin{cases} \xi_e,&e\in J,\\ p_e,&e\notin J. \end{cases}(1) The partial replacement ρJ(ξ,ω)\rho_J(\xi,\omega) is the configuration equal to ξ\xi on JJ and to ω\omega outside JJ.✦

A finite observation history h=(Jh,ξh)h=(J_h,\xi_h) consists of a finite observed set Jh⊂EJ_h\subset E and a configuration ξh\xi_h specifying its values.✦ For a finite set R⊂ER\subset E, the extended history h⊕(R,ω)h\oplus(R,\omega) records the values of ω\omega on RR, overwriting any earlier values there.✦ Its definition and the history parameter vector 𝒑hq\boldsymbol p_h^q are given in (2). h⊕(R,ω)=(Jh∪R,ρR(ω,ξh)),𝒑hq=(q𝟏)Jh,ξh.h\oplus(R,\omega) =\bigl(J_h\cup R,\rho_R(\omega,\xi_h)\bigr), \qquad \boldsymbol p_h^q=(q\boldsymbol 1)^{J_h,\xi_h}.(2)

Coarse Blocks and Packets

A coarse point v=(v1,v2)v=(v_1,v_2) belongs to ℤ2\mathbb Z^2.✦ The four directions d=0,1,2,3d=0,1,2,3 have outward steps ad=(0,−1),(1,0),(0,1),(−1,0)a_d=(0,-1),(1,0),(0,1),(-1,0), in that order.✦ For a nonnegative integer scale rr, the embedding and the surrounding and inner cubes are defined by (3). cr(v)=((20r+1)v1,(20r+1)v2,0),Qv=Λ10r(cr(v)),Bv=Λ4r(cr(v)).c_r(v)=\bigl((20r+1)v_1,(20r+1)v_2,0\bigr), \qquad Q_v=\Lambda_{10r}(c_r(v)), \qquad B_v=\Lambda_{4r}(c_r(v)).(3) For coarse points v,w∈ℤ2v,w\in\mathbb Z^2, the interface Ir(v,w)I_r(v,w) is the set of lattice bonds with one endpoint in QvQ_v and the other in QwQ_w, in either order. For coarse points v,w∈ℤ2v,w\in\mathbb Z^2, the interbox variable set LM(v,w)L_M(v,w) is Ir(v,w)I_r(v,w) in the bond model and the empty set in the site model.✦

The block WM(v,a)W_M(v,a) consists of the variables in QvQ_v and its interface with its parent aa.✦ The root variables UMU_M and the exposed variables XM(D)X_M(D) for a finite processed set D⊂ℤ2D\subset\mathbb Z^2 are defined alongside it in (4). WM(v,a)=ℰM(Qv)∪LM(v,a),UM=ℰM(Q0)∪⋃d=03LM(0,ad),XM(D)=UM∪⋃v∈DℰM(Qv)∪⋃v,w∈DLM(v,w).\begin{aligned} W_M(v,a)&=\mathcal E_M(Q_v)\cup L_M(v,a),\\ U_M&=\mathcal E_M(Q_0)\cup\bigcup_{d=0}^3L_M(0,a_d),\\ X_M(D)&=U_M\cup\bigcup_{v\in D}\mathcal E_M(Q_v) \cup\bigcup_{v,w\in D}L_M(v,w). \end{aligned}(4)

An exploration packet t=(vt,at,Gt)t=(v_t,a_t,G_t) consists of a coarse vertex, a parent vertex, and a finite lattice graph containing QvtQ_{v_t} and the lattice origin.✦ The root connection event of an exploration packet t=(vt,at,Gt)t=(v_t,a_t,G_t) is Ht=ℋGt(0,Bvt)H_t=\mathcal H_{G_t}(0,B_{v_t}).✦ For a graph GG containing QvQ_v and a coarse vertex xx, the extension of GG toward xx adds the vertices and bonds of QxQ_x and the interface bonds Ir(v,x)I_r(v,x).✦ For an exploration packet t=(vt,at,Gt)t=(v_t,a_t,G_t) and a coarse vertex xx, the child packet t[x]t[x] is the packet with vertex xx, parent vtv_t, and graph obtained from GtG_t by adding the vertices and bonds of QxQ_x and the interface bonds Ir(vt,x)I_r(v_t,x). The root packet t0t_0 has vertex and parent 00 and graph GQ0G_{Q_0}.✦

The Exploration Rule

An exploration state s=(h,D,𝒬,𝒢,ℬ)s=(h,D,\mathcal Q,\mathcal G,\mathcal B) consists of a finite history, a finite processed set, a finite ordered queue of packets, and finite sets of good and bad coarse vertices.✦ The visited set is D∪{vt:t∈𝒬}D\cup\{v_t:t\in\mathcal Q\}.✦ For a packet tt, the candidate list 𝒞s(t)\mathcal C_s(t) consists of the children t[vt+ad]t[v_t+a_d] in direction order, retaining only those whose vertices are outside the visited set.✦

Write t::𝒯t::\mathcal T for a nonempty queue with first packet tt and remaining queue 𝒯\mathcal T. The revelation set RsR_s consists of the unobserved variables of the first queued block, and hs+(ω)h_s^+(\omega) is the history after their revelation, as specified in (5). Rs={⌀,𝒬=⌀,WM(vt,at)\Jh,𝒬=t::𝒯,hs+(ω)=h⊕(Rs,ω).R_s= \begin{cases} \varnothing,&\mathcal Q=\varnothing,\\ W_M(v_t,a_t)\setminus J_h,&\mathcal Q=t::\mathcal T, \end{cases} \qquad h_s^+(\omega)=h\oplus(R_s,\omega).(5) For q∈[0,1]q\in[0,1] and δ∈ℝ\delta\in\mathbb R, acceptance of a packet tt in state ss is the condition 𝒜s(t,ω)\mathcal A_s(t,\omega) in (6), where ξhs+(ω)\xi_{h_s^+(\omega)} denotes the values of the extended history. 𝒜s(t,ω)⇔ξhs+(ω)∈Ht and ℙ𝒑hs+(ω)q(Hu)>1−δfor every u∈𝒞s(t).\mathcal A_s(t,\omega) \quad\Longleftrightarrow\quad \xi_{h_s^+(\omega)}\in H_t \ \text{ and }\ \mathbb P_{\boldsymbol p_{h_s^+(\omega)}^q}(H_u)>1-\delta \quad\text{for every }u\in\mathcal C_s(t).(6)✦

The single exploration step Φq,δ(s,ω)\Phi_{q,\delta}(s,\omega) uses the history hs+(ω)h_s^+(\omega). For a nonempty queue t::𝒯t::\mathcal T, it adds vtv_t to DD and removes tt from the queue. On acceptance, it appends 𝒞s(t)\mathcal C_s(t) to 𝒯\mathcal T and adds vtv_t to 𝒢\mathcal G; on rejection, it leaves 𝒯\mathcal T as the queue and adds vtv_t to ℬ\mathcal B. The other classification set is unchanged in either case. An empty queue leaves the state unchanged. The finite run Φq,δn(s,ω)\Phi_{q,\delta}^n(s,\omega) applies this step nn times with the same configuration ω\omega, starting from ss at n=0n=0.✦

A valid exploration state ss at (q,δ)(q,\delta) is a state satisfying the conditions 𝖵q,δ(s)\mathsf V_{q,\delta}(s) in (7). The last condition is the strict pending connection promise. 𝖵q,δ(s)⇔0∈D,(vt)t∈𝒬 has no repetitions,vt∉D,at∈Dfor every t∈𝒬,Jh⊆XM(D),ℰM(Gt)⊆Jh∪WM(vt,at)for every t∈𝒬,ℙ𝒑hq(Ht)>1−δfor every t∈𝒬.\begin{aligned} \mathsf V_{q,\delta}(s)\quad\Longleftrightarrow\quad& 0\in D,\qquad (v_t)_{t\in\mathcal Q}\text{ has no repetitions},\\ &v_t\notin D,\quad a_t\in D &&\text{for every }t\in\mathcal Q,\\ &J_h\subseteq X_M(D),\\ &\mathcal E_M(G_t)\subseteq J_h\cup W_M(v_t,a_t) &&\text{for every }t\in\mathcal Q,\\ &\mathbb P_{\boldsymbol p_h^q}(H_t)>1-\delta &&\text{for every }t\in\mathcal Q. \end{aligned}(7)✦

Scale Parameters and Initialization

A quarter-face index (i,σ)(i,\sigma) is a pair consisting of a coordinate ii and a sign vector σ∈{−1,1}3\sigma\in\{-1,1\}^3.✦ The quarter-face Fi,σ(c,n)F_{i,\sigma}(c,n) of the cube Λn(c)\Lambda_n(c) corresponding to the index (i,σ)(i,\sigma) is the set in (8); the 24 signed-coordinate quarter-faces may overlap on their boundaries. Fi,σ(c,n)={x∈Λn(c):xi=ci+σin,0≤σj(xj−cj)≤n for j≠i}.F_{i,\sigma}(c,n)= \{x\in\Lambda_n(c):x_i=c_i+\sigma_i n,\ 0\le \sigma_j(x_j-c_j)\le n\text{ for }j\ne i\}.(8) The confined seed event 𝒮M(c,a,b;T)\mathcal S_M(c,a,b;T) consists of configurations having an available vertex x∈Λa(c)x\in\Lambda_a(c) and a vertex y∈Ty\in T joined by a finite path of open lattice adjacencies restricted to Λb(c)\Lambda_b(c).✦ Restricted adjacency requires both vertices of each step to belong to the containing cube.✦

Finite scale parameters 𝔰=(p,q,δ,η,τ,γ,m,K,R,r)\mathfrak s=(p,q,\delta,\eta,\tau,\gamma,m,K,R,r) form a tuple satisfying 0<p<10<p<1, p/2<q<pp/2<q<p, and δ,η,τ,γ∈(0,1)\delta,\eta,\tau,\gamma\in(0,1). The radii m,R,rm,R,r and trial count KK are nonnegative integers with m>0m>0, K>0K>0, m<Rm<R, and 100(R+1)<r100(R+1)<r. Write NM(m)=|ℰM(Λm(0))|N_M(m)=|\mathcal E_M(\Lambda_m(0))| for the seed variable count✦ and ε=12(1/100)7\varepsilon=\tfrac12(1/100)^7 for the contour error tolerance.✦ The error and size budgets are (9). δ+52ηδ<ε,τ<η4,γ<δ,2γτ<η4,4K(p/2)NM(m)+1<η4,1(1−p)K(8m+5)3(R−m)<η4.\begin{gathered} \delta+\frac{52\eta}{\delta}<\varepsilon,\qquad \tau<\frac{\eta}{4},\qquad \gamma<\delta,\qquad \frac{2\gamma}{\tau}<\frac{\eta}{4},\\ \frac{4}{K(p/2)^{N_M(m)+1}}<\frac{\eta}{4}, \qquad \frac{1}{(1-p)^{K(8m+5)^3}(R-m)}<\frac{\eta}{4}. \end{gathered}(9) The quarter-face requirement on these parameters is (10), for every center cc, every quarter-face index (i,σ)(i,\sigma), and each n∈{2r,2r+1,10r}n\in\{2r,2r+1,10r\}. ℙq(𝒮M(c,m,n;Fi,σ(c,n)))>1−γ.\mathbb P_q\bigl(\mathcal S_M(c,m,n;F_{i,\sigma}(c,n))\bigr)>1-\gamma.(10)

The initial state sinits_{\mathrm{init}} declares the root variables open, processes the coarse origin, and queues its four child packets as in (11), where 𝟏\boldsymbol 1 is the configuration with every coordinate open. hinit=(UM,𝟏),sinit=(hinit,{0},[t0[a0],t0[a1],t0[a2],t0[a3]],{0},⌀).h_{\mathrm{init}}=(U_M,\boldsymbol 1),\qquad s_{\mathrm{init}}= \bigl(h_{\mathrm{init}},\{0\}, [t_0[a_0],t_0[a_1],t_0[a_2],t_0[a_3]],\{0\},\varnothing\bigr).(11)✦ Write ℙI=ℙ𝒑hinitq\mathbb P_I=\mathbb P_{\boldsymbol p_{h_{\mathrm{init}}}^q} for the initial pinned product measure.

The Claim

Theorem 1. Let 𝒑∈[0,1]E\boldsymbol p\in[0,1]^E, let J⊂EJ\subset E be finite, and let ξ\xi be a configuration. For every measurable event AA, the finite-history factorization is (12). ℙ𝒑([ξ]J∩A)=ℙ𝒑([ξ]J)ℙ𝒑J,ξ(A).\mathbb P_{\boldsymbol p}([\xi]_J\cap A) =\mathbb P_{\boldsymbol p}([\xi]_J)\, \mathbb P_{\boldsymbol p^{J,\xi}}(A).(12)✦ For any finite history hh, parameter q∈[0,1]q\in[0,1], finite observation set RR, and configuration ω\omega, the parameter update is (13). 𝒑h⊕(R,ω)q=(𝒑hq)R,ω.\boldsymbol p_{h\oplus(R,\omega)}^q =(\boldsymbol p_h^q)^{R,\omega}.(13)✦

Fix either model MM, a nonnegative integer rr, q∈[0,1]q\in[0,1], and δ∈ℝ\delta\in\mathbb R. Let ss be valid at (q,δ)(q,\delta), with queue t::𝒯t::\mathcal T, and let u∈𝒯u\in\mathcal T. For every configuration ω\omega, the later packet probability satisfies (14). ℙ𝒑hs+(ω)q(Hu)=ℙ𝒑hq(Hu).\mathbb P_{\boldsymbol p_{h_s^+(\omega)}^q}(H_u) =\mathbb P_{\boldsymbol p_h^q}(H_u).(14)✦ For any exploration state ss valid at (q,δ)(q,\delta) and every configuration ω\omega, a single exploration step preserves validity, as in (15). 𝖵q,δ(Φq,δ(s,ω)).\mathsf V_{q,\delta}\bigl(\Phi_{q,\delta}(s,\omega)\bigr).(15)✦ For any exploration state ss valid at (q,δ)(q,\delta), every configuration ω\omega, and every nonnegative integer nn, the finite-run statement is (16). 𝖵q,δ(Φq,δn(s,ω)).\mathsf V_{q,\delta}\bigl(\Phi_{q,\delta}^n(s,\omega)\bigr).(16)✦ The initial state associated with finite scale parameters 𝔰\mathfrak s is valid, as in (17). 𝖵q,δ(sinit).\mathsf V_{q,\delta}(s_{\mathrm{init}}).(17)✦

In the paper, the result reads: conditional on any positive-probability finite revealed history hh, all unrevealed variables are independent Bernoulli(q)(q), and ℙI(Ht∣h)>1−δ\mathbb P_I(H_t\mid h)>1-\delta for every pending packet tt at every step.

What Is Checked

The factorization concerns measurable events and arbitrary finite patterns; the exploration statements concern finite observation histories and packet graphs in either percolation model.