The Setting
Let and be matroids on of equal rank, queried through one independence oracle, and let be the number of their common bases: the sets that are a base of and a base of .✦ The approximate counter for works on the paired ground set , two copies of , with the paired slots: the list of the pairs that join an element of the first copy to its copy in the second.✦ The paired matroid on is , the direct sum of on the first copy and the dual of on the second.✦
For a matroid on a finite set , a natural number and a real number , the matroid weight of a set is (1)✦ where is the rank function of and the exponent is when . For the paired matroid, is the sum of over the sets that contain exactly one element of each pair .
The annealing lowers geometrically from over phases. In each phase a Metropolis chain weighted by runs for steps; from the averages along the run of a few functions of the state, the phase estimates one ratio and retunes the multipliers, the positive factors the chain places on its states with one pair empty and another full, for the next phase. The estimate of is built from the product of the ratios. Below, the schedule is fixed and the errors of a run are bounded, together with a purely numerical inequality, part (a) of the theorem.
States and Weights of a Phase
A phase works over a finite set with a list of pairs of elements of ; for the matroid, and is the paired slots. A list of pairs of elements of is fresh when its entries are distinct, and covers when every element of is an entry of one of its pairs.
A pair is single in a set when contains exactly one of its entries✦, full when contains both✦, and empty when contains neither✦. A plain state of is a set in which every listed pair is single.✦ A defect type is an ordered pair of distinct pairs of ✦, and a defect state of type is a set in which is empty, is full and every other listed pair is single✦. The chain state space of is the set of its plain and defect states.✦
A real function on the subsets of is read as the multiaffine polynomial on whose coefficient function is . The slot total of along is the iterated derivative (2)✦ where is the derivative along a vector and is the indicator vector of the two entries of the pair . When the pairs are disjoint and avoid a set , is the sum of over the sets that add to one entry of each pair. Write , which is for the paired slots and . For a defect type , the slot defect is the slot total along with and removed, evaluated at the set consisting of both entries of .✦
The face Hessian of a real function on the subsets 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 with gives for all with ; for a symmetric form this is the condition of at most one positive eigenvalue.✦ A function on the subsets of has the slot signature property when, for every list of pairs of elements of and every , the bilinear form of the face Hessian has one positive direction.✦
Multipliers are positive reals , one for each defect type. The multiplier of a set is when is a defect state of type and otherwise✦; its chain weight and the total chain weight are (3) Multipliers are good for when they satisfy the lower half and the upper half for every defect type .
The Metropolis Chain
A lazy reversible chain on a finite set is a transition matrix on , with nonnegative entries and rows summing to , together with a strictly positive distribution on , such that for all and for every .✦ Given a strictly positive distribution on a finite set and moves on that satisfy and sum to at most along each row, the chain from the moves is the lazy reversible chain on with stationary distribution that goes from to with probability and stays at with the remaining probability.✦
Two sets are exchange adjacent when and for a set and distinct elements .✦ The Metropolis move kernel on is (4)✦ When is a nonempty fresh list covering and the multipliers and are positive, the Metropolis chain is the chain from the moves on with stationary distribution .✦
An observable is a real function on ; its stationary mean is .✦ For a real function on the subsets of , the phase observables are the indicator of the plain states, the defect indicator of the defect states of type for each defect type, and the plain observable of , equal to on plain states and to elsewhere.✦
Along a path of states, the path sum of is the sum of its values at the entries, a repeated state counted each time, and the path average is the path sum over the number of entries.✦ For a nonnegative function on and an event on paths, the probability of over steps from is (5)✦ where the path expectation of a function of paths is the expected value of on the path of the first steps of the chain from , the starting state included✦.
The Claim
Definition 1. For a positive integer and a natural number , the annealing ratio and the number of phases are (6)✦ (7)✦ For an accuracy and a number of phases, the annealing tolerance is (8)✦ For a matroid on , the annealed weight of phase is the matroid weight (1) at : (9)✦
Theorem 1. (a) For every positive integer and every natural number , (10)✦
(b) Let be a nonempty fresh list of pairs covering , let be a positive function with the slot signature property, let the multipliers be positive and good for , and let satisfy on plain states. Let be a nonnegative function on with , let be a natural number, let , and let be a natural number with . Then the Metropolis chain run for steps from satisfies, over the phase observables of , (11)✦
(c) Let , , and be positive reals with , let , let and , and let . Then (12)✦
(d) Let , let be a natural number and the tolerance (8). If reals satisfy , then (13)✦
(e) Let and be matroids on of equal rank and let . Then (14)✦
(f) Let , and let , and be reals with and . Then (15)✦
What Is Checked
The claim is stated over the schedule (6), (7), (8) and the annealed weights (9); over the plain and defect states of a list of pairs, its slot totals and , the slot signature property and the chain weights (3); over the Metropolis chain from the moves (4), its phase observables and the probability (5) of a path event; and over the paired matroid, the matroid weight (1) and the number of common bases.
For positive multipliers and a positive , the library shows that the Metropolis moves are nonnegative✦ and satisfy detailed balance, ✦; for a nonempty fresh list covering , it shows that the moves out of any state sum to at most ✦.