Skip-free Markov chains

Choi, Michael; Patie, Pierre

doi:10.1090/tran/7773

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