OctoInformBeta

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

Lemma 5.1: For positive ff with the slot signature property and wpr≥c0/(4cpr)w_{pr} \ge c_0/(4c_{pr}): c0Var⁡μH≤n(1+8n)D(H)c_0\operatorname{Var}_\mu H \le n(1+8n)\,D(H), with sink and splitting lemmas

A Poincaré bound for the variance on transversals.

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

Take a finite set Γ\Gamma, a list PP of nn disjoint pairs (xi,yi)(x_i, y_i) of its elements, and a positive weight ff on the subsets of Γ\Gamma; the two matroids whose common bases are counted enter only through a condition on ff, the slot signature property. A transversal of PP is a set made of one element from each pair, and μ\mu is the distribution on transversals proportional to ff. A Markov chain moves by exchanging one element for another among the sets that meet every pair once and the defect sets, weighted by ff times a multiplier wprw_{pr}. The question is the chain’s Poincaré constant seen from the transversals: how large the variance of a function HH under μ\mu can be against the chain’s Dirichlet form D(H)D(H).

Slot Totals and Slot Variance

A list Q=(p1,…,pk)Q = (p_1, \dots, p_k) of pairs pj=(xj,yj)p_j = (x_j, y_j) of elements of Γ\Gamma is fresh for a set B⊆ΓB \subseteq \Gamma when its 2k2k entries are pairwise distinct and none lies in BB.✦ For a pair pp and a list Q′Q', pQ′pQ' is the list that starts with pp and continues with Q′Q', and |Q||Q| is the length of QQ.

A multiaffine polynomial in variables ziz_i, i∈Γi \in \Gamma, is given by its coefficient function gg on the subsets of Γ\Gamma, as ∑Sg(S)zS\sum_S g(S)\, z^S, where zSz^S is the product of the ziz_i with i∈Si \in S. The slot total ∂Qg\partial_Q g of gg along QQ is the coefficient function of the iterated directional derivative of this polynomial along the indicator vectors 𝟏{x1,y1},…,𝟏{xk,yk}\mathbf{1}_{\{x_1, y_1\}}, \dots, \mathbf{1}_{\{x_k, y_k\}} of the pairs of QQ.✦ When QQ is fresh for a set AA, ∂Qg(A)=∑u1∈{x1,y1}⋯∑uk∈{xk,yk}g(A∪{u1,…,uk}).\partial_Q g(A) = \sum_{u_1 \in \{x_1, y_1\}} \cdots \sum_{u_k \in \{x_k, y_k\}} g(A \cup \{u_1, \dots, u_k\}).(1) Set zQ(A)=∂Qf(A)z_Q(A) = \partial_Q f(A) and c0=zP(∅)c_0 = z_P(\emptyset).

For a function HH on the subsets of Γ\Gamma, the slot variance of HH along QQ at AA is the number VQ(A)=∂Q(fH2)(A)−∂Q(fH)(A)2zQ(A).V_Q(A) = \partial_Q(fH^2)(A) - \frac{\partial_Q(fH)(A)^2}{z_Q(A)}.(2)✦ When QQ is fresh for AA, VQ(A)V_Q(A) is zQ(A)z_Q(A) times the variance of HH under the distribution proportional to ff on the sets summed in (1), so that VP(∅)=c0Var⁡μHV_P(\emptyset) = c_0 \operatorname{Var}_\mu H.

For two pairs pp and rr, the defect total cprQ(A)c^Q_{pr}(A) of ff along QQ at AA is the slot total of ff along QQ with pp and rr removed, taken at AA with both elements of rr added.✦ Set cpr=cprP(∅)c_{pr} = c^P_{pr}(\emptyset).

