OctoInformBeta

OpenAI preprint, September 2026 · Section 2. From conditioning to a threshold bound

Section 2 (proof counterpart): Selected-coordinate winning probabilities control finite-law moments and quantitative threshold estimates

Moment bounds for repeated entangled wins.

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 repeated entangled strategy can correlate its answers across coordinates. The quantity of interest is the probability that its number of wins exceeds the single-game entangled value by a positive fraction of the repetition length.

A finite probability law ρ\rho on a finite set Ω\Omega is a function assigning nonnegative weights ρ(ω)\rho(\omega) with total mass one.✦ The expectation of a function ff from Ω\Omega to a real vector space is the weighted sum in (1): 𝔼ρ[f]=∑ω∈Ωρ(ω)f(ω).\mathbb E_\rho[f]=\sum_{\omega\in\Omega}\rho(\omega)f(\omega).(1)✦ The uniform law uIu_I on a nonempty finite coordinate set II, and the product law of coordinate laws ρi\rho_i, have the weights in (2); here k=|I|k=|I| and zz assigns an outcome to each coordinate: uI(i)=1k,(⨂i∈Iρi)(z)=∏i∈Iρi(zi).u_I(i)=\frac1k, \qquad \Bigl(\bigotimes_{i\in I}\rho_i\Bigr)(z) =\prod_{i\in I}\rho_i(z_i).(2)

Let w(ω,i)w(\omega,i) be a winning predicate on outcomes and coordinates. For a tested set C⊆IC\subseteq I, the selected-win event ECE_C consists of outcomes winning every coordinate in CC; its indicator is 𝟏EC\mathbf1_{E_C} and its probability is pCp_C. The win count WkW_k and winning fraction RR are functions on Ω\Omega that count successful coordinate tests and average their indicators under uIu_I, respectively. For a tested set C⊆IC\subseteq I and t∈ℕt\in\mathbb N, the restricted moment mC(t)m_C(t) is the expectation under ρ\rho of RtR^t multiplied by the selected-win indicator.✦ These quantities and the threshold probability Θρ(s)\Theta_\rho(s), for s∈ℝs\in\mathbb R, are defined in (3): EC={ω:w(ω,i) holds for every i∈C},pC=𝔼ρ[𝟏EC],Wk(ω)=∑i∈I𝟏{w(ω,i)},R(ω)=Wk(ω)k,mC(t)=𝔼ρ[𝟏ECRt],Θρ(s)=𝔼ρ[𝟏{R≥s}].\begin{aligned} E_C&=\{\omega:w(\omega,i)\text{ holds for every }i\in C\}, &p_C&=\mathbb E_\rho[\mathbf1_{E_C}],\\ W_k(\omega)&=\sum_{i\in I}\mathbf1_{\{w(\omega,i)\}}, &R(\omega)&=\frac{W_k(\omega)}k,\\ m_C(t)&=\mathbb E_\rho[\mathbf1_{E_C}R^t], &\Theta_\rho(s)&=\mathbb E_\rho[\mathbf1_{\{R\ge s\}}]. \end{aligned}(3)

The Repeated Experiment

A two-player nonlocal game GG has nonempty finite question alphabets X,YX,Y and answer alphabets A,BA,B, a question law μ\mu on X×YX\times Y, and an acceptance predicate V(x,y,a,b)V(x,y,a,b).✦ Write d=|A||B|d=|A||B|; all logarithms are natural.

