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乙edDepcvztment 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. IACKNαりLEDGEMENTS
I e xp
九e
るる my 'Lee p oも 9ル叫しU山cLe to P九o4. O.P. SIw九mou. Hebeen
anext
九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"た乙adu
九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-nythe
るta6
る oる -theImm.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 ya-u
de-6eitvea.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, andInj:Ua.n
Inるtえtu-teo'
Techno乙099, De.e.hえ 40九 the corn p-te-t2on o' -tん心6t
んe
ム1
るTんえる -.tudy
enc.
え・oc.c.hed
a. 乙0-t oも the -tんme I -6 ho u2t ん工veo-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九etu1n
たる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
一
α.
te i
e ,os n<k N 一α t
=nk + こ Bk .eki n=k
=i
N 一α_ t
=n
n
+;'_
k \k k_ +1
… i'
-. n一i乞
Bi=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-
1UIU
, 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
昭
anderive 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 lk1でて二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.Lone 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._
Ki
.入 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 11
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 161
(e)Linear growth model without immigration 165
'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