Business Simulation Exam
ADM 3305 Business Simulation Analytics
Simulation of Stochastic Processes
Continuous Time Markov Chains
© 2020 Antoine Sauré
All forms (printed, digital, etc.) of course materials prepared by the instructor (including e-mailed or Brightspace content) are protected by copyright. This covers all files, assessments, solutions, cases, recordings and other materials. Copying, scanning, photographing, posting, or sharing by any means is a violation of copyright and will be subject to appropriate penalty as prescribed by University of Ottawa regulation.
Based on “Discrete time Markov chains” lecture notes by X. Xie (2012).
1
Last Two Lectures
Stochastic Processes
Discrete Time Markov Chains (DTMCs)
Basic definitions
Classification
Steady-state Probabilities (Analysis)
Simulation of DTMCs
Today’s Lecture
Continuous Time Markov Chains (CTMCs)
Basic definitions
Steady-state Analysis
Simulation of CTMCs
Learning goal:
By the end of this lecture, you will have a good feel for how CTMCs work and an idea of the things you can do with them
Continuous Time Markov Chains
Discrete Time Markov Chain (DTMC)
Stochastic process
Discrete
event
Continuous event
Discrete
time
Continuous time
Memoryless
A CTMC is a continuous time and memoryless discrete event stochastic process
Memoryless
5
Continuous Time Markov Chain (CTMC)
Definition: A stochastic process with discrete state space and continuous time {X(t), t > 0} is a Continuous Time Markov Chain (CTMC) if and only if:
P[X(t + s) = j|X(u), 0 ≤ u ≤ s] = P[X(t + s) = j |X(s)] ∀ t, s, j
Memoryless Property:
In a CTMC, the past history impacts the future evolution of the system via the current state of the system
Continuous Time Markov Chain (CTMC)
Poisson Arrivals
Exponential service time
N(t) : number of customers at time t
Customer Arrivals
Customer Departures
Homogeneous CTMCs
Definition: A CTMC {X(t), t > 0} is homogeneous if and only if:
P[X(t + s)= j|X(t) = i] = pij(s)
Practical interpretation of the memoryless property:
In reliability, "a machine that does not fail at age t is as good as new"
We will only consider homogeneous CTMC
Behavior of a CTMC
Two major components:
Ti = sojourn time in state i (random variable)
pij = probability of moving to state j after leaving state i
X(t)
Sojourn Times
Let Ti be the random variable corresponding to the time spent in state i
The memoryless property of the homogeneous CTMC implies that:
The exponential distribution is the only continuous probability distribution having this property
In a CTMC, the sojourn time in any state is exponentially distributed
The Exponential Distribution
Let T be a continuous random variable with an exponential distribution of parameter l
l corresponds to the event rate (e.g., arrival rate, failure rate, repair rate, production rate, etc.)
Cumulative probability distribution and density function:
Mean: E[T] = 1/l; standard deviation: s[T] = 1/l; coefficient of variation: Cv(T) = s[T]/E[T] = 1
FT(t) = P{T ≤ t}
fT(t) = dFT(t)/dt
11
The Exponential Distribution
Memoryless property:
For a machine with exponentially distributed lifetime, we say that it is "as good as new" if it is not failed
The remaining lifetime of an used but UP machine has the same distribution as a new machine
FT(t) = P{T ≤ t}
fT(t) = dFT(t)/dt
12
Transition Probabilities
When a CTMC leaves state i, it jumps to state j with probability pij
This probability is independent of:
Time as we consider homogeneous CTMC
Sojourn time Ti as the process is Markovian (i.e., memoryless property)
Characterization of a CTMC
A CTMC is fully characterized by:
{mi}i E where mi is the parameter of the exponential distribution of sojourn time Ti
{pij}i ≠ j where pij is the transition probability from state i to state j when leaving state i
Classification of CTMCs
Each CTMC is associated with an underlying DTMC by ignoring the sojourn times
A state i of a CTMC is said transient (recurrent or absorbing) if it is transient (recurrent or absorbing) in the underlying DTMC
A CTMC is irreducible if its underlying DTMC is irreducible
The concept of periodicity is not relevant in this case
Alternative Characterization of a CTMC
In each state, several potential events can happen leading to different transitions
A CTMC transitions from state i to state j in Tij time units, where Tij is an exponentially distributed random variable with parameter mij
The parameter mij is called the transition rate from state i to state j
Equivalence of the Characterizations
Let Ti = Minj {Tij} and pij = P{Tij = Ti}
Ti is exponentially distributed with parameter and pij is independent of Ti
Steady State Distribution of a CTMC
For an irreducible CTMC with positive recurrent states, the probability distribution converges to a vector of stationary probabilities (p1, p2, ...) that is independent of the initial distribution p(0). Further it is the unique solution of the following equation system:
Sj ≠ i pjmji = Sj ≠ i pimij and Sj pj = 1
Probability flow balance equation:
Sj ≠ i pjmji is the total flow into state i and Sj ≠ i pimij the total flow out of state i
Total flow in = Total flow out
Example: A Manufacturing System
A system consists of three machines and two repairmen. At most two machines can operate at any time. The amount of time that an operating machine works before breaking down is exponentially distributed with mean 5 days. The amount of time that it takes a single repairman to fix a machine is exponentially distributed with mean 4 days. Only one repairman can work on a failed machine at any given time.
Let X(t) be the number of machines in operating condition at time t. Model X(t) as a continuous time Markov chain by providing the corresponding graphical representation.
Example: Memoryless Property and Sojourn Times
A system has two components: A and B. The operating times until failure of the two components are independent and exponentially distributed random variables with parameters λ = 2 for component A and μ = 4 for component B. Assume rates are per year. The system fails at the first component failure.
What is the mean time to failure for component A?
What is the mean time to failure for component B?
What is the mean time to system failure?
What is the probability that it is component A that causes system failure?
Suppose that it is component A that fails first. What is the mean remaining operating life of component B?
20
Example: A Call Center
A ticket office has two agents answering incoming phone calls. In addition, a third caller can be put on HOLD until one of the agents becomes available. If all three phone lines (both agent lines plus the hold line) are busy, a potential caller gets a busy signal, and is assumed lost. Suppose that the calls and attempted calls occur according to a Poisson process of rate 30 calls/hour, that the length of a telephone conversation is exponentially distributed with mean 3 minutes, and that the agents work 8 hours per day.
Model the evolution of the number of phone lines that are busy as a continuous time Markov chain by providing the corresponding graphical representation.
Simulate the evolution of the number of phone lines that are busy for a minimum of 10 one-day replications. Assume that no phone lines are in use at the beginning of the day.
Example: A Call Center
Based on your simulation results, answer the following questions:
What percentage of the phone calls will be lost?
What is the average holding time for those calls that get through?
Determine the stationary (i.e., steady state) probabilities for this process and answer the questions in part c) based on your results. Explain any differences.
Simulation of CTMCs
Simulating CTMC up to time t = T, where t is the latest time that a transition takes place
23
Simulation of CTMCs
The time it takes to make a transition from the state i can be described by an exponential distribution
Thus, to simulate a CTMC, we simulate:
1) when the transition takes place
2) where it transitions to
24
25
{
}
{
}
¨,,
iii
PTtxTtPTxtx
³+³=³""
(
)
1,0
0,0
t
T
et
Ft
t
l
-
ì
-³
=
í
<
î
(
)
,0
0,0
t
T
et
ft
t
l
l
-
ì
³
=
í
<
î
{
}
{
}
{
}
(
)
{
}
¨
1
ts
t
s
t
PtTts
PTtsTt
PTt
ee
ePTs
e
l
l
l
l
-+
-
-
-
££+
£+³=
³
-
==-=£