A local positive operator-valued measure (POVM) PP with a finite outcome alphabet AA on a finite-dimensional Hilbert space is a family of positive semidefinite effects PaP^a, indexed by a∈Aa\in A, whose sum is the identity.✦ A coefficient matrix HH in finite local bases represents the bipartite state vector in (4), where its squared Hilbert-Schmidt norm is also defined: |H⟩=∑u,vHuv|u⟩⊗|v⟩,∥H∥HS2=∑u,v|Huv|2.|H\rangle=\sum_{u,v}H_{uv}|u\rangle\otimes|v\rangle, \qquad \|H\|_{\mathrm{HS}}^2=\sum_{u,v}|H_{uv}|^2.(4) For local operators L,NL,N, their bipartite operator expectation eH(L,N)e_H(L,N) and real Born probability βH(L,N)\beta_H(L,N) are given by (5): eH(L,N)=⟨H|L⊗N|H⟩,βH(L,N)=Re⁡eH(L,N).e_H(L,N)=\langle H|L\otimes N|H\rangle, \qquad \beta_H(L,N)=\operatorname{Re}e_H(L,N).(5) For ∥H∥HS2=1\|H\|_{\mathrm{HS}}^2=1 and local POVMs P,QP,Q, the joint measurement distribution assigns an outcome pair (a,b)(a,b) the weight βH(Pa,Qb)\beta_H(P^a,Q^b).✦

A single-round entangled strategy SS for GG consists of a unit bipartite pure state |HS⟩|H_S\rangle on nonzero finite-dimensional local Hilbert spaces, and local POVMs {Axa}a∈A\{A_x^a\}_{a\in A} and {Byb}b∈B\{B_y^b\}_{b\in B} for each question. Its Born probabilities pS(a,b∣x,y)p_S(a,b\mid x,y), winning probability val⁡G(S)\operatorname{val}_G(S), and the finite-dimensional entangled value vv are defined by (6): pS(a,b∣x,y)=βHS(Axa,Byb),val⁡G(S)=∑x,yμ(x,y)∑a,bV(x,y,a,b)pS(a,b∣x,y),v=supSval⁡G(S).\begin{aligned} p_S(a,b\mid x,y)&=\beta_{H_S}(A_x^a,B_y^b),\\ \operatorname{val}_G(S) &=\sum_{x,y}\mu(x,y) \sum_{\substack{a,b\\V(x,y,a,b)}}p_S(a,b\mid x,y), \qquad v=\sup_S\operatorname{val}_G(S). \end{aligned}(6)

A repeated quantum experiment MM for GG on II consists of a normalized coefficient matrix HH and local POVM families P𝒙P_{\boldsymbol x} and Q𝒚Q_{\boldsymbol y}, whose outcomes are full answer vectors in AIA^I and BIB^I and whose questions are full local vectors in XIX^I and YIY^I.✦ A question profile z:I→X×Yz:I\to X\times Y is a function assigning the question pair zi=(xi,yi)z_i=(x_i,y_i) to each coordinate.✦ A transcript (z,𝒂,𝒃)(z,\boldsymbol a,\boldsymbol b) is a question profile and a pair of full answer vectors.✦ The conditional answer distribution νz\nu_z and the joint transcript law ρM\rho_M are given by (7): νz(𝒂,𝒃)=βH(P𝒙𝒂,Q𝒚𝒃),ρM(z,𝒂,𝒃)=(∏i∈Iμ(xi,yi))νz(𝒂,𝒃).\begin{aligned} \nu_z(\boldsymbol a,\boldsymbol b) &=\beta_H(P_{\boldsymbol x}^{\boldsymbol a}, Q_{\boldsymbol y}^{\boldsymbol b}),\\ \rho_M(z,\boldsymbol a,\boldsymbol b) &=\Bigl(\prod_{i\in I}\mu(x_i,y_i)\Bigr) \nu_z(\boldsymbol a,\boldsymbol b). \end{aligned}(7) The coordinate winning predicate for a transcript is V(xi,yi,ai,bi)V(x_i,y_i,a_i,b_i).✦ The joint selected-win indicator and winning probability of MM are 𝟏EC\mathbf1_{E_C} and pCp_C from (3), taken under ρM\rho_M. Write ΘM=ΘρM\Theta_M=\Theta_{\rho_M}. For a positive excess δ\delta, the threshold event has the two equivalent forms in (8): ΘM(v+δ)=PrρM[R≥v+δ]=PrρM[Wk≥⌈(v+δ)k⌉].\Theta_M(v+\delta) =\Pr_{\rho_M}[R\ge v+\delta] =\Pr_{\rho_M}[W_k\ge\lceil(v+\delta)k\rceil].(8)✦ For a repeated quantum experiment MM and a tested set C⊆IC\subseteq I with pC>0p_C>0 and |C|<k|C|<k, the conditioning budget τ(C)\tau(C) is the real number given by (9): τ(C)=log⁡(1/pC)+|C|log⁡dk−|C|.\tau(C)=\frac{\log(1/p_C)+|C|\log d}{k-|C|}.(9)

