Transcript Continuous Time Markov Chains

Continuous Time Markov Chains
Birth and Death Processes,Transition Probability
Function, Kolmogorov Equations, Limiting
Probabilities, Uniformization
Chapter 6
1
Markovian Processes
State Space
Discrete
Parameter
Space (Time)
Discrete
Continuous
Continuous
Markov chains
(Chapter 4)
Continuous time Brownian
Markov chains motion process
(Chapters 5, 6) (Chapter 10)
Chapter 6
2
Continuous Time Markov Chain
A stochastic process {X(t), t  0} is a continuous time Markov
chain (CTMC) if for all s, t  0 and nonnegative integers i,
j, x(u), 0  u < s,


P X  s  t   j X  s   i, X  u   x  u  , 0  u  s


 P X s  t   j X s  i
and if this probability is independent of s, then the CTMC has
stationary transition probabilities:
Pij  t   P  X  s  t   j X  s   i for all s
Chapter 6
3
Alternate Definition
Each time the process enters state i,
The amount of time it spends in state i before making a
transition to a different state is exponentially distributed
with parameter vi, and
When it leaves state i, it next enters state j with probability
Pij, where Pii = 0 and  j Pij  1
Let
qij  vi Pij , then vi   j qij ,
Pij  h 
1  Pii  h 
lim
 vi and lim
 qij
h 0
h 0
h
h
Chapter 6
4
Birth and Death Processes
If a CTMC has states {0, 1, …} and transitions from state n
may go only to either state n - 1 or state n + 1, it is called a
birth and death process. The birth (death) rate in state n is ln
(mn), so v0  l0
vi  li  mi , i  0
P01  1
Pi ,i 1 
lo
0
1
m1
li
li  mi
l1
m2
, Pi ,i 1 
mi
li  mi
2
,i 0
ln-1
n-1
Chapter 6
ln
n
mn
n+1
mn+1
5
Chapman-Kolmogorov Equations
“In order to get from state i at time 0 to state j at time t + s,
the process must be in some state k at time t”

Pij  t  s    Pik  t  Pkj  s 
k 0
From these can be derived two sets of differential equations:
“Backward” Pij  t    qik Pkj  t   vi Pij  t 
k i
“Forward”
Pij  t    qkj Pik  t   v j Pij  t 
k j
Chapter 6
6
Limiting Probabilities
If
• All states of the CTMC communicate: For each pair i, j,
starting in state i there is a positive probability of ever
being in state j, and
• The chain is positive recurrent: starting in any state, the
expected time to return to that state is finite,
then limiting probabilities exist: Pj  lim Pij  t 
t 
(and when the limiting probabilities exist, the chain is called ergodic)
Can we find them by solving something like p = p P for
discrete time Markov chains?
Chapter 6
7
Infinitesimal Generator (Rate) Matrix
 qij , if i  j
Let R be a matrix with elements rij  
vi , if i  j

(the rows of R sum to 0)
Let t   in the forward equations. In steady state:
lim Pij  t   lim  qkj Pik  t   v j Pij  t 
t 
t 
k j
0   qkj Pk  v j Pj
k j
These can be written in matrix form as PR = 0 along with j Pj  1
and solved for the limiting probabilities.
What do you get if you do the same with the backward equations?
Chapter 6
8
Balance Equations
The PR = 0 equations can also be interpreted as balancing:
v j Pj   qkj Pk
k j
rate at which process leaves j  rate at which process enters j
For a birth-death process, they are equivalent to levelcrossing equations ln Pn  mn1Pn1
rate of crossing from n to n  1  rate of crossing from n  1 to n
so P  l0 l1 ln 1 P and a steady state exists if

n
0
l0l1 ln1
m1m 2 m n

mm
n 1
Chapter 6
1
2
mn
9
Time Reversibility
A CTMC is time-reversible if and only if Pq
i ij  Pj q ji when i  j
There are two important results:
1. An ergodic birth and death process is time reversible
2. If for some set of numbers {Pi},
 i Pi  1 and
Pq
i ij  Pj q ji when i  j
then the CTMC is time-reversible and Pi is the limiting
probability of being in state i.
This can be a way of finding the limiting probabilities.
Chapter 6
10
Uniformization
Before, we assumed that Pii = 0, i.e., when the process leaves
state i it always goes to a different state. Now, let v be any
number such that vi  v for all i. Assume that all transitions
occur at rate v, but that in state i, only the fraction vi/v of them
are real ones that lead to a different state. The rest are
fictitious transitions where the process stays in state i.
Using this fictitious rate, the time the process spends in state i
is exponential with rate v. When a transition occurs, it goes to
state j with probability
 vi
1 , j  i

 v
*
Pij  
 vi P , j  i
 v ij
Chapter 6
11
Uniformization (2)
In the uniformized process, the number of transitions up to
time t is a Poisson process N(t) with rate v. Then we can
compute the transition probabilities by conditioning on N(t):


Pij  t   P X  t   j X  0   i




  P X  t   j X  0   i, N  t   n P N  t   n X  0   i
n 0
e  vt  vt 
  P X  t   j X  0   i, N  t   n
n!
n 0


e  vt  vt 
  Pij
n!
n 0


n
n
*n
Chapter 6
12
More on the Rate Matrix
Can write the backward differential equations as P  t   RP  t 
and their solution is P  t   P  0 eRt  eRt since P  0  I
n

where Rt
t
n
e  R
n 0
n!
but this computation is not very efficient. We can also
approximate:
t

e  lim  I  R 
n 
n

Rt
n

t
or e   I  R 
n

Rt
Chapter 6
1 n

 for large n

13