STAT 380 Lecture 19
End of Summary for Continuous Time Markov Chains:
In this case we write 
for the instantaneous
``birth'' rate:
and 
for the instantaneous
``death'' rate:
We have
then process is a pure birth process.
If all 
a pure death process. 
Necessary condition for existence of 
is
In this case
provided 
.
Detailed development
Suppose X a Markov Chain with stationary transitions. Then
This shows
which is the Chapman-Kolmogorov equation.
Now consider the chain starting from i and let 
be
the first t for which 
. Then is
a stopping time.
[Technically:
for each t.] Then
by the Markov property.
Conclusion: given X(0)=i, has memoryless porperty
so has an exponential distribution. Let 
be the
rate parameter.
Embedded Chain: Skeleton
Let 
be the stopping times at which
tranisitons occur. Then
. The sequence 
is a Markov chain by the
Markov property. That 
reflects the fact
that 
by design.
As before we say 
if 
for some t.
It is fairly clear that for the X(t) if and only
if for the embedded chain .
We say 
(i and j communicate) if and 
.
Now consider
Suppose the chain has made n transitions so far so that
. Then the event X(t+h)=j is, except
for possibilities of probability o(h) the event that
The probability of this is
Kolmogorov's Equations
The Chapman-Kolmogorov equations are
Subtract 
from both sides, divide by h and let 
.
Remember that 
is the identity.
We find
which gives
The Chapman-Kolmogorov equations can also be written
Now subtracting from both sides, dividing by h and letting
gives
Look at these equations in component form:
becomes
For 
our calculations of instantaneous transition
rates gives
For i = k we have
(X(h)=i either means 
which has probability
or there have been two or more transitions in
[0,h], a possibility of probability o(h).)
Thus
Let 
be the matrix with entries
is the infinitesimal generator of the chain.
Thus
becomes
Called Kolmogorov's backward equations.
On the other hand
becomes
These are Kolmogorov's forward equations.
Remark: When the state space is infinite the forward equations may not be justified. In deriving them we interchanged a limit with an infinite sum; the interchange is always justified for the backward equations but not for forward.
Example: 
. Then
and the chain is otherwise specivied by 
and 
. The matrix
is
The backward equations become
while the forward equations are
Add first and third backward equations to get
so
Put t=0 to get 
. This gives
Plug this back in to the first equation and get
Multiply by 
and get
which can be integrated to get
Alternative calculation:
can be written as
where
and
Then
Now
so we get
where
Notice: rows of 
are a stationary initial distribution. If rows are
then
so
Moreover
Fact: 
is long run fraction of time in
state 0.
Fact:
Ergodic Theorem in continuous time.
Birth and Death Processes
Consider a population of X(t) individuals. Suppose
in next time interval (t,t+h) probability of population
increase of 1 (called a birth) is 
and
probability of decrease of 1 (death) is 
.
Jargon: X is a birth and death process.
Special cases:
All ; called a pure birth process.
All (0 is absorbing): pure death process.
and 
is a linear
birth and death process.
, 
: Poisson Process.
and is a linear
birth and death process with immigration.
Queuing Theory
Ingredients of Queuing Problem:
1: Queue input process.
2: Number of servers
3: Queue discipline: first come first serve? last in first out? pre-emptive priorities?
4: Service time distribution.
Example:
Imagine customers arriving at a facility at times of a Poisson
Process N with rate 
. This is the input process,
denoted M (for Markov) in queuing literature.
Single server case:
Service distribution: exponential service times, rate 
.
Queue discipline: first come first serve.
X(t) = number of customers in line at time t.
X is a Markov process called M/M/1 queue:
Example: 
queue:
Customers arrive according to PP rate . Each
customer begins service immediately. X(t) is number
being served at time t. X is a birth and death process
with
and
