= Weighted matching Markov chain
{title2=$\pi_\lambda(M)=\lambda^{|M|}/Z_G(\lambda)$}
On the <matchings in a graph>, a <lazy Markov chain> proposes adding an <edge>, deleting an <edge>, or exchanging an <edge> for the unique matching <edge> incident with it. A proposal incident with two matching <edges> is rejected. Select the proposed <edge> uniformly and use the <Metropolis–Hastings acceptance probability> for the displayed weights. Symmetric proposals give <detailed balance>; deletions connect every state to the empty <matching in a graph>. The normalizing constant is the <matching generating function>.
Back to article page
