Skip-free Markov chains
HTML articles powered by AMS MathViewer
- by Michael C. H. Choi and Pierre Patie PDF
- Trans. Amer. Math. Soc. 371 (2019), 7301-7342 Request permission
Abstract:
The aim of this paper is to develop a general theory for the class of skip-free Markov chains on denumerable state space. This encompasses their potential theory via an explicit characterization of their potential kernel expressed in terms of the family of fundamental excessive functions, which are defined by means of the theory of the Martin boundary. We also describe their fluctuation theory generalizing the celebrated fluctuations identities that were obtained by using the Wiener–Hopf factorization for the specific skip-free random walks. We proceed by resorting to the concept of similarity to identify the class of skip-free Markov chains whose transition operator has only real and simple eigenvalues. We manage to find a set of sufficient and easy-to-check conditions on the one-step transition probability for a Markov chain to belong to this class. We also study several properties of this class including their spectral expansions given in terms of a Riesz basis, derive a necessary and sufficient condition for this class to exhibit a separation cutoff, and give a tighter bound on its convergence rate to stationarity than existing results.References
- J. Abate and W. Whitt, Spectral theory for skip-free Markov chains, Probab. Eng. Informational Sci. 3 (1989) no. 1, 77–88.
- A. Adikahri, Skip free processes, 1986. Thesis (Ph.D.)–University of California, Berkeley.
- David Aldous and Persi Diaconis, Shuffling cards and stopping times, Amer. Math. Monthly 93 (1986), no. 5, 333–348. MR 841111, DOI 10.2307/2323590
- William J. Anderson, Continuous-time Markov chains, Springer Series in Statistics: Probability and its Applications, Springer-Verlag, New York, 1991. An applications-oriented approach. MR 1118840, DOI 10.1007/978-1-4612-3038-0
- Søren Asmussen, Applied probability and queues, 2nd ed., Applications of Mathematics (New York), vol. 51, Springer-Verlag, New York, 2003. Stochastic Modelling and Applied Probability. MR 1978607
- F. Avram, P. Patie, and J. Wang, Purely excessive functions and hitting times of continuous-time branching processes, J. Methodol. Comput. Appl. Probab. (2018) https://doi.org/10.1007/s11009-018-9616-5.
- P. J. Brockwell, J. Gani, and S. I. Resnick, Birth, immigration and catastrophe processes, Adv. in Appl. Probab. 14 (1982), no. 4, 709–731. MR 677553, DOI 10.2307/1427020
- Guan-Yu Chen and Laurent Saloff-Coste, The cutoff phenomenon for ergodic Markov processes, Electron. J. Probab. 13 (2008), no. 3, 26–78. MR 2375599, DOI 10.1214/EJP.v13-474
- Guan-Yu Chen and Laurent Saloff-Coste, Computing cutoff times of birth and death chains, Electron. J. Probab. 20 (2015), no. 76, 47. MR 3371435, DOI 10.1214/EJP.v20-4077
- Michael Chek Hin Choi, Analysis of Non-Reversible Markov Chains, ProQuest LLC, Ann Arbor, MI, 2017. Thesis (Ph.D.)–Cornell University. MR 3755018
- Kai Lai Chung and John B. Walsh, Markov processes, Brownian motion, and time symmetry, 2nd ed., Grundlehren der mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences], vol. 249, Springer, New York, 2005. MR 2152573, DOI 10.1007/0-387-28696-9
- John B. Conway, A course in functional analysis, 2nd ed., Graduate Texts in Mathematics, vol. 96, Springer-Verlag, New York, 1990. MR 1070713
- Persi Diaconis and James Allen Fill, Strong stationary times via a new form of duality, Ann. Probab. 18 (1990), no. 4, 1483–1522. MR 1071805
- Persi Diaconis and Laurent Saloff-Coste, Separation cut-offs for birth and death chains, Ann. Appl. Probab. 16 (2006), no. 4, 2098–2122. MR 2288715, DOI 10.1214/105051606000000501
- Jian Ding, Eyal Lubetzky, and Yuval Peres, Total variation cutoff in birth-and-death chains, Probab. Theory Related Fields 146 (2010), no. 1-2, 61–85. MR 2550359, DOI 10.1007/s00440-008-0185-3
- H. Dym and H. P. McKean, Gaussian processes, function theory, and the inverse spectral problem, Probability and Mathematical Statistics, Vol. 31, Academic Press [Harcourt Brace Jovanovich, Publishers], New York-London, 1976. MR 0448523
- E. B. Dynkin, The boundary theory of Markov processes (discrete case), Uspehi Mat. Nauk 24 (1969), no. 2 (146), 3–42 (Russian). MR 0245096
- William Feller, Diffusion processes in one dimension, Trans. Amer. Math. Soc. 77 (1954), 1–31. MR 63607, DOI 10.1090/S0002-9947-1954-0063607-6
- William Feller, Infinitely divisible distributions and Bessel functions associated with random walks, SIAM J. Appl. Math. 14 (1966), 864–875. MR 207060, DOI 10.1137/0114071
- William Feller, An Introduction to Probability Theory and Its Applications. Vol. I, John Wiley & Sons, Inc., New York, N.Y., 1950. MR 0038583
- James Allen Fill, Eigenvalue bounds on convergence to stationarity for nonreversible Markov chains, with an application to the exclusion process, Ann. Appl. Probab. 1 (1991), no. 1, 62–87. MR 1097464
- James Allen Fill, On hitting times and fastest strong stationary times for skip-free and more general chains, J. Theoret. Probab. 22 (2009), no. 3, 587–600. MR 2530104, DOI 10.1007/s10959-009-0233-7
- M. L. Gorbachuk and V. I. Gorbachuk, M. G. Krein’s lectures on entire operators, Operator Theory: Advances and Applications, vol. 97, Birkhäuser Verlag, Basel, 1997. MR 1466698, DOI 10.1007/978-3-0348-8902-5
- Priscilla Greenwood and Jim Pitman, Fluctuation identities for Lévy processes and splitting at the maximum, Adv. in Appl. Probab. 12 (1980), no. 4, 893–902. MR 588409, DOI 10.2307/1426747
- Roger A. Horn and Charles R. Johnson, Matrix analysis, 2nd ed., Cambridge University Press, Cambridge, 2013. MR 2978290
- S. Karlin and J. L. McGregor, The differential equations of birth-and-death processes, and the Stieltjes moment problem, Trans. Amer. Math. Soc. 85 (1957), 489–546. MR 91566, DOI 10.1090/S0002-9947-1957-0091566-1
- Julian Keilson, Log-concavity and log-convexity in passage time densities of diffusion and birth-death processes, J. Appl. Probability 8 (1971), 391–398. MR 290461, DOI 10.2307/3211909
- John G. Kemeny, J. Laurie Snell, and Anthony W. Knapp, Denumerable Markov chains, 2nd ed., Graduate Texts in Mathematics, No. 40, Springer-Verlag, New York-Heidelberg-Berlin, 1976. With a chapter on Markov random fields, by David Griffeath. MR 0407981
- John T. Kent and Nicholas T. Longford, An eigenvalue decomposition for first hitting times in random walks, Z. Wahrsch. Verw. Gebiete 63 (1983), no. 1, 71–84. MR 699787, DOI 10.1007/BF00534178
- W. Ledermann and G. E. H. Reuter, Spectral theory for the differential equations of simple birth and death processes, Philos. Trans. Roy. Soc. London Ser. A 246 (1954), 321–369. MR 60103, DOI 10.1098/rsta.1954.0001
- C. Lefèvre, P. Patie, and S. Vakeroudis, Fluctuation theory of one-sided Ornstein-Uhlenbeck type processes, working paper, 2016.
- David A. Levin, Yuval Peres, and Elizabeth L. Wilmer, Markov chains and mixing times, American Mathematical Society, Providence, RI, 2009. With a chapter by James G. Propp and David B. Wilson. MR 2466937, DOI 10.1090/mbk/058
- Y. H. Mao, C. Zhang, and Y. H. Zhang, Separation cutoff for upward skip-free chains, J. Appl. Probab. 53 (2016), no. 1, 299–306. MR 3540798, DOI 10.1017/jpr.2015.26
- Laurent Miclo, On absorption times and Dirichlet eigenvalues, ESAIM Probab. Stat. 14 (2010), 117–150. MR 2654550, DOI 10.1051/ps:2008037
- L. Miclo, On the Markovian similarity, preprint, 2016.
- L. Miclo and P. Patie, On a gateway between continuous and discrete Bessel and Laguerre processes, Ann. Henri Lebesgue (to appear).
- P. Patie and M. Savov, Spectral expansion of non-self-adjoint generalized Laguerre semigroups, Mem. Amer. Math. Soc. (to appear).
- P. Patie and C. Van Weverberg, Exit times of continuous state branching processes with immigration, working paper, 2016.
- P. Patie and V. Vigon, On completely assymetric Markov processes, working paper, 2016.
- P. Patie and J. Wang, Potential and fluctuation theory of Galton-Watson process with immigration, working paper, 2018.
- Michael Reed and Barry Simon, Methods of modern mathematical physics. I, 2nd ed., Academic Press, Inc. [Harcourt Brace Jovanovich, Publishers], New York, 1980. Functional analysis. MR 751959
- G. E. H. Reuter, Denumerable Markov processes. II, J. London Math. Soc. 34 (1959), 81–91. MR 102124, DOI 10.1112/jlms/s1-34.1.81
- Gareth O. Roberts and Jeffrey S. Rosenthal, Geometric ergodicity and hybrid Markov chains, Electron. Comm. Probab. 2 (1997), no. 2, 13–25. MR 1448322, DOI 10.1214/ECP.v2-981
- Laurent Saloff-Coste, Lectures on finite Markov chains, Lectures on probability theory and statistics (Saint-Flour, 1996) Lecture Notes in Math., vol. 1665, Springer, Berlin, 1997, pp. 301–413. MR 1490046, DOI 10.1007/BFb0092621
- D. Siegmund, The equivalence of absorbing and reflecting barrier problems for stochastically monotone Markov processes, Ann. Probability 4 (1976), no. 6, 914–924. MR 431386, DOI 10.1214/aop/1176995936
- Frank Spitzer, A combinatorial lemma and its application to probability theory, Trans. Amer. Math. Soc. 82 (1956), 323–339. MR 79851, DOI 10.1090/S0002-9947-1956-0079851-X
- Fred W. Steutel and Klaas van Harn, Infinite divisibility of probability distributions on the real line, Monographs and Textbooks in Pure and Applied Mathematics, vol. 259, Marcel Dekker, Inc., New York, 2004. MR 2011862
- R. C. Thompson, Singular values, diagonal elements, and convexity, SIAM J. Appl. Math. 32 (1977), no. 1, 39–63. MR 424847, DOI 10.1137/0132003
- Hermann Thorisson, Coupling, stationarity, and regeneration, Probability and its Applications (New York), Springer-Verlag, New York, 2000. MR 1741181, DOI 10.1007/978-1-4612-1236-2
- Cédric Villani, Hypocoercivity, Mem. Amer. Math. Soc. 202 (2009), no. 950, iv+141. MR 2562709, DOI 10.1090/S0065-9266-09-00567-5
- O. V. Viskov, A random walk with an upper-continuous component, and the Lagrange inversion formula, Teor. Veroyatnost. i Primenen. 45 (2000), no. 1, 166–175 (Russian, with Russian summary); English transl., Theory Probab. Appl. 45 (2001), no. 1, 164–172. MR 1810980, DOI 10.1137/S0040585X97978105
- Wolfgang Woess, Denumerable Markov chains, EMS Textbooks in Mathematics, European Mathematical Society (EMS), Zürich, 2009. Generating functions, boundary theory, random walks on trees. MR 2548569, DOI 10.4171/071
- Robert M. Young, An introduction to nonharmonic Fourier series, 1st ed., Academic Press, Inc., San Diego, CA, 2001. MR 1836633
Additional Information
- Michael C. H. Choi
- Affiliation: Institute for Data and Decision Analytics, The Chinese University of Hong Kong, Shenzhen, Guangdong 518172, People’s Republic of China
- MR Author ID: 1090620
- ORCID: 0000-0003-0309-3217
- Email: michaelchoi@cuhk.edu.cn
- Pierre Patie
- Affiliation: School of Operations Research and Information Engineering, Cornell University, Ithaca, New York 14853
- MR Author ID: 702262
- Email: pp396@cornell.edu
- Received by editor(s): January 17, 2017
- Received by editor(s) in revised form: March 8, 2018
- Published electronically: January 24, 2019
- Additional Notes: The second author is grateful for the hospitality of the LMA at the UPPA, where part of this work was completed.
This work was partially supported by NSF Grant DMS-1406599 and by ARC IAPAS, a fund of the Communautée francaise de Belgique. - © Copyright 2019 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 371 (2019), 7301-7342
- MSC (2010): Primary 60J10, 60J45, 60J50
- DOI: https://doi.org/10.1090/tran/7773
- MathSciNet review: 3939579