The face Hessian ℋA(g)\mathcal{H}_A(g) of gg at AA is the symmetric matrix with rows and columns indexed by Γ\A\Gamma \setminus A, zero diagonal, and entry g(A∪{i,j})g(A \cup \{i, j\}) for distinct ii and jj.✦ A bilinear form β\beta on a real vector space has one positive direction when, for every ee with β(e,e)>0\beta(e, e) > 0, every vv with β(v,e)=0\beta(v, e) = 0 has β(v,v)≤0\beta(v, v) \le 0; for a symmetric form this is having at most one positive eigenvalue.✦ A function ff on the subsets of Γ\Gamma has the slot signature property when, for every list QQ of pairs and every A⊆ΓA \subseteq \Gamma, the face Hessian ℋA(∂Qf)\mathcal{H}_A(\partial_Q f) has one positive direction.✦

The Chain

A pair is empty, full or single in a set SS when SS contains none, both or exactly one of its elements. A plain state of PP is a subset of Γ\Gamma in which every pair of PP is single.✦ For two distinct pairs pp and rr of PP, a defect state of PP for pp and rr is a subset of Γ\Gamma in which pp is empty, rr is full and every other pair of PP is single.✦ A chain state of PP is a plain state or a defect state for some two pairs.✦ 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 aa and bb outside AA, and the chain’s edge set EPE_P consists of the ordered pairs (S,T)(S, T) of exchange-adjacent chain states of PP.

The multipliers are positive reals wprw_{pr}, one for every two pairs pp and rr. The multiplier m(S)m(S) of a set SS is wprw_{pr} when SS is a defect state of PP for pp and rr, and 11 otherwise✦, and the conductance of an edge (S,T)(S, T) is κ(S,T)=min⁡{m(S)f(S),m(T)f(T)}.\kappa(S, T) = \min\{m(S) f(S),\ m(T) f(T)\}.(3)✦ The multipliers are good when c0/(4cpr)≤wpr≤4c0/cprc_0/(4c_{pr}) \le w_{pr} \le 4c_0/c_{pr} for any two distinct pairs pp and rr of PP; the lower half is the left inequality.

For subsets AA and BB of Γ\Gamma, a subset SS of Γ\Gamma respects (A,B)(A, B) when it contains AA and avoids BB; an edge (S,T)(S, T) respects (A,B)(A, B) when both SS and TT respect (A,B)(A, B). For a finite set EE of ordered pairs of subsets of Γ\Gamma with weights ω\omega, the energy of HH on EE restricted to (A,B)(A, B) is DA,BE,ω(H)=12∑(S,T)∈E(S,T) respects (A,B)ω(S,T)(H(S)−H(T))2,D^{E,\omega}_{A,B}(H) = \frac{1}{2} \sum_{\substack{(S,T) \in E \\ (S,T) \text{ respects } (A,B)}} \omega(S, T)\, \bigl(H(S) - H(T)\bigr)^2,(4)✦ and D(H)=D∅,∅EP,κ(H)D(H) = D^{E_P,\kappa}_{\emptyset,\emptyset}(H) is the chain’s Dirichlet form.

A variance node of PP is a triple (Q,A,B)(Q, A, B) of a list QQ of pairs of PP and two disjoint subsets AA and BB of Γ\Gamma such that QQ is fresh for A∪BA \cup B and every pair of PP outside QQ has one element in AA and the other in BB.✦

The Claim

Theorem 1 (Sink of scores). Let II be a finite nonempty set, and let real scores aija_{ij}, for i,j∈Ii, j \in I, satisfy the pair inequality aijaji≤1/16a_{ij} a_{ji} \le 1/16 for distinct ii and jj and the triple inequality aijajk≤aika_{ij} a_{jk} \le a_{ik} for pairwise distinct ii, jj and kk. Then the scores have a sink, an index kk with akt≤1for every t≠k.a_{kt} \le 1 \quad \text{for every } t \ne k.(5)✦

Theorem 2 (Sink for slot totals). Let ff be a positive function on the subsets of Γ\Gamma with the slot signature property, let QQ be a nonempty list of pairs and GG a list that contains every pair of QQ, and let AA and BB be subsets of Γ\Gamma such that QQ is fresh for AA and GG is fresh for BB. Then there is a pair pp of QQ such that every pair r≠pr \ne p of QQ satisfies crpQ(A)cprG(B)≤zQ(A)zG(B).c^Q_{rp}(A)\, c^G_{pr}(B) \le z_Q(A)\, z_G(B).(6)✦

