Random sampling for the monomer-dimer model on a lattice

J. Van Den Berg, R. Brouwer

Research output: Contribution to JournalArticleAcademicpeer-review


In the monomer-dimer model on a graph, each matching (collection of nonoverlapping edges) M has a probability proportional to λ|M|, where λ>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 λ and ∈ (the maximal allowed variational distance from the desired distribution), 0(|A|2|E|) steps suffice, where |E| is the number of edges and |Λ| 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) significantly fewer steps, namely (for fixed λ and ∈) 0(|Λ|(ln|Λ|)2).

Original languageEnglish
Pages (from-to)1585-1597
Number of pages13
JournalJournal of Mathematical Physics
Issue number3
Publication statusPublished - Mar 2000
Externally publishedYes


Dive into the research topics of 'Random sampling for the monomer-dimer model on a lattice'. Together they form a unique fingerprint.

Cite this