Convergence analysis of some multivariate Markov chains using stochastic monotonicity
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.
scientific article