  We study Bayesian inversion for a model elliptic PDE with unknown diffusion
coefficient. We provide complexity analyses of several Markov Chain-Monte Carlo
(MCMC) methods for the efficient numerical evaluation of expectations under the
Bayesian posterior distribution, given data $\delta$. Particular attention is
given to bounds on the overall work required to achieve a prescribed error
level $\varepsilon$. Specifically, we first bound the computational complexity
of "plain" MCMC, based on combining MCMC sampling with linear complexity
multilevel solvers for elliptic PDE. Our (new) work versus accuracy bounds show
that the complexity of this approach can be quite prohibitive. Two strategies
for reducing the computational complexity are then proposed and analyzed:
first, a sparse, parametric and deterministic generalized polynomial chaos
(gpc) "surrogate" representation of the forward response map of the PDE over
the entire parameter space, and, second, a novel Multi-Level Markov Chain Monte
Carlo (MLMCMC) strategy which utilizes sampling from a multilevel
discretization of the posterior and of the forward PDE.
  For both of these strategies we derive asymptotic bounds on work versus
accuracy, and hence asymptotic bounds on the computational complexity of the
algorithms. In particular we provide sufficient conditions on the regularity of
the unknown coefficients of the PDE, and on the approximation methods used, in
order for the accelerations of MCMC resulting from these strategies to lead to
complexity reductions over "plain" MCMC algorithms for Bayesian inversion of
PDEs.}
