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

被引:23
作者
Frigessi, A [1 ]
Martinelli, F [1 ]
Stander, J [1 ]
机构
[1] UNIV PLYMOUTH,DEPT MATH & STAT,PLYMOUTH PL4 8AA,DEVON,ENGLAND
关键词
Gibbs sampler; metropolis algorithm; NP-completeness; range of interaction; rate of convergence; spectral gap; stopping rule;
D O I
10.1093/biomet/84.1.1
中图分类号
Q [生物科学];
学科分类号
07 ; 0710 ; 09 ;
摘要
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 --> infinity if the target field satisfies certain spatial mixing conditions. Otherwise, if the held 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.
引用
收藏
页码:1 / 18
页数:18
相关论文
共 27 条
[1]   ROUNDING EFFECTS OF QUENCHED RANDOMNESS ON 1ST-ORDER PHASE-TRANSITIONS [J].
AIZENMAN, M ;
WEHR, J .
COMMUNICATIONS IN MATHEMATICAL PHYSICS, 1990, 130 (03) :489-528
[2]  
[Anonymous], 1992, Stochastic Stability of Markov chains
[3]  
Asmussen S., 1992, ACM Transactions on Modeling and Computer Simulation, V2, P130, DOI 10.1145/137926.137932
[4]   BAYESIAN COMPUTATION AND STOCHASTIC-SYSTEMS [J].
BESAG, J ;
GREEN, P ;
HIGDON, D ;
MENGERSEN, K .
STATISTICAL SCIENCE, 1995, 10 (01) :3-41
[5]  
BESAG J, 1993, J ROY STAT SOC B MET, V55, P25
[6]  
Diaconis P., 1991, Ann. Appl. Probab., P36
[7]  
EMNGERSEN KL, 1996, ANN STAT, V24, P101
[8]   SAMPLING FROM LOG-CONCAVE DISTRIBUTIONS [J].
Frieze, Alan ;
Kannan, Ravi ;
Polson, Nick .
ANNALS OF APPLIED PROBABILITY, 1994, 4 (03) :812-837
[9]  
FRIGESSI A, 1993, J R STAT SOC B, V55, P205
[10]  
FRIGESSI A, 1993, J STAT PHYS, V75, P585