  The basic question in perturbation analysis of Markov chains is: how do small
changes in the transition kernels of Markov chains translate to chains in their
stationary distributions? Many papers on the subject have shown, roughly, that
the change in stationary distribution is small as long as the change in the
kernel is much less than some measure of the convergence rate. This result is
essentially sharp for generic Markov chains. In this paper we show that much
larger errors, up to size roughly the square root of the convergence rate, are
permissible for many target distributions associated with graphical models. The
main motivation for this work comes from computational statistics, where there
is often a tradeoff between the per-step error and per-step cost of approximate
MCMC algorithms. Our results show that larger perturbations (and thus
less-expensive chains) still give results with small error.
