Convergence analysis of some multivariate Markov chains using stochastic monotonicity. (English) Zbl 1277.60117

Khare, Kshitij; Mukherjee, Nabanita

Ann. Appl. Probab. 23, No. 2, 811-833 (2013).

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 [K. Khare and 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.

Reviewer: Alex V. Kolnogorov (Novgorod)

MSC:

60J10	Markov chains (discrete-time Markov processes on discrete state spaces)
60J22	Computational methods in Markov chains
47H05	Monotone operators and generalizations

Keywords:

convergence analysis; Markov chains; stochastic monotonicity; partial ordering

Citations:

Zbl 1171.60016

References:

[1]	Athreya, K. B., Doss, H. and Sethuraman, J. (1996). On the convergence of the Markov chain simulation method. Ann. Statist. 24 69-100. · Zbl 0860.60057
[2]	Beskos, A. and Roberts, G. O. (2005). One-shop CFTP; application to a class of truncated Gaussian densities. Methodol. Comput. Appl. Probab. 7 407-437. · Zbl 1103.65013
[3]	Diaconis, P., Khare, K. and Saloff-Coste, L. (2010). Gibbs sampling, conjugate priors and coupling. Sankhya A 72 136-169. · Zbl 1209.60042
[4]	Donnelly, P. and Rodrigues, E. R. (2000). Convergence to stationarity in the Moran model. J. Appl. Probab. 37 705-717. · Zbl 0968.60079
[5]	Ewens, W. J. (2004). Mathematical Population Genetics. I : Theoretical Introduction , 2nd ed. Interdisciplinary Applied Mathematics 27 . Springer, New York. · Zbl 1060.92046
[6]	Fill, J. A. and Machida, M. (2001). Stochastic monotonicity and realizable monotonicity. Ann. Probab. 29 938-978. · Zbl 1015.60010
[7]	Hubbell, S. P. (2001). The Unified Neutral Theory of Biodiversity and Biogeography. Monographs in Population Biology 32 . Princeton Univ. Press, Princeton, NJ.
[8]	Kamae, T., Krengel, U. and O’Brien, G. L. (1977). Stochastic inequalities on partially ordered spaces. Ann. Probab. 5 899-912. · Zbl 0371.60013
[9]	Khare, K. and Zhou, H. (2009). Rates of convergence of some multivariate Markov chains with polynomial eigenfunctions. Ann. Appl. Probab. 19 737-777. · Zbl 1171.60016
[10]	Lund, R. B. and Tweedie, R. L. (1996). Geometric convergence rates for stochastically ordered Markov chains. Math. Oper. Res. 21 182-194. · Zbl 0847.60053
[11]	McGill, B. J. (2003). A test of the unified neutral theory of biodiversity. Nature 422 881-885.
[12]	Moran, P. A. P. (1958). Random processes in genetics. Proc. Cambridge Philos. Soc. 54 60-71. · Zbl 0091.15701
[13]	Propp, J. G. and Wilson, D. B. (1998). How to get a perfectly random sample from a generic Markov chain and generate a random spanning tree of a directed graph. J. Algorithms 27 170-217. · Zbl 0919.68092
[14]	Roberts, G. O. and Rosenthal, J. S. (1999). Convergence of slice sampler Markov chains. J. R. Stat. Soc. Ser. B Stat. Methodol. 61 643-660. · Zbl 0929.62098
[15]	Stoyan, D. (1983). Comparison Methods for Queues and Other Stochastic Models . Wiley, Chichester. · Zbl 0536.60085
[16]	Watkins, J. C. (2010). Convergence time to the Ewens sampling formula in the infinite alleles Moran model. J. Math. Biol. 60 189-206. · Zbl 1311.92130
[17]	Wilson, D. B. (2004). Mixing times of lozenge tiling and card shuffling Markov chains. Ann. Appl. Probab. 14 274-325. · Zbl 1040.60063