Maximal coupling procedure and stability of discrete Markov chains. I

Kartashov, M.; Golomozyĭ, V.

doi:10.1090/S0094-9000-2013-00891-6

Maximal coupling procedure and stability of discrete Markov chains. I

Authors: M. V. Kartashov and V. V. Golomozyĭ
Translated by: N. Semenov
Journal: Theor. Probability and Math. Statist. 86 (2013), 93-104
MSC (2010): Primary 60J45; Secondary 60A05, 60K05
DOI: https://doi.org/10.1090/S0094-9000-2013-00891-6
Published electronically: August 20, 2013
MathSciNet review: 2986452
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

Abstract: Two discrete Markov chains whose one-step transition probabilities are close to each other in the uniform total variation norm or in the $V$-norm are considered. The problem of stability of the transition probabilities for an arbitrary number of steps is investigated. The main assumption is either the uniform mixing or $V$-mixing condition. In particular, we prove that the uniform distance between the distributions of the chains after an arbitrary number of steps does not exceed $\varepsilon /(1-\rho )$, where $\varepsilon$ is the uniform distance between the transition matrices and where $\rho$ is the uniform mixing coefficient. A number of general examples are considered. The proofs are based on the maximal coupling procedure that maximizes the one-step coupling probabilities.

References

W. Doeblin, Exposé de la théorie des chaînes simples constantes de Markov à un nombre fini d’états, Mathematique de l’Union Interbalkanique 2 (1938), 77–105.

Randal Douc, Gersende Fort, and Arnaud Guillin, Subgeometric rates of convergence of $f$-ergodic strong Markov processes, Stochastic Process. Appl. 119 (2009), no. 3, 897–923. MR 2499863, DOI https://doi.org/10.1016/j.spa.2008.03.007

R. Douc, E. Moulines, and Jeffrey S. Rosenthal, Quantitative bounds on convergence of time-inhomogeneous Markov chains, Ann. Appl. Probab. 14 (2004), no. 4, 1643–1665. MR 2099647, DOI https://doi.org/10.1214/105051604000000620

Randal Douc, Gersende Fort, Eric Moulines, and Philippe Soulier, Practical drift conditions for subgeometric rates of convergence, Ann. Appl. Probab. 14 (2004), no. 3, 1353–1377. MR 2071426, DOI https://doi.org/10.1214/105051604000000323

Randal Douc, Eric Moulines, and Philippe Soulier, Computable convergence rates for sub-geometric ergodic Markov chains, Bernoulli 13 (2007), no. 3, 831–848. MR 2348753, DOI https://doi.org/10.3150/07-BEJ5162

William Feller, An introduction to probability theory and its applications. Vol. II, John Wiley & Sons, Inc., New York-London-Sydney, 1966. MR 0210154

V. V. Golomozyĭ, Stability of non-homogeneous Markov chains, Visnyk Kyiv Univ., Ser. Fiz. Mat. Nauk 4 (2009), 10–15. (Ukrainian)

V. V. Golomoziĭ, A subgeometric estimate for the stability of time-homogeneous Markov chains, Teor. Ĭmovīr. Mat. Stat. 81 (2009), 31–45 (Ukrainian, with English, Russian and Ukrainian summaries); English transl., Theory Probab. Math. Statist. 81 (2010), 35–50. MR 2667308, DOI https://doi.org/10.1090/S0094-9000-2010-00808-8

Søren F. Jarner and Gareth O. Roberts, Polynomial convergence rates of Markov chains, Ann. Appl. Probab. 12 (2002), no. 1, 224–247. MR 1890063, DOI https://doi.org/10.1214/aoap/1015961162

N. V. Kartashov, Strong stable Markov chains, VSP, Utrecht; TBiMC Scientific Publishers, Kiev, 1996. MR 1451375

N. V. Kartashov, Exponential asymptotics of matrices of the Markov renewal, Asymptotic Problems for Stochastic Processes, Preprint 77-24, Institute of Mathematics of Academy of Science off Ukraine, Kiev, 1977, 2–43. (Russian)

