Computational complexity of Markov chain Monte Carlo methods for finite Markov random fields Export

@article{citeulike:1165586, abstract = {This paper studies the computational complexity of Markov chain Monte Carlo algorithms with finite-valued Markov random fields on a finite regular lattice as target distributions. We state conditions under which the complexity for approximate convergence is polynomial in n, the number of variables. Approximate convergence takes time O(n log n) as n[-\&gt;]{infty} if the target field satisfies certain spatial mixing conditions. Otherwise, if the field has a potential with finite interaction range independent of n, the complexity is exponential in n{gamma}, with {gamma}<1, which is still more favourable than enumerating all the states. When the interaction range grows with n, the algorithms can converge exponentially in n. Analogous results are provided for an expectation approximated by an average along the chain. 10.1093/biomet/84.1.1}, author = {Frigessi, Arnoldo and Martinelli, Fabio and Stander, Julian}, citeulike-article-id = {1165586}, citeulike-linkout-0 = {http://dx.doi.org/10.1093/biomet/84.1.1}, citeulike-linkout-1 = {http://biomet.oxfordjournals.org/cgi/content/abstract/84/1/1}, day = {1}, doi = {10.1093/biomet/84.1.1}, journal = {Biometrika}, keywords = {complexity, learning, trustworthiness}, month = {March}, number = {1}, pages = {1--18}, posted-at = {2007-03-15 14:45:05}, priority = {2}, title = {Computational complexity of Markov chain Monte Carlo methods for finite Markov random fields}, url = {http://dx.doi.org/10.1093/biomet/84.1.1}, volume = {84}, year = {1997} }

TY - JOUR ID - citeulike:1165586 L3 - citeulike-article-id:1165586 N2 - This paper studies the computational complexity of Markov chain Monte Carlo algorithms with finite-valued Markov random fields on a finite regular lattice as target distributions. We state conditions under which the complexity for approximate convergence is polynomial in n, the number of variables. Approximate convergence takes time O(n log n) as n[-&gt;]{infty} if the target field satisfies certain spatial mixing conditions. Otherwise, if the field has a potential with finite interaction range independent of n, the complexity is exponential in n{gamma}, with {gamma}<1, which is still more favourable than enumerating all the states. When the interaction range grows with n, the algorithms can converge exponentially in n. Analogous results are provided for an expectation approximated by an average along the chain. 10.1093/biomet/84.1.1 IS - 1 JF - Biometrika EP - 18 TI - Computational complexity of Markov chain Monte Carlo methods for finite Markov random fields VL - 84 SP - 1 KW - complexity KW - learning KW - trustworthiness AU - Frigessi, Arnoldo AU - Martinelli, Fabio AU - Stander, Julian PY - 1997/03/01/ UR - http://dx.doi.org/10.1093/biomet/84.1.1 ER -