OctoInformBeta

OpenAI preprint, September 2026 · §6. Two consequences for simulation

Lemma 6.1: For ff with the slot signature property, good multipliers, a class observable GG and ν≤Uπ\nu\le U\pi, the error is at most 4000Un6Var⁡π(G)/N4000Un^6\operatorname{Var}_\pi(G)/N

Warm-started Metropolis time averages have mean squared error O(1/N)O(1/N)..

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

Markov chain Monte Carlo estimates a stationary mean by a time average. A chain with stationary distribution π\pi is run for NN steps from a start X0X_0 drawn from ν\nu, and for an observable GG, a real function on the states, N−1∑t=0N−1G(Xt)N^{-1}\sum_{t=0}^{N-1}G(X_t) is the estimate of the stationary mean π(G)\pi(G). The start is warm when ν≤Uπ\nu\le U\pi for a constant UU, and the question is how fast the mean squared error of the estimate falls with NN. The answer comes first for any finite lazy reversible chain, under an inequality tying the observable to the Dirichlet form, and then for the weighted Metropolis chain on the plain and defect states of nn disjoint pairs, the sets that take exactly one element of every pair, or both elements of one pair and none of another and one element of each other pair, with a constant that is a polynomial in nn.

Lazy Reversible Chains

A lazy reversible chain on a finite state space XX is a transition matrix PP on XX, with nonnegative entries and rows summing to 11, together with a strictly positive distribution π\pi on XX, such that π(x)P(x,y)=π(y)P(y,x)\pi(x)P(x,y)=\pi(y)P(y,x) for all states x,yx,y and P(x,x)≥1/2P(x,x)\ge 1/2 for every state xx. The transition operator of a lazy reversible chain (P,π)(P,\pi) on XX is the map that sends a function ff on XX to the function PfPf given by Pf(x)=∑yP(x,y)f(y)Pf(x)=\sum_yP(x,y)f(y).✦ For functions f,hf,h on XX, the stationary mean π(f)\pi(f), the stationary inner product ⟨f,h⟩π\langle f,h\rangle_\pi and the Dirichlet form ℰ(f)\mathcal{E}(f) of the chain are defined by π(f)=∑xπ(x)f(x),⟨f,h⟩π=∑xπ(x)f(x)h(x),ℰ(f)=⟨f,f−Pf⟩π.\pi(f)=\sum_x\pi(x)f(x),\qquad \langle f,h\rangle_\pi=\sum_x\pi(x)f(x)h(x),\qquad \mathcal{E}(f)=\langle f,f-Pf\rangle_\pi .(1)

Let π\pi be a strictly positive distribution on XX, and let mm be move probabilities on XX: m(x,y)≥0m(x,y)\ge 0, ∑ym(x,y)≤1/2\sum_ym(x,y)\le 1/2 for every xx, and π(x)m(x,y)=π(y)m(y,x)\pi(x)m(x,y)=\pi(y)m(y,x). The chain from the moves mm is the lazy reversible chain with stationary distribution π\pi that goes from xx to a state y≠xy\ne x with probability m(x,y)m(x,y) and stays at xx with the remaining probability.✦

For a state xx and a function FF of paths (x0,…,xN−1)(x_0,\dots,x_{N-1}) of NN states, 𝔼xF\mathbb{E}_xF is the sum of P(x0,x1)⋯P(xN−2,xN−1)F(x0,…,xN−1)P(x_0,x_1)\cdots P(x_{N-2},x_{N-1})\,F(x_0,\dots,x_{N-1}) over all such paths with x0=xx_0=x: the expectation of F(X0,…,XN−1)F(X_0,\dots,X_{N-1}) for the chain started at X0=xX_0=x.✦ For a function FF of paths and a function ν\nu on the states, 𝔼νF=∑xν(x)𝔼xF\mathbb{E}_\nu F=\sum_x\nu(x)\,\mathbb{E}_xF is the expectation of FF for the chain started from ν\nu. The path sum of a function gg on XX along a path is the sum of its values at the states of the path✦, and the squared path sum moment of gg over N≥1N\ge 1 steps is MN(g)(x)=𝔼x[(∑t=0N−1g(Xt))2],M_N(g)(x)=\mathbb{E}_x\Big[\Big(\sum_{t=0}^{N-1}g(X_t)\Big)^2\Big],(2)✦ with M0(g)=0M_0(g)=0. For g=G−π(G)g=G-\pi(G), the number MN(g)(x)/N2M_N(g)(x)/N^2 is the mean squared error of the time average of GG over NN steps from xx.

Plain and Defect States

