The Setting
Markov chain Monte Carlo estimates a stationary mean by a time average. A chain with stationary distribution is run for steps from a start drawn from , and for an observable , a real function on the states, is the estimate of the stationary mean . The start is warm when for a constant , and the question is how fast the mean squared error of the estimate falls with . The answer comes first for any finite lazy reversible chain, under an inequality tying the observable to the Dirichlet form, and then for the weighted Metropolis chain on the plain and defect states of disjoint pairs, the sets that take exactly one element of every pair, or both elements of one pair and none of another and one element of each other pair, with a constant that is a polynomial in .
Lazy Reversible Chains
A lazy reversible chain on a finite state space is a transition matrix on , with nonnegative entries and rows summing to , together with a strictly positive distribution on , such that for all states and for every state . The transition operator of a lazy reversible chain on is the map that sends a function on to the function given by .✦ For functions on , the stationary mean , the stationary inner product and the Dirichlet form of the chain are defined by (1)
Let be a strictly positive distribution on , and let be move probabilities on : , for every , and . The chain from the moves is the lazy reversible chain with stationary distribution that goes from to a state with probability and stays at with the remaining probability.✦
For a state and a function of paths of states, is the sum of over all such paths with : the expectation of for the chain started at .✦ For a function of paths and a function on the states, is the expectation of for the chain started from . The path sum of a function on along a path is the sum of its values at the states of the path✦, and the squared path sum moment of over steps is (2)✦ with . For , the number is the mean squared error of the time average of over steps from .
Plain and Defect States
Let be a finite set and a nonempty list of pairs of elements of whose entries are distinct and whose support, the set of all entries, is . A pair is empty, single or full in a subset of when contains none, exactly one or both of its elements, respectively. A plain state of is a subset of in which every pair of is single.✦ A defect state for two distinct pairs of is a subset of in which is empty, is full and every other pair of is single.✦ The chain states of are its plain and defect states✦; they form the finite state space .
A real function on the subsets of is a class observable when it is constant on each defect class: whenever and are defect states for the same and .✦
Let be positive multipliers indexed by two pairs and , and let be a positive function on the subsets of . The multiplier of a chain state is when is a defect state for and , and when is plain.✦ The weight of is ✦, the total weight is ✦, and . The mean of an observable under is ✦, and its variance is (3)✦
Two subsets and of are exchange adjacent when and for a set and distinct elements outside .✦ The Metropolis moves on are (4)✦ and the weighted Metropolis chain is the chain from the moves with stationary distribution .✦
Good Multipliers and the Slot Signature
The multiaffine polynomial of a real function on the subsets of is in variables , , where is the product of the with ; is its coefficient function. For a vector , is the coefficient function of the derivative of that polynomial in the direction , and along a list of vectors .✦ The indicator vector of a finite set has entry on and elsewhere✦, and a pair has the direction .✦ The slot total of along a list of pairs is the iterated derivative (5)✦ when the pairs are disjoint and avoid a set , its value at is the sum of over the sets obtained from by adding one element of each pair.
Write . For distinct pairs of , the defect total is the slot total along without and , at the set : the sum of over the sets that contain both elements of , no element of and one element of each other pair.✦ The multipliers satisfy the lower half of the good multiplier condition when , and the upper half when , for all distinct pairs of ; they are good when both halves hold.
The face Hessian of a function on the subsets of at a set is the symmetric matrix indexed by , with zero diagonal and entry for .✦ A bilinear form on a real vector space has one positive direction when implies for every with ; for a symmetric form this is the condition of at most one positive eigenvalue.✦ The function has the slot signature property when, for every list of pairs of and every set , the face Hessian has one positive direction.✦
The Claim
Theorem 1. Let be a lazy reversible chain on a finite state space with stationary distribution , let be a real function on , and let be a constant such that for every real function on . Let , and let be a real function on with for every state . Then for every (6)✦
Let be a nonempty list of pairs of elements of with distinct entries and support , let be positive good multipliers and a positive function on the subsets of with the slot signature property, and let be a class observable. Let , and let be a real function on with for every chain state . Then for every the weighted Metropolis chain satisfies (7)✦
Under the same hypotheses on , , and , if and for every chain state , then for every (8)✦
In the paper, the result reads: for good multipliers, a class observable and a trajectory of the weighted Metropolis chain started from , every gives , where stands for the paper’s constant .
What Is Checked
The claim is stated over a lazy reversible chain with its stationary inner product, its Dirichlet form and the squared path sum moment (2), and over the weighted Metropolis chain on the plain and defect states of , the chain from the moves (4) with stationary distribution , for positive good multipliers, a positive with the slot signature property and a class observable .
About the Metropolis moves the library proves that they are nonnegative✦, that they are in detailed balance with , ✦, and that they sum to at most from every chain state.✦