= Annealing ratios for a matching generating function
{title2=$Z_G(b)/Z_G(a)=\mathbb E_{\pi_a}(b/a)^{|M|}$}
For $0<a\leq b$, expand the <expectation> under the <weighted matching Markov chain> stationary weights to obtain the displayed identity. If the largest <matching in a graph> has $n$ <edges> and $b/a\leq1+1/n$, the observable lies in $[1,e]$. Its sample mean has controlled error by the <Hoeffding inequality>. A product of $J$ ratios, each estimated to relative accuracy $O(\varepsilon/J)$, approximates the full ratio to relative accuracy $O(\varepsilon)$.
Back to article page
