Birth-death processes

J. Virtamo

38.3143 Queueing Theory / Birth-death processes

1

Birth-death processes

General A birth-death (BD process) process refers to a Markov process with

- a discrete state space - the states of which can be enumerated with index i=0,1,2,. . . such that - state transitions can occur only between neighbouring states, i i + 1 or i i - 1

l0

l1

l2

0

1

2

...

m1

m2

m3

li

l i+1

i

i+1

m i+1

m i+2

Transition rates

qi,j

=

i ?i 0

when j = i + 1

if

j =i-1

otherwise

probability of birth in interval t is it probability of death in interval t is ?it when the system is in state i

J. Virtamo

38.3143 Queueing Theory / Birth-death processes

2

The equilibrium probabilities of a BD process We use the method of a cut = global balance condition applied on the set of states 0, 1, . . . , k. In equilibrium the probability flows across the cut are balanced (net flow =0)

kk = ?k+1k+1

k = 0, 1, 2, . . .

We obtain the recursion

k+1

=

k ?k+1

k

By means of the recursion, all the state probabilities can be expressed in terms of that of the state 0, 0,

k

=

k-1k-2 ? ? ? 0 ?k?k-1 ? ? ? ?1

0

=

k-1 i=0

i ?i+1

0

The probability 0 is determined by the normalization condition 0

0

=

1

+

0 ?1

+

1 01 ?1?2

+

???

=

1

+

1

k-1

k=1 i=0

i ?i+1

J. Virtamo

38.3143 Queueing Theory / Birth-death processes

3

The time-dependent solution of a BD process

Above we considered the equilibrium distribution of a BD process.

Sometimes the state probabilities at time 0, (0), are known - usually one knows that the system at time 0 is precisely in a given state k; then k(0) = 1 and j(0) = 0 when j = k

and one wishes to determine how the state probabilities evolve as a function of time (t) - in the limit we have limt (t) = .

This is determined by the equation

ddt(t) = (t) ? Q

where

-0

?1

Q

=

0

... ...

0 -(1 + ?1)

?2 0 ...

0

1 -(2 + ?2)

?3 0

... 0 2 -(3 + ?3) ?4

...

...

0

3

-(4 + ?4)

J. Virtamo

38.3143 Queueing Theory / Birth-death processes

4

The time-dependent solution of a BD process (continued)

l0 0

m1

l1 1

m2

l2 2

m3

l i-1

...

i

mi

li i+1

m i+1

l i+1 m i+2

The equations component wise

di(t) dt

= -(i + ?i)i(t) + i-1i-1(t) + ?i+1i+1(t)

flows out

flows in

d0(t) dt

=

-00(t) + ?11(t) flow out flow in

i = 1, 2, . . .

J. Virtamo

38.3143 Queueing Theory / Birth-death processes

5

Example 1. Pure death process

i = 0 ?i = i?

i = 0, 1, 2, . . .

all individuals have the same mortality rate ?

i(0)

=

1 0

i=n i=n

the system starts from state n

0 m

1

2

...

n-1

n

2m

3m

(n-1) m n m

State 0 is an absorbing state, other states are transient

d dt

n(t)

=

-n?n(t)

d dt

i(t)

= (i + 1)?i+1(t) - i?i(t)

n(t) = e-n?t i = 0, 1, . . . , n - 1

d dt

(ei?ti(t))

=

(i + 1)?i+1(t)ei?t

i(t)

=

(i + 1)e-i?t?

t 0

i+1(t

)ei?t

dt

n-1(t)

=

ne-(n-1)?t?

t 0

e-n?t

e(n-1)?t

dt

= n e-(n-1)?t(1 - e-?t)

e-?t

Recursively

i(t) = ni (e-?t)i(1 - e-?t)n-i

Binomial distribution: the survival probability at time t is e-?t inde-

pendent of others

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download