๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

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


A Poisson approximation with application
โœ Peter Olofsson ๐Ÿ“‚ Article ๐Ÿ“… 1999 ๐Ÿ› Elsevier Science ๐ŸŒ English โš– 80 KB

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