HOMOGENEOUS FINITE SOURCE B!UTH AND DEATH PROCES WITH APPLICATIONS

HOMOGENEOUS FINITE SOURCE B!UTH AND DEATH PROCES WITH APPLICATIONS

By

N. SREEKUMARAN NA1R

Thesis submitted

ir> fulfilment of the requirements of the degree of

DOCTOR OF PHILOSOPHY

to the

Department of Mathematics

INDIAN INSTITUTE OF TECHNOLOGY,DELHI Hauz Khas,New Delhi-110016,india

April,1992

ノーア.?

ら、コ，

9

^{亡， 二}

ノゾ

fl

！一

-r h

^{屯ーユ三‘}

!-

^．ぐ

一d国ゆ 卿曲ー

も

一1-h句 」

Toni ア paren Is

CERTIFICATE

It is certified that the thesis entitled "KOMOGENEOUS FINITE SOひRCE BIRTH AND DEATH PROCESS WITH APPLICATIONS"

presented by Shri . N. BREERUMARAN NAIR is worthy of cons iderat ion for the award of the degree of DOCTOR OF PHILOSOPHY and is a record of the original bonafide research work carried out by him under my guidance and supervision and that the results contained in it have or ln full to any other University or Institute

diploma .

ェ certify that he has pursued the prescribed course

research・ A

Prof . O . P . SHARMA _レ／

Supervisor

Department of Mathematics

Indian Institute of Technology Hauz Khas. New Delhi-1100l6.

not been submitted 'n par^七

for the award of any degree or

of

pa.九tmen..t o各

るu99e.tiOflる and んe.Zp.

P九。も． N. S. Kadiりbo, Head

tんe 心

a-cu

乙

ty

and IlT DeZんえ 心。九 I thanた6wUw acたn-ow乙ed

Depcvztment o4

るta-4各 o-6 the theえ't time乙w

the he2p o6 P'to4. P.K.

wOLL&t 21

た

e to ac.

た

now.e.'Lge

De. I

ACKNαりLEDGEMENTS

I e xp

九

e

るる my 'Lee p oも 9ル叫し^U山^{cLe to P}九o4. O.P. SIw九mou. He

been

an

ext

九

emeLy unde

しい比比奴

-rt9,

c-oopeえatえve, 6元ierzd2y appえ00-c.んable るupe九vえる。え du九ing t he c.ow'cるe a心 tんえる

1

る■し比

geiy due to h

えー

6

40え c4えtえcae cno2y4iる，

a.n.d c2o

る

e

る

IL-pe

九

i,

えるえ

on

.that -the theる1る んa.る p九e.る^en一t 乃

ha.pe He a&'kty4 4o

und ;tjne 谷。九 me wんetheえ o心各^{ice o}九 aえ ん

ome.

る

.tUiy.

gui.4 - n

え

t

る

wa6 at

B

ん

attαc

ん

a

九

ya, P

九

o4. J.8. S

九

iva.

る

ta-va an-d D

九． Wagiるん Sh"た乙^a

du

九

tng the eα

九

Zy p

ん

a-

る

e o4 thl- wo

九た．

My

る

ince

九

e tha-n

たる

a

九

e

ae.-6o due. to a-U my 各^{e ow 九eるeoレ乞C.ん} る

C

れ

^ola

える

and

る

4lend

る． ^M九． M. v.R. Mciieイ山火L九 uロる a乙wayる

a-va

え

eable w

ん

en-e ve

九

I needed he2p.

I る^-t九ong-Ly be.&..we tん^{at -t}ん^{e wo}えた^ing

c.on.t

ル

tb"

七二 to a-ny

the

る

ta6

る oる -the

Imm.rnotogy aZwag

る

C

ん

atte

九

jee

、る bene.voeence. Mえる も九えendt y る^{u.g ge}る^ttonる

o' l't.

a-p p九eし<zは:4._on. I enjoyed cent九e.

-t a.nd る九イ^en'る nLttUルe. oる ^a-M

type at', -tu.dy. The

Compute九 Centルe encocwLged me

R. R.M

