Comparing sweep strategies for stochastic relaxation (Q1176229)

The problem of simulation of probability measures in high-dimensional spaces is considered. The stochastic relaxation procedure, whose idea consists in iterative simulation of a part of coordinates according to appropriate conditional distribution, is studied. The random (random sweep strategies) and non-random (deterministic sweep strategies) choice mechanism for such parts of coordinates on each step of the relaxation procedure are compared. The main result gives upper bounds on the rate of convergence of stochastic relaxation for general Gaussian distributions, which are shown to be exponential, for deterministic and random sweep strategies. All bounds are given in terms of the smallest eigenvalues of the inverse covariance matrix of the Gaussian distribution. An example in which the bound on the rate of convergence in the deterministic case is asymptotically achieved is constructed.