Timeline for Sampling i.i.d. variables with restrictions
Current License: CC BY-SA 4.0
10 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 27, 2020 at 9:45 | comment | added | Peter Wildemann | The idea of first sampling the "parity field" that you proposed actually turned out to lead to a nice solution! According to an article by Lupu and Werner (arxiv.org/abs/1511.05524), the odd edges in the random current satisfy the law of the socalled loop o(1) model. This model you can sample via the Markov chain that "flips along elementary loops". Moreover, the random current model is then obtained by an independent Poisson process as you explained. | |
| Jun 27, 2020 at 9:43 | vote | accept | Peter Wildemann | ||
| May 28, 2020 at 9:18 | comment | added | Peter Wildemann | Yes, conditioned on the parity of the edges, the model indeed decouples, although I don't think that this really leads to any major simplification. However, your above comment seems quite helpful. I will spend some time on this and try to come back with my findings. | |
| May 27, 2020 at 16:22 | comment | added | James Martin | @PeterWildemann: I added an edit above | |
| May 27, 2020 at 8:20 | history | edited | James Martin | CC BY-SA 4.0 |
added 1575 characters in body
|
| May 27, 2020 at 4:21 | comment | added | James Martin | @PeterWildemann Another way to put it: although you can't calculate the probability $\pi(x)$ that you want, for a given feasible configuration $x$, you can calculate the ratio $\pi(y)/\pi(x)$ where $x$ and $y$ are two feasible configurations - it's just the same as the ratio of the unconditioned probabilities $\mathbb{P}_X^{\otimes n}(y)/\mathbb{P}_X^{\otimes n}(x)$. Knowing these ratios is exactly what you need in order to make Metropolis-Hastings work. (Obviously the game is not over at that point - you still need to deal with the question of convergence somehow....) | |
| May 26, 2020 at 20:14 | comment | added | James Martin | For how to choose the loops, the answer must depend on the graph. Suppose you were on a 2-dimensional lattice torus. Then I think a decent option would just be the 4-cycles around 1x1 faces. I think that gives an irreducible chain, because any other cycle can be constructed from a whole bunch of 4-cycles by taking symmetric differences.... but I could be mistaken there.... | |
| May 26, 2020 at 20:08 | comment | added | James Martin | I thought the conditional distribution given the rest of the graph would be easy. Isn't it just independent Poissons, subject to the parity constraints? And once you fix everything outside the cycle, the parity constraints just become constraints on the parity on the values of neighbouring edges in the cycle. There will always be two classes (as I mentioned, if the parity constraints are currently satisfied, then to keep them satisfied you either change the parity of all values around the cycle, or keep the parity of all values around the cycle unchanged). Maybe I misunderstood the model.... | |
| May 26, 2020 at 19:50 | comment | added | Peter Wildemann | Thank you for your input, James! Using MCMC methods seems like the most natural approach to me as well, the problem being that I do not see how to construct a Markov chain with the correct invariant measure. In particular the "Glauber dynamics" you proposed seems difficult to implement, since the model does not satisfy (as far as I can see) a Domain Markov Property, so the conditional measure is not tractable. (Also, I wouldn't know from which distribution to pick the loops. Perhaps a uniform even subgraph or the Loop-O(1) measure might work ...) | |
| May 26, 2020 at 16:53 | history | answered | James Martin | CC BY-SA 4.0 |