The Setting
Fix a finite set split into disjoint pairs , a positive function on the subsets of , and positive multipliers , one for each ordered pair 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 made of and the multipliers. With two pairs, the chain lives on , , , and on , , and from it can step to or to .
A Poincaré inequality for a reversible chain bounds the variance of an observable under the stationary law by the chain’s energy at ; 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 is a pair of a real function on and a real function on such that, for all , (1)✦ The stationary law of a finite lazy reversible chain on is .
For real functions on write ✦ and ✦, and let be the identity operator on real functions on . The energy of the chain at a real function on is (2)✦
A system of moves for a positive probability vector on is a nonnegative function on such that and for all and . The chain built from such moves is the lazy reversible chain with stationary law and transition probabilities (3)✦
Chain States and Exchange Edges
A pair is empty, single or full in a subset of when contains none, exactly one or both of its elements. A subset of is a plain state when every pair is single in ✦, and a defect state for two distinct pairs and when is empty in , is full in and every other pair is single in ✦. The chain states are the plain states and the defect states; is their set.✦
The weight of a subset of is (4)✦ and the total weight is ✦.
Two subsets and of are exchange adjacent when and for a subset of and distinct elements .✦ The exchange edges are the ordered pairs of exchange-adjacent chain states, (5)✦ and the conductance of a pair of subsets of is (6)✦
A subset of respects two subsets and of when and ✦, and a pair respects them when and both do✦. For a finite set of ordered pairs of subsets of , a real function on such pairs and a real function on the subsets of , the restricted energy of on with respect to and is (7)✦ The edge energy of a real function on the subsets of is , the restricted energy over the exchange edges (5) with the conductance (6) and no restriction.
The Claim
Definition 1. Let the finite set be covered by pairs whose entries are distinct, let be a positive function on the subsets of , and let the multipliers be positive. The Metropolis chain is the lazy reversible chain on the chain states with stationary law , built as in (3) from the moves✦ (8)✦ Its Dirichlet form is , and for every real function on the subsets of the energy of the chain at the restriction of to is (9)✦
In the paper, the result reads: the lazy Metropolis chain with one-element exchanges inside has and .
What Is Checked
The claim is stated over a finite set covered by pairs with distinct entries, a positive function on its subsets and positive multipliers , through the plain and defect states , the weights (4) with total , 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 and , the library proves that the moves (8) are nonnegative✦ and in detailed balance with ✦, and, when the pairs have distinct entries covering , that every row sum is at most ✦.