In the monomer-dimer model on a graph, each matching (collection of non-overlapping edges) ${M$ has a probability proportional to $lambda^{|M|$, where $lambda > 0$ is the model parameter, and $|M|$ denotes the number of edges in $M$. An approximate random sample from the monomer-dimer distribution can be obtained by running an appropriate Markov chain (each step of which involves an elementary local change in the configuration) sufficiently long. Jerrum and Sinclair have shown (roughly speaking) that for an arbitrary graph and fixed $lambda$ and $varepsilon$ (the maximal allowed variational distance from the desired distribution), $O(|Lambda|^2 |E|)$ steps suffice, where $|E|$ is the number of edges and $|Lambda|$ the number of vertices of the graph. For sufficiently nice subgraphs (e.g. cubes) of the $d$-dimensional cubic lattice we give an explicit recipe to generate approximate random samples in (asymptotically) siginificantly fewer steps, namely (for fixed $lambda$ and $varepsilon$) $O(|Lambda| , (ln |Lambda|)^2)$.

, , ,
CWI. Probability, Networks and Algorithms [PNA]

van den Berg, R., & Brouwer, R. (1999). Random sampling for the monomer-dimer model on a lattice. CWI. Probability, Networks and Algorithms [PNA]. CWI.