The Setting
Let and be matroids of equal rank on , each with ground set all of . A common base is a subset of that is a base of and of , and is the number of common bases.✦ A fully polynomial randomized approximation scheme (FPRAS) for reaches the matroids only through an independence oracle and gets its randomness only from fair coins. Running the annealing estimator for in this model means computing ranks from the oracle with few queries and drawing each of its random choices from fair bits; the success probability of one such run, a constant, is then lifted to , for a given , by a median of independent runs.
An independence oracle on takes a selector and the indicator vector of a subset and answers yes or no.✦ An independence oracle on is exact for matroids and on when, for and every , answers yes precisely when is independent in .✦
A rational is -accurate for when .✦ The uniform average of a real function on a finite set is (1)✦ and is the uniform average of the indicator of an event . The probabilities below are taken over a finite set of tables of fair bits, a table being an array of bit words on which a draw tree is run.
Ranks from the Oracle
For and , the greedy scan of starts from the empty set and takes the elements of one at a time, from the largest to the smallest, adding an element to the current set when answers yes.✦ The oracle rank is the size of the set the scan ends with, and is the rank of in .✦
For natural numbers and , a machine with registers and labels keeps a stack of bits in each register and runs a program, which assigns to each label one of five instructions: push a bit on a register and go to a given label; pop a register and go to one of three labels according as it was empty or its top bit was or ; toss a fair coin and go to one of two labels on the outcome; query on the word in a register, position marking element and missing positions marking nothing, and go to one of two labels on the answer; or halt. A configuration of the machine consists of the contents of the registers, the current label, an optional rational output, absent at first, and the numbers of oracle calls and of bit operations made so far.✦ The execution of a program with oracle from a configuration on coin bits is the sequence of configurations with and obtained from by one step of with as the coin.✦
Programs are put together by concatenation: a program with labels followed by one with labels gives a program with labels that runs the first below and, from on, the second with its jump targets shifted up by .✦ The rank program is the concatenation of a greedy program, built around two register copies, and a counting program, built around a binary increment.✦ It reads the indicator word of from an input register and uses four further registers as work space. The greedy program runs the greedy scan on words: for each of it queries on that element together with the elements accepted so far, and it writes the answers, with a for each of , into an acceptance word . The counting program writes the number of s of in binary, least significant bit first, as the word ; the binary value of a word is .✦ The rank time and the rank work of are (2) where , the sum running over the s of , with the number of low-order ones of the binary counter of the counting program that the increments.✦
Draws from Fair Bits
A random draw tree with outcomes in a set is either a leaf holding an outcome , or a draw node with a bound that picks a number among uniformly at random and continues with the subtree attached to that number.✦ The binding of a tree with outcomes in and a function that gives each a tree is the tree obtained from by replacing each leaf by the tree .✦ The mapping of by a function is the tree that relabels each outcome as .✦ The optional binding of a tree with optional outcomes and a function that gives each nonempty outcome a tree is the tree obtained from by replacing each leaf with a nonempty outcome by the tree , an empty outcome being a failure that is kept.✦
The rational coin with parameters and is a single draw node with bound whose leaf for each shows whether .✦ The Bernoulli tree of a rational is the rational coin with the absolute value of the numerator of and its denominator minus one, a coin of bias when .✦ The uniform choice on a nonempty finite set is a single draw node with bound whose leaves enumerate .✦ For repeated draws, the chain sample tree of a kernel, which gives for each state a tree of the next state, runs steps from a state and returns the trajectory with ✦; the history tree of a kernel on lists runs rounds, each drawing a value from the kernel at the list built so far and appending it, and fails as soon as one round fails.✦
A tree is run on a table of bit words of one length, with one row per draw and a fixed number of attempts in each row. A leaf returns its outcome. A draw node with bound reads the first bits of each word of the current row as rejection-sampling attempts, takes the first accepted value and continues with its subtree on the remaining rows. The run gives no value when the rows run out, the words are too short, or every attempt of a row is rejected.
The Estimator
The estimator works on the paired ground set , with and the two copies of and the slot pairs listed for ✦, and on the paired matroid , the direct sum of on the first copy and the dual of on the second✦; is the rank of .
For a list of disjoint pairs in a finite set , here with the slot pairs, a pair is empty, single or full in a subset of when contains none, exactly one or both of its entries. A plain state of is a subset of in which every pair of is single✦, and a defect state for two distinct pairs and of is a subset in which is empty, is full and every other pair is single.✦ The chain state space consists of the plain and the defect states. An exchange choice for is a pair with and ✦; it exchanges for .✦
Multipliers are numbers indexed by ordered pairs of pairs. For multipliers and a phase index , a natural number counting the annealing phases of the estimator, the anneal weight and the chain weight of are (3) where when is a defect state for and , and when is plain.✦
For a weight on , the Metropolis step from stays at with probability ; otherwise it picks an exchange choice for uniformly, and when is a chain state it moves to with probability , staying at otherwise.✦
The empirical mean of a function on sets over a list of sets is , counted with multiplicity; a condition in brackets, as in , stands for the function of that is when the condition holds and otherwise.✦ The learned update of multipliers along is (4) for distinct pairs of the list, the other entries staying unchanged. The stored multipliers start from and are updated by (4) along the sets of the trajectories of phases in turn.
One run of the estimator has phases, with chain states in each. Phase , given the trajectories of the earlier phases, fails unless every stored multiplier with is positive; otherwise it takes a start state from the restart procedure at and runs Metropolis steps for the weight of (3), recording the trajectory of states.✦ The restart procedure draws a uniform plain state at , and passes from to by capped rounds at phase , with cap ✦, where (5)✦ After the phases, with every stored multiplier positive, the restart procedure at gives a plain state . The run outputs the annealing estimate (6) when has rank in , and otherwise.✦
The run is a draw tree: the history tree of its phases, each a chain sample tree of Metropolis steps whose laziness and acceptance are Bernoulli trees and whose exchange choice and initial plain state are uniform choices.
For a rational with binary digits in the denominator of its lowest terms, the anneal length, the tolerance, the accuracy exponent and the sample count are (7) With and from (5), the fair bank is the set of tables of rows, each of words of bits, where (8)✦ The output of one run on is the value of the run’s tree on , with at most draws, and when it gives no value.✦
The median of rationals is the entry at position , counting from , of the list sorted in increasing order.✦ For a rational with binary digits in the denominator of its lowest terms, the repetition count is (9)✦ The FPRAS bank is the set of -tuples of tables of the fair bank with and .✦ The bounded output on is the median of the runs, .
The Claim
Theorem 1. Let and be matroids on , each with ground set all of , with common bases.
(a) If is an independence oracle exact for and , then for and every , (10)✦
(b) Let be an independence oracle exact for and , let have indicator word , and let be a configuration of the machine at label with in the input register, the work registers empty, any words in the other registers, and oracle calls and bit operations on its counters. Then for and every sequence of coin bits, the execution of with oracle from on satisfies, with the rank time and the rank work of (2), (11)✦
(c) Let , let and have equal rank, let be rational, let be a natural number with , put , and let be a natural number with . Then (12)✦
(d) Let be a nonempty finite set, a function, and rationals, and a rational with repetition count as in (9). If , then (13)✦
(e) Let , let and have equal rank, and let and be rationals. Then (14)✦
In the paper, the result reads: ranks come from the oracle by a greedy scan with at most queries, the exact rational choices of the algorithm come from fair bits with a bounded number of trials, and the output is the median of independent bounded runs.
What Is Checked
The claims are stated over matroids and on with ground set and their number of common bases; over an exact independence oracle, the oracle rank and the rank program with its rank time and rank work in (10) and (11); over equal ranks, the parameters (7) and the output of one run of the estimator, with its annealing estimate (6), on the fair bank (8) in (12); over the median of values on a finite set in (13); and over the bounded output on the FPRAS bank in (14), with probabilities as uniform averages (1).
Of the slot pairs, the library proves that they are fresh for the empty set✦, a list of pairs being fresh for a set when the entries of all its pairs are distinct and none lies in ✦; that their support, the set of all their entries, is the whole of ✦; and that the list is nonempty when .✦