Nikolaus Schweizer

Daniel Rudolf, Nikolaus Schweizer

Perturbation theory for Markov chains addresses the question how small differences in the transitions of Markov chains are reflected in differences between their distributions. We prove powerful and flexible bounds on the distance of the $n$th step distributions of two Markov chains when one of them satisfies a Wasserstein ergodicity condition. Our work is motivated by the recent interest in approximate Markov chain Monte Carlo (MCMC) methods in the analysis of big data sets. By using an approach based on Lyapunov functions, we provide estimates for geometrically ergodic Markov chains under weak assumptions. In an autoregressive model, our bounds cannot be improved in general. We illustrate our theory by showing quantitative estimates for approximate versions of two prominent MCMC algorithms, the Metropolis-Hastings and stochastic Langevin algorithms.

Daniel Rudolf, Nikolaus Schweizer

We prove explicit error bounds for Markov chain Monte Carlo (MCMC) methods to compute expectations of functions with unbounded stationary variance. We assume that there is a $p\in(1,2)$ so that the functions have finite $L_p$-norm. For uniformly ergodic Markov chains we obtain error bounds with the optimal order of convergence $n^{1/p-1}$ and if there exists a spectral gap we almost get the optimal order. Further, a burn-in period is taken into account and a recipe for choosing the burn-in is provided.

Christian Bender, Christian Gaertner, Nikolaus Schweizer

We introduce a novel numerical approach for a class of stochastic dynamic programs which arise as discretizations of backward stochastic differential equations or semi-linear partial differential equations. Solving such dynamic programs numerically requires the approximation of nested conditional expectations, i.e., iterated integrals of previous approximations. Our approach allows us to compute and iteratively improve upper and lower bounds on the true solution starting from an arbitrary and possibly crude input approximation. We demonstrate the benefits of our approach in a high dimensional financial application.