M. V. Kartashov, Boundedness, limits, and stability of solutions of an inhomogeneous perturbation of a renewal equation on a half-line, Teor. Ĭmovīr. Mat. Stat. 81 (2009), 65–75 (Ukrainian, with English and Ukrainian summaries); English transl., Theory Probab. Math. Statist. 81 (2010), 71–83. MR 2667311, DOI https://doi.org/10.1090/S0094-9000-2010-00811-8

M. V. Kartashov and V. V. Golomoziĭ, The mean coupling time of independent discrete renewal processes, Teor. Ĭmovīr. Mat. Stat. 84 (2011), 77–83 (Ukrainian, with English, Russian and Ukrainian summaries); English transl., Theory Probab. Math. Statist. 84 (2012), 79–86. MR 2857418, DOI https://doi.org/10.1090/S0094-9000-2012-00855-7

I. N. Kovalenko and N. Ju. Kuznecov, Postroenie vlozhennogo protsessa vosstanovleniya dlya sushchestvenno mnogomernykh protsessov teorii massovogo obsluzhivaniya i ego primenenie k polucheniyu predel′nykh teorem, Preprint 80 [Preprint 80], vol. 12, Akad. Nauk Ukrain. SSR, Inst. Kibernet., Kiev, 1980 (Russian). MR 612478

Torgny Lindvall, On coupling of discrete renewal processes, Z. Wahrsch. Verw. Gebiete 48 (1979), no. 1, 57–70. MR 533006, DOI https://doi.org/10.1007/BF00534882

Torgny Lindvall, Lectures on the coupling method, Wiley Series in Probability and Mathematical Statistics: Probability and Mathematical Statistics, John Wiley & Sons, Inc., New York, 1992. A Wiley-Interscience Publication. MR 1180522

S. P. Meyn and R. L. Tweedie, Markov chains and stochastic stability, Communications and Control Engineering Series, Springer-Verlag London, Ltd., London, 1993. MR 1287609

Peter Ney, A refinement of the coupling method in renewal theory, Stochastic Process. Appl. 11 (1981), no. 1, 11–26. MR 608004, DOI https://doi.org/10.1016/0304-4149%2881%2990018-1

E. Nummelin, A splitting technique for Harris recurrent Markov chains, Z. Wahrsch. Verw. Gebiete 43 (1978), no. 4, 309–318. MR 0501353, DOI https://doi.org/10.1007/BF00534764

Esa Nummelin, General irreducible Markov chains and nonnegative operators, Cambridge Tracts in Mathematics, vol. 83, Cambridge University Press, Cambridge, 1984. MR 776608

Esa Nummelin and Pekka Tuominen, Geometric ergodicity of Harris recurrent Markov chains with applications to renewal theory, Stochastic Process. Appl. 12 (1982), no. 2, 187–202. MR 651903, DOI https://doi.org/10.1016/0304-4149%2882%2990041-2

E. Nummelin and R. L. Tweedie, Geometric ergodicity and $R$-positivity for general Markov chains, Ann. Probability 6 (1978), no. 3, 404–420. MR 474504, DOI https://doi.org/10.1214/aop/1176995527

S. T. Rachev, The Monge-Kantorovich problem on mass transfer and its applications in stochastics, Teor. Veroyatnost. i Primenen. 29 (1984), no. 4, 625–653 (Russian). MR 773434

Hermann Thorisson, Coupling, stationarity, and regeneration, Probability and its Applications (New York), Springer-Verlag, New York, 2000. MR 1741181

Pekka Tuominen and Richard L. Tweedie, Subgeometric rates of convergence of $f$-ergodic Markov chains, Adv. in Appl. Probab. 26 (1994), no. 3, 775–798. MR 1285459, DOI https://doi.org/10.2307/1427820

J. N. Corcoran and R. L. Tweedie, Perfect sampling of ergodic Harris chains, Ann. Appl. Probab. 11 (2001), no. 2, 438–451. MR 1843053, DOI https://doi.org/10.1214/aoap/1015345299

V. M. Zolotarev, Modern Theory of Summation of Independent Random Variables, “Nauka”, Moscow, 1986; English transl., VSP, Utrecht, the Netherlands, Tokyo, Japan, 1997.