Perturbation theory for Markov chains via Wasserstein distance

Daniel Rudolf, Nikolaus Schweizer

Research output: Contribution to journalArticleScientificpeer-review

Abstract

Perturbation theory for Markov chains addresses the question of how small differences in the transition probabilities of Markov chains are reflected in differences between their distributions. We prove powerful and flexible bounds on the distance of the nth 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.
Original languageEnglish
Pages (from-to)2610-2639
JournalBernoulli
Volume24
Issue number4A
DOIs
Publication statusPublished - Nov 2018

Fingerprint

Wasserstein Distance
Perturbation Theory
Markov chain
Metropolis-Hastings
Markov Chain Monte Carlo Algorithms
Markov Chain Monte Carlo Methods
Autoregressive Model
Ergodicity
Transition Probability
Estimate
Lyapunov Function

Keywords

  • perturbations
  • Markov chains
  • Wasserstein distance
  • MCMC
  • big data

Cite this

Rudolf, Daniel ; Schweizer, Nikolaus. / Perturbation theory for Markov chains via Wasserstein distance. In: Bernoulli. 2018 ; Vol. 24, No. 4A. pp. 2610-2639.
@article{31476b5d5dfd42d5bdb0dc43ca67342a,
title = "Perturbation theory for Markov chains via Wasserstein distance",
abstract = "Perturbation theory for Markov chains addresses the question of how small differences in the transition probabilities of Markov chains are reflected in differences between their distributions. We prove powerful and flexible bounds on the distance of the nth 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.",
keywords = "perturbations, Markov chains, Wasserstein distance, MCMC, big data",
author = "Daniel Rudolf and Nikolaus Schweizer",
year = "2018",
month = "11",
doi = "10.3150/17-BEJ938",
language = "English",
volume = "24",
pages = "2610--2639",
journal = "Bernoulli",
issn = "1350-7265",
publisher = "International Statistical Institute",
number = "4A",

}

Perturbation theory for Markov chains via Wasserstein distance. / Rudolf, Daniel; Schweizer, Nikolaus.

In: Bernoulli, Vol. 24, No. 4A, 11.2018, p. 2610-2639.

Research output: Contribution to journalArticleScientificpeer-review

TY - JOUR

T1 - Perturbation theory for Markov chains via Wasserstein distance

AU - Rudolf, Daniel

AU - Schweizer, Nikolaus

PY - 2018/11

Y1 - 2018/11

N2 - Perturbation theory for Markov chains addresses the question of how small differences in the transition probabilities of Markov chains are reflected in differences between their distributions. We prove powerful and flexible bounds on the distance of the nth 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.

AB - Perturbation theory for Markov chains addresses the question of how small differences in the transition probabilities of Markov chains are reflected in differences between their distributions. We prove powerful and flexible bounds on the distance of the nth 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.

KW - perturbations

KW - Markov chains

KW - Wasserstein distance

KW - MCMC

KW - big data

U2 - 10.3150/17-BEJ938

DO - 10.3150/17-BEJ938

M3 - Article

VL - 24

SP - 2610

EP - 2639

JO - Bernoulli

JF - Bernoulli

SN - 1350-7265

IS - 4A

ER -