Catalogo Articoli (Spogli Riviste)

OPAC HELP

Titolo:
COMPUTATIONAL-COMPLEXITY OF MARKOV-CHAIN MONTE-CARLO METHODS FOR FINITE MARKOV RANDOM-FIELDS
Autore:
FRIGESSI A; MARTINELLI F; STANDER J;
Indirizzi:
UNIV ROMA TRE,DIPARTIMENTO MATEMAT,VIA SEGRE 2 I-00146 ROME ITALY UNIV PLYMOUTH,DEPT MATH & STAT PLYMOUTH PL4 8AA DEVON ENGLAND
Titolo Testata:
Biometrika
fascicolo: 1, volume: 84, anno: 1997,
pagine: 1 - 18
SICI:
0006-3444(1997)84:1<1:COMMMF>2.0.ZU;2-O
Fonte:
ISI
Lingua:
ENG
Soggetto:
BAYESIAN COMPUTATION; CONVERGENCE-RATES; SPIN SYSTEMS; ISING-MODEL; DYNAMICS; LATTICE; REGION;
Keywords:
GIBBS SAMPLER; METROPOLIS ALGORITHM; NP-COMPLETENESS; RANGE OF INTERACTION; RATE OF CONVERGENCE; SPECTRAL GAP; STOPPING RULE;
Tipo documento:
Article
Natura:
Periodico
Settore Disciplinare:
CompuMath Citation Index
Science Citation Index Expanded
Citazioni:
26
Recensione:
Indirizzi per estratti:
Citazione:
A. Frigessi et al., "COMPUTATIONAL-COMPLEXITY OF MARKOV-CHAIN MONTE-CARLO METHODS FOR FINITE MARKOV RANDOM-FIELDS", Biometrika, 84(1), 1997, pp. 1-18

Abstract

This paper studies the computational complexity of Markov chain MonteCarlo 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.

ASDD Area Sistemi Dipartimentali e Documentali, Università di Bologna, Catalogo delle riviste ed altri periodici
Documento generato il 24/09/20 alle ore 02:42:11