This thesis is devoted to the construction, analysis, and implementation of two types of hierarchical Markov Chain Monte Carlo (MCMC) methods for the solution of large-scale Bayesian Inverse Problems (BIP).

The first hierarchical method we present is based on the idea of parallel tempering and is well-suited for BIP whose underlying posterior measure is multi-modal or concentrates around a lower-dimensional, non-linear manifold. In particular, we present two generalizations of the Parallel Tempering algorithm in the context of discrete-time Markov chain Monte Carlo methods for Bayesian inverse problems. These generalizations use state-dependent swapping rates and are inspired by the so-called continuous-time Infinite Swapping algorithm presented in Plattner et al. [J Chem Phys 135(13):134111, 2011]. We present a thorough analysis of the convergence of our proposed methods and show that they are reversible and geometrically ergodic. Numerical experiments conducted over an array of BIP show that our proposed algorithms significantly improve sampling efficiency over competing methodologies.

Our second hierarchical method is based on multi-level MCMC (ML-MCMC) techniques. In this setting, instead of sampling directly from a sufficiently accurate (and computationally expensive) posterior measure, one introduces a sequence of accuracy levels for the solution of the underlying computational model, which induces a hierarchy of posterior measures with increasing accuracy and cost to sample from. The key point of this algorithm is to construct highly coupled Markov chains together with the standard Multi-level Monte Carlo argument to obtain a better cost-tolerance complexity than a single-level MCMC algorithm. We present two types of multi-level MCMC algorithms which can be thought of as an extension of the ideas presented in Dodwell, et al. [SIAM-ASA J. Uncertain. Quantif (2015): 1075-1108].

Our first ML-MCMC method extends said ideas to a setting where a wider class of Independent Metropolis-Hastings (IMH) proposals are considered. We provide a thorough theoretical analysis and provide sufficient conditions on the proposals and the family of posteriors so that there exists a unique invariant probability measure for the coupled chains generated by our method, and the convergence to it is uniformly ergodic. We also generalize the cost-tolerance theorem of Dodwell et al., to our setting, and propose a self-tuning continuation-type ML-MCMC algorithm.

Our second ML-MCMC method presents an algorithm that admits state-dependent proposals by using a maximal coupling approach. This is desirable, from a methodological perspective, whenever it is difficult to construct suitable IMH proposals, or when the empirical measure resulting from samples from the posterior at the previous level does not satisfy the assumptions required for convergence of the ML-MCMC method. We present a theoretical analysis of the method at hand and show that this new method has an invariant probability measure and converges to it with geometric ergodicity. We also extend the cost-tolerance theorem of Dodwell et. al. to this algorithm, albeit with quite restrictive assumptions. We illustrate both of the proposed ML-MCMC methodologies on several numerical examples.