OctoInformBeta

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

Lemma 6.2: With law f/c0f/c_0 and, under the slot signature property and good multipliers, Poincaré constant 18n418n^4; warm trace steps cost at most U/π(A)U/\pi(A) in expectation

The Metropolis chain watched on transversals is lazy and reversible.

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

Let Γ\Gamma be a finite set, 𝒫=({x1,y1},…,{xn,yn})\mathcal{P} = (\{x_1,y_1\},\dots,\{x_n,y_n\}) a list of pairs of its elements, and ff a positive function on the subsets of Γ\Gamma, the coefficients of a multiaffine polynomial. Write Ω0\Omega_0 for the set of transversals of 𝒫\mathcal{P}, the sets that take one element from each pair, and c0c_0 for the total of ff over Ω0\Omega_0. The aim is to draw a transversal SS with probability μ(S)=f(S)/c0\mu(S) = f(S)/c_0. For the common bases of two matroids, the matroids enter through one condition on ff, the slot signature property, which is defined with the slot totals below.

The sampler is a Metropolis chain on a larger state space: the transversals together with the defect states, which leave one pair empty and take both elements of another. Read only at the times it sits on a transversal, the Metropolis chain becomes a chain on Ω0\Omega_0, its trace. The questions are whether the trace has law μ\mu and forgets its start quickly, and how many steps of the Metropolis chain one step of the trace costs.

Lazy Reversible Chains

A lazy reversible chain on a finite set XX is a transition matrix PP on XX, with nonnegative entries and rows summing to 11, together with a probability distribution π\pi on XX that is positive at every state, such that for all states xx and yy π(x)P(x,y)=π(y)P(y,x)andP(x,x)≥12.\pi(x)P(x,y) = \pi(y)P(y,x) \qquad\text{and}\qquad P(x,x) \ge \tfrac12 .(1)✦ The transition operator sends a real function gg on XX to PgPg, with (Pg)(x)=∑yP(x,y)g(y)(Pg)(x) = \sum_{y} P(x,y)g(y)✦; PkgP^k g is gg with the operator applied kk times✦, and Pk(x,y)P^k(x,y), the entry of the kkth power of PP, is the probability that the chain started at xx is at yy after kk steps.

For real functions gg and g′g' on XX, the stationary inner product is ⟨g,g′⟩π=∑xπ(x)g(x)g′(x)\langle g,g'\rangle_\pi = \sum_x \pi(x)g(x)g'(x)✦ and the mean of gg is π(g)=∑xπ(x)g(x)\pi(g) = \sum_x \pi(x)g(x).✦ The variance and the Dirichlet form of gg are Var⁡π(g)=⟨g−π(g),g−π(g)⟩π,ℰ(g)=⟨g,g−Pg⟩π.\operatorname{Var}_\pi(g) = \bigl\langle g - \pi(g),\, g - \pi(g)\bigr\rangle_\pi, \qquad \mathcal{E}(g) = \langle g,\, g - Pg\rangle_\pi .(2) A lazy reversible chain (P,π)(P,\pi) on XX satisfies a Poincaré inequality with constant KK, a real number, when Var⁡π(g)≤Kℰ(g)\operatorname{Var}_\pi(g) \le K\,\mathcal{E}(g) for every real function gg on XX. The point density at a state yy is the function hyh_y on XX equal to 1/π(y)1/\pi(y) at yy and to 00 elsewhere.✦