Let Γ\Gamma be a finite set and 𝒫=(p1,…,pn)\mathcal{P}=(p_1,\dots,p_n) a nonempty list of pairs pi={xi,yi}p_i=\{x_i,y_i\} of elements of Γ\Gamma whose 2n2n entries are distinct and whose support, the set of all entries, is Γ\Gamma. A pair pp is empty, single or full in a subset SS of Γ\Gamma when SS contains none, exactly one or both of its elements, respectively. A plain state of 𝒫\mathcal{P} is a subset of Γ\Gamma in which every pair of 𝒫\mathcal{P} is single.✦ A defect state for two distinct pairs p,rp,r of 𝒫\mathcal{P} is a subset of Γ\Gamma in which pp is empty, rr is full and every other pair of 𝒫\mathcal{P} is single.✦ The chain states of 𝒫\mathcal{P} are its plain and defect states✦; they form the finite state space Ω\Omega.

A real function GG on the subsets of Γ\Gamma is a class observable when it is constant on each defect class: G(S)=G(T)G(S)=G(T) whenever SS and TT are defect states for the same pp and rr.✦

Let wprw_{pr} be positive multipliers indexed by two pairs pp and rr, and let ff be a positive function on the subsets of Γ\Gamma. The multiplier of a chain state SS is λ(S)=wpr\lambda(S)=w_{pr} when SS is a defect state for pp and rr, and λ(S)=1\lambda(S)=1 when SS is plain.✦ The weight of SS is ω(S)=λ(S)f(S)\omega(S)=\lambda(S)f(S)✦, the total weight is W=∑S∈Ωω(S)W=\sum_{S\in\Omega}\omega(S)✦, and π(S)=ω(S)/W\pi(S)=\omega(S)/W. The mean of an observable GG under π\pi is π(G)=∑S∈Ωπ(S)G(S)\pi(G)=\sum_{S\in\Omega}\pi(S)G(S)✦, and its variance is Var⁡π(G)=∑S∈Ωπ(S)(G(S)−π(G))2.\operatorname{Var}_\pi(G)=\sum_{S\in\Omega}\pi(S)\big(G(S)-\pi(G)\big)^2 .(3)✦

Two subsets SS and TT of Γ\Gamma are exchange adjacent when S=A∪{a}S=A\cup\{a\} and T=A∪{b}T=A\cup\{b\} for a set AA and distinct elements a,ba,b outside AA.✦ The Metropolis moves on Ω\Omega are Q(S,T)=min⁡{ω(S),ω(T)}2n2ω(S) if S and T are exchange adjacent,Q(S,T)=0 otherwise,Q(S,T)=\frac{\min\{\omega(S),\omega(T)\}}{2n^2\,\omega(S)}\ \text{ if $S$ and $T$ are exchange adjacent},\qquad Q(S,T)=0\ \text{ otherwise},(4)✦ and the weighted Metropolis chain is the chain from the moves QQ with stationary distribution π\pi.✦

Good Multipliers and the Slot Signature

The multiaffine polynomial of a real function ff on the subsets of Γ\Gamma is ∑Sf(S)zS\sum_Sf(S)z^S in variables ziz_i, i∈Γi\in\Gamma, where zSz^S is the product of the ziz_i with i∈Si\in S; ff is its coefficient function. For a vector a∈ℝΓa\in\mathbb{R}^\Gamma, DafD_af is the coefficient function of the derivative of that polynomial in the direction aa, and along a list of vectors D(a1,…,ak)f=Da1⋯DakfD_{(a_1,\dots,a_k)}f=D_{a_1}\cdots D_{a_k}f.✦ The indicator vector 𝟏E\mathbf{1}_E of a finite set E⊆ΓE\subseteq\Gamma has entry 11 on EE and 00 elsewhere✦, and a pair p={x,y}p=\{x,y\} has the direction 𝟏p=𝟏{x,y}\mathbf{1}_p=\mathbf{1}_{\{x,y\}}.✦ The slot total of ff along a list of pairs (p1,…,pk)(p_1,\dots,p_k) is the iterated derivative ∂(p1,…,pk)f=D(𝟏p1,…,𝟏pk)f;\partial_{(p_1,\dots,p_k)}f=D_{(\mathbf{1}_{p_1},\dots,\mathbf{1}_{p_k})}f ;(5)✦ when the pairs are disjoint and avoid a set AA, its value at AA is the sum of ff over the sets obtained from AA by adding one element of each pair.

Write c0=∂𝒫f(∅)c_0=\partial_{\mathcal{P}}f(\emptyset). For distinct pairs p,rp,r of 𝒫\mathcal{P}, the defect total cprc_{pr} is the slot total along 𝒫\mathcal{P} without pp and rr, at the set rr: the sum of ff over the sets that contain both elements of rr, no element of pp and one element of each other pair.✦ The multipliers satisfy the lower half of the good multiplier condition when c0/(4cpr)≤wprc_0/(4c_{pr})\le w_{pr}, and the upper half when wpr≤4c0/cprw_{pr}\le 4c_0/c_{pr}, for all distinct pairs p,rp,r of 𝒫\mathcal{P}; they are good when both halves hold.

