The Setting
The Markov chain behind the approximate count of common bases of two matroids on moves on subsets of the paired ground set , where the two copies of each form a pair. The library works with any finite set and a list of disjoint pairs of its elements. These notes define, for a real function on the subsets of , its averages over classes of chain states, the projection built from them, and its mean and variance over the chain states under the chain weight defined below.
A pair of elements of is empty in a subset of when contains neither of its elements✦, single when contains exactly one✦, and full when contains both.✦ A plain state, or transversal, of is a subset of in which every pair of is single; is the set of them.✦ For distinct pairs and of , a defect state of class is a subset of in which is empty, is full and every other pair of is single; the defect class is the set of them.✦ A chain state is a plain state or a defect state of some class✦, and the chain states form the finite set (1)✦
Weights and Slot Totals
Let be a real function on the subsets of , and let be real multipliers, one for each ordered pair of pairs of . The multiplier of a subset of is when and otherwise.✦ The chain weight of and the total chain weight are (2)
Read a real function on the subsets of as the multiaffine polynomial in the variables for , where is the product of the with . For a vector of , is the coefficient function of the derivative of this polynomial along , and the iterated derivative along a list of vectors is , which is itself for the empty list.✦ The indicator vector of a finite set has entry on and elsewhere✦, and the direction of a pair is .✦ The slot total of along is the iterated derivative along the directions of its pairs, (3)✦ and at a set that no pair of meets, is the sum of over the sets obtained from by adding one element of each pair.
For distinct pairs and of , the defect total of at a set is the slot total along the list obtained by removing and , taken at with both elements of added: (4)✦ At a set that no pair meets, it is the sum of over the sets that add to both elements of , no element of and one element of each other pair. Write and .
The Definition
Definition 1. A class observable of is a real function on the subsets of that is constant on each defect class: (5)✦
Let be any real function on the subsets of , and let be the function . The transversal mean of is its mean, weighted by , over the sets made of one element of each pair of : (6)✦ For distinct pairs and of , the defect class mean of is its mean, weighted by , over the sets made of both elements of and one element of each pair other than and : (7)✦ The projection of is the real function on the subsets of given by (8)✦
For a real function on the subsets of , the chain mean and the chain variance are its mean and variance over the chain states, weighted by the chain weight of (2): (9)✦ (10)✦
In the paper, the result reads: keeps every value of on and replaces the values of on each defect class by the conditional mean of on that class.
What Is Checked
The definitions (8) to (10) are stated over a finite set , the list of pairs of its elements with its transversals and defect classes, a real function on the subsets of with its slot totals (3) and defect totals (4), and the multipliers with the chain weight (2) on the chain states of (1).