Publisher

Date

2005

Description

The purpose of this note is to point out that Karlin and McGregor's integral representation for the transition probabilities of a birth-death process on a semi-infinite lattice with an absorbing bottom state remains valid if one allows the possibility of absorption into the bottom state from any other state. Conditions for uniqueness of the minimal transition function are also given.

Format

Identifier

Database

Rights

Link to record

Show preview

Hide preview

BIRTH-DEATH PROCESSES WITH KILLING

Erik A. van Doorn∗ and Alexander I. Zeifman†

∗Department of Applied Mathematics

University of Twente

P.O. Box 217, 7500 AE Enschede, The Netherlands

E-mail: e.a.vandoorn@utwente.nl

†Vologda State Pedagogical University

and Vologda Scientific Coordinate Centre of CEMI RAS

S. Orlova 6, Vologda, Russia

E-mail: zai@uni-vologda.ac.ru

9 December 2004

Abstract. The purpose of this note is to point out that Karlin and McGregor’s

integral representation for the transition probabilities of a birth-death process

on a semi-infinite lattice with an absorbing bottom state remains valid if one

allows the possibility of absorption into the bottom state from any other state.

Conditions for uniqueness of the minimal transition function are also given.

Keywords and phrases: Karlin-McGregor representation, orthogonal polynomi-

als, transition function, transition probabilities, state-dependent killing rate,

total catastrophe

2000 Mathematics Subject Classification: Primary 60J80

1 Introduction

We consider a Markov chain X ≡ {X(t), t ≥ 0} taking values in S ≡ {0, 1, . . .} with q-matrix Q ≡ (qij , i, j ∈ S) given by

qi,i+1 = λi, qi+1,i = µi+1, qii = −(λi + µi + γi), i ≥ 0, qij = 0, |i− j| > 1,

(1)

where λi > 0 and γi ≥ 0 for i ≥ 0, µi > 0 for i > 0, and µ0 = 0. The parameters λi and µi are the birth and death rates in state i, while γi may be

regarded as the rate of absorption, or killing, into a fictitious state ∂, say. A

transition to the absorbing state is sometimes referred to in the literature as a

total catastrophe (see for example Chao and Zheng (2003)).

We will assume that the (standard) transition function P (.) ≡ {pij(.), i, j ∈ S}, where

pij(t) ≡ Pr{X(t) = j |X(0) = i}, t ≥ 0, i, j ∈ S,

is the minimal Q-function, that is, the minimal transition function with q-

matrix Q. As a consequence P (.) satisfies the system

P ′(t) = QP (t) = P (t)Q, t ≥ 0, (2)

of backward and forward equations (see for example Anderson (1991)). We note

parenthetically that imposing the forward equations is equivalent to imposing

“continuity at infinity”, in the sense that almost surely the only discontinuities

of the process (before absorption) are simple discontinuities with saltus ±1, even if the process goes to infinity in finite time and returns from there (see

Karlin and McGregor (1959)). A prominent role in what follows will be played

by the polynomials {Rn} which are uniquely determined by the transition rates of X through the recurrence relation

λnRn+1(x) = (λn + µn + γn − x)Rn(x)− µnRn−1(x), n ≥ 1, λ0R1(x) = λ0 + γ0 − x, R0(x) = 1.

(3)

Karlin and McGregor (1957) have shown that if the killing rates γi are all

zero except γ0 ≥ 0 (in their notation γi = 0 for all i, but µ0 ≥ 0, and the

1

absorbing state is labeled −1), then the transition probabilities pij(t) may be represented in the form

pij(t) = pij ∫ ∞ 0

e−xtRi(x)Rj(x)ψ(dx), t ≥ 0, i, j ∈ S. (4)

Here pin are constants given by

pi0 ≡ 1 and pin ≡ λ0λ1 . . . λn−1 µ1µ2 . . . µn

, n > 0, (5)

and ψ is a Borel measure of total mass 1 on [0,∞) with respect to which the polynomials {Rn} are orthogonal. The orthogonalizing measure for {Rn} is in virtual all practical cases unique, and in many cases known explicitly.

The usefulness of the integral representation (4) derives from the monotonic

properties of e−xt, and from the fact that the dependence on t, i and j is

factored in the integrand.

If we allow for killing rates γi ≥ 0 in each state i ∈ S, the polynomials {Rn} of (3) still constitute an orthogonal polynomial sequence with respect to a Borel

measure ψ on [0,∞). The main purpose of this note is to point out that also the representation (4) remains valid in this case.

The remainder of this paper is organized as follows. In Section 2 we will

gather some preliminary results, which are needed in Section 3 to prove our

assertion. In Section 4 we will investigate under which condition on Q the

minimal Q-function P (.) is the only Q-function satisfying both backward and

forward equations. We conclude in Section 5 with an example.

2 An associated birth-death process

We shall have use for the quantities λ˜i and µ˜i, i ≥ 0, recurrently defined by

µ˜0 = 0, λ˜0 = λ0 + γ0

µ˜i = (λi−1/λ˜i−1)µi, λ˜i = λi + γi + µi − µ˜i, i > 0. (6)

It is easily seen by induction that

λ˜i ≥ λi + γi ≥ λi > 0 and µ˜i+1 > 0, i ≥ 0,

2

so that λ˜i and µ˜i may be interpreted as the birth and death rates, respectively,

of a (conservative) birth-death process X˜ ≡ {X˜(t), t ≥ 0} on S with q-matrix Q˜ ≡ (q˜ij) given by

q˜i,i+1 = λ˜i, q˜i+1,i = µ˜i+1, q˜ii = −(λ˜i + µ˜i), i ≥ 0, q˜ij = 0, |i− j| > 1.

(7)

We let

p˜i0 ≡ 1 and p˜in ≡ λ˜0λ˜1 . . . λ˜n−1 µ˜1µ˜2 . . . µ˜n

, n > 0, (8)

and observe from (1), (6) and (7) that

Π˜1/2Q˜Π˜−1/2 = Π1/2QΠ−1/2, (9)

where Π˜1/2 and Π1/2 denote the diagonal matrices with entries √ p˜in and

√ pin,

respectively, on the diagonals.

Evidently, X˜ need not be uniquely determined by Q˜, but in what follows we will assume that X˜ is the minimal Q˜-process, represented by the minimal Q˜-function P˜ (.) ≡ {p˜ij(.), i, j ∈ S}, which therefore satisfies the system

P˜ ′(t) = Q˜P˜ (t) = P˜ (t)Q˜, t ≥ 0, (10)

of backward and forward equations. Also, Karlin and McGregor’s integral rep-

resentation applies to p˜ij(t), that is,

p˜ij(t) = p˜ij ∫ ∞ 0

e−xtR˜i(x)R˜j(x)ψ˜(dx), t ≥ 0, i, j ∈ S, (11)

where {R˜n} are the polynomials satisfying the recurrence

λ˜nR˜n+1(x) = (λ˜n + µ˜n − x)R˜n(x)− µ˜nR˜n−1(x), n ≥ 1, λ˜0R˜1(x) = λ˜0 − x, R˜0(x) = 1,

(12)

and ψ˜ is a Borel measure (of total mass 1) on [0,∞) with respect to which the {R˜n} are orthogonal. Actually, if Q˜ is such that

∞∑ n=0

( p˜in +

1 λ˜np˜in

) =∞, (13)

then the Stieltjes moment problem associated with {R˜n} is determined, which means that ψ˜ is the unique orthogonalizing measure on [0,∞) for {R˜n}. In this

3

case P˜ (.) is the unique Q˜-function satisfying the system (10) of backward and

forward equations. If the series in (13) converges, then the Stieltjes moment

problem is indeterminate, that is, there are infinitely many orthogonalizing

measures for {R˜n}. In this case there are also infinitely many Q˜-functions satisfying (10). The measure ψ˜ corresponding to the minimal Q˜-function may

now be characterized as the one which is supported by the zeros of the (entire)

function R˜∞(x) ≡ limn→∞ R˜n(x); we will refer to ψ˜ as the minimal measure for {R˜n} (see Karlin and McGregor (1957) for more details).

It is sometimes desirable for X˜ to be non-explosive, which requires Q˜ to be such that

∞∑ n=0

1 λ˜np˜in

n∑ i=0

p˜ii =∞, (14)

which is stronger than (13). If (and only if) condition (14) is satisfied, then

the minimal Q˜-function P˜ (.) is in fact the unique Q˜-function satisfying just the

backward equations P˜ ′(t) = Q˜P˜ (t).

We conclude this section with the observation that, apart from a multi-

plicative constant, the polynomials R˜n and Rn are identical. Indeed, it follows

readily by induction from (6) and the recurrence relations (3) and (12) that

R˜n(x) = λ0λ1 . . . λn−1 λ˜0λ˜1 . . . λ˜n−1

Rn(x) = √ pin p˜in Rn(x), n ≥ 0. (15)

So, the polynomials {Rn} of (3) are orthogonal with respect to any measure which is an orthogonalizing measure for {R˜n}, and with respect to ψ˜ in partic- ular.

3 Representation

Our main result is expressed in the corollary to the following theorem.

Theorem 1 The minimal Q-function P (.) ≡ {pij(.)} and the minimal Q˜- function P˜ (.) ≡ {p˜ij(.)} satisfy

P (t) = Π−1/2Π˜1/2P˜ (t)Π˜−1/2Π1/2, t ≥ 0. (16)

4

Proof Denoting the right-hand side of (16) by F (t), it follows from (9) and

(10) that F (.) satisfies the system of backward and forward equations (2). F (.)

is also the minimal non-negative solution of (2) since the opposite would imply

that P˜ (.) is not the minimal non-negative solution of (10), and therefore (see for

example Anderson, 1991, Theorem 2.2.2) not the minimal Q˜-function. Hence,

by the same theorem in Anderson (1991), F (.) is the minimal Q-function, that

is, F (t) = P (t), t ≥ 0. 2

Corollary 2 The minimal Q-function P (.) ≡ {pij(.)} of the process X may be represented in the form (4), where {Rn} are the polynomials defined in (3) and ψ is the orthogonalizing measure (of total mass 1) for {Rn} on [0,∞) which, if it is not unique, is the minimal measure.

Proof By (16) and (11) we have

pij(t) =

√ p˜iipij piip˜ij

p˜ij(t) = √ p˜ii pii pij p˜ij

∫ ∞ 0

e−xtR˜i(x)R˜j(x)ψ˜(dx).

Substituting (15) and noting, in view of (15), that {Rn} is orthogonal with respect to ψ = ψ˜ yields the result. 2

So, as announced, we may conclude that the representation (4) remains valid

whether the killing rates γi, i > 0, are zero or not.

As in Karlin and McGregor (1957), certain non-minimal Q-functions (if

there are any) may also be represented in the form (4), with ψ replaced by

an appropriate (non-minimal) orthogonalizing measure for {Rn}. A necessary and sufficient condition for P (.) to be the only Q-function satisfying (2) will be

derived in the next section, but otherwise we will not pursue this issue.

As an aside we note that the concept of similarity for birth-death processes

introduced in Lenin et al. (2000) may be extended to birth-death processes with

killing. Namely, in view of (16) the transition probability functions pij(.) and

p˜ij(.) differ only by a multiplicative constant. Hence the process X is similar (in the sense of Lenin et al. (2000)) to the pure birth-death process X˜ .

5

4 Uniqueness

If condition (13) is satisfied then the minimal Q˜-function P˜ (.) is the unique

Q˜-function satisfying (10), and, as we shall see in this section, P (.) is the

unique Q-function satisfying (2). On the other hand, (13) is not necessary for

uniqueness of P (.). Before giving a necessary and sufficient condition we need

some preliminary results.

First, we observe from (15) and (6) that for all x

λ˜np˜inR˜n(x)R˜n+1(x) = λnpinRn(x)Rn+1(x), n ≥ 0. (17)

It is easily seen from (12) that R˜n(0) = 1 for all n, so, as a consequence of (15)

and (17), we have

p˜in = pinR2n(0), n ≥ 0, (18)

and

λ˜np˜in = λnpinRn(0)Rn+1(0), n ≥ 0. (19)

It will also be useful to note from the recurrence relation (3) and the fact that

λn−1pin−1 = µnpin that, for n ≥ 1,

λnpin(Rn+1(0)−Rn(0)) = λn−1pin−1(Rn(0)−Rn−1(0)) + γnpinRn(0),

while λ0pi0(R1(0)−R0(0)) = γ0pi0R0(0), so that

λnpin(Rn+1(0)−Rn(0)) = n∑

k=0

γkpikRk(0), n ≥ 0, (20)

and

Rn+1(0) = 1 + n∑

j=0

1 λjpij

j∑ k=0

γkpikRk(0), n ≥ 0. (21)

Our final preliminary result is the following lemma, which is the general-

ization to the setting at hand of (part of) Lemma 6 (on p. 526) of Karlin and

McGregor (1957). Recall that ψ (= ψ˜) is either the unique or else the minimal

orthogonalizing measure for {R˜n}, and hence for {Rn}.

6

Lemma 3 We have ∞∑ j=0

γjpij

∫ ∞ 0

x−1Rj(x)ψ(dx) = 1− lim n→∞

1 Rn(0)

. (22)

Proof From Karlin and McGregor, 1957, Lemma 6 we know that∫ ∞ 0

x−1ψ˜(dx) = ∞∑ n=0

1 λ˜np˜in

,

where both members may be infinite. It subsequently follows by induction from

the recurrence relation (12) that∫ ∞ 0

x−1R˜j(x)ψ˜(dx) = ∞∑ n=j

1 λ˜np˜in

, j ≥ 0. (23)

Hence, with the help of (15), (19), (18), and (20) we can write

∞∑ j=0

γjpij

∫ ∞ 0

x−1Rj(x)ψ(dx) = ∞∑ j=0

γj √ pij p˜ij

∫ ∞ 0

x−1R˜j(x)ψ˜(dx)

= ∞∑ j=0

γj √ pij p˜ij

∞∑ n=j

1 λ˜np˜in

= ∞∑ j=0

γjpijRj(0) ∞∑ n=j

1 λnpinRn(0)Rn+1(0)

= ∞∑ n=0

1 λnpinRn(0)Rn+1(0)

n∑ j=0

γjpijRj(0)

= ∞∑ n=0

( 1

Rn(0) − 1 Rn+1(0)

) ,

which yields the required result. 2

We can now give a necessary and sufficient condition for P (.), the minimal

Q-function, to be the unique Q-function satisfying (2).

Theorem 4 In order that there be only one Q-function P (.) satisfying the com-

bined system of backward and forward equations it is necessary and sufficient

that at least one of the two conditions

lim n→∞Rn(0) =∞ (24)

7

or ∞∑ n=0

( pin +

1 λnpin

) =∞ (25)

be satisfied.

Proof As in the proof of Theorem 15 of Karlin and McGregor (1957), we

consider the Laplace transform D(s) ≡ (Dij(s)) of the difference of any two Q-functions satisfying (2) and find that

Dij(s) = pijRi(−s)Rj(−s)D00(s), s ≥ 0.

Since the zeros of R˜n(x), and hence Rn(x), are all positive (see Karlin and

McGregor (1957)), while, by (21), Rn(0) is increasing in n, we have

Rn(−s) ≥ Rn(0) ≥ 1, s ≥ 0,

for all n. Hence, if (24) is satisfied then Ri(−s) → ∞ as i → ∞. But since Dij(s) is bounded we must have D00(s) = 0, and hence Dij(s) = 0 for all

i, j. On the other hand, if (24) is not satisfied then ∑

j(λjpij) −1 < ∞ as a

consequence of (21). So if, at the same time, (25) is satisfied, we must have∑ j pij =∞, and hence

∑ j pijRj(−s) =∞ for s ≥ 0. But, since

∑ j Dij(s) must

be bounded, it follows again that D00(s) = 0, and hence Dij(s) = 0 for all i, j.

Now suppose neither (24) nor (25) are satisfied. Then, in view of (18) and

(19), also (13) is not satisfied. As a result there is a number ξ1 > 0 and a

one-parameter family {ψξ, 0 ≤ ξ ≤ ξ1} of so-called extremal solutions to the Stieltjes moment problem associated with {R˜n}. The index ξ in ψξ denotes the smallest point in the support of the measure, and the minimal measure ψ = ψ˜

should be identified with ψξ1 (see Karlin and McGregor (1957) or van Doorn

(1987) for more details). Next letting

φ(ξ) ≡ ∞∑ j=0

γjpij

∫ ∞ 0

x−1Rj(x)ψξ(dx), 0 ≤ ξ ≤ ξ1,

we note that, by Lemma 3, the boundedness of Rn(0) amounts to φ(ξ1) < 1.

The proof of Theorem 15 of Karlin and McGregor (1957) can now be copied

to show that φ(ξ) is continuous, so that there must be a number ξ0 such that

8

φ(ξ) < 1 for ξ ∈ (ξ0, ξ1]. As in Karlin and McGregor (1957) the extremal measures ψξ, ξ0 < ξ ≤ ξ1, can subsequently be used to construct infinitely many distinct Q-functions satisfying (2). 2

If only finitely many γi are positive then, by (21), statement (24) is equiva-

lent to ∑∞

n=0(λnpin) −1 = ∞, so that (25) alone is necessary and sufficient for

uniqueness. Thus we have regained the necessary and sufficient condition for

uniqueness given in Theorem 15 of Karlin and McGregor (1957) in the case that

killing is possible in state 0 only.

In general, the first condition in the above theorem does not imply the

second one. Indeed, from (19) we obtain

Rn+1(0) = Rn(0) + γn λn Rn(0) +

1 λnpin

n−1∑ k=0

γkpikRk(0).

Hence, we may choose λn and µn such that the series in (25) converges, and

subsequently γn successively so large that Rn+1(0) ≥ Rn(0) + 1. As a result (24) does hold.

We also note that if Rn(0) is bounded then (13) and (25) are equivalent, in

view of (18) and (19). So, in accordance with our assertion at the beginning

of this section, if P˜ (.) is the unique Q˜-function satisfying (10), then P (.) is the

unique Q-function satisfying (2). (The reverse does not necessarily hold true.)

The integral in (22) seems enigmatic, but has in fact a clear probabilistic

interpretation. Namely, let T∂ denote the killing time, that is, the (possibly

defective) random variable representing the time at which absorption in the

absorbing state ∂ occurs. Since, by the forward equations,

Pr{T∂ ≤ t |X(0) = 0} = ∞∑ j=0

γj

∫ t 0 p0j(u)du,

we have

Pr{T∂ <∞|X(0) = 0} = ∞∑ j=0

γj

∫ ∞ 0

p0j(u)du,

so that, by substituting the integral representation (4) and interchanging the

integrals, we get

Pr{T∂ <∞|X(0) = 0} = ∞∑ j=0

γjpij

∫ ∞ 0

x−1Rj(x)ψ(dx). (26)

9

So Lemma 3 tells us that absorption at ∂ from state 0 (and hence from any

state) is certain if and only if Rn(0) is unbounded. More information about the

killing time T∂ is given in van Doorn and Zeifman (2005).

5 Example

If the killing rates are constant, γi = γ, say, then, by conditioning, the transition

probabilities pij(.) of the process with killing can simply be expressed in terms

of the transition probabilities p˜ij(.) of the process with the same birth and death

rates, but zero killing rates. Namely,

pij(t) = e−γtp˜ij(t), i, j ∈ S, t ≥ 0.

So interesting cases arise when the killing rates are state dependent.

As an example we will consider the process X with linear birth, death and killing rates, namely,

λi = λi+ θ, µi = iµ, γi = iγ, i ∈ S,

with λ, θ, µ, γ > 0. It is easy to see that (25) is satisfied, so X is uniquely determined by its rates. Karlin and Tavare´ (1982) have analysed the process

by adroitly relating it to an honest birth-death process with known transition

probabilities. We shall see that a direct approach based on the integral repre-

sentation (4) yields the same result. Indeed, the recurrence relation (3) becomes

(λn+ θ)Rn+1(x) = (θ + (λ+ µ+ γ)n− x)Rn(x)− µnRn−1(x), n > 1, θR1(x) = θ − x, R0(x) = 1.

Now writing

β ≡ θ λ , ρ ≡

√ (λ+ µ+ γ)2 − 4λµ, κ ≡ θ

( 1− 2µ

λ+ µ+ γ + ρ

) and

Pn(x) ≡ (

2λ λ+ µ+ γ − ρ

)n (β)nRn(ρx+ κ), n ≥ 0,

where (β)n ≡ Γ(β + n)/Γ(β), we see after a little algebra that {Pn} satisfies the recurrence

cPn+1(x) = ((c− 1)x+ (c+ 1)n+ cβ)Pn(x)− n(n+ β − 1)Pn−1(x),

10

where

c = λ+ µ+ γ − ρ λ+ µ+ γ + ρ

.

The polynomials Pn can now be identified (see Chihara, 1978, Section VI.3) with

the Meixner polynomials of the first kind, which are orthogonal with respect to

a discrete measure with masses at 0, 1, . . . . Specifically,

(1− c)β ∞∑ x=0

Pm(x)Pn(x) cx(β)x x!

= δm,n (β)nn! cn

, m, n ≥ 0.

As a consequence the orthogonality relation for the polynomials {Rn} may be given as

(1− c)β ∞∑ x=0

Rm(ρx+ κ)Rn(ρx+ κ) cx(β)x x!

= δm,n µnn! (β)nλn

, m, n ≥ 0.

By elementary substitution of these findings in the integral representation (4)

we regain the result obtained earlier in Karlin and Tavare´ (1982).

11

References

Anderson, W.J. (1991), Continuous-Time Markov Chains (Springer, New York).

Chao, X. and Zheng, Y. (2003), Transient analysis of immigration birth-death

processes with total catastrophes, Probab. Engrg. Inform. Sci. 17, 83-106.

Chihara, T.S. (1978), An Introduction to Orthogonal Polynomials (Gordon and

Breach, New York).

van Doorn, E.A. (1987), The indeterminate rate problem for birth-death pro-

cesses, Pacific J. Math. 130, 379-393.

van Doorn, E.A. and Zeifman, A.I. (2005), Extinction probability in a birth-

death process with killing, J. Appl. Probab. 42, to appear.

Karlin, S. and McGregor, J.L. (1957), The differential equations of birth-and-

death processes, and the Stieltjes moment problem, Trans. Amer. Math. Soc.

85, 589-646.

Karlin, S. and McGregor, J.L. (1959), A characterization of birth and death

processes, Proc. Natl. Acad. Sci. USA 45, 375-379.

Karlin, S. and Tavare´, S. (1982), Linear birth and death processes with killing,

J. Appl. Probab. 19, 477-487.

Lenin, R.B., Parthasarathy, P.R., Scheinhardt, W.R.W. and van Doorn, E.A.

(2000), Families of birth-death processes with similar time-dependent behaviour.

J. Appl. Probab. 37, 835-849.

12

Erik A. van Doorn∗ and Alexander I. Zeifman†

∗Department of Applied Mathematics

University of Twente

P.O. Box 217, 7500 AE Enschede, The Netherlands

E-mail: e.a.vandoorn@utwente.nl

†Vologda State Pedagogical University

and Vologda Scientific Coordinate Centre of CEMI RAS

S. Orlova 6, Vologda, Russia

E-mail: zai@uni-vologda.ac.ru

9 December 2004

Abstract. The purpose of this note is to point out that Karlin and McGregor’s

integral representation for the transition probabilities of a birth-death process

on a semi-infinite lattice with an absorbing bottom state remains valid if one

allows the possibility of absorption into the bottom state from any other state.

Conditions for uniqueness of the minimal transition function are also given.

Keywords and phrases: Karlin-McGregor representation, orthogonal polynomi-

als, transition function, transition probabilities, state-dependent killing rate,

total catastrophe

2000 Mathematics Subject Classification: Primary 60J80

1 Introduction

We consider a Markov chain X ≡ {X(t), t ≥ 0} taking values in S ≡ {0, 1, . . .} with q-matrix Q ≡ (qij , i, j ∈ S) given by

qi,i+1 = λi, qi+1,i = µi+1, qii = −(λi + µi + γi), i ≥ 0, qij = 0, |i− j| > 1,

(1)

where λi > 0 and γi ≥ 0 for i ≥ 0, µi > 0 for i > 0, and µ0 = 0. The parameters λi and µi are the birth and death rates in state i, while γi may be

regarded as the rate of absorption, or killing, into a fictitious state ∂, say. A

transition to the absorbing state is sometimes referred to in the literature as a

total catastrophe (see for example Chao and Zheng (2003)).

We will assume that the (standard) transition function P (.) ≡ {pij(.), i, j ∈ S}, where

pij(t) ≡ Pr{X(t) = j |X(0) = i}, t ≥ 0, i, j ∈ S,

is the minimal Q-function, that is, the minimal transition function with q-

matrix Q. As a consequence P (.) satisfies the system

P ′(t) = QP (t) = P (t)Q, t ≥ 0, (2)

of backward and forward equations (see for example Anderson (1991)). We note

parenthetically that imposing the forward equations is equivalent to imposing

“continuity at infinity”, in the sense that almost surely the only discontinuities

of the process (before absorption) are simple discontinuities with saltus ±1, even if the process goes to infinity in finite time and returns from there (see

Karlin and McGregor (1959)). A prominent role in what follows will be played

by the polynomials {Rn} which are uniquely determined by the transition rates of X through the recurrence relation

λnRn+1(x) = (λn + µn + γn − x)Rn(x)− µnRn−1(x), n ≥ 1, λ0R1(x) = λ0 + γ0 − x, R0(x) = 1.

(3)

Karlin and McGregor (1957) have shown that if the killing rates γi are all

zero except γ0 ≥ 0 (in their notation γi = 0 for all i, but µ0 ≥ 0, and the

1

absorbing state is labeled −1), then the transition probabilities pij(t) may be represented in the form

pij(t) = pij ∫ ∞ 0

e−xtRi(x)Rj(x)ψ(dx), t ≥ 0, i, j ∈ S. (4)

Here pin are constants given by

pi0 ≡ 1 and pin ≡ λ0λ1 . . . λn−1 µ1µ2 . . . µn

, n > 0, (5)

and ψ is a Borel measure of total mass 1 on [0,∞) with respect to which the polynomials {Rn} are orthogonal. The orthogonalizing measure for {Rn} is in virtual all practical cases unique, and in many cases known explicitly.

The usefulness of the integral representation (4) derives from the monotonic

properties of e−xt, and from the fact that the dependence on t, i and j is

factored in the integrand.

If we allow for killing rates γi ≥ 0 in each state i ∈ S, the polynomials {Rn} of (3) still constitute an orthogonal polynomial sequence with respect to a Borel

measure ψ on [0,∞). The main purpose of this note is to point out that also the representation (4) remains valid in this case.

The remainder of this paper is organized as follows. In Section 2 we will

gather some preliminary results, which are needed in Section 3 to prove our

assertion. In Section 4 we will investigate under which condition on Q the

minimal Q-function P (.) is the only Q-function satisfying both backward and

forward equations. We conclude in Section 5 with an example.

2 An associated birth-death process

We shall have use for the quantities λ˜i and µ˜i, i ≥ 0, recurrently defined by

µ˜0 = 0, λ˜0 = λ0 + γ0

µ˜i = (λi−1/λ˜i−1)µi, λ˜i = λi + γi + µi − µ˜i, i > 0. (6)

It is easily seen by induction that

λ˜i ≥ λi + γi ≥ λi > 0 and µ˜i+1 > 0, i ≥ 0,

2

so that λ˜i and µ˜i may be interpreted as the birth and death rates, respectively,

of a (conservative) birth-death process X˜ ≡ {X˜(t), t ≥ 0} on S with q-matrix Q˜ ≡ (q˜ij) given by

q˜i,i+1 = λ˜i, q˜i+1,i = µ˜i+1, q˜ii = −(λ˜i + µ˜i), i ≥ 0, q˜ij = 0, |i− j| > 1.

(7)

We let

p˜i0 ≡ 1 and p˜in ≡ λ˜0λ˜1 . . . λ˜n−1 µ˜1µ˜2 . . . µ˜n

, n > 0, (8)

and observe from (1), (6) and (7) that

Π˜1/2Q˜Π˜−1/2 = Π1/2QΠ−1/2, (9)

where Π˜1/2 and Π1/2 denote the diagonal matrices with entries √ p˜in and

√ pin,

respectively, on the diagonals.

Evidently, X˜ need not be uniquely determined by Q˜, but in what follows we will assume that X˜ is the minimal Q˜-process, represented by the minimal Q˜-function P˜ (.) ≡ {p˜ij(.), i, j ∈ S}, which therefore satisfies the system

P˜ ′(t) = Q˜P˜ (t) = P˜ (t)Q˜, t ≥ 0, (10)

of backward and forward equations. Also, Karlin and McGregor’s integral rep-

resentation applies to p˜ij(t), that is,

p˜ij(t) = p˜ij ∫ ∞ 0

e−xtR˜i(x)R˜j(x)ψ˜(dx), t ≥ 0, i, j ∈ S, (11)

where {R˜n} are the polynomials satisfying the recurrence

λ˜nR˜n+1(x) = (λ˜n + µ˜n − x)R˜n(x)− µ˜nR˜n−1(x), n ≥ 1, λ˜0R˜1(x) = λ˜0 − x, R˜0(x) = 1,

(12)

and ψ˜ is a Borel measure (of total mass 1) on [0,∞) with respect to which the {R˜n} are orthogonal. Actually, if Q˜ is such that

∞∑ n=0

( p˜in +

1 λ˜np˜in

) =∞, (13)

then the Stieltjes moment problem associated with {R˜n} is determined, which means that ψ˜ is the unique orthogonalizing measure on [0,∞) for {R˜n}. In this

3

case P˜ (.) is the unique Q˜-function satisfying the system (10) of backward and

forward equations. If the series in (13) converges, then the Stieltjes moment

problem is indeterminate, that is, there are infinitely many orthogonalizing

measures for {R˜n}. In this case there are also infinitely many Q˜-functions satisfying (10). The measure ψ˜ corresponding to the minimal Q˜-function may

now be characterized as the one which is supported by the zeros of the (entire)

function R˜∞(x) ≡ limn→∞ R˜n(x); we will refer to ψ˜ as the minimal measure for {R˜n} (see Karlin and McGregor (1957) for more details).

It is sometimes desirable for X˜ to be non-explosive, which requires Q˜ to be such that

∞∑ n=0

1 λ˜np˜in

n∑ i=0

p˜ii =∞, (14)

which is stronger than (13). If (and only if) condition (14) is satisfied, then

the minimal Q˜-function P˜ (.) is in fact the unique Q˜-function satisfying just the

backward equations P˜ ′(t) = Q˜P˜ (t).

We conclude this section with the observation that, apart from a multi-

plicative constant, the polynomials R˜n and Rn are identical. Indeed, it follows

readily by induction from (6) and the recurrence relations (3) and (12) that

R˜n(x) = λ0λ1 . . . λn−1 λ˜0λ˜1 . . . λ˜n−1

Rn(x) = √ pin p˜in Rn(x), n ≥ 0. (15)

So, the polynomials {Rn} of (3) are orthogonal with respect to any measure which is an orthogonalizing measure for {R˜n}, and with respect to ψ˜ in partic- ular.

3 Representation

Our main result is expressed in the corollary to the following theorem.

Theorem 1 The minimal Q-function P (.) ≡ {pij(.)} and the minimal Q˜- function P˜ (.) ≡ {p˜ij(.)} satisfy

P (t) = Π−1/2Π˜1/2P˜ (t)Π˜−1/2Π1/2, t ≥ 0. (16)

4

Proof Denoting the right-hand side of (16) by F (t), it follows from (9) and

(10) that F (.) satisfies the system of backward and forward equations (2). F (.)

is also the minimal non-negative solution of (2) since the opposite would imply

that P˜ (.) is not the minimal non-negative solution of (10), and therefore (see for

example Anderson, 1991, Theorem 2.2.2) not the minimal Q˜-function. Hence,

by the same theorem in Anderson (1991), F (.) is the minimal Q-function, that

is, F (t) = P (t), t ≥ 0. 2

Corollary 2 The minimal Q-function P (.) ≡ {pij(.)} of the process X may be represented in the form (4), where {Rn} are the polynomials defined in (3) and ψ is the orthogonalizing measure (of total mass 1) for {Rn} on [0,∞) which, if it is not unique, is the minimal measure.

Proof By (16) and (11) we have

pij(t) =

√ p˜iipij piip˜ij

p˜ij(t) = √ p˜ii pii pij p˜ij

∫ ∞ 0

e−xtR˜i(x)R˜j(x)ψ˜(dx).

Substituting (15) and noting, in view of (15), that {Rn} is orthogonal with respect to ψ = ψ˜ yields the result. 2

So, as announced, we may conclude that the representation (4) remains valid

whether the killing rates γi, i > 0, are zero or not.

As in Karlin and McGregor (1957), certain non-minimal Q-functions (if

there are any) may also be represented in the form (4), with ψ replaced by

an appropriate (non-minimal) orthogonalizing measure for {Rn}. A necessary and sufficient condition for P (.) to be the only Q-function satisfying (2) will be

derived in the next section, but otherwise we will not pursue this issue.

As an aside we note that the concept of similarity for birth-death processes

introduced in Lenin et al. (2000) may be extended to birth-death processes with

killing. Namely, in view of (16) the transition probability functions pij(.) and

p˜ij(.) differ only by a multiplicative constant. Hence the process X is similar (in the sense of Lenin et al. (2000)) to the pure birth-death process X˜ .

5

4 Uniqueness

If condition (13) is satisfied then the minimal Q˜-function P˜ (.) is the unique

Q˜-function satisfying (10), and, as we shall see in this section, P (.) is the

unique Q-function satisfying (2). On the other hand, (13) is not necessary for

uniqueness of P (.). Before giving a necessary and sufficient condition we need

some preliminary results.

First, we observe from (15) and (6) that for all x

λ˜np˜inR˜n(x)R˜n+1(x) = λnpinRn(x)Rn+1(x), n ≥ 0. (17)

It is easily seen from (12) that R˜n(0) = 1 for all n, so, as a consequence of (15)

and (17), we have

p˜in = pinR2n(0), n ≥ 0, (18)

and

λ˜np˜in = λnpinRn(0)Rn+1(0), n ≥ 0. (19)

It will also be useful to note from the recurrence relation (3) and the fact that

λn−1pin−1 = µnpin that, for n ≥ 1,

λnpin(Rn+1(0)−Rn(0)) = λn−1pin−1(Rn(0)−Rn−1(0)) + γnpinRn(0),

while λ0pi0(R1(0)−R0(0)) = γ0pi0R0(0), so that

λnpin(Rn+1(0)−Rn(0)) = n∑

k=0

γkpikRk(0), n ≥ 0, (20)

and

Rn+1(0) = 1 + n∑

j=0

1 λjpij

j∑ k=0

γkpikRk(0), n ≥ 0. (21)

Our final preliminary result is the following lemma, which is the general-

ization to the setting at hand of (part of) Lemma 6 (on p. 526) of Karlin and

McGregor (1957). Recall that ψ (= ψ˜) is either the unique or else the minimal

orthogonalizing measure for {R˜n}, and hence for {Rn}.

6

Lemma 3 We have ∞∑ j=0

γjpij

∫ ∞ 0

x−1Rj(x)ψ(dx) = 1− lim n→∞

1 Rn(0)

. (22)

Proof From Karlin and McGregor, 1957, Lemma 6 we know that∫ ∞ 0

x−1ψ˜(dx) = ∞∑ n=0

1 λ˜np˜in

,

where both members may be infinite. It subsequently follows by induction from

the recurrence relation (12) that∫ ∞ 0

x−1R˜j(x)ψ˜(dx) = ∞∑ n=j

1 λ˜np˜in

, j ≥ 0. (23)

Hence, with the help of (15), (19), (18), and (20) we can write

∞∑ j=0

γjpij

∫ ∞ 0

x−1Rj(x)ψ(dx) = ∞∑ j=0

γj √ pij p˜ij

∫ ∞ 0

x−1R˜j(x)ψ˜(dx)

= ∞∑ j=0

γj √ pij p˜ij

∞∑ n=j

1 λ˜np˜in

= ∞∑ j=0

γjpijRj(0) ∞∑ n=j

1 λnpinRn(0)Rn+1(0)

= ∞∑ n=0

1 λnpinRn(0)Rn+1(0)

n∑ j=0

γjpijRj(0)

= ∞∑ n=0

( 1

Rn(0) − 1 Rn+1(0)

) ,

which yields the required result. 2

We can now give a necessary and sufficient condition for P (.), the minimal

Q-function, to be the unique Q-function satisfying (2).

Theorem 4 In order that there be only one Q-function P (.) satisfying the com-

bined system of backward and forward equations it is necessary and sufficient

that at least one of the two conditions

lim n→∞Rn(0) =∞ (24)

7

or ∞∑ n=0

( pin +

1 λnpin

) =∞ (25)

be satisfied.

Proof As in the proof of Theorem 15 of Karlin and McGregor (1957), we

consider the Laplace transform D(s) ≡ (Dij(s)) of the difference of any two Q-functions satisfying (2) and find that

Dij(s) = pijRi(−s)Rj(−s)D00(s), s ≥ 0.

Since the zeros of R˜n(x), and hence Rn(x), are all positive (see Karlin and

McGregor (1957)), while, by (21), Rn(0) is increasing in n, we have

Rn(−s) ≥ Rn(0) ≥ 1, s ≥ 0,

for all n. Hence, if (24) is satisfied then Ri(−s) → ∞ as i → ∞. But since Dij(s) is bounded we must have D00(s) = 0, and hence Dij(s) = 0 for all

i, j. On the other hand, if (24) is not satisfied then ∑

j(λjpij) −1 < ∞ as a

consequence of (21). So if, at the same time, (25) is satisfied, we must have∑ j pij =∞, and hence

∑ j pijRj(−s) =∞ for s ≥ 0. But, since

∑ j Dij(s) must

be bounded, it follows again that D00(s) = 0, and hence Dij(s) = 0 for all i, j.

Now suppose neither (24) nor (25) are satisfied. Then, in view of (18) and

(19), also (13) is not satisfied. As a result there is a number ξ1 > 0 and a

one-parameter family {ψξ, 0 ≤ ξ ≤ ξ1} of so-called extremal solutions to the Stieltjes moment problem associated with {R˜n}. The index ξ in ψξ denotes the smallest point in the support of the measure, and the minimal measure ψ = ψ˜

should be identified with ψξ1 (see Karlin and McGregor (1957) or van Doorn

(1987) for more details). Next letting

φ(ξ) ≡ ∞∑ j=0

γjpij

∫ ∞ 0

x−1Rj(x)ψξ(dx), 0 ≤ ξ ≤ ξ1,

we note that, by Lemma 3, the boundedness of Rn(0) amounts to φ(ξ1) < 1.

The proof of Theorem 15 of Karlin and McGregor (1957) can now be copied

to show that φ(ξ) is continuous, so that there must be a number ξ0 such that

8

φ(ξ) < 1 for ξ ∈ (ξ0, ξ1]. As in Karlin and McGregor (1957) the extremal measures ψξ, ξ0 < ξ ≤ ξ1, can subsequently be used to construct infinitely many distinct Q-functions satisfying (2). 2

If only finitely many γi are positive then, by (21), statement (24) is equiva-

lent to ∑∞

n=0(λnpin) −1 = ∞, so that (25) alone is necessary and sufficient for

uniqueness. Thus we have regained the necessary and sufficient condition for

uniqueness given in Theorem 15 of Karlin and McGregor (1957) in the case that

killing is possible in state 0 only.

In general, the first condition in the above theorem does not imply the

second one. Indeed, from (19) we obtain

Rn+1(0) = Rn(0) + γn λn Rn(0) +

1 λnpin

n−1∑ k=0

γkpikRk(0).

Hence, we may choose λn and µn such that the series in (25) converges, and

subsequently γn successively so large that Rn+1(0) ≥ Rn(0) + 1. As a result (24) does hold.

We also note that if Rn(0) is bounded then (13) and (25) are equivalent, in

view of (18) and (19). So, in accordance with our assertion at the beginning

of this section, if P˜ (.) is the unique Q˜-function satisfying (10), then P (.) is the

unique Q-function satisfying (2). (The reverse does not necessarily hold true.)

The integral in (22) seems enigmatic, but has in fact a clear probabilistic

interpretation. Namely, let T∂ denote the killing time, that is, the (possibly

defective) random variable representing the time at which absorption in the

absorbing state ∂ occurs. Since, by the forward equations,

Pr{T∂ ≤ t |X(0) = 0} = ∞∑ j=0

γj

∫ t 0 p0j(u)du,

we have

Pr{T∂ <∞|X(0) = 0} = ∞∑ j=0

γj

∫ ∞ 0

p0j(u)du,

so that, by substituting the integral representation (4) and interchanging the

integrals, we get

Pr{T∂ <∞|X(0) = 0} = ∞∑ j=0

γjpij

∫ ∞ 0

x−1Rj(x)ψ(dx). (26)

9

So Lemma 3 tells us that absorption at ∂ from state 0 (and hence from any

state) is certain if and only if Rn(0) is unbounded. More information about the

killing time T∂ is given in van Doorn and Zeifman (2005).

5 Example

If the killing rates are constant, γi = γ, say, then, by conditioning, the transition

probabilities pij(.) of the process with killing can simply be expressed in terms

of the transition probabilities p˜ij(.) of the process with the same birth and death

rates, but zero killing rates. Namely,

pij(t) = e−γtp˜ij(t), i, j ∈ S, t ≥ 0.

So interesting cases arise when the killing rates are state dependent.

As an example we will consider the process X with linear birth, death and killing rates, namely,

λi = λi+ θ, µi = iµ, γi = iγ, i ∈ S,

with λ, θ, µ, γ > 0. It is easy to see that (25) is satisfied, so X is uniquely determined by its rates. Karlin and Tavare´ (1982) have analysed the process

by adroitly relating it to an honest birth-death process with known transition

probabilities. We shall see that a direct approach based on the integral repre-

sentation (4) yields the same result. Indeed, the recurrence relation (3) becomes

(λn+ θ)Rn+1(x) = (θ + (λ+ µ+ γ)n− x)Rn(x)− µnRn−1(x), n > 1, θR1(x) = θ − x, R0(x) = 1.

Now writing

β ≡ θ λ , ρ ≡

√ (λ+ µ+ γ)2 − 4λµ, κ ≡ θ

( 1− 2µ

λ+ µ+ γ + ρ

) and

Pn(x) ≡ (

2λ λ+ µ+ γ − ρ

)n (β)nRn(ρx+ κ), n ≥ 0,

where (β)n ≡ Γ(β + n)/Γ(β), we see after a little algebra that {Pn} satisfies the recurrence

cPn+1(x) = ((c− 1)x+ (c+ 1)n+ cβ)Pn(x)− n(n+ β − 1)Pn−1(x),

10

where

c = λ+ µ+ γ − ρ λ+ µ+ γ + ρ

.

The polynomials Pn can now be identified (see Chihara, 1978, Section VI.3) with

the Meixner polynomials of the first kind, which are orthogonal with respect to

a discrete measure with masses at 0, 1, . . . . Specifically,

(1− c)β ∞∑ x=0

Pm(x)Pn(x) cx(β)x x!

= δm,n (β)nn! cn

, m, n ≥ 0.

As a consequence the orthogonality relation for the polynomials {Rn} may be given as

(1− c)β ∞∑ x=0

Rm(ρx+ κ)Rn(ρx+ κ) cx(β)x x!

= δm,n µnn! (β)nλn

, m, n ≥ 0.

By elementary substitution of these findings in the integral representation (4)

we regain the result obtained earlier in Karlin and Tavare´ (1982).

11

References

Anderson, W.J. (1991), Continuous-Time Markov Chains (Springer, New York).

Chao, X. and Zheng, Y. (2003), Transient analysis of immigration birth-death

processes with total catastrophes, Probab. Engrg. Inform. Sci. 17, 83-106.

Chihara, T.S. (1978), An Introduction to Orthogonal Polynomials (Gordon and

Breach, New York).

van Doorn, E.A. (1987), The indeterminate rate problem for birth-death pro-

cesses, Pacific J. Math. 130, 379-393.

van Doorn, E.A. and Zeifman, A.I. (2005), Extinction probability in a birth-

death process with killing, J. Appl. Probab. 42, to appear.

Karlin, S. and McGregor, J.L. (1957), The differential equations of birth-and-

death processes, and the Stieltjes moment problem, Trans. Amer. Math. Soc.

85, 589-646.

Karlin, S. and McGregor, J.L. (1959), A characterization of birth and death

processes, Proc. Natl. Acad. Sci. USA 45, 375-379.

Karlin, S. and Tavare´, S. (1982), Linear birth and death processes with killing,

J. Appl. Probab. 19, 477-487.

Lenin, R.B., Parthasarathy, P.R., Scheinhardt, W.R.W. and van Doorn, E.A.

(2000), Families of birth-death processes with similar time-dependent behaviour.

J. Appl. Probab. 37, 835-849.

12

Comments