Continuous-Time Markov Chains
Thirteen modules on continuous-time Markov chains and on what happens when their rates come in two very different sizes: fast mixing inside groups of states, slow movement between them. Run the chains, change the rates and the small parameter ε, watch the equations solve themselves, then check yourself with concept questions and practice problems.
Follows the chapter order of G. G. Yin and Q. Zhang, Continuous-Time Markov Chains and Applications: A Two-Time-Scale Approach, 2nd ed. (Springer, Stochastic Modelling and Applied Probability 37, 2013), covering all ten chapters. Chapter numbers refer to that book; the questions, examples and models here are written for this page.
Generators and sample paths
A continuous-time Markov chain on finitely many states is determined by one matrix, its generator
The idea
The transition matrix
Why two time scales. In the systems the book has in mind (machines that fail and get repaired, queues, networks, economic regimes) some rates are much larger than others. Writing the generator as
Explore
Worked example
Take the generator
Describe how the chain moves, find its stationary distribution, and compare the fraction of time in each state with the fraction of jumps into it.
What are the mean holding times in states 1, 2, 3?
The leaving rates are
, so the mean holding times are .Write down the transition matrix of the jump chain.
Divide each off-diagonal entry by its row's leaving rate and put zeros on the diagonal:
From state 2 the chain always returns to 1.
Solve
, .The third column gives
, so . The first column gives , so . The second column, , checks out. Normalising,The jump chain has its own stationary distribution
(with ). How is it related to ?The chain enters state
at long-run rate (time fraction times leaving rate), so :Check:
. State 1 gets the most jumps but state 2 holds the most time, because the chain lingers there.
Check your understanding
Row
- Probability
; mean wait . - Probability
; mean wait .The holding time is exponential with rate 4. Its mean is the reciprocal of the rate. - Probability
in a short time ; there is no single "next jump" probability. is the chance of a jump to state 3 within time . Conditioned on a jump happening, the destination has a fixed distribution.
Why must every row of a generator sum to zero?
- Because the stationary distribution satisfies
. is a statement about the columns, weighted by . It is a property of one special vector, not of the rows. - Because each row of
sums to 1 for all ; differentiate at . - Because probabilities are nonnegative.Nonnegativity is why the off-diagonal entries are
. It says nothing about the sum.
Chain A has generator
- B has a different stationary distribution, ten times larger.
: the same solves both systems, and it must still sum to 1. - B has a different jump chain.The jump probabilities are ratios
; multiplying every rate by 10 cancels. - Same jump chain and same
, but B runs ten times faster: has the law of .
Practice
The two-state chainAn explicit transition matrix
A two-state chain jumps
Hint
Solution
The equation
Both rows tend to
From the martingale to the forward equationTaking expectations
Let
Solution
For
Differentiating gives
The forward equation and irreducibility
The distribution of a Markov chain solves a linear differential equation,
The idea
Explore
Worked example
A two-state chain has time-varying rates:
Find
. When is weakly irreducible, and when irreducible? reads , so . This needs (weak irreducibility); both entries are positive when both rates are positive (irreducibility).Write the forward equation for
alone.Using
:Solve it when the rates are constant.
The gap to
closes at rate , the absolute value of the nonzero eigenvalue of .Now let the rates vary. What equation does the gap
satisfy, and what does it say?Since
, the equation becomes , soThe chain is pulled toward
at rate while moves away at speed . If the rates are and , then does not depend on , the pull wins, and settles near , which is . That small lag is exactly what Module 4 computes.
Check your understanding
- Yes: state 1 is transient, so its stationary probability is 0 and
. is a solution, but is it the only one? Look at state 3. - No:
solves for every . - Yes, because
has rank .Two rows of are zero and the first is nonzero, so the rank is 1, not 2.
In the "Cyclic" example the path of
- The chain is periodic.A continuous-time chain is never periodic:
for every . has a pair of complex eigenvalues , so contains terms and .- Rounding error in the numerical solution.The spiral is real. Try smaller and smaller steps and it stays.
- Yes, because
is stationary. would be stationary for a chain whose rates stayed frozen at time . Here they keep moving. - No:
lags behind , unless happens to be constant.
Practice
The solvability conditionOne direction of the Fredholm alternative
Let
Solution
Why is a stochastic matrixPositivity without probability
Show directly from the matrix exponential that
Hint
Choose
Solution
Birth–death chains and a finite queue
Most Markov models are built by listing what can happen next and at what rate. In a birth–death chain the state only moves up or down by one, and that is enough to solve for the stationary distribution in closed form. Here it is for a queue with a waiting room of size
The idea
The book's catalogue of models goes on: system reliability (components failing and being repaired), competing risks, Cox processes, random evolutions, seasonal models, and chains inside optimisation algorithms and controlled systems. The common thread is time-scale separation: in each, some rates are naturally much larger than others, and
Explore
Worked example
Two identical machines each fail at rate
Write the generator.
With 0 failed, two machines can fail: rate
. With 1 failed, one can fail (rate ) or the repair finishes (rate ). With 2 failed, only repair (rate ):Use detailed balance to express
in terms of . and .Normalise with
, and give the availability. , and the entries sum to , so . Availability .Suppose repairs are much faster than failures:
. How does the downtime scale? . A machine is under repair a fraction of the time, and the second one must fail during that short repair, which has probability . Fast repairs make the chain spend almost all its time in state 0: a first glimpse of a two-time-scale model.
Check your understanding
In the finite queue, take
- There is none: the queue is critically loaded.That is true for an infinite waiting room. With room for only
customers the chain is finite and irreducible. - Uniform:
. - Concentrated at
.Detailed balance with gives : no state is preferred.
Why does the fraction of arrivals that are turned away equal
- Because the server is idle exactly
of the time.True, but that is about state 0. What is special about the moments when customers arrive? - Arrivals come from a Poisson process independent of the past of the queue, so the state an arrival sees has the time-stationary distribution.
- It doesn't: arrivals are more likely when the queue is short.Here the arrival rate is
in every state, so arrivals do not prefer any state.
A birth–death chain on
- Always.
- Only when
for all .That is the special case of a uniform . Detailed balance only needs , which can always be arranged. - Only for the finite queue.The cut argument uses nothing about the particular rates.
Practice
A tiny queue by handLittle's law
Take
Solution
Zero flow across a cutDeriving detailed balance
For a birth–death chain with stationary
Solution
A fast chain: outer expansion and initial layer
Speed a chain up by a factor
The idea
Let
Outer terms. Substitute and match powers of
with
Initial layer. In the stretched time,
which decays like
Explore
Two states. Rates
Worked example
For the two-state chain of the explorer, with rates
What is
?The quasi-stationary distribution:
. With , .Find
.A zero-sum row vector
times is , soIn the explorer
and .Solve
with .Write
. Then and , soWhen
rises, sits slightly below it: the chain lags behind its moving target by about , as in Module 2.Evaluate at
, where and . and , so . For : . The explorer's last two boxes compare this with the exact value.
Check your understanding
Why can't the outer expansion
is forced by ; it is not free to equal .- It can, if enough terms are kept.Every
with carries a factor . No combination of them can close an gap . - Because the outer terms are not smooth at
.They are as smooth as . The trouble is their value at 0, not their smoothness.
- Like
.The layer lives on the fast time . - Like
.The fast mode dies first. What is left after that? - Like
(for a typical ).
Suppose
exactly for all .Only if is constant. Otherwise the chain lags behind its moving target. , but is still of order .- The error becomes
.The term is still there; only the zeroth-order layer disappeared.
Practice
Constant generatorsWhen the expansion terminates
If
Solution
Uniform away from zeroReading the error bound
Use the
Solution
Weak and strong interactions
Now the fast part of the generator splits the states into groups that do not communicate, and a slow part moves the chain between groups. Inside each group the distribution equilibrates almost at once. The weights of the groups follow a smaller Markov chain whose generator is an average of the slow rates.
The idea
So
Explore
Fast rates:
Worked example
Compute everything the explorer uses:
Find
and .For a two-state block with rates
(first to second) and (back), . So and .Compute
and . and . SoSolve for
with .By the two-state formula from Module 1,
and .What is the stationary distribution of the full chain, to leading order in
?Let
in the leading term: , soA direct computation with
gives , against here. The 4-state problem has been reduced to three 2-state problems: one for each group, and one for the aggregated chain.
Check your understanding
Group 1 has
- 2That is the rate from
only. The chain spends half of its group-1 time in , where it cannot leave. - 1
- 0, the smaller rateThe aggregated rate is an average, not a minimum.
In the right-hand plot the group probabilities show no fast transient at the start, even when the chain starts in a single state. Why?
is block diagonal, so the fast dynamics only move probability inside a group; each group's total changes at rate .- Because
sums to 1.That is true but says nothing about time evolution. What does do to the total mass of a group? - They do have one, it is just too small to see.At leading order it is exactly zero:
.
What happens if
converges to a unique stationary distribution.With the groups never communicate, so the chain is not irreducible. stays at its initial value: the group weights are frozen, and inside each group the distribution tends to .- The theorem fails.It still applies, with
.
Practice
is a generatorTwo lines
Show that
Solution
For
Where comes fromAveraging the forward equation
Multiply the forward equation
Solution
Since
Transient and absorbing states
Add states that the fast dynamics leaves and never returns to. Their probability dies out within a time of order
The idea
Read
Explore
Recurrent group
Worked example
For the chain in the explorer, compute the exit probabilities
Write
and check that it is Hurwitz.On
: . Its row sums are and , so each diagonal entry outweighs the rest of its row and, by Gershgorin's theorem, every eigenvalue has negative real part. (They are and .)Find
by a first-step argument.From
: with probability go straight to , with to . From : to , to , to . So and , giving , . This is written out; and .Starting in
, what is ? . The explorer's right panel shows the mass settling to these levels within a few multiples of .Compute
and . . From : is a direct change of group, weight ; changes group only if the chain then exits to , weight . So . From : , then on to with probability : .
Check your understanding
A transient state
The two exits are not equally likely: they race at rates 3 and 1. These are rates; is a probability vector.
Transient states have probability
- That would be fine: states with vanishing probability cannot matter.Small probability is not the same as small flow. Slow jumps into transient states happen at rate
. - Slow jumps into transient states happen at rate
, and a fraction of them end in a different group; dropping them loses real group changes. - Because
would no longer be invertible.Deleting the states removes altogether. The problem is what happens to .
For
- exactly 0.The slow part keeps feeding the transient states.
- of order
: fed at rate by slow jumps, drained at rate . - decaying like
.The drain is fast, on the scale , but the feed never stops.
Practice
Two absorbing statesA slow leak back
States 1 and 2 are absorbing for the fast part; state 3 is transient with fast rates 1 into state 1 and 2 into state 2. Slowly, state 1 jumps to 3 at rate
Solution
The exit probabilities add upUsing the row sums
Show that
Solution
The transient rows of
Occupation measures and their fluctuations
The forward equation tells us
The idea
For a constant
Why
Explore
Generator
Worked example
A two-state chain has rates
What is
for the unscaled generator?From Module 1,
, with .Compute
.Find
.Check against renewal theory: on and off periods with means
, and variances , give variance per unit time , which is the same expression.Now
, . How spread out is the time spent in state 1 during ? , so , a standard deviation of 0.05. The time in state 1 is or so, even though the chain makes about 100 jumps. Fluctuations of order are much larger than the errors of the forward equation.
Check your understanding
You divide
- divided by 4.That is how the mean
, of order , scales. The fluctuations are larger. - divided by 2.
- unchanged.That is true of
, not of .
Which statement about
- Both are
.The mean is. A random quantity can be much larger than its mean in absolute value. - The mean is
; the typical size is of order . - The mean is of order
. , and Module 4 bounds the integrand by .
The explorer starts each chain from
- Yes: the mean would shift by an amount of order 1.How long does the effect of the starting state last, and how much does it contribute to
? - No: the starting state matters only for a time of order
, which changes by and by .
Practice
The deviation matrixA closed form
Let
Hint
Solution
Since
A tail estimateUsing the Gaussian limit
With
Solution
We need
The aggregated process
With weak and strong interactions, a single sample path splits into two parts. Which group the chain is in behaves more and more like a Markov chain with generator
The idea
The centering uses the random indicator
Explore
The four-state chain of Module 5:
Worked example
In the explorer's chain, show that
Through which states can the chain enter
?The slow moves into
are (rate 0.4) and (rate 1.2). So it enters at or at , depending on where it was in .Just after entering, what is the rate of leaving
?0.9 if it entered at
, 0.3 if at . The future of depends on more than its present value 1, so is not Markov.How long does the chain remember its entry point?
The block
has nonzero eigenvalue . After a time of a few times the position inside has distribution close to , whatever the entry point.What does a stay in
look like in the limit?Over a stay of order 1, the exit rate is averaged against
and equals . The memory lasts only , so stays become exponential with mean 2, independent of the past: the Markov property returns in the limit.
Check your understanding
On a fixed interval
- both the number of jumps and the number of group switches grow like
.Group switches are driven by , whose rates do not depend on . - the number of jumps grows like
but the number of group switches stays of order 1. - both stay of order 1.Inside a group the rates are of order
.
Why is time in
- The two give the same limit.
does not go to 0: the time spent in is random even in the limit. - The time the path spends in
stays random as , so only the split inside the group becomes deterministic. - Because
is not known explicitly.It is: it solves . The issue is randomness, not computability.
When is
- Never.It can be, under a condition on
. - When, for each pair of groups
, every state of has the same total slow rate into . - When every
is irreducible.The explorer's blocks are irreducible, and still is not Markov there.
Practice
Long-run time in one stateCombining the two scales
For the explorer's chain, find the limit as
Solution
The aggregated chain spends a fraction
Lumpability exactlyChecking the Markov property
Change the explorer's slow rates so that
Solution
Give both states of
Backward equations and the terminal layer
An expected payoff collected at a final time
The idea
Duality. Forward equations act on row vectors (distributions), and the leading term has the form
Explore
Worked example
Use the four-state chain of Module 5 with
What does the terminal layer do to
?Inside
, the values 1 and 0 merge into their -average ; inside both are 0. So .Solve
backward from , writing . . With and , the first column of is , soWhat do both tend to as
? Interpret. , the long-run probability of found in Module 5. Far from , the starting state is forgotten.Is there a terminal layer when
is constant on each group, say ?No:
, so . The answer is to leading order. Try the "indicator of " preset: the curves leave without any fast transient.
Check your understanding
Near
- A time of order
(here about ). - A time of order 1.The merging is done by the fast part
, not the slow part. - They never agree: their payoffs differ.The payoffs differ only at
. Starting slightly earlier, the chain has time to mix inside its group.
Which average of the payoff over a group enters
- The plain average over the states of the group.States are not visited equally often by the fast chain.
- The
-weighted average . - The value at the state the chain is in at time
.That state is forgotten within a time of order .
Why is the boundary layer at
- Each equation has a layer where its data are given:
at time 0 for the forward equation, at time for the backward one. - Because
changes fastest near .The layer appears even for constant generators. It is about the side condition. - The backward equation has layers at both ends.Its condition is imposed only at
; at nothing has to be matched.
Practice
A maximum principleBounds on expected payoffs
Show that
Solution
Probabilistically,
Probability of ending in a groupNo layer at all
For
Solution
Markov decision problems on two time scales
When a controller can change the rates, the optimal cost solves a dynamic-programming equation on the full state space. On two time scales, a smaller problem with one state per group gets the value right to within
The idea
Explore
Each entry reads action 0 / action 1. Group
Worked example
Solve the explorer's limit problem for the decision
With
, what are , and ?Fast rates:
at 2, at 3, so . Then and .Same for group 2 with
. at 1, at 4, so , and .Solve
. and . The determinant is , soNow try
with the same . Is it better? , , . Solving gives : cheaper to run, but the chain drifts into the expensive group more than twice as fast. Checking all 16 decisions shows is optimal, so , and the explorer confirms it is exactly optimal for the full problem once .
Check your understanding
Why is a decision in the limit problem a whole tuple
- Different states of the group can use different actions, and the mix determines
, hence both and . - Because the limit problem has more states than the original.It has fewer: one per group.
- A single action per group would give the same value.Not here: the optimal
uses both actions in each group.
At
- Yes:
should be optimal.The theorem promises near-optimality as , not optimality at a given . - No: the theorem says
, which at allows a visible gap.
As
- Because the optimal actions in the two states are equal.In the limit policy they are not: 0 in
, 1 in . - The chain moves between
and within a time of order , so the starting state affects the cost only over a time of order . - Because discounting makes all values equal.The values of the two groups stay different, about 4.85 and 7.44.
Practice
Discounted costs are averagesThe resolvent
Show that
Solution
The long-run average cost of Letting ρ → 0
In the limit, what is the long-run average cost per unit time of the policy
Solution
The aggregated chain under
Production planning with an unreliable machine
A machine breaks down and is repaired at random, and its output must meet a steady demand. A good policy keeps a safety stock, the hedging point. When breakdowns and repairs are fast compared with the time scale of the costs, the right safety stock is of order
The idea
The example. One machine, up or down: breakdown rate
Average capacity is
Explore
Worked example
Find the long-run behaviour of the surplus under a hedging-point policy, the optimal
Which levels does
visit in the long run, and with which velocities?Once below
, never goes above it. Up and below : . Up at : . Down: . So the stationary law lives on , with an atom at (machine up and waiting).Let
be the stationary densities below . Why is , and what form must they have?In equilibrium the net flow of probability across any level
is zero: mass crosses upward at rate and downward at rate . The balance equation for the up state, , then gives withSo
has a law that does not depend on : an atom at 0 and an exponential tail of mean depth of order , proportional to .Differentiate
, where and . What is the optimality condition?Since the law of
is free of , ( has no atom at 0 when ). So at the optimuma "critical fractile": backlog should occur a fraction
of the time with .With the explorer's numbers, find
. . Normalising the densities and the atom shows for every and , so . Setting this to : , soBoth
and the optimal cost are proportional to , and tend to the limit problem's answers, 0 and 0.
Check your understanding
Keep
- 0, the value of the limit problem.Only if
shrinks too. With you keep one unit of stock. : excursions below are only deep, so nearly all the time. .The average capacity exceeds demand, so the surplus is stable for every .
In the limit problem, why does the capacity enter only through
- Because the planner should prepare for the worst case, capacity 0.Worst-case planning would ignore that the machine is up most of the time.
- The machine state switches so fast that production averages out: over any interval of order 1 it is up a fraction
of the time. - Because the policy produces at full speed
all the time.It cannot produce when the machine is down.
In the explorer, doubling
- Down periods last
, so the dips below are deep, and the safety stock that guards against them scales the same way. - Because the cost rates
are proportional to .The cost rates do not change with . - It is a coincidence of these parameter values.It holds for any parameters: the whole stationary law of
is a rescaling by .
Practice
When is the surplus stable?The sign of β
Show that
Solution
The limit problem from a backlogA deterministic plan
In the limit problem with the explorer's numbers, start from
Solution
Produce at the full average rate
Tuning a threshold by stochastic approximation
When the cost of a threshold policy has no formula, simulate it. A stochastic-approximation recursion uses noisy estimates of the slope of the cost, taken from short simulated runs, and walks the threshold toward the optimum. Here it is on the machine of Module 11, where the exact answer is known, so you can see how well it does.
The idea
Explore
The machine of Module 11 with
Worked example
The finite difference has its own bias: even with perfect cost estimates, the recursion settles where the difference quotient vanishes, not where
From Module 11, write
for . , with .For
, compute the exact central difference .Integrate
over and divide by :Where does it vanish?
At
, i.e.Evaluate the bias for
and . : , bias , invisible next to the noise. : , , bias . A large gives quieter estimates but a biased answer: the usual trade-off of finite differences.
Check your understanding
Why run
- Otherwise the gradient estimate would be biased.Independent runs give an estimate with the same mean. The difference is in its variance.
- The noise in the two cost estimates is then largely shared and cancels in the difference, so the slope estimate has much smaller variance.
- To save simulation time.Both runs still have to be simulated; only the machine history is shared.
With a constant step size
- Converge to
exactly.Each step adds noise of size (noise in ), which never stops. - Fluctuate in a neighbourhood of
whose size shrinks as . - Drift away, because the noise accumulates.Near
the mean step pulls them back.
Which ODE describes the iterates for small
, the gradient flow of the long-run cost. , with the noisy estimates.In the limit the noise averages out; the ODE involves only its mean. .The recursion moves against the slope, not against the cost itself.
Practice
A pathwise derivativeNo finite differences needed
Start the surplus at
Solution
The dynamics of
A Markov chain approximationDiscretising a drift
For
Solution
Jump
LQ control with Markov switching
A linear system whose coefficients switch with a Markov chain is best controlled by a linear feedback whose gain depends on the current regime. The gains come from coupled Riccati equations, one per state of the chain. On two time scales, they collapse to one averaged Riccati equation per group.
The idea
Only the Riccati part is shared within a group. The feedback still uses the
Explore
Scalar system, the four-state chain of Module 5.
Worked example
A scalar system switches very fast between two regimes,
Write the scalar Riccati equations for the two regimes.
, .Why are
and nearly equal for small ?The coupling term
is huge unless . Any difference is damped at rate , so .Average the two equations with weights
to get an equation for the common value .The
terms cancel because . What remains is with : , . Its solution is .Far from
the gain is , so . Is the closed loop stable?In regime 1 the closed loop is
, unstable on its own. In regime 2 it is . With fast switching, : stable. The averaged design stabilises the switched system though it would not stabilise regime 1 alone.
Check your understanding
Where does the term
- From the Brownian noise
.The noise only enters the equation for , through . - From the chance of switching to regime
: it is the generator of acting on the value function . - From the terminal cost
. enters only through the terminal condition.
In the nearly optimal feedback
, the Riccati solution; and are still those of the current state.- All of it: the feedback depends only on the group.The controller still knows the current state and uses its
and . - None of it.The Riccati part is shared within a group, as the explorer shows.
To form the averaged equation, a student averages
- Nothing; it gives the same answer.In the explorer's group 2,
, while . - The control enters the cost quadratically, so the right average is
, which is larger by Jensen's inequality. - One should average
instead of the coefficients. is the unknown being solved for; the coefficients are what get averaged.
Practice
From HJB to RiccatiThe scalar case
For a scalar system with one regime, substitute
Solution
The minimum over
The long-horizon gainAn algebraic Riccati equation
For one scalar regime, find the limit of
Solution
Set