Convergence analysis of some multivariate Markov chains using stochastic monotonicity
type: Item
instance of: scholarly article
title: Convergence analysis of some multivariate Markov chains using stochastic monotonicity
zbMATH Open document ID: 1277.60117
DOI: 10.1214/12-AAP856
author: Kshitij Khare
author: Nabanita Mukherjee
published in: The Annals of Applied Probability
publication date: 2013-04-24T00:00:00Z
full work available at URL: https://arxiv.org/abs/1302.5606
full work available at URL: https://projecteuclid.org/euclid.aoap/1360682030
review text: Consider a discrete-time Markov chain with a finite state space, transition probability density \(K(x,x')\) and stationary distribution \(\pi(x)\). Let \[ \|K_x^n-\pi\|_{TV}=0.5 \sum_{x' \in X} |K^n(x,x')-\pi(x')| \] denote the total variation distance between the density of the chain after \(n\) steps and the stationary density. The authors provide a nonasymptotic analysis of convergence to stationarity for a collection of Markov chains thereby generalizing results in [\textit{K. Khare} and \textit{H. Zhou}, Ann. Appl. Probab. 19, No. 2, 737--777 (2009; Zbl 1171.60016)]. This allows essentially to improve crude upper bounds of convergence. For example, the obtained estimate for sequential Pólya urn model is the following \[ 0.375 (1-1/111)^n \leq \|K_x^n-\pi\|_{TV}\leq 100 (1-1/111)^n, \] while the crude upper bound is \(\|K_x^n-\pi\|_{TV} \leq 2.2186\times 10^{19} (1-1/111)^n\). Examples include the multi-allele Moran model in population genetics and its variants in community ecology, a generalized Ehrenfest urn model and variants of the Pólya urn model. It is shown that all these Markov chains are stochastically monotone with respect to an appropriate partial ordering. This allows to obtain explicit nonasymptotic bounds for distance to stationarity from arbitrary starting points. Note that, in previous works, bounds, if any, were available only from special starting points. The analysis also works for nonreversible Markov chains.
reviewed by: Alex V. Kolnogorov
Mathematics Subject Classification ID: 60J10
Mathematics Subject Classification ID: 60J22
Mathematics Subject Classification ID: 47H05
zbMATH DE Number: 6157204
zbMATH Keywords: convergence analysis
zbMATH Keywords: Markov chains
zbMATH Keywords: stochastic monotonicity
zbMATH Keywords: partial ordering
MaRDI profile type: Publication
arXiv ID: 1302.5606
cites work: On the convergence of the Markov chain simulation method
cites work: One-shot CFTP; application to a class of truncated Gaussian densities
cites work: Gibbs sampling, conjugate priors and coupling
cites work: Convergence to stationarity in the Moran model
cites work: Mathematical population genetics. I: Theoretical introduction.
cites work: Stochastic monotonicity and realizable monotonicity
cites work: Stochastic inequalities on partially ordered spaces
cites work: Rates of convergence of some multivariate Markov chains with polynomial eigenfunctions
cites work: Geometric Convergence Rates for Stochastically Ordered Markov Chains
cites work: Q3266127
cites work: How to Get a Perfectly Random Sample from a Generic Markov Chain and Generate a Random Spanning Tree of a Directed Graph
cites work: Convergence of Slice Sampler Markov Chains
cites work: Q3321201
cites work: Convergence time to the Ewens sampling formula in the infinite alleles Moran model
cites work: Mixing times of lozenge tiling and card shuffling Markov chains
OpenAlex ID: W1985778783
Recommended article: Rates of convergence of some multivariate Markov chains with polynomial eigenfunctions
Recommended article: Q3788832
Recommended article: Convergence to stationarity in the Moran model
Recommended article: Convergence of independent particle systems
Recommended article: Some things we've learned (about Markov chain Monte Carlo)
Recommended article: A local limit theorem for a family of non-reversible Markov chains
Recommended article: Stability and exponential convergence of continuous-time Markov chains
description: scientific article