to wo尤た． んa.九d Riたれy、る -tえmei.y

env

ん

-/ton

刀

ier-t.

chee

九心

IL

乙

Nat

え

ong-12

Inる-tえtute D九．

he乙p

D. o' a-nd

Pande y

a-u

de-6eitve

a.t NIl

compute.>t a. 各ルえerwJty atinoるphe.'te.

1 g

奴

lte6u

乙乙

y c.c

た

now

必

edge the 6 c.c.

しし

t e

る 。も

4e

九・

ed by -t

ん

e

Nc-t-Lono2 Inる-tズtu-te oiS IIflflltLflOtO9y, and

Inj:Ua.n

Inるtえtu-te

o'

Techno乙099, De.e.hえ ⁴⁰九 the corn p-te-t2on o' ^-tん心6

t

ん

e

ム

1

る

Tんえる -.tudy

enc.

え・

oc.c.hed

a. 乙0-t oも the -tんme I -6 ho u2t ん工ve

o-t

ん

eu

直名

e

る

pen-t w t

ん my 4am.i2y . I wou2d ia-12 in my duty i 4

'Lo no-t exp'te-<

る

my 9

元

at

元

.-tur.Leto my wi

心

e Ra.

柵

11

and -to え

n

る

an-t da

・

u-9

ん

te S

九

ut

え，

w

ん

o pati.ert*2y

る

u-

各る叫

ed th

元

4 n-e.gLe.ct.

owe a to-t -to my pa'tent.6.

La乃-t

but no.t

乙

^ea.-6;t;

a. wo'tcL o心 るin-ce九^e

tu1n

たる

1

る

a.

とる

o

^{due to}

川匠． Suんe乃h Cんa.nd Ln M't.N.C. Pande y,

M

九．

BabuJa-L

a-nd M九．

Sa)t- るh Kwnc.え 各。九 -tんeえ尤 he2p.

N. SREEKLJMARAN NAIR

Iyl m

SYNOPSIS

Finite state birth and death process finds many app] ications -in operations research as well as in natural Sc」ences and demography. As the name suggests,this stochastic process had its origin in biology but 's extensively used in studying the Markovi an models in queue, ng theory, i nventory and machine interference problems etc . Researchers have studied applications of this process based on the steady state solutions of the differential difference equations determined by the process . Some expression for trans」ent state probabi i ities have also been reported by different authors.

However most the solutions have one or more of the following short comings:

Initial state of the process is assumed empty which is generally incompatible with the practical situations.

Specificai ly, a simple transient solution for qeneral 入 and g,with

一 n n arbitrary initial or absorbing boundary states is missing Thi s thesis aims to present such

Reported solutions are in terms of Bessel functions or are expressed ln complicated integral forms which are not amenable to further algebraic manipulations.

Usually solutions have been obtained for particular cases of 入 and ^LLn

・

Boundary states are assumed to be reflecting.

a solution. The input and in the

refi ecti ng i i terature.

solutions

'J,

obtained are free from all the above mentioned shortcomings . Their applications in biology and queue i ng theory are a i so cons -i dered . The efficacy of the resu 1 ts derived a re

liustrated by numerical computations.

The thesis is divided into five chapters. Each chapter gives a brief introduction about the aim of the chapter and then presents development of the theory and finally shows its applications and numerical computations. The detai is of the different chapters are as follows:

CHAPTER X:

This chapter explains the preliminary concepts and parameters involved in birth and death and related stochastic processes. Differential difference equations of the finite state birth and death process have been derived. Properties of Laplace transforms and parameters of queueing theory have also been discussed. Also a detailed review of the recent developments in the areas of birth and death process, Markovian queues and applications of birth and death process

in biology is presented.

Chapter II:

This chapter deals with an extensive study of the transient behaviour of finite state time homogeneous birth and death process with reflecting boundary states. After a brief

VII

input.

detail

solution has been obtained

as a biological application.

Finally a model from

y b

taking genetics

introduction and derivation of differential difference equations and its Laplace transformation a simple matrix method is developed to obtain the closed form expression for the transient state probabilities in terms of eigenvalues of a symmetric tridiagonal matrix and can be written as

