The Setting
Take a finite set split into disjoint pairs and a positive function on its subsets. A Markov chain moves, by exchanging one element for another, among the plain states and the defect states. Averaging an observable over each class of defect states gives its projection. The question is whether the stationary variance of the projection is bounded by a polynomial multiple of the Dirichlet form of the observable itself, a Poincaré inequality in observable form. The two matroids of the counting problem enter only through one hypothesis on , the slot signature property.
Let be a list of pairs of elements of , of length . A list of pairs of elements of is fresh for a subset of when the entries of its pairs are pairwise distinct and none of them lies in .✦ The support of a list of pairs of elements of is the set of elements of that are an entry of some pair of , and covers when its support is .✦ An observable is a real function on the subsets of .
Slot Totals and Good Multipliers
A real function on the subsets of is the coefficient function of the multiaffine polynomial in the variables , . For a vector , is the coefficient function of the derivative of this polynomial in the direction , and the iterated derivative along a list of vectors is , which is for the empty list.✦ The indicator vector of a finite set has entry on and elsewhere✦, and the direction of a pair is .✦ The slot total of along is the iterated derivative along the directions of its pairs, (1)✦ and when the pairs are disjoint and avoid a set , its value is the sum of over the sets obtained from by adding one element of each pair. We write .
For pairs and of the list and a subset of , the slot defect of at is the slot total along the list with and removed, taken at with both entries of added: (2)✦ When the pairs are disjoint and avoid , it is the sum of over the sets that add to both entries of , no entry of and one entry of each other pair.
The face Hessian of a real function on the subsets of at a subset is the symmetric matrix with rows and columns indexed by , zero diagonal, and entry for distinct and .✦ A bilinear form on a real vector space has one positive direction when, for every vector with , every vector with satisfies ; for a symmetric form this is having at most one positive eigenvalue.✦ A real function on the subsets of has the slot signature property when, for every list of pairs of elements of and every subset of , the bilinear form of has one positive direction.✦
Multipliers are reals , one for each ordered pair of pairs of elements of . Multipliers are good for a function along a list of pairs of elements of when, for all distinct pairs and of , (3)
The Chain
A pair of elements of is empty in a subset of when neither nor lies in ✦, full when both do✦, and single when exactly one does.✦ A subset of is a plain state of when every pair of the list is single in .✦ For distinct pairs and of the list, a subset of is a defect state for when is empty in , is full in and every other pair of the list is single in .✦ A chain state of is a subset of that is a plain state or a defect state for some ✦, and is the finite set of chain states.✦
The multiplier of a subset is when is a defect state for , and otherwise.✦ The weight of and the total weight are (4) and the mean and the variance of an observable are (5)
Two subsets and of are exchange adjacent when and for a set and distinct elements .✦ The edge set of the chain consists of the ordered pairs of exchange adjacent chain states✦, and the conductance of an edge is (6)✦
A subset of respects a pair of subsets of when and ✦, and an edge respects when both of its endpoints do.✦ For a finite set of edges, ordered pairs of subsets of , with conductances , the energy of an observable restricted to is (7)✦ The energy of an observable is the restricted energy taken over the edge set with conductances . The Dirichlet form of the chain is (8)✦
The Projection
The plain mean and, for pairs and of the list, the defect mean of an observable are (9) with the pointwise product. The observable projection of is the observable equal to the defect mean on the defect states and to elsewhere: (10)✦ The defect types of are the ordered pairs of distinct pairs of the list, and is their set.✦
The Claim
Theorem 1. Let be a finite set, let be a list of pairs of elements of that is fresh for and covers , let be a positive real function on the subsets of with the slot signature property, and let be positive multipliers that are good for along . Then every observable satisfies (11)✦ and if is nonempty, then (12)✦
In the paper, the result reads: for good multipliers and every function on , with .
What Is Checked
The bounds (11) and (12) are stated over the chain states of a list of pairs fresh for and covering , the weights built from the multipliers and from , the exchange edges with conductances , the restricted energy and the Dirichlet form , the variance , the slot totals and slot defects behind , , and , the projection and the defect types , under the slot signature property of and good multipliers.