Hostname: page-component-7b7567c8c-slfcl Total loading time: 0 Render date: 2026-11-19T13:56:31.191Z Has data issue: false hasContentIssue false

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

Published online by Cambridge University Press:  19 February 2016

Philippe Flajolet*
Affiliation:
INRIA
Fabrice Guillemin*
Affiliation:
France Telecom
*
∗ Postal address: Algorithms Project, INRIA, F-78150 Rocquencourt, France. Email address: Philippe.Flajolet@inria.fr
∗∗ Postal address: France Telecom, BD.CNET, DAC/ATM, 2, Avenue Pierre Marzin, 22300 Lannion, France. Email address: Fabrice.Guillemin@cnet.francetelecom.fr

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.

Information

Type
General Applied Probability
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.)

Article purchase

Temporarily unavailable