,1 Introduction CTMC
A Continuous Time Markov Chain (CTMC) on a countable state space S is a process {X(t), t ≥ 0},
opposed to a sequence like a DTMC. Meaning that there are no self loops. Where X(t) is the state at
time t and t ∈ R.
Figure 1: Visual representation of a possible trajectory for a CTMC
When arriving in state i, for each state j and clock starts that represents the time until a transition to
state j is made from state i. These times are independent Exponential distributions Exp(q Pij ), where
qij is the transition rate from state i to state j and the (total) rate out of state i is νi := j qij .
A transition will be made when the first exponential clock runs out. Thus the time spent in state i is:
X
min(Exp(qij )) ∼ Exp( qij )
j
qij
and state j is the next state with probability νi .
Note that it is impossible for two exponential clocks to run out at the same time. P (Exp1 (µ) =
Exp2 (µ)) = 0
Theorem 1.1. A process as described automatically satisfies the Markov property for all times
t0 < t1 < · · · < tn < tn+1 and all states i, j, i1 , . . . , in−1 ∈ S,
Additionally, the transition rates qij are independent of t causing CTMC automatically to be Time-
homogeneous.
P (X(t) = j|X(s) = i) = P (X(t − s) = j|X(0) = i)
The checklist for formulating a CTMC:
• State X(t) := . . . at time t
• Specify the state space and the transition rates (give the transition diagram with the transition
rates when convenient).
• Motivate that all transition times are Exponential and specify how they where established
Example - Machine reliability with 2 machines
Two machines are used in production. Each of the two machines lasts for an Exp() stretch of
time before it gets broken. Once it gets broken it immediately goes into repair for an Exp(µ)
amount of time. After a repair the machine is immediately in use again before it gets broken
again. The up-times and repair-times are all independent.
Argue X(t) = number of functioning machines at time t is a CTMC.
2
, S = {0, 1, 2}
λ 2λ
0 1 2
2µ µ
• 1 → 2: When the repair time of the broken machine is over, Exp(µ)
• 1 → 0: When the working machine breaks, Exp(λ)
• 0 → 1: When the repair time of one of the broken machines is over,
min[Exp1 (µ), Exp2 (µ)] = Exp(2µ)
• 2 → 1: When one of the two working machines brakes,
min[Exp1 (λ), Exp2 (λ)] = Exp(2λ)
• 2 → 0: Not a possible transition, because it is impossible that both machines break at
exactly the same time.
Example - M/M/2/4
Customers arrive according to a P P (λ). There are 2 servers and 2 spots in the waiting
room. When both servers are bussy an arriving customer is willing to wait with probability p,
independently of other customers. When the waiting room is full the customer will not enter.
The service times of the customers are i.i.d. Exp(µ). The servers don’t idle, ie serve customers
back to back as long as there are customers in the system.
Formulate an appropriate CTMC.
X(t) := the number of customers in the system at time t.
S := {0, 1, 2, 3, 4}
Customers arrive according to a P P (λ), which means that the inter arrival time of these
customers are Exp(λ). It is given that the service times are Exp(µ).
Possible transitions:
• 4 → 3: When one of the two working servers is finished. min[Exp1 (µ), Exp2 (µ)] =
Exp(2µ)
• 3 → 2: When one of the two working servers is finished. min[Exp1 (µ), Exp2 (µ)] =
Exp(2µ)
• 2 → 1: When one of the two working servers is finished. min[Exp1 (µ), Exp2 (µ)] =
Exp(2µ)
• 1 → 0: When the working server is finished. Exp(µ)
• 0 → 1: When a customer arrives. Exp(λ)
• 1 → 2: When a customer arrives. Exp(λ)
• 2 → 3: When a customer that is willing to wait arrives. Exp(pλ)
• 3 → 4: When a customer that is willing to wait arrives. Exp(pλ)
Voordelen van het kopen van samenvattingen bij Stuvia op een rij:
Verzekerd van kwaliteit door reviews
Stuvia-klanten hebben meer dan 700.000 samenvattingen beoordeeld. Zo weet je zeker dat je de beste documenten koopt!
Snel en makkelijk kopen
Je betaalt supersnel en eenmalig met iDeal, creditcard of Stuvia-tegoed voor de samenvatting. Zonder lidmaatschap.
Focus op de essentie
Samenvattingen worden geschreven voor en door anderen. Daarom zijn de samenvattingen altijd betrouwbaar en actueel. Zo kom je snel tot de kern!
Veelgestelde vragen
Wat krijg ik als ik dit document koop?
Je krijgt een PDF, die direct beschikbaar is na je aankoop. Het gekochte document is altijd, overal en oneindig toegankelijk via je profiel.
Tevredenheidsgarantie: hoe werkt dat?
Onze tevredenheidsgarantie zorgt ervoor dat je altijd een studiedocument vindt dat goed bij je past. Je vult een formulier in en onze klantenservice regelt de rest.
Van wie koop ik deze samenvatting?
Stuvia is een marktplaats, je koop dit document dus niet van ons, maar van verkoper havikjavanas. Stuvia faciliteert de betaling aan de verkoper.
Zit ik meteen vast aan een abonnement?
Nee, je koopt alleen deze samenvatting voor €13,49. Je zit daarna nergens aan vast.
