Timeline for How to sample a uniform random polyomino?
Current License: CC BY-SA 3.0
3 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 18, 2016 at 7:43 | comment | added | Nathan Clisby | Like sequential importance sampling, it can fail for some problems. My sense is that this happens when there is a global constraint that needs to be satisfied which cannot be easily decomposed into a sequence of local constraints as the object is built up. (I think it will work pretty well for sampling polyominoes.) | |
| Jul 18, 2016 at 7:40 | comment | added | Nathan Clisby | Very closely related to this, but from the physics literature, is the PERM (pruned-enriched Rosenbluth method) introduced by Peter Grassberger. See: arxiv.org/abs/cond-mat/0201313 for an overview, and references therein. This will work with the kinetic growth algorithm. The unweighted method described above corresponds to the "Rosenbluth method" which typically has large variance, while PERM generates many configurations at once which allows you to automatically optimise the weights and so reduce the variance. | |
| Jul 18, 2016 at 6:35 | history | answered | Brendan McKay | CC BY-SA 3.0 |