Theory of Probability and Mathematical Statistics
Maximal coupling and stability of discrete non-homogeneous Markov chains
V. V. Golomozyĭ, M. V. Kartashov
Download PDF
Abstract: We consider two time non-homogeneous discrete Markov chains whose one-step transition probabilities are close in the uniform total variation norm. The problem of stability of the transition probabilities for an arbitrary number of steps is investigated. The main assumption is the uniform mixing. We prove that the uniform difference between the distributions of the chains after an arbitrary number of steps does not exceed ε/(1-ρ), where ε is the uniform distance between transition matrices and ρ is the uniform mixing coefficient. The proofs are based on the maximal coupling procedure that maximize the one-step coupling probabilities.
Keywords: Coupling theory, coupling method, maximal coupling, discrete Markov chains, stability of distributions.
Bibliography: 1. W. Doeblin. Expose de la theorie des chaines simples constantes de Markov a un nomber fini d'estats, Mathematique de l'Union Interbalkanique 2 (1938), 77-105.
2. W. Feller, An Introduction to Probability Theory and its Applications, vol. 1, John Wiley & Sons, New York, 1966.
3. N. V. Kartashov, Strong Stable Markov Chains, VSP/TViMS, Utrecht/Kiev, The Netherlands/Ukraine, 1996.
4. 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 of Ukraine, Kiev, 1977, pp. 2-43. (Russian)
5. E. Nummelin, A splitting technique for Harris recurrent chains, Z. Wahrscheinlichkeitstheorie verw. Gebiete 43 (1978), 309-318.
6. E. Nummelin and R. L. Tweedie, Geometric ergodicity and R-positivity for general Markov chains, Ann. Probab. 6 (1978), 404-420.
7. T. Lindvall, On coupling of discrete renewal sequences, Z. Wahrscheinlichkeitstheorie verw. Gebiete 48 (1979), 57-70.
8. I. N. Kovalenko and N. Ju. Kuznecov, Construction of the embedded renewal process for essentially multidimensional processes in the queueing theory and its application to deriving of limit theorems, Preprint 80, vol. 12, no. 80-12, Akad. Nauk Ukrain. SSR, Inst. Kibernet., Kiev, 1980 (Russian).
9. P. Ney, A refinement of the coupling method in renewal theory, Stoch. Process. Appl. 11 (1981), 11-26.
10. E. Numemelin and P. Tuominen, Geometric ergodicity of Harris recurrent Markov chains with applications to renewal theory, Stoch. Process. Appl. 12 (1982), 187-202.
11. E. Nummelin, General Irreducible Markov Chains and Nonnegative Operators, Cambridge University Press, Cambridge, 1984.
12. T. Lindvall, Lectures on the Coupling Method, John Wiley and Sons, 1991.
13. S. P. Meyn and R. L. Tweedie, Markov chains and Stochastic Stability, Springer-Verlag, London, 1993.
14. P. Tuominen and R. Tweedie, Subgeometric rates of convergence of f-ergodic Markov chains, Adv. Appl. Probab. 26 (1994), 775-798.
15. P. Tuominen and R. L. Tweedie, Subgeometric rates of convergence of f-ergodic Markov chains, Adv. Appl. Probab. 26 (1994), 775-798.
16. R. L. Tweedie and J. N. Corcoran, Perfect sampling of ergodic Harris chains, Ann. Appl. Probab. 11 (2001), no. 2, 438-451.
17. H. Thorisson, Coupling, Stationarity, and Regeneration, Springer, New York, 2000.
18. S. F. Jarner and G. O. Roberts, Polynomial convergence rates of Markov chains, Ann. Appl. Probab. 12 (2001), 224-247.
19. R. Douc, E. Moulines, and J. S. Rosenthal, Quantitative bounds for geometric convergence rates of Markov chains, Ann. Appl. Probab. 14 (2004), 1643-1664.
20. R. Douc, E. Moulines, and J. S. Rothenthal, Quantitative bounds on convergence of time-inhomogeneous Markov chains, Ann. Appl. Probab. 14 (2004), no. 4, 1643-1665.
21. R. Douc, E. Moulines, and P. Soulier, Practical drift conditions for subgeometric rates of convergence, Ann. Appl. Probab. 14 (2004), no. 4, 1353-1377.
22. R. Douc, E. Moulines, and P. Soulier, Computable convergence rates for subgeometrically ergodic Markov chains, Bernoulli 13 (2007), no. 3, 831-848.
23. R. Douc, G. Fort, and A. Guillin, Subgeometric rates of convergence of f-ergodic strong Markov processes, Stoch. Process. Appl. 119 (2009), no. 3, 897-923.
24. V. V. Golomozyĭ, Stability of non-homogeneous Markov chains, Visnyk Kyiv Univ., Ser. Fiz. Mat. Nauk 4 (2009), 10-15. (Ukrainian)
25. V. V. Golomozyĭ, A subgeometric estimate of the stability for time-homogeneous Markov chains, Teor. Imovir. Matem. Statist. 81 (2010), 31-46; English transl. in Theor. Probability and Math. Statist. 81 (2010), 35-50.
26. M. V. Kartashov, Boundedness, limits, and stability of solutions of a perturbation of a nonhomogeneous renewal equation on a semiaxis, Teor. Imovir. Matem. Statist. 81 (2009), 65-75; English transl. in Theor. Probability and Math. Statist. 81 (2010), 71-83.
27. M. V. Kartashov and V. V. Golomozyĭ, The mean coupling time for independent discrete renewal processes, Teor. Imovir. Matem. Statist. 84 (2011), 78-85; English transl. in Theor. Probability and Math. Statist. 84 (2012), 79-86.
28. M. V. Kartashov and V. V. Golomozyĭ, Maximal coupling procedure and stability of discrete Markov chains. I, Teor. Imovir. Matem. Statist. 86 (2012), 81-92; English transl. in Theor. Probability and Math. Statist. 86 (2013), 93-104.
29. M. V. Kartashov and V. V. Golomozyĭ, Maximal coupling procedure and stability of discrete Markov chains. II, Teor. Imovir. Matem. Statist. 87 (2012), 58-70; English transl. in Theor. Probability and Math. Statist. 87 (2013), 65-78.
30. M. V. Kartashov and V. V. Golomozyĭ, On coupling moment integrability for time-inhomogeneous Markov chains, Teor. Imovir. Matem. Statist. 89 (2014), 1-12; English transl. in Theor. Probability and Math. Statist. 89 (2014), 1-12.
31. V. V. Golomozyĭ, An inequality for the coupling moment in the case of two inhomogeneous Markov chains, Teor. Imovir. Matem. Statist. 90 (2014), 39-51; English transl. in Theor. Probability and Math. Statist. 90 (2015), 43-56.