Theorem 3 (Adaptive splitting). Let ff and HH be functions on the subsets of Γ\Gamma with ff positive, let EE be a finite set of ordered pairs of subsets of Γ\Gamma with weights ω≥0\omega \ge 0 on EE, let C≥0C \ge 0, and let 𝒩\mathcal{N} be a family of triples (Q,A,B)(Q, A, B) of a list of pairs and two subsets of Γ\Gamma. Suppose that every triple (Q,A,B)(Q, A, B) in 𝒩\mathcal{N} with QQ nonempty splits: there are a pair p=(x,y)p = (x, y) and a list Q′Q' such that QQ is a reordering of pQ′pQ', pQ′pQ' is fresh for AA, the triples (Q′,A∪{x},B∪{y})(Q', A \cup \{x\}, B \cup \{y\}) and (Q′,A∪{y},B∪{x})(Q', A \cup \{y\}, B \cup \{x\}) are in 𝒩\mathcal{N}, and VpQ′(A)−VQ′(A∪{x})−VQ′(A∪{y})≤CDA,BE,ω(H).V_{pQ'}(A) - V_{Q'}(A \cup \{x\}) - V_{Q'}(A \cup \{y\}) \le C\, D^{E,\omega}_{A,B}(H).(7) Then every triple (Q,A,B)(Q, A, B) in 𝒩\mathcal{N} satisfies VQ(A)≤|Q|CDA,BE,ω(H).V_Q(A) \le |Q|\, C\, D^{E,\omega}_{A,B}(H).(8)✦

Theorem 4 (Variance on transversals). Let PP be a list of nn pairs of elements of Γ\Gamma, fresh for ∅\emptyset, let ff be a positive function on the subsets of Γ\Gamma with the slot signature property, let positive multipliers wprw_{pr} satisfy the lower half c0/(4cpr)≤wprc_0/(4c_{pr}) \le w_{pr} for any two distinct pairs pp and rr of PP, and let HH be a function on the subsets of Γ\Gamma. Then VP(∅)≤n(1+8n)D(H).V_P(\emptyset) \le n(1+8n)\, D(H).(9)✦ Moreover, for every variance node (Q,A,B)(Q, A, B) of PP with QQ nonempty there are a pair p=(x,y)p = (x, y) and a list Q′Q' such that QQ is a reordering of pQ′pQ', pQ′pQ' is fresh for AA, the triples (Q′,A∪{x},B∪{y})(Q', A \cup \{x\}, B \cup \{y\}) and (Q′,A∪{y},B∪{x})(Q', A \cup \{y\}, B \cup \{x\}) are variance nodes of PP, and VpQ′(A)−VQ′(A∪{x})−VQ′(A∪{y})≤(1+8n)DA,BEP,κ(H).V_{pQ'}(A) - V_{Q'}(A \cup \{x\}) - V_{Q'}(A \cup \{y\}) \le (1+8n)\, D^{E_P,\kappa}_{A,B}(H).(10)✦

In the paper, the result reads: for good multipliers and every real function HH on the chain’s state space Ω\Omega, Var⁡μH≤CpD(H)/c0\operatorname{Var}_\mu H \le C_p\, D(H)/c_0 with Cp=n(1+8n)C_p = n(1+8n).

What Is Checked

The bound (9) is stated over the slot totals, defect totals and slot variance of a positive ff with the slot signature property along a list PP of nn pairs fresh for ∅\emptyset, and over the Dirichlet form of the chain that joins the plain and defect states of PP by exchange edges with conductance (3), for multipliers satisfying the lower half; the one-step bound (10) is stated over the variance nodes of PP and the energy (4) restricted to the edges that respect (A,B)(A, B).