Random sampling for the monomer–dimer model on a lattice
2000; American Institute of Physics; Volume: 41; Issue: 3 Linguagem: Inglês
10.1063/1.533198
ISSN1527-2427
AutoresJacob van den Berg, Rachel M. Brouwer,
Tópico(s)Bayesian Methods and Mixture Models
ResumoIn 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), O(|Λ|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 ε) O(|Λ|(ln|Λ|)2).
Referência(s)