The Claim

Theorem 1. For a finite outcome law ρ\rho and coordinate winning tests on a nonempty finite set II, the moment recursion (10) holds for every C⊆IC\subseteq I and t∈ℕt\in\mathbb N: mC(t+1)=1k∑i∈ImC∪{i}(t).m_C(t+1)=\frac1k\sum_{i\in I}m_{C\cup\{i\}}(t).(10)✦

Let r,e≥0r,e\ge0 and T∈ℕT\in\mathbb N. Suppose the insertion estimate (11) holds for every tested set CC with |C|<T|C|<T: 1k∑i∈IpC∪{i}≤rpC+e.\frac1k\sum_{i\in I}p_{C\cup\{i\}}\le r p_C+e.(11) For every C⊆IC\subseteq I and t∈ℕt\in\mathbb N with |C|+t≤T|C|+t\le T, the moment upper bound is (12): mC(t)≤rtpC+e∑j=0t−1rj.m_C(t)\le r^t p_C+e\sum_{j=0}^{t-1}r^j.(12)✦

Let u≥0u\ge0, δ>0\delta>0, u+δ≤1u+\delta\le1, and e≥0e\ge0. For T∈ℕT\in\mathbb N, assume (11) for every |C|<T|C|<T with r=u+δ/2r=u+\delta/2. The abstract threshold power bound is (13): Θρ(u+δ)(u+δ)T≤(u+δ/2)T+2eδ.\Theta_\rho(u+\delta)(u+\delta)^T \le (u+\delta/2)^T+\frac{2e}{\delta}.(13)✦

For the repeated quantum experiment MM, let C⊆IC\subseteq I satisfy pC>0p_C>0 and |C|<k|C|<k. Suppose 0<δ≤10<\delta\le1 and τ(C)≤δ8/280\tau(C)\le\delta^8/2^{80}. The fresh-coordinate insertion bound is (14): ∑i∈I\CpC∪{i}≤(v+δ/4)pC(k−|C|).\sum_{i\in I\setminus C}p_{C\cup\{i\}} \le (v+\delta/4)p_C(k-|C|).(14)✦

Let δ>0\delta>0 and v+δ≤1v+\delta\le1. For every integer T≥0T\ge0 satisfying T≤δ9k/(290(1+log⁡d))T\le\delta^9 k/(2^{90}(1+\log d)), the repeated-game threshold power bound is (15): ΘM(v+δ)(v+δ)T≤(v+δ/2)T+2δexp⁡(−δ8k283).\Theta_M(v+\delta)(v+\delta)^T \le (v+\delta/2)^T +\frac2\delta\exp\!\left(-\frac{\delta^8 k}{2^{83}}\right).(15)✦ For δ>0\delta>0 and v+δ≤1v+\delta\le1, the mean threshold bound is (16): ΘM(v+δ)≤e−δ.\Theta_M(v+\delta)\le e^{-\delta}.(16)✦

What Is Checked

The abstract bounds are stated over finite outcome laws and coordinate winning tests; the game bounds are stated over finite-dimensional shared states and full-vector local POVMs with independent question sampling. The joint measurement distributions defined by (5) and the transcript law in (7) have nonnegative weights with total mass one.