OctoInformBeta

OpenAI preprint, September 2026 · §5. A chain and its observable Poincaré bound · §5, (5.4) and (5.5)

The Metropolis chain and its Dirichlet form (5.4), (5.5): Lazy one-element exchanges on plain and defect states, with energy ⟨H,(I−P)H⟩π=D(H)/(2n2Λ)\langle H,(I-P)H\rangle_\pi = D(H)/(2n^2\Lambda)

The energy of the Metropolis chain as an edge sum.

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

Fix a finite set Γ\Gamma split into n≥1n \ge 1 disjoint pairs {x1,y1},…,{xn,yn}\{x_1,y_1\},\dots,\{x_n,y_n\}, a positive function ff on the subsets of Γ\Gamma, and positive multipliers wprw_{pr}, one for each ordered pair (p,r)(p,r) of the pairs. The Metropolis chain walks on the sets that take one element from each pair, and on the sets that leave one pair empty, take another whole and take one element from each of the rest. A step exchanges one element of the current set for one outside it, and it is accepted by the Metropolis rule toward weights λ(S)\lambda(S) made of ff and the multipliers. With two pairs, the chain lives on {x1,x2}\{x_1,x_2\}, {x1,y2}\{x_1,y_2\}, {y1,x2}\{y_1,x_2\}, {y1,y2}\{y_1,y_2\} and on {x1,y1}\{x_1,y_1\}, {x2,y2}\{x_2,y_2\}, and from {x1,x2}\{x_1,x_2\} it can step to {x1,y2}\{x_1,y_2\} or to {x1,y1}\{x_1,y_1\}.

A Poincaré inequality for a reversible chain bounds the variance of an observable HH under the stationary law by the chain’s energy at HH; for the Metropolis chain the question is how that energy reads as a sum over the exchange edges, the pairs of states that differ by exchanging one element. The library defines lazy reversible chains and their energy, and gives the energy of the Metropolis chain as a weighted sum over exchange edges.

Lazy Reversible Chains

A finite lazy reversible chain on a finite set XX is a pair (P,π)(P,\pi) of a real function PP on X×XX\times X and a real function π\pi on XX such that, for all x,y∈Xx,y\in X, π(x)>0,∑xπ(x)=1,P(x,y)≥0,∑yP(x,y)=1,π(x)P(x,y)=π(y)P(y,x),P(x,x)≥12.\pi(x)>0,\quad \sum_{x}\pi(x)=1,\quad P(x,y)\ge 0,\quad \sum_{y}P(x,y)=1,\quad \pi(x)P(x,y)=\pi(y)P(y,x),\quad P(x,x)\ge\tfrac12 .(1)✦ The stationary law of a finite lazy reversible chain (P,π)(P,\pi) on XX is π\pi.

For real functions g,hg,h on XX write ⟨g,h⟩π=∑xπ(x)g(x)h(x)\langle g,h\rangle_\pi=\sum_x \pi(x)g(x)h(x)✦ and (Pg)(x)=∑yP(x,y)g(y)(Pg)(x)=\sum_y P(x,y)g(y)✦, and let II be the identity operator on real functions on XX. The energy of the chain (P,π)(P,\pi) at a real function HH on XX is ℰP(H)=⟨H,(I−P)H⟩π=∑xπ(x)H(x)(H(x)−(PH)(x)).\mathcal{E}_P(H)=\langle H,(I-P)H\rangle_\pi=\sum_x \pi(x)H(x)\bigl(H(x)-(PH)(x)\bigr).(2)✦

A system of moves for a positive probability vector π\pi on XX is a nonnegative function qq on X×XX\times X such that ∑yq(x,y)≤12\sum_y q(x,y)\le\tfrac12 and π(x)q(x,y)=π(y)q(y,x)\pi(x)q(x,y)=\pi(y)q(y,x) for all xx and yy. The chain built from such moves is the lazy reversible chain with stationary law π\pi and transition probabilities P(x,y)=q(x,y)+𝟏[x=y](1−∑zq(x,z)).P(x,y)=q(x,y)+\mathbf{1}[x=y]\Bigl(1-\sum_{z}q(x,z)\Bigr).(3)✦

Chain States and Exchange Edges

A pair is empty, single or full in a subset SS of Γ\Gamma when SS contains none, exactly one or both of its elements. A subset SS of Γ\Gamma is a plain state when every pair is single in SS✦, and a defect state for two distinct pairs pp and rr when pp is empty in SS, rr is full in SS and every other pair is single in SS✦. The chain states are the plain states and the defect states; Ω\Omega is their set.✦

The weight of a subset SS of Γ\Gamma is λ(S)=m(S)f(S),m(S)={wprif S is a defect state for p and r,1otherwise,\lambda(S)=m(S)\,f(S),\qquad m(S)=\begin{cases} w_{pr} & \text{if $S$ is a defect state for $p$ and $r$},\\ 1 & \text{otherwise},\end{cases}(4)✦ and the total weight is Λ=∑S∈Ωλ(S)\Lambda=\sum_{S\in\Omega}\lambda(S)✦.

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 subset AA of Γ\Gamma and distinct elements a,b∉Aa,b\notin A.✦ The exchange edges are the ordered pairs of exchange-adjacent chain states, E={(S,T)∈Ω×Ω:S and T are exchange adjacent},E=\{(S,T)\in\Omega\times\Omega : S \text{ and } T \text{ are exchange adjacent}\},(5)✦ and the conductance of a pair (S,T)(S,T) of subsets of Γ\Gamma is c(S,T)=min⁡{λ(S),λ(T)}.c(S,T)=\min\{\lambda(S),\lambda(T)\}.(6)✦

A subset SS of Γ\Gamma respects two subsets AA and BB of Γ\Gamma when A⊆SA\subseteq S and S∩B=∅S\cap B=\emptyset✦, and a pair (S,T)(S,T) respects them when SS and TT both do✦. For a finite set FF of ordered pairs of subsets of Γ\Gamma, a real function κ\kappa on such pairs and a real function HH on the subsets of Γ\Gamma, the restricted energy of HH on FF with respect to AA and BB is DA,BF,κ(H)=12∑(S,T)∈F(S,T) respects A,Bκ(S,T)(H(S)−H(T))2.D^{F,\kappa}_{A,B}(H)=\frac12\sum_{\substack{(S,T)\in F\\ (S,T)\text{ respects }A,\,B}} \kappa(S,T)\bigl(H(S)-H(T)\bigr)^2 .(7)✦ The edge energy of a real function HH on the subsets of Γ\Gamma is D(H)=D∅,∅E,c(H)D(H)=D^{E,c}_{\emptyset,\emptyset}(H), the restricted energy over the exchange edges (5) with the conductance (6) and no restriction.

The Claim

Definition 1. Let the finite set Γ\Gamma be covered by n≥1n\ge 1 pairs whose 2n2n entries are distinct, let ff be a positive function on the subsets of Γ\Gamma, and let the multipliers wprw_{pr} be positive. The Metropolis chain is the lazy reversible chain on the chain states Ω\Omega with stationary law π(S)=λ(S)/Λ\pi(S)=\lambda(S)/\Lambda, built as in (3) from the moves✦ q(S,T)={min⁡{λ(S),λ(T)}2n2λ(S)if S and T are exchange adjacent,0otherwise.q(S,T)=\begin{cases}\dfrac{\min\{\lambda(S),\lambda(T)\}}{2n^2\lambda(S)} & \text{if $S$ and $T$ are exchange adjacent},\\[1ex] 0 & \text{otherwise}.\end{cases}(8)✦ Its Dirichlet form is ℰ\mathcal{E}, and for every real function HH on the subsets of Γ\Gamma the energy of the chain at the restriction of HH to Ω\Omega is ℰP(H|Ω)=ℰ(H)=D(H)2n2Λ.\mathcal{E}_P(H|_{\Omega})=\mathcal{E}(H)=\frac{D(H)}{2n^2\Lambda}.(9)✦

In the paper, the result reads: the lazy Metropolis chain with one-element exchanges inside Ω\Omega has D(H)=∑edges {S,S′}min⁡{λ(S),λ(S′)}(H(S)−H(S′))2D(H)=\sum_{\text{edges }\{S,S'\}}\min\{\lambda(S),\lambda(S')\} \bigl(H(S)-H(S')\bigr)^2 and ℰ(H)=⟨H,(I−P)H⟩π=D(H)/(2n2Λ)\mathcal{E}(H)=\langle H,(I-P)H\rangle_\pi =D(H)/(2n^2\Lambda).

What Is Checked

The claim is stated over a finite set Γ\Gamma covered by n≥1n\ge1 pairs with 2n2n distinct entries, a positive function ff on its subsets and positive multipliers wprw_{pr}, through the plain and defect states Ω\Omega, the weights (4) with total Λ\Lambda, the exchange edges (5), the conductance (6), the restricted energy (7), and the lazy reversible chains (1) built from moves (3) with their energy (2).

For positive ff and ww, the library proves that the moves (8) are nonnegative✦ and in detailed balance with λ/Λ\lambda/\Lambda✦, and, when the n≥1n\ge1 pairs have 2n2n distinct entries covering Γ\Gamma, that every row sum ∑Tq(S,T)\sum_T q(S,T) is at most 12\tfrac12✦.