Let π\pi be a positive probability distribution on XX and MM a nonnegative matrix on XX with row sums at most 1/21/2 and in detailed balance, π(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 on XX with law π\pi and transition matrix P(x,y)=M(x,y)+[x=y](1−∑zM(x,z)),P(x,y) = M(x,y) + [x=y]\Bigl(1 - \sum_{z} M(x,z)\Bigr),(3)✦ where [x=y][x=y] is 11 when x=yx = y and 00 otherwise.

The Trace on a Set of States

Fix a lazy reversible chain (P,π)(P,\pi) on XX and a nonempty set AA of states, with complement Ac=X\AA^c = X \setminus A. The exit probability of a state zz of AcA^c is e(z)=∑y∈AP(z,y)e(z) = \sum_{y\in A} P(z,y).✦ A killed kernel on a finite set YY is a nonnegative matrix QQ on YY together with a number rr, 0≤r<10 \le r < 1, that bounds every row sum of QQ.✦ When every state of AcA^c has positive exit probability, the killed chain on AcA^c is the killed kernel Q(z,z′)=P(z,z′)Q(z,z') = P(z,z') for z,z′∈Acz, z' \in A^c, with r=1−∏z∈Ace(z)r = 1 - \prod_{z\in A^c} e(z).✦

The Green function of a killed kernel QQ sends a real function gg on YY to Gg=∑k≥0QkgGg = \sum_{k\ge 0} Q^k g✦, where QkgQ^k g is gg with the operator (Qg)(z)=∑z′Q(z,z′)g(z′)(Qg)(z) = \sum_{z'} Q(z,z')g(z') applied kk times.✦ For the killed chain on AcA^c, the hitting kernel and the duration are H(z,y)=(GP(⋅,y))(z),d(z)=(G𝟏)(z)(z∈Ac,y∈A):H(z,y) = \bigl(G\,P(\cdot,y)\bigr)(z), \qquad d(z) = (G\mathbf{1})(z) \qquad (z\in A^c,\ y\in A):(4) H(z,y)H(z,y) is the probability that the chain started at zz enters AA first at yy, and d(z)d(z) is the expected number of steps it takes from zz to enter AA.

For states xx and yy of AA, the trace matrix and the return cost are PA(x,y)=P(x,y)+∑z∈AcP(x,z)H(z,y),R(x)=1+∑z∈AcP(x,z)d(z):P_A(x,y) = P(x,y) + \sum_{z\in A^c} P(x,z)H(z,y), \qquad R(x) = 1 + \sum_{z\in A^c} P(x,z)d(z):(5) PA(x,y)P_A(x,y) is the probability that the next visit of the chain to AA after xx is at yy, and R(x)R(x) is the expected number of steps until that visit. The mass of AA is π(A)=∑x∈Aπ(x)\pi(A) = \sum_{x\in A}\pi(x)✦, and the trace chain on AA has transition matrix PAP_A and law πA(x)=π(x)/π(A)\pi_A(x) = \pi(x)/\pi(A).✦

The Metropolis Chain on Transversals

Let the list 𝒫\mathcal{P} be nonempty, fresh, its 2n2n entries being distinct, and covering Γ\Gamma, every element of Γ\Gamma being an entry of some pair. A pair is empty, single or full in a set S⊆ΓS \subseteq \Gamma when SS contains none, exactly one or both of its elements. A plain state is a set in which every pair of 𝒫\mathcal{P} is single, so that the plain states are the transversals.✦ For two distinct pairs pp and rr of 𝒫\mathcal{P}, a defect state for (p,r)(p,r) is a set in which pp is empty, rr is full and every other pair of 𝒫\mathcal{P} is single.✦ The chain states are the plain states and the defect states.✦ Two sets SS and TT are exchange adjacent when S=D∪{a}S = D\cup\{a\} and T=D∪{b}T = D\cup\{b\} for a set DD and two distinct elements aa and bb outside DD.✦

A system of multipliers ww gives a positive number wprw_{pr} to every ordered pair of distinct pairs pp and rr of 𝒫\mathcal{P}; let ww be such a system. The weight ω(S)\omega(S) of a chain state SS is its multiplier times f(S)f(S): wprf(S)w_{pr}f(S) when SS is a defect state for (p,r)(p,r), and f(S)f(S) when SS is plain✦; Λ\Lambda is the sum of ω\omega over all chain states.✦ The Metropolis moves between chain states are M(S,T)=min⁡(ω(S),ω(T))2n2ω(S) when S and T are exchange adjacent,M(S,T)=0 otherwise,M(S,T) = \frac{\min\bigl(\omega(S),\omega(T)\bigr)}{2n^2\,\omega(S)} \ \text{ when $S$ and $T$ are exchange adjacent,} \qquad M(S,T) = 0 \ \text{ otherwise},(6)✦ and the Metropolis chain is the chain from these moves, as in (3), on the chain states, with law π(S)=ω(S)/Λ\pi(S) = \omega(S)/\Lambda.✦ The Metropolis trace chain is the trace of the Metropolis chain on Ω0\Omega_0, with transition matrix PΩ0P_{\Omega_0} and law πΩ0\pi_{\Omega_0}, built from the killed Metropolis chain, the killed chain on the defect states.✦

Slot Totals and the Slot Signature

The slot total ∂𝒬g\partial_{\mathcal{Q}} g of a real function gg on the subsets of Γ\Gamma along a list 𝒬\mathcal{Q} of pairs is the iterated directional derivative of the multiaffine polynomial with coefficients gg along the indicator vectors 𝟏{x,y}\mathbf{1}_{\{x,y\}} of the pairs {x,y}\{x,y\} of 𝒬\mathcal{Q}.✦ When the pairs of 𝒬\mathcal{Q} are disjoint and avoid a set CC, the value ∂𝒬g(C)\partial_{\mathcal{Q}} g(C) is the sum of gg over the sets obtained from CC by adding one element of each pair. The total c0c_0 and, for distinct pairs pp and r={xj,yj}r = \{x_j,y_j\} of 𝒫\mathcal{P}, the defect total cprc_{pr}, which at a set CC is the slot total along 𝒫\mathcal{P} with pp and rr removed, taken at CC with both elements of rr added, are, at C=∅C = \emptyset, c0=∂𝒫f(∅),cpr=∂𝒫\{p,r}f({xj,yj}),c_0 = \partial_{\mathcal{P}} f(\emptyset), \qquad c_{pr} = \partial_{\mathcal{P}\setminus\{p,r\}} f(\{x_j,y_j\}),(7) where 𝒫\{p,r}\mathcal{P}\setminus\{p,r\} denotes that list; cprc_{pr} is the sum of ff over the defect states for (p,r)(p,r).

The face Hessian of gg at a set C⊆ΓC \subseteq \Gamma is the symmetric matrix Hess⁡C(g)\operatorname{Hess}_C(g) indexed by Γ\C\Gamma\setminus C, with zero diagonal and entry g(C∪{i,j})g(C\cup\{i,j\}) at distinct ii and jj.✦ A bilinear form BB on a real vector space has one positive direction when every vector ee with B(e,e)>0B(e,e) > 0 and every vector vv with B(v,e)=0B(v,e) = 0 satisfy B(v,v)≤0B(v,v) \le 0.✦ The function ff has the slot signature property when, for every list 𝒬\mathcal{Q} of pairs of elements of Γ\Gamma and every set C⊆ΓC\subseteq\Gamma, the bilinear form of Hess⁡C(∂𝒬f)\operatorname{Hess}_C(\partial_{\mathcal{Q}} f) has one positive direction.✦ The multipliers ww are good when every wprw_{pr} satisfies the lower bound c0/(4cpr)≤wprc_0/(4c_{pr}) \le w_{pr} and the upper bound wpr≤4c0/cprw_{pr} \le 4c_0/c_{pr}; the lower half of goodness is the lower bound. The multipliers satisfy the lower half of goodness when c04cpr≤wprfor all distinct pairs p and r of 𝒫.\frac{c_0}{4c_{pr}} \le w_{pr} \qquad \text{for all distinct pairs $p$ and $r$ of $\mathcal{P}$.}(8)

The Claim

Theorem 1. Let (P,π)(P,\pi) be a lazy reversible chain on a finite set XX, and let AA be a nonempty set of states such that every state outside AA has positive exit probability. For all states xx and yy of AA, the trace matrix satisfies π(x)PA(x,y)=π(y)PA(y,x),\pi(x)P_A(x,y) = \pi(y)P_A(y,x),(9)✦ and for every state xx of AA, PA(x,x)≥12.P_A(x,x) \ge \tfrac12 .(10)✦

Let 𝒫\mathcal{P} be a nonempty fresh list of nn pairs covering Γ\Gamma, ww positive multipliers and ff a positive function on the subsets of Γ\Gamma. At every transversal SS, the Metropolis trace chain has law πΩ0(S)=f(S)c0.\pi_{\Omega_0}(S) = \frac{f(S)}{c_0} .(11)✦ If moreover ff has the slot signature property and the multipliers satisfy the lower half of goodness (8), then every real function gg on Ω0\Omega_0 satisfies Var⁡πΩ0(g)≤18n4ℰΩ0(g),\operatorname{Var}_{\pi_{\Omega_0}}(g) \le 18n^4\,\mathcal{E}_{\Omega_0}(g),(12)✦ where ℰΩ0\mathcal{E}_{\Omega_0} is the Dirichlet form of the Metropolis trace chain.

If K≥1K \ge 1 and m>0m > 0 are such that π(x)≥m\pi(x) \ge m for every state xx of XX and the chain (P,π)(P,\pi) satisfies a Poincaré inequality with constant KK, then for every natural number kk and all states xx and yy, |(Pkhy)(x)−1|≤e−k/Km\bigl|(P^k h_y)(x) - 1\bigr| \le \frac{e^{-k/K}}{m}(13)✦ and |Pk(x,y)π(y)−1|≤e−k/Km.\Bigl|\frac{P^k(x,y)}{\pi(y)} - 1\Bigr| \le \frac{e^{-k/K}}{m} .(14)✦

If UU is a real number and ν\nu a real function on AA with ν(x)≤UπA(x)\nu(x) \le U\pi_A(x) for every state xx of AA (for a distribution ν\nu, a warm start with parameter UU), then the return cost satisfies ∑x∈Aν(x)R(x)≤Uπ(A).\sum_{x\in A} \nu(x)R(x) \le \frac{U}{\pi(A)} .(15)✦ For the Metropolis chain above, with law π\pi, the transversals have mass π(Ω0)=c0Λ.\pi(\Omega_0) = \frac{c_0}{\Lambda} .(16)✦

In the paper, the result reads: with good multipliers, the trace PAP_A on A=Ω0A = \Omega_0 is reversible with stationary law μ\mu, irreducible and lazy, with inverse spectral gap at most 18n418n^4; hence |PAk(x,y)/μ(y)−1|≤exp⁡(−k/(18n4))/min⁡zμ(z)|P_A^k(x,y)/\mu(y) - 1| \le \exp(-k/(18n^4))/\min_z \mu(z), and a trace step started from ν≤Uμ\nu \le U\mu costs in expectation at most U/π(A)≤5Un2U/\pi(A) \le 5Un^2 underlying transitions.

The library states the mixing bounds (13) and (14) for every lazy reversible chain with a Poincaré inequality, and the Poincaré inequality (12) under the lower half of goodness alone.

What Is Checked

The claim is stated over lazy reversible chains (1) on a finite set, with their transition operator, kk-step transition probabilities, point densities, variance and Dirichlet form (2), and over the trace matrix, return cost and trace chain (5) on a set of states, built from the killed chain, its Green function, hitting kernel and duration (4). Its Metropolis part is stated over the chain states of a fresh covering list of pairs, the weights ω\omega, the Metropolis chain from the moves (6) and its trace on Ω0\Omega_0, the totals (7), the slot signature property of ff and the lower half of goodness (8).

The library also proves that the trace matrix has nonnegative entries✦ and rows summing to 11✦; that the Metropolis moves are nonnegative✦, sum to at most 1/21/2 from every chain state✦ and are in detailed balance with ω/Λ\omega/\Lambda✦; that there is a transversal✦; and that from every defect state the Metropolis chain reaches a transversal in one step with positive probability.✦