OctoInformBeta

OpenAI preprint, September 2026 · Section 1. Introduction

Section 1 (setting): Single-round value and the ceiling event for joint measurements on strings of questions

Finite entangled games and threshold repetition.

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

Threshold parallel repetition concerns the probability of exceeding a game’s single-round entangled value over many coordinates. Each player receives a string of questions and returns a string of answers.

Let X,YX,Y be finite nonempty question alphabets and A,BA,B finite nonempty answer alphabets. Write k≥0k\geq 0 for the repetition length, and use bold letters for strings of length kk.

The Definition

Definition 1. A finite two-player game GG on X,Y,A,BX,Y,A,B is a pair consisting of a question probability distribution μ\mu and an acceptance function VV, with G=(μ,V),μ:X×Y→ℝ≥0,∑x∈X,y∈Yμ(x,y)=1,V:X×Y×A×B→{0,1}.\begin{gathered} G=(\mu,V),\qquad \mu:X\times Y\longrightarrow\mathbb R_{\geq 0},\qquad \sum_{x\in X,\,y\in Y}\mu(x,y)=1,\\ V:X\times Y\times A\times B\longrightarrow\{0,1\}. \end{gathered}(1)✦ Acceptance in (1) means V(x,y,a,b)=1V(x,y,a,b)=1.

A finite-dimensional entangled strategy SS for question sets X,YX,Y and answer alphabets A,BA,B consists of a unit bipartite state and a local positive operator-valued measurement for each question, as specified by S=(ℋA,ℋB,ψ,{Max},{Nby}),ℋA=ℂnA,ℋB=ℂnB,nA,nB≥1,ψ∈ℋA⊗ℋB,⟨ψ,ψ⟩=1,Max≽0,∑a∈AMax=IℋA,Nby≽0,∑b∈BNby=IℋB.\begin{gathered} S=\bigl(\mathcal H_A,\mathcal H_B,\psi,\{M_a^x\},\{N_b^y\}\bigr),\qquad \mathcal H_A=\mathbb C^{n_A},\quad \mathcal H_B=\mathbb C^{n_B},\quad n_A,n_B\geq 1,\\ \psi\in\mathcal H_A\otimes\mathcal H_B,\qquad \langle\psi,\psi\rangle=1,\\ M_a^x\succeq 0,\quad \sum_{a\in A}M_a^x=I_{\mathcal H_A},\qquad N_b^y\succeq 0,\quad \sum_{b\in B}N_b^y=I_{\mathcal H_B}. \end{gathered}(2)✦ The conditions in (2) hold for every question and answer; denote the set of these strategies by 𝒮(X,Y;A,B)\mathcal S(X,Y;A,B). A single-round strategy SS for GG is an element of 𝒮(X,Y;A,B)\mathcal S(X,Y;A,B).✦

The Born probability pS(a,b∣x,y)p_S(a,b\mid x,y) of answers a,ba,b for questions x,yx,y under SS is the expectation pS(a,b∣x,y)=Re⁡⟨ψ∣Max⊗Nby∣ψ⟩.p_S(a,b\mid x,y) =\operatorname{Re}\langle\psi\mid M_a^x\otimes N_b^y\mid\psi\rangle.(3)✦ The winning probability wG(S)w_G(S) of a single-round strategy SS is the accepted probability from (3), averaged over the referee’s questions: wG(S)=∑x∈X,y∈Yμ(x,y)∑a∈A,b∈BV(x,y,a,b)pS(a,b∣x,y).w_G(S)=\sum_{x\in X,\,y\in Y}\mu(x,y) \sum_{a\in A,\,b\in B}V(x,y,a,b)\,p_S(a,b\mid x,y).(4)✦ The finite-dimensional entangled value vv of GG is the supremum of the winning probabilities in (4) over all single-round strategies: v=supS∈𝒮(X,Y;A,B)wG(S).v=\sup_{S\in\mathcal S(X,Y;A,B)} w_G(S).(5)✦

A joint kk-fold strategy SkS_k for GG is an element of the strategy set in (6), whose questions and answers are strings: 𝒮k(G)=𝒮(Xk,Yk;Ak,Bk).\mathcal S_k(G)=\mathcal S(X^k,Y^k;A^k,B^k).(6)✦ The number of wins WkW_k at a transcript (𝒙,𝒚,𝒂,𝒃)(\mathbf x,\mathbf y,\mathbf a,\mathbf b) is the coordinate count Wk(𝒙,𝒚,𝒂,𝒃)=∑i=1kV(xi,yi,ai,bi).W_k(\mathbf x,\mathbf y,\mathbf a,\mathbf b) =\sum_{i=1}^{k}V(x_i,y_i,a_i,b_i).(7)✦

Let δ∈ℝ\delta\in\mathbb R, with δ>0\delta>0 representing a positive excess over (5). The threshold success probability PG,SkδP_{G,S_k}^{\delta} of a joint strategy SkS_k is the probability that the count in (7) reaches the ceiling threshold under independently sampled question pairs: PG,Skδ=∑𝒙∈Xk,𝒚∈Yk(∏i=1kμ(xi,yi))⋅∑𝒂∈Ak,𝒃∈BkpSk(𝒂,𝒃∣𝒙,𝒚)𝟏{Wk≥⌈(v+δ)k⌉}.\begin{aligned} P_{G,S_k}^{\delta} ={}&\sum_{\mathbf x\in X^k,\,\mathbf y\in Y^k} \left(\prod_{i=1}^{k}\mu(x_i,y_i)\right)\\ &\quad\cdot\sum_{\mathbf a\in A^k,\,\mathbf b\in B^k} p_{S_k}(\mathbf a,\mathbf b\mid\mathbf x,\mathbf y)\, \mathbf 1_{\{W_k\geq\lceil(v+\delta)k\rceil\}}. \end{aligned}(8)✦ The threshold game value vkδ(G)v_k^{\delta}(G) is the supremum of the probabilities in (8) over all joint kk-fold strategies: vkδ(G)=supSk∈𝒮k(G)PG,Skδ.v_k^{\delta}(G)=\sup_{S_k\in\mathcal S_k(G)} P_{G,S_k}^{\delta}.(9)✦

What Is Checked

The definitions (1) to (9) are stated over finite nonempty game alphabets, unit states on finite-dimensional bipartite spaces and local positive operator-valued measurements, for every repetition length k≥0k\geq 0 and real threshold parameter δ\delta.