Matching generating function ($Z_G(\lambda )={\sum }_k{m}_k{\lambda }^k$)

The coefficient $m_k$ counts matchings in a graph with $k$ edges. For a bipartite graph with $n$ vertices on each side, $m_n$ counts perfect matchings and equals the permanent of a matrix of its bipartite adjacency matrix. Positive activity $\lambda$ makes $Z_G$ the normalizing constant of the weighted matching Markov chain.

For $0<a\le 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\le 1+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(\epsilon /J)$, approximates the full ratio to relative accuracy $O(\epsilon )$.