The face Hessian of a function gg on the subsets of Γ\Gamma at a set AA is the symmetric matrix HA(g)H_A(g) indexed by Γ\A\Gamma\setminus A, with zero diagonal and entry g(A∪{i,j})g(A\cup\{i,j\}) for i≠ji\ne j.✦ A bilinear form BB on a real vector space has one positive direction when B(e,e)>0B(e,e)>0 implies B(v,v)≤0B(v,v)\le 0 for every vv with B(v,e)=0B(v,e)=0; for a symmetric form this is the condition of at most one positive eigenvalue.✦ The function ff has the slot signature property when, for every list PP of pairs of Γ\Gamma and every set A⊆ΓA\subseteq\Gamma, the face Hessian HA(∂Pf)H_A(\partial_Pf) has one positive direction.✦

The Claim

Theorem 1. Let PP be a lazy reversible chain on a finite state space XX with stationary distribution π\pi, let gg be a real function on XX, and let K≥0K\ge 0 be a constant such that ⟨g,h⟩π2≤K⟨g,g⟩πℰ(h)\langle g,h\rangle_\pi^2\le K\,\langle g,g\rangle_\pi\,\mathcal{E}(h) for every real function hh on XX. Let U≥0U\ge 0, and let ν\nu be a real function on XX with ν(x)≤Uπ(x)\nu(x)\le U\pi(x) for every state xx. Then for every N≥1N\ge 1 1N2∑x∈Xν(x)MN(g)(x)≤2UK⟨g,g⟩πN.\frac{1}{N^2}\sum_{x\in X}\nu(x)\,M_N(g)(x)\le\frac{2UK\langle g,g\rangle_\pi}{N}.(6)✦

Let 𝒫\mathcal{P} be a nonempty list of nn pairs of elements of Γ\Gamma with distinct entries and support Γ\Gamma, let ww be positive good multipliers and ff a positive function on the subsets of Γ\Gamma with the slot signature property, and let GG be a class observable. Let U≥0U\ge 0, and let ν\nu be a real function on Ω\Omega with ν(S)≤Uπ(S)\nu(S)\le U\pi(S) for every chain state SS. Then for every N≥1N\ge 1 the weighted Metropolis chain satisfies 1N2∑S∈Ων(S)MN(G−π(G))(S)≤2U⋅2000n6Var⁡π(G)N.\frac{1}{N^2}\sum_{S\in\Omega}\nu(S)\,M_N\big(G-\pi(G)\big)(S)\le \frac{2U\cdot 2000\,n^6\operatorname{Var}_\pi(G)}{N}.(7)✦

Under the same hypotheses on 𝒫\mathcal{P}, ww, ff and GG, if 0≤G(S)≤10\le G(S)\le 1 and ν(S)≤10n2π(S)\nu(S)\le 10n^2\pi(S) for every chain state SS, then for every N≥1N\ge 1 1N2∑S∈Ων(S)MN(G−π(G))(S)≤40000n8N.\frac{1}{N^2}\sum_{S\in\Omega}\nu(S)\,M_N\big(G-\pi(G)\big)(S)\le\frac{40000\,n^8}{N}.(8)✦

In the paper, the result reads: for good multipliers, a class observable GG and a trajectory X0,X1,…X_0,X_1,\dots of the weighted Metropolis chain started from ν≤Uπ\nu\le U\pi, every N≥1N\ge 1 gives 𝔼ν[(N−1∑t<NG(Xt)−π(G))2]≤2UKobsVar⁡π(G)/N\mathbb{E}_\nu\big[\big(N^{-1}\sum_{t<N}G(X_t)-\pi(G)\big)^2\big]\le 2UK_{\mathrm{obs}}\operatorname{Var}_\pi(G)/N, where 2000n62000n^6 stands for the paper’s constant KobsK_{\mathrm{obs}}.

What Is Checked

The claim is stated over a lazy reversible chain with its stationary inner product, its Dirichlet form and the squared path sum moment (2), and over the weighted Metropolis chain on the plain and defect states of 𝒫\mathcal{P}, the chain from the moves (4) with stationary distribution π=ω/W\pi=\omega/W, for positive good multipliers, a positive ff with the slot signature property and a class observable GG.

About the Metropolis moves the library proves that they are nonnegative✦, that they are in detailed balance with π\pi, π(S)Q(S,T)=π(T)Q(T,S)\pi(S)Q(S,T)=\pi(T)Q(T,S)✦, and that they sum to at most 1/21/2 from every chain state.✦