Hostname: page-component-586b7cd67f-dlnhk Total loading time: 0 Render date: 2024-11-23T01:21:33.840Z Has data issue: false hasContentIssue false
  • English
  • Français

The formal theory of birth-and-death processes, lattice path combinatorics and continued fractions

Part of: Stochastic processes Combinatorics Markov processes

Published online by Cambridge University Press:  19 February 2016

Philippe Flajolet  and
Fabrice Guillemin
Philippe Flajolet*
Affiliation:
INRIA
Fabrice Guillemin*
Affiliation:
France Telecom
*
∗ Postal address: Algorithms Project, INRIA, F-78150 Rocquencourt, France. Email address: [email protected]
∗∗ Postal address: France Telecom, BD.CNET, DAC/ATM, 2, Avenue Pierre Marzin, 22300 Lannion, France. Email address: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

Classic works of Karlin and McGregor and Jones and Magnus have established a general correspondence between continuous-time birth-and-death processes and continued fractions of the Stieltjes-Jacobi type together with their associated orthogonal polynomials. This fundamental correspondence is revisited here in the light of the basic relation between weighted lattice paths and continued fractions otherwise known from combinatorial theory. Given that sample paths of the embedded Markov chain of a birth-and-death process are lattice paths, Laplace transforms of a number of transient characteristics can be obtained systematically in terms of a fundamental continued fraction and its family of convergent polynomials. Applications include the analysis of evolutions in a strip, upcrossing and downcrossing times under flooring and ceiling conditions, as well as time, area, or number of transitions while a geometric condition is satisfied.

Keywords

Lattice path combinatoricscontinued fractionsorthogonal polynomialsbirth-and-death processfirst passage timeexcursionstransient characteristics

MSC classification

Primary: 60J25: Continuous-time Markov processes on general state spaces 05A15: Exact enumeration problems, generating functions
Secondary: 60G17: Sample path properties
Type
General Applied Probability
Information
Advances in Applied Probability , Volume 32 , Issue 3 , September 2000 , pp. 750 - 778
Copyright
Copyright © Applied Probability Trust 2000 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

[1] Abate, J. and Whitt, W. (1999). Computing Laplace transforms for numerical inversion via continued fractions. INFORMS J. Comput. 11, 394–405.Google Scholar
[2] Abate, J. and Whitt, W. (1998). Laplace transforms of density probability density functions with series representation. AT&T Labs Res. Rept.Google Scholar
[3] Abate, J. and Whitt, W. (1995). Numerical inversion of Laplace transforms of probability distributions. ORSA J. Comput. 7, 36–43.CrossRefGoogle Scholar
[4] Askey, R. and Ismail, M. E. H. (1984). Recurrence Relations, Continued Fractions, and Orthogonal Polynomials. Mem. Amer. Math. Soc. 49, No. 300.Google Scholar
[5] Asmussen, S. (1987). Applied Probability and Queues. John Wiley, New York.Google Scholar
[6] Bharucha-Reid, A. T. (1997). Elements of the Theory of Markov Processes and Their Applications. Dover, Mineola, NY.Google Scholar
[7] Bordes, G. and Roehner, B. (1983). Applications of Stieltjes theory for S-fractions to birth and death processes. Adv. Appl. Prob. 15, 507–530.Google Scholar
[8] Chihara, T. S. (1978). An Introduction to Orthogonal Polynomials. Gordon and Breach, New York.Google Scholar
[9] Cohen, J. W. (1982). The Single Server Queue. North-Holland, Amsterdam.Google Scholar
[10] Erdélyi, A., (1953). Higher Transcendental Functions. McGraw-Hill, New York.Google Scholar
[11] Flajolet, P. (1980). Combinatorial aspects of continued fractions. Discrete Math. 32, 125–161.Google Scholar
[12] Flajolet, P. (1982). On congruences and continued fractions for some classical combinatorial quantities. Discrete Math. 41, 145–153.Google Scholar
[13] Flajolet, P., Françon, J. and Vuillemin, J. (1980). Sequence of operations analysis for dynamic data structures. J. Algorithms 1, 111–141.Google Scholar
[14] Flajolet, P., Puech, C. and Vuillemin, J. (1986). The analysis of simple list structure. Information Sci. 38, 121–146.Google Scholar
[15] Flajolet, P. and Schott, R. (1990). Non-overlapping partitions, continued fractions, Bessel functions and a divergent series. Eur. J. Combin. 11, 421–432.Google Scholar
[16] Godsil, C. D. (1993). Algebraic Combinatorics. Chapman and Hall, New York.Google Scholar
[17] Goulden, I. P. and Jackson, D. M. (1983). Combinatorial Enumeration. John Wiley, New York.Google Scholar
[18] Goulden, I. P. and Jackson, D. M. (1986). Path generating functions and continued fractions. J. Combin. Theory A, 41, 1–10.Google Scholar
[19] Guillemin, F. and Pinchon, D. (1998). Continued fraction analysis of the duration of an excursion in an M/M/∞ system. J. Appl. Prob. 35, 165–183.CrossRefGoogle Scholar
[20] Guillemin, F. and Pinchon, D. (1999). On a random variable associated with excursion in an M/M/∞ system. Queueing Systems.CrossRefGoogle Scholar
[21] Guillemin, F. and Pinchon, D. (1998). On the area swept under the occupation process of an M/M/1 queue in a busy period. Queueing Systems 20, 383–398.CrossRefGoogle Scholar
[22] Guillemin, F. and Pinchon, D. (1999). Excursions of birth and death processes, orthogonal polynomials, and continued fractions. J. Appl. Prob. 36, 752–770.Google Scholar
[23] Good, I. J. (1958). Random motion and analytic continued fractions. Proc. Cambr. Philos. Soc. 54, 43–47.CrossRefGoogle Scholar
[24] Henrici, P. (1977). Applied and Computational Complex Analysis. Vol. 2. John Wiley, New York.Google Scholar
[25] Ismail, M. E. H., Letessier, J., Masson, D. and Valent, G. (1990). Birth and death processes and orthogonal polynomials. In Orthogonal Polynomials, ed. Nevai, P.. Kluwer, Amsterdam, pp. 229–255.CrossRefGoogle Scholar
[26] Ismail, M. E. H., Letessier, D. and Valent, G. (1988). Linear birth and death models and associated Laguerre and Meixner polynomials. J. Approx. Theory 55, 337–348.Google Scholar
[27] Jones, W. B. and Magnus, A. (1977). Application of Stieltjes fractions to birth-death processes. In Padé and Rational Approximation, eds Saff, E. B. and Varga, R. S.. Academic Press, New York, 173–179.Google Scholar
[28] Jones, W. B. and Thron, W. J. (1990). Continued fractions: analytic theory and applications. In Encyclopedia of Mathematics and its Applications. Vol. 11. Addison–Wesley, New York.Google Scholar
[29] Karlin, S. and McGregor, J. L. (1957). The differential equation of birth and death processes, and the Stieltjes moment problem. Trans. Amer. Math. Soc. 85, 489–546.Google Scholar
[30] Karlin, S. and McGregor, J. L. (1957). The classification of birth and death processes. Trans. Amer. Math. Soc. 86, 366–401.Google Scholar
[31] Karlin, S. and McGregor, J. L. (1958). Linear growth birth and death processes. J. Math. Mech. 7, 643–662.Google Scholar
[32] Karlin, S. and McGregor, J. L. (1958). Many server queueing processes with Poisson input and exponential service times. Pacific J. Math. 8, 87–118.Google Scholar
[33] Karlin, S. and McGregor, J. L. (1959). A characterization of birth and death processes. Proc. Nat. Acad. Sci. USA 45, 375–379.Google Scholar
[34] Karlin, S. and Taylor, H. (1975). A First Course in Stochastic Processes. Academic Press, New York.Google Scholar
[35] Kleinrock, L. (1975). Queueing systems, Vol. I: Theory. John Wiley, New York.Google Scholar
[36] Lebedev, N. (1965). Special Functions and their Applications. Prentice Hall, New York.Google Scholar
[37] Murphy, J. A. and O'Donohoe, J. L. (1975). Some properties of continued fractions with applications in Markov processes. J. Inst. Math. Appl. 16, 57–71.Google Scholar
[38] Norris, J. R. (1997). Markov Chains. Cambridge University Press.Google Scholar
[39] Preater, J. (1998). M/M/∞ transience revisited. J. Appl. Prob. 34, 1061–1067.Google Scholar
[40] Sumita, U. (1984). On conditional passage time structure of birth-death processes. J. Appl. Prob. 21, 10–21.Google Scholar
[41] Wall, H. S. (1967). Analytic Theory of Continued Fractions. Chelsea, New York.Google Scholar