The Setting
Let be a finite set, a list of pairs of its elements, and a positive function on the subsets of , the coefficients of a multiaffine polynomial. Write for the set of transversals of , the sets that take one element from each pair, and for the total of over . The aim is to draw a transversal with probability . For the common bases of two matroids, the matroids enter through one condition on , 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 , its trace. The questions are whether the trace has law 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 is a transition matrix on , with nonnegative entries and rows summing to , together with a probability distribution on that is positive at every state, such that for all states and (1)✦ The transition operator sends a real function on to , with ✦; is with the operator applied times✦, and , the entry of the th power of , is the probability that the chain started at is at after steps.
For real functions and on , the stationary inner product is ✦ and the mean of is .✦ The variance and the Dirichlet form of are (2) A lazy reversible chain on satisfies a Poincaré inequality with constant , a real number, when for every real function on . The point density at a state is the function on equal to at and to elsewhere.✦
Let be a positive probability distribution on and a nonnegative matrix on with row sums at most and in detailed balance, . The chain from the moves is the lazy reversible chain on with law and transition matrix (3)✦ where is when and otherwise.
The Trace on a Set of States
Fix a lazy reversible chain on and a nonempty set of states, with complement . The exit probability of a state of is .✦ A killed kernel on a finite set is a nonnegative matrix on together with a number , , that bounds every row sum of .✦ When every state of has positive exit probability, the killed chain on is the killed kernel for , with .✦
The Green function of a killed kernel sends a real function on to ✦, where is with the operator applied times.✦ For the killed chain on , the hitting kernel and the duration are (4) is the probability that the chain started at enters first at , and is the expected number of steps it takes from to enter .
For states and of , the trace matrix and the return cost are (5) is the probability that the next visit of the chain to after is at , and is the expected number of steps until that visit. The mass of is ✦, and the trace chain on has transition matrix and law .✦
The Metropolis Chain on Transversals
Let the list be nonempty, fresh, its entries being distinct, and covering , every element of being an entry of some pair. A pair is empty, single or full in a set when contains none, exactly one or both of its elements. A plain state is a set in which every pair of is single, so that the plain states are the transversals.✦ For two distinct pairs and of , a defect state for is a set in which is empty, is full and every other pair of is single.✦ The chain states are the plain states and the defect states.✦ Two sets and are exchange adjacent when and for a set and two distinct elements and outside .✦
A system of multipliers gives a positive number to every ordered pair of distinct pairs and of ; let be such a system. The weight of a chain state is its multiplier times : when is a defect state for , and when is plain✦; is the sum of over all chain states.✦ The Metropolis moves between chain states are (6)✦ and the Metropolis chain is the chain from these moves, as in (3), on the chain states, with law .✦ The Metropolis trace chain is the trace of the Metropolis chain on , with transition matrix and law , built from the killed Metropolis chain, the killed chain on the defect states.✦
Slot Totals and the Slot Signature
The slot total of a real function on the subsets of along a list of pairs is the iterated directional derivative of the multiaffine polynomial with coefficients along the indicator vectors of the pairs of .✦ When the pairs of are disjoint and avoid a set , the value is the sum of over the sets obtained from by adding one element of each pair. The total and, for distinct pairs and of , the defect total , which at a set is the slot total along with and removed, taken at with both elements of added, are, at , (7) where denotes that list; is the sum of over the defect states for .
The face Hessian of at a set is the symmetric matrix indexed by , with zero diagonal and entry at distinct and .✦ A bilinear form on a real vector space has one positive direction when every vector with and every vector with satisfy .✦ The function has the slot signature property when, for every list of pairs of elements of and every set , the bilinear form of has one positive direction.✦ The multipliers are good when every satisfies the lower bound and the upper bound ; the lower half of goodness is the lower bound. The multipliers satisfy the lower half of goodness when (8)
The Claim
Theorem 1. Let be a lazy reversible chain on a finite set , and let be a nonempty set of states such that every state outside has positive exit probability. For all states and of , the trace matrix satisfies (9)✦ and for every state of , (10)✦
Let be a nonempty fresh list of pairs covering , positive multipliers and a positive function on the subsets of . At every transversal , the Metropolis trace chain has law (11)✦ If moreover has the slot signature property and the multipliers satisfy the lower half of goodness (8), then every real function on satisfies (12)✦ where is the Dirichlet form of the Metropolis trace chain.
If and are such that for every state of and the chain satisfies a Poincaré inequality with constant , then for every natural number and all states and , (13)✦ and (14)✦
If is a real number and a real function on with for every state of (for a distribution , a warm start with parameter ), then the return cost satisfies (15)✦ For the Metropolis chain above, with law , the transversals have mass (16)✦
In the paper, the result reads: with good multipliers, the trace on is reversible with stationary law , irreducible and lazy, with inverse spectral gap at most ; hence , and a trace step started from costs in expectation at most 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, -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 , the Metropolis chain from the moves (6) and its trace on , the totals (7), the slot signature property of and the lower half of goodness (8).
The library also proves that the trace matrix has nonnegative entries✦ and rows summing to ✦; that the Metropolis moves are nonnegative✦, sum to at most from every chain state✦ and are in detailed balance with ✦; that there is a transversal✦; and that from every defect state the Metropolis chain reaches a transversal in one step with positive probability.✦