Convergence of Monte Carlo methods for multivariate probabilities

R.S.MacKay, Mathematics, R.S.MacKay@warwick.ac.uk

Markov chain Monte Carlo methods simulate a given probability distribution rho on a space X by designing the chain to have rho as unique attracting stationary measure.  It is conventional to say that the empirical measure rho_N := N^{-1} sum_{n=0..N-1} delta_{x_n} for N steps starting from initial state x_0 converges to rho like N^{-1/2}, which is regarded as very slow (delta_x is the atomic measure on state x in X).  An alternative view, however, is to prove that given an observable phi: X -> R and tolerance eps_phi then P{|rho_N(phi)-rho(phi)| > eps_phi}  < C eta^N for some C>0, eta in (0,1), which can be described as exponential convergence.  See for example 
Ch 6 of Dembo A, Zeitouni O, Large deviation techniques and applications, Springer 1993, 1998.
In particular, if X is a metric space with metric d, phi is restricted to Lipschitz functions and eps_phi = eps |phi|_L where |phi|_L is the best Lipschitz constant, then such a result holds with C, eta independent of phi for suitable Markov chains (make sure you can prove this for starters).  We can summarise by defining a distance D between probabilities rho and rho' by
D(rho',rho) = sup (rho'(phi)-rho(phi))/|phi|_L 
over non-constant Lipschitz functions phi, and proving that
P{D(rho_N,rho)>eps} < C eta^N. (*)

For X= prod_{s in S} X_s, a product of metric spaces with a large number of factors, the above metric D tends not to be useful, whatever way to metrise X is chosen.  I propose instead to replace the Lipschitz functions by Dobrushin's class with semi-norm
|phi| = sum_{s in S} Delta_s(phi)
where Delta_s(phi) is the sup over states on all sites but s of the best Lipschitz constant with respect to changes on site s only.  See
MacKay RS, Parameter-dependence of Markov processes on large networks, in ECCS'07 Proceedings (on CD; an updated version is on my website http://www2.warwick.ac.uk/fac/sci/maths/people/staff/Robert_MacKay). 

Prove an analogue of (*) for suitable choices of Markov chain on large products, eg weakly dependent PCAs; test the result numerically on some examples.

See also:
Eizenberg A, Kifer Y, Large deviations for PCA II, J Stat Phys 117 (2004) 845-889
Kontoyiannis I, Lastras-Montano LA, Meyn SP, Exponential bounds and stopping rules for MCMC and general Markov chains, ACM Internat Conf Proc 180 (2006) article 45