p-(t) n = n n +Hn+1Hn+2.-. な

A N

i=i や」 nl

一

^α

．

^t

e i

e ,os n<k N 一α t

=nk ＋ こ ^{Bk .eki} n=k

=i

N 一α＿ t

=n

n

^+;'

_

k \k k

_ +1

^{… i}

'

^-. _n一i

乞

^B

i=i nl k<n: N

where て gives the steady state distribution of the process and works out to be

0 n ^{r ,\ 1' o} _{ニ fl＋ー＋}

! /-i一

一 l

入。入_i /

.

^{I U,.}

'

X X01^{・ ・}

「

^N

^{- 11-}

¹

UIU

, v 2^・・HN 」

and

入。与…入 ^n-1

_{i : nS N}

α．、s are the eigenvalues of the symmetric tridiagonal matrix and A _nl and B nl are polynomials of the eigenvalues α^．、s. The

一 i

an arbitrary initial has been studied in

Vnl

+ n け一 n- k 一（×+u )t e

(1-p)pn

N+1 ^ごメi where て

D=

irr N+ i i -p

i N+1

2 Cos and A and a =

t

are functions of

k二nくN

o三n:: N

B ni

a 二H d 五

an e

一11 ・1■ n n N

や」 ニ B 一 一

CHAPTER III

Finite state Markovian queues are the immediate and important applications of finite state birth and death p roces s. This chapter studies many finite capacity Markovian queueing models as particular cases of the results derived in chapter 2. For each model transient state probabilities have been obtained as the sum of stationary and transient components without using Bessel functions or integral formu 1 at i ons. In case of double一ended queue and HIM/i/N queues,very simplified analytic expressions are obtained for state probabilities and other parameters. For M/M/1/N, the state probabilities work out to be

p_(t) n ^{= rT + u} n

k一n 一（2'、 -I-u)t

N rl ニ ・

『1 e 、「1 n A 価石 a.t o玉nくk

Chebychev、s polynomials of the first kind.

For H/M/c/N system with homogeneous servers the results obtained coincide with the results reported b y

IX

Dass(i 987). Other cases like M/M/c/N with heterogeneous servers,MIMIc/c loss system etc. are also discussed. Using the simple expression obtained for the state probabilities, the waiting time distributions are also derived for M/M/c/N and M/M/1/N systems. Steady state results are derived which coincide with the ones reported in the literature. Numerical computations are carried out to verify the validity of the results derived.

CHAPTER IV:

This chapter deals with the birth and death process where at least one of the boundary state of the process is absorbing. Three possible cases have been discussed, name i y:

(I)state O is absorbing and N is reflecting, ie，入O = o andPN>o

(2)state O is reflecting and N is absorbing, ie， 八o>o and pN = o

(3)both the boundary states are absorbing, ie， 入o = HN = o.

The transient solutions have been obtained for cases in simple forms. Probability distribution

all of

the three the time of absorption and its moments have a1SO been Obtained for eaCh case .

Applications of this process in queueing theory as

where A,s are pol ynomi als

This chapter al applications such as,model

a.,s.

i

deals with the biological the spread of an epidemic in a

the first passage time distribution which has i i terature. This chapter mak

昭

^an

derive probability density function of the ^{fi rst} process

recel ved attempt

■

11

5

1 0 1 t

ttle attention -m

well as biology have been discussed. In queueing context busy period distribution of MIMIc/N queue and HIM/i/N queue are derived-For double ended queue both customers and servers busy period distributions are obtained ln s i mp i e form . Generally for queueing models only first two moments are reported in the literature but in these cases we succeed ifl

finding

七

he general moments. For instance if m stands for the r一th raw moment of busy period distribution of H/H/i/N queue then,

m 二 H l^{k1でて二es「十二}1 N

工（\ +p－五戸 a

一

^r-1 _瓦

i=i

finite population,finite population growth model with 1 1 near and constant birth and death rates and a simple birth and death model for incubation period.

CHAPTER V

Another important aspect of the birth and death

passage time random variable. ^All the four cases of the boundary conditions a re attempted . For process with atleast

×'

both

(t)=

f km A . e -ciN-m te iN-m

i OSmくk

B . e -f3'.m te im

i kく爪ゴN

r 」＝

E f.L

one reflecting barrier,complete probability distribution have been obtained and have shown that the total integral of the density

density

function function

S f 1 O

uni the

ty. Let f. (t)denote Km first passage time

七he then

probabi 1 ity for the case reflecting barriers fkm(t) is given by

N一m H_冊1Hm+2

＝ 入k_入k+ i..

'. .p._

_K

i

．入 _m-1 i=

O: t＜叩

= o ,elsewhere

Similar expressions have also と真en obtained for the other cases. Expression for its moments are also obtained. In the case of both absorbing barriers total integral is not unity and hence distribution is not a complete one.

The thesis concludes with a bibliography, which covers the important publications of b」rth and death and related process in the last half century.

×11

2 2 3 7■ 6 8 1 1 11 2 2 4 2 2

28

33

4 6 3 つ」

CONTENTS

PAGE NO CERTI FICATE

ACKNOWLEDGEMENTS ₁₁

CONTENTS 111

SYNOPSIS vi

CHAPT ER INTRODUCTION AND REVIEW i一32

General Descr」pt-ion

2 Defin」t-ions and preliminary concept8 Stochastic process

Markov process

B」rth and death process Laplace transformation (e)Queue」ng process

3 1」terature review

Theoretical developments of birth and death process

biology

queueing theory

CHAPTER 2 TRANSIENT ANALYSIS OF FINITE STATE

BIRTH AND DEATH PROCESS WITH REFLECTING

BOUNDARY STATES 33-79

Introduction

2.2 Differential difference equations and Lap i ace transforms

2.3 Analysis of the matrix

1■1 も11 も11 』11 a b C d 11も ー旦1 一1も 11叫 も11 も11 血11 a b C 11も 11も 11も

Birth and Birth and

death death

process process

n n 11 ・『1 ・

1』 ・

し ・

L

2 .5 2.6

App) icat ions in Appi icat」ons i n Explicit

transi ent express」on for Laplace transform and state

2.4

probab」^lities genet」Cs

general biology

O 5 6 6

78

0 2 8 8

97 103 105 CHAPTER 3 BIRTH AND DEATH QUEUEING MODELS 80一142

3 Introduction

3.2 Double一ended queue 3.3 H/M/i/N model

3.4 HIM/c/N queue with homogeneous servers 3.5 M/M/c/c loss system

3.6 Waiting time distribution of Markovian queues 107 3.7 Numerical results and conclusions 117

CHAPTER 4 FINITE STATE BIRTH AND DEATH PROCESS WITH

ABSORBING BOUNDARY STATES 143一203

4 Introducti on i 43

4.2 Process with state O as absorb」ng and state

N as reflecting 144

(a)Derivation of transient state probabilities 144 (b)Probability distribution of the time of

absorption 152

(C)Busy period distributions of finite

capacity Markovian queues i 55 (d)Modelling of spread of an epidemic in a

finite population ¹⁶¹

(e)Linear growth model without immigration ¹⁶⁵

'v

4.3 Process with state N as absorbing and state

o as reflecting 168

(a) Derivation of trans_」en、t state probabli」ties 168 (b) Probability d」stribution of time of

absorption and its moments 175 (C) Process w」th constant birth and death rates 176 (d) Busy period distribution of double一ended

queue 119

4.4 Process w」th both boundary states as

absorbi ng 183

A simple model for incubation period 197 4.5 Nun馴ョrical Illustrations i 99

CHAPTER 5 FIRST PASSAGE TIME AND OTHER PARAMETERS OF FINITE STATE BIRTH AND DEATH PROCESS 204-234

5. i Introduction 204

5.2 Process w」th both boundary states as

reflecting 207

5.3 Process with state O as absorbing and state

N as reflecting 214

5.4 Process with state O as reflecting and state

N as absorbing 221

5.5 Process with both the boundary states as

absorbing 226

BIBL IOGRAPHY 235

v