Qu, Y., Blanchet, J., & Glynn, P. (2023). Computable Bounds on Convergence of Markov Chains in Wasserstein Distance. ArXiv. /abs/2308.10341

View Publication

Abstract

We introduce a unified framework to estimate the convergence of Markov chains to equilibrium using Wasserstein distance. The framework provides convergence bounds with various rates, ranging from polynomial to exponential, all derived from a single contractive drift condition. This approach removes the need for finding a specific set with drift outside and contraction inside. The convergence bounds are explicit, as they can be estimated based on one-step expectations and do not rely on equilibrium-related quantities. To enhance the applicability of the framework, we introduce the large M technique and the boundary removal technique. We illustrate these methods in queueing models and algorithms in stochastic optimization.

Authors
Yanlin Qu, Jose Blanchet, Peter Glynn
Publication date
2023/8/20
Journal
arXiv preprint arXiv:2308.10341