In this paper we prove an optimal spectral structure theorem for stochastic matrices reversible with respect to a fixed probability measure $\pi$ on a finite set and devise a new simulation algorithm for Markov random fields. We compute the minimum value for the second largest eigenvalue of all such matrices and characterize the class of matrices for which this minimum is attained. In fact, they share a common right eigenvector that can be written in terms of $\pi$. Furthermore, by iterating this procedure, we obtain a unique matrix which is minimal with respect to the lexicographic order of the eigenvalues. We give a probabilistic interpretation of the corresponding eigenvectors. Our results allow us to devise a dynamic Monte Carlo scheme which has an optimal worst-case performance. Regarding the simulation of lattice-based Gibbs distributions, we design a modified Gibbs sampler, whose performance is better in terms of both weak convergence at low temperatures and asymptotic variance of time averages at all temperatures.
Publié le : 1992-08-14
Classification:
Reversible stochastic matrices,
space average estimation,
Monte Carlo methods,
simulation of Markov random fields,
Gibbs sampler,
image analysis,
60J10,
15A51,
65C05,
60G60
@article{1177005652,
author = {Frigessi, Arnoldo and Hwang, Chii-Ruey and Younes, Laurent},
title = {Optimal Spectral Structure of Reversible Stochastic Matrices, Monte Carlo Methods and the Simulation of Markov Random Fields},
journal = {Ann. Appl. Probab.},
volume = {2},
number = {4},
year = {1992},
pages = { 610-628},
language = {en},
url = {http://dml.mathdoc.fr/item/1177005652}
}
Frigessi, Arnoldo; Hwang, Chii-Ruey; Younes, Laurent. Optimal Spectral Structure of Reversible Stochastic Matrices, Monte Carlo Methods and the Simulation of Markov Random Fields. Ann. Appl. Probab., Tome 2 (1992) no. 4, pp. 610-628. http://gdmltest.u-ga.fr/item/1177005652/