Approximating the Permanent via Importance Sampling with Application to the Dimer Covering Problem
โ Scribed by Isabel Beichl; Francis Sullivan
- Publisher
- Elsevier Science
- Year
- 1999
- Tongue
- English
- Weight
- 151 KB
- Volume
- 149
- Category
- Article
- ISSN
- 0021-9991
No coin nor oath required. For personal study only.
โฆ Synopsis
We estimate the asymptotic growth rate of the number of dimer covers of a cubic lattice. Our estimate, ฮป 3 = 0.4466 ยฑ 0.0006 is consistent with the lower bounds obtained by Hammersley and (later) Schrijver and the more recent improved upper bound obtained by Ciucu. Obtaining this estimate is an important step toward approximating the partition function of the cubic monomer-dimer system. From the partition function, all of the standard thermodynamic quantities can be evaluated. It is well known that computing ฮป 3 is equivalent to computing the permanent of a certain 0-1 matrix. We describe an extremely efficient Monte Carlo algorithm for approximating the permanent. Previous work on Monte Carlo approaches includes the pioneering results of Jerrum and Sinclair, who use a rapidly mixing random walk. Our method is inspired by results of Soules on convergence of Sinkhorn balancing to obtain a maximum entropy, doubly stochastic matrix. We use the Sinkhorn balanced matrix to generate an importance function that allows us to do direct random sampling, rather than a random walk that converges to a limiting distribution.
๐ SIMILAR VOLUMES
We present a Poisson approximation with applications to extreme value theory. Let X1; X2; : : : be i.i.d. and let n be the j largest order statistics. Then the asymptotic behavior of the vector (M (1) n ; : : : ; M ( j) n ) is the same as that of (M (1) N ; : : : ; M ( j) N ) where N is a random va