Annealing ratios for a matching generating function

ID: annealing-ratios-for-a-matching-generating-function

For , expand the expectation under the weighted matching Markov chain stationary weights to obtain the displayed identity. If the largest matching in a graph has edges and , the observable lies in . Its sample mean has controlled error by the Hoeffding inequality. A product of ratios, each estimated to relative accuracy , approximates the full ratio to relative accuracy .

New to topics? Read the docs here!