1999

# Random sampling for the monomer-dimer model on a lattice

## Publication

### Publication

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)$.

Additional Metadata | |
---|---|

Interacting random processes; statistical mechanics type models; percolation theory (msc 60K35), Lattice systems (Ising, dimer, Potts, etc.) and systems on graphs (msc 82B20), Numerical methods (Monte Carlo, series resummation, etc.) (msc 82B80), Dynamic lattice systems (kinetic Ising, etc.) and systems on graphs (msc 82C20) | |

Logistics (theme 3), Energy (theme 4) | |

CWI | |

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

Organisation | Stochastics |

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