Timeline for How to sample a uniform random polyomino?
Current License: CC BY-SA 3.0
7 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jul 21, 2016 at 17:51 | vote | accept | Matthew Kahle | ||
| Jul 20, 2016 at 6:41 | comment | added | Nathan Clisby | Matthew, thanks for pointing this out, as previously described the algorithm was incorrect, now I think it should be fine. | |
| Jul 20, 2016 at 6:37 | history | edited | Nathan Clisby | CC BY-SA 3.0 |
corrected error in the choice of "move", other minor changes
|
| Jul 19, 2016 at 14:22 | comment | added | Matthew Kahle | Does it really satisfy detailed balance? If I am understanding the algorithm correctly, it seems like the probability of an L-tetromino transforming to square-tetromino is twice as large as a square-tetromino transforming to L-tetromino. | |
| Jul 18, 2016 at 7:15 | comment | added | Nathan Clisby | I agree with Brendan's point, with the caveat that when trying to infer the convergence properties of the Markov chain one may obtain a clearer signal by starting at a configuration that is far from equilibrium (e.g. straight rod or a solid ball). As an aside, the "kinetic growth" algorithm (as I would think of it) suggested can generate any polyomino, but overweights dense configurations and underweights sparse ones. | |
| Jul 18, 2016 at 6:05 | comment | added | Brendan McKay | Given that a close-to-reality bound on the mixing time is unlikely to available, I'd recommend starting the chain at some sort of pseudo-random polyomino rather than a fixed one. For example, make one by adding new squares at random starting with a single square, then start the chain with that. Then the chain is just fixing up an approximation that spans the whole space rather than trying to reach everywhere from one point. | |
| Jul 18, 2016 at 3:46 | history | answered | Nathan Clisby | CC BY-SA 3.0 |