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.

SimulationYin–Zhang, Ch. 1: Introduction and Overview · Ch. 2: Mathematical Preliminaries

Generators and sample paths

A continuous-time Markov chain on finitely many states is determined by one matrix, its generator Q. The diagonal says how long the chain waits in each state, and the off-diagonal entries say where it goes next. Set the rates below and run the chain.

The idea

Generator. An m×m matrix Q=(qij) with qij≥0 for i≠j and every row summing to zero, so qii=−∑j≠iqij. Write qi=−qii for the total rate of leaving i. A time-dependent Q(t) must have this form at each t (the book also asks for measurability and bounded entries).
Construction from rates. In state i, wait a time that is exponential with rate qi (mean 1/qi), then jump to j≠i with probability qij/qi, independently of the past. The sequence of states visited is the jump chain, a discrete-time chain with those transition probabilities. If qi=0, state i is absorbing.

The transition matrix P(t)=(P(α(t)=j∣α(0)=i)) then satisfies P(t+s)=P(t)P(s) and

P(α(t+h)=j∣α(t)=i)=qijh+o(h)(j≠i),P(t)=eQt.
Martingale characterisation. Q generates α(⋅) exactly when, for every function f on the state space,
f(α(t))−∫0t(Qf)(α(s))ds,(Qf)(i)=∑j≠iqij(f(j)−f(i)),
is a martingale. This is the definition the book works with, and it is what makes the expected-value equations of later modules come out in one line.
Long-run time fractions. If Q is irreducible (every state can reach every other), then with probability one 1t∫0tI{α(s)=i}ds→νi, where ν is the unique probability vector with νQ=0.

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 Qε=Q~/ε+Q^, with a small ε>0, separates the fast moves from the slow ones. Modules 4 to 13 are about that limit. Note that Q/ε generates the same chain as Q, only run 1/ε times faster.

Explore

Speed
Arrow width is the rate qij. The filled node is the current state, and its outgoing arrows are highlighted.
fraction of time so far stationary νi. Below: the last 12 time units of the path.

Worked example

Take the generator

Q=(−3211−1022−4).

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.

  1. What are the mean holding times in states 1, 2, 3?

    The leaving rates are q1=3, q2=1, q3=4, so the mean holding times are 1/3, 1, 1/4.

  2. 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:

    Π=(02/31/31001/21/20).

    From state 2 the chain always returns to 1.

  3. Solve νQ=0, ν1+ν2+ν3=1.

    The third column gives ν1−4ν3=0, so ν1=4ν3. The first column gives −3ν1+ν2+2ν3=0, so ν2=10ν3. The second column, 2ν1−ν2+2ν3=8ν3−10ν3+2ν3=0, checks out. Normalising,

    ν=115(4, 10, 1).
  4. The jump chain has its own stationary distribution π (with πΠ=π). How is it related to ν?

    The chain enters state i at long-run rate νiqi (time fraction times leaving rate), so πi∝νiqi:

    π∝(4⋅3, 10⋅1, 1⋅4)=(12,10,4),π=113(6,5,2).

    Check: π1=π2+12π3=513+113=613. State 1 gets the most jumps but state 2 holds the most time, because the chain lingers there.

Check your understanding

Row i of a generator is (1, −4, 3), with qii=−4 in the middle. What is the chance the next jump goes to the third state, and how long does the chain wait on average?

  1. Probability 3/4; mean wait 1/4.
  2. Probability 3/4; mean wait 4.The holding time is exponential with rate 4. Its mean is the reciprocal of the rate.
  3. Probability 3h in a short time h; there is no single "next jump" probability.3h is the chance of a jump to state 3 within time h. Conditioned on a jump happening, the destination has a fixed distribution.
The two exits race as independent exponential clocks with rates 1 and 3. The first ring comes after an Exp(4) time, and the rate-3 clock wins with probability 3/(1+3).

Why must every row of a generator sum to zero?

  1. Because the stationary distribution satisfies νQ=0.νQ=0 is a statement about the columns, weighted by ν. It is a property of one special vector, not of the rows.
  2. Because each row of P(t)=eQt sums to 1 for all t; differentiate at t=0.
  3. Because probabilities are nonnegative.Nonnegativity is why the off-diagonal entries are ≥0. It says nothing about the sum.
P(t)1=1 for all t, and ddtP(t)|t=0=Q, so Q1=0. In words: the rate of leaving i equals the sum of the rates of going to each other state.

Chain A has generator Q and chain B has generator 10Q. Which is true?

  1. B has a different stationary distribution, ten times larger.ν(10Q)=10νQ=0: the same ν solves both systems, and it must still sum to 1.
  2. B has a different jump chain.The jump probabilities are ratios qij/qi; multiplying every rate by 10 cancels.
  3. Same jump chain and same ν, but B runs ten times faster: αB(t) has the law of αA(10t).
Scaling a generator rescales time and nothing else. That is the starting point of the two-time-scale theory: Q/ε is the chain of Q run at speed 1/ε, which mixes in time of order ε.

Practice

The two-state chainAn explicit transition matrix

A two-state chain jumps 1→2 at rate λ>0 and 2→1 at rate μ>0. Find P(t)=eQt explicitly and its limit as t→∞.

Hint

p11(t) solves p11′=−λp11+μ(1−p11). Alternatively, Q has eigenvalues 0 and −(λ+μ).

Solution

The equation p11′=μ−(λ+μ)p11 with p11(0)=1 gives

P(t)=1λ+μ(μ+λe−(λ+μ)tλ−λe−(λ+μ)tμ−μe−(λ+μ)tλ+μe−(λ+μ)t).

Both rows tend to ν=(μ,λ)/(λ+μ), at the exponential rate λ+μ.

From the martingale to the forward equationTaking expectations

Let pj(t)=P(α(t)=j). Using the martingale characterisation with f=I{⋅=j}, show that pj′(t)=∑ipi(t)qij.

Solution

For f(k)=I{k=j} we get (Qf)(i)=∑kqikf(k)=qij (using ∑kqik=0). A martingale has constant expectation, so

pj(t)−pj(0)=E∫0tqα(s)jds=∫0t∑ipi(s)qijds.

Differentiating gives p′(t)=p(t)Q, the forward equation of the next module.

InteractiveYin–Zhang, Ch. 2: Mathematical Preliminaries

The forward equation and irreducibility

The distribution of a Markov chain solves a linear differential equation, p′(t)=p(t)Q. For three states every solution is a curve in a triangle, and you can drag its starting point. When the generator is weakly irreducible, every curve ends at the same point.

The idea

Kolmogorov equations. Write P(t,s) for the matrix of probabilities P(α(t)=j∣α(s)=i), t≥s. Then
∂∂tP(t,s)=P(t,s)Q(t)  (forward),∂∂sP(t,s)=−Q(s)P(t,s)  (backward),
with P(s,s)=I. The row vector p(t)=(P(α(t)=1),…,P(α(t)=m)) solves p′(t)=p(t)Q(t). For constant Q, P(t,s)=eQ(t−s).
Weak irreducibility. Q is weakly irreducible if the system νQ=0, ∑iνi=1 has exactly one solution. That solution is then automatically ≥0. Q is irreducible if in addition every νi>0. Equivalently, Q is weakly irreducible when fQ=0 and f1=0 force f=0; its rank is then m−1.
Quasi-stationary distribution. For a time-dependent Q(t), the solution ν(t) of ν(t)Q(t)=0, ν(t)1=1. It is the distribution the chain would settle into if the rates were frozen at their time-t values. It is not, in general, the distribution of α(t).
Exponential convergence. If a constant Q is weakly irreducible, there are K,κ>0 with |eQt−1ν|≤Ke−κt. Every row of eQt tends to ν, and κ can be taken just below the smallest |Reλ| over the nonzero eigenvalues λ of Q.
Fredholm alternative. If Q is weakly irreducible, fQ=g has a solution exactly when g1=0, and fixing f1 makes it unique. Every expansion in Modules 4 to 6 is built by solving equations of this form.

Explore

Generator
Each point of the triangle is a distribution (p1,p2,p3); a corner is a sure state. Drag p(0). Dots mark t=1,2,…
p1 p2 p3, with νi dashed.

Worked example

A two-state chain has time-varying rates: 1→2 at rate λ(t) and 2→1 at rate μ(t). Compare the quasi-stationary distribution with the actual distribution p(t).

  1. Find ν(t). When is Q(t) weakly irreducible, and when irreducible?

    ν(t)Q(t)=0 reads −λν1+μν2=0, so ν(t)=(μ(t),λ(t))/(λ(t)+μ(t)). This needs λ+μ>0 (weak irreducibility); both entries are positive when both rates are positive (irreducibility).

  2. Write the forward equation for p1(t) alone.

    Using p2=1−p1:  p1′=−λp1+μ(1−p1)=−(λ+μ)p1+μ.

  3. Solve it when the rates are constant.

    p1(t)=ν1+(p1(0)−ν1)e−(λ+μ)t.

    The gap to ν closes at rate λ+μ, the absolute value of the nonzero eigenvalue of Q.

  4. Now let the rates vary. What equation does the gap d(t)=p1(t)−ν1(t) satisfy, and what does it say?

    Since μ=(λ+μ)ν1, the equation becomes p1′=−(λ+μ)(p1−ν1), so

    d′(t)=−(λ(t)+μ(t))d(t)−ν1′(t).

    The chain is pulled toward ν(t) at rate λ+μ while ν(t) moves away at speed ν1′. If the rates are λ0(t)/ε and μ0(t)/ε, then ν does not depend on ε, the pull wins, and d settles near −εν1′/(λ0+μ0), which is O(ε). That small lag is exactly what Module 4 computes.

Check your understanding

Q=(−110000000). Is Q weakly irreducible?

  1. Yes: state 1 is transient, so its stationary probability is 0 and ν=(0,1,0).(0,1,0) is a solution, but is it the only one? Look at state 3.
  2. No: (0,s,1−s) solves νQ=0, ν1=1 for every s∈[0,1].
  3. Yes, because Q has rank m−1.Two rows of Q are zero and the first is nonzero, so the rank is 1, not 2.
States 2 and 3 are both absorbing, two closed classes, so the long-run distribution depends on where the chain starts. Compare the "Two closed classes" generator in the explorer.

In the "Cyclic" example the path of p(t) spirals into ν. What causes the spiral?

  1. The chain is periodic.A continuous-time chain is never periodic: pii(t)≥e−qit>0 for every t.
  2. Q has a pair of complex eigenvalues −a±ib, so eQt contains terms e−atcos⁡bt and e−atsin⁡bt.
  3. Rounding error in the numerical solution.The spiral is real. Try smaller and smaller steps and it stays.
The probabilities still converge, at rate a, but they overshoot and come back as they go. Generators of reversible chains (detailed balance) have only real eigenvalues, so their paths cannot spiral.

Q(t) is weakly irreducible for every t and varies slowly. Is p(t)=ν(t) for all t if p(0)=ν(0)?

  1. Yes, because ν(t) is stationary.ν(t) would be stationary for a chain whose rates stayed frozen at time t. Here they keep moving.
  2. No: p(t) lags behind ν(t), unless ν(t) happens to be constant.
Differentiate ν(t)Q(t)=0: if p≡ν then ν′=p′=pQ=νQ=0, so ν would have to be constant. The worked example measures the lag.

Practice

The solvability conditionOne direction of the Fredholm alternative

Let Q be a generator. Show that if fQ=g has a solution then g1=0. If Q is weakly irreducible, show the solution is unique once f1 is fixed.

Solution

g1=fQ1=f⋅0=0. If f1Q=f2Q=g with f11=f21, then h=f1−f2 has hQ=0 and h1=0, so h=0 by the second form of weak irreducibility.

Why eQt is a stochastic matrixPositivity without probability

Show directly from the matrix exponential that eQt has nonnegative entries and rows summing to 1 when Q is a generator.

Hint

Choose c≥maxiqi. Then Q+cI has nonnegative entries, and Q and cI commute.

Solution

eQt=e−cte(Q+cI)t=e−ct∑ntnn!(Q+cI)n, a sum of nonnegative matrices. And eQt1=∑ntnn!Qn1=1 since Q1=0. This also gives a way to simulate: run a Poisson clock of rate c and move by I+Q/c at each tick (uniformisation).

SimulationYin–Zhang, Ch. 3: Markovian Models

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 K.

The idea

Birth–death chain. On {0,1,…,K}, the only nonzero off-diagonal rates are qn,n+1=λn (a birth) and qn,n−1=μn (a death).
Detailed balance. If all λn,μn>0 in range, the stationary distribution satisfies νnλn=νn+1μn+1, so
νn=ν0∏k=0n−1λkμk+1,ν0 fixed by ∑nνn=1.
The reason: the cut between {0,…,n} and {n+1,…,K} is crossed by a single pair of edges, and in equilibrium the flow across a cut is zero.
A finite queue. Customers arrive at rate λ, one server works at rate μ, and at most K customers fit in the system; arrivals to a full system are turned away. This is the birth–death chain with λn=λ (n<K), μn=μ (n≥1). With ρ=λ/μ≠1,
νn=(1−ρ)ρn1−ρK+1,n=0,…,K,
and νn=1/(K+1) when ρ=1. No condition ρ<1 is needed: the state space is finite.
Arrivals see time averages. Poisson arrivals are independent of the queue's past, so the fraction of arrivals that find the system full equals the fraction of time it is full, νK.

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 Qε=Q~/ε+Q^ makes that explicit.

Explore

Speed
Queue length over the last 40 time units.
fraction of time at each length so far νn from detailed balance
Press Run. The blue bars converge to the gold ones, and the share of arrivals turned away converges to νK, the share of time the queue is full. Try λ>μ: the queue does not blow up, it sits near K and turns many customers away. Changing a rate restarts the statistics.

Worked example

Two identical machines each fail at rate λ while running. One repairer fixes failed machines one at a time at rate μ. Let α(t)∈{0,1,2} be the number of failed machines. Find the long-run availability (at least one machine working) for λ=1, μ=4.

  1. Write the generator.

    With 0 failed, two machines can fail: rate 2λ. With 1 failed, one can fail (rate λ) or the repair finishes (rate μ). With 2 failed, only repair (rate μ):

    Q=(−2λ2λ0μ−(λ+μ)λ0μ−μ).
  2. Use detailed balance to express ν1,ν2 in terms of ν0.

    ν1=2λμν0 and ν2=λμν1=2λ2μ2ν0.

  3. Normalise with λ=1, μ=4, and give the availability.

    ν∝(1, 12, 18), and the entries sum to 138, so ν=113(8,4,1). Availability =1−ν2=1213≈0.923.

  4. Suppose repairs are much faster than failures: μ=μ0/ε. How does the downtime scale?

    ν2=2λ2/μ21+2λ/μ+2λ2/μ2=2λ2ε2/μ02+O(ε3). A machine is under repair a fraction O(ε) of the time, and the second one must fail during that short repair, which has probability O(ε). 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 λ=μ. What is the stationary distribution?

  1. There is none: the queue is critically loaded.That is true for an infinite waiting room. With room for only K customers the chain is finite and irreducible.
  2. Uniform: νn=1/(K+1).
  3. Concentrated at n=K.Detailed balance with λ=μ gives νn+1=νn: no state is preferred.
νn+1/νn=λ/μ=1. Set λ=μ in the explorer: all the gold bars have the same height.

Why does the fraction of arrivals that are turned away equal νK, the fraction of time the system is full?

  1. Because the server is idle exactly ν0 of the time.True, but that is about state 0. What is special about the moments when customers arrive?
  2. Arrivals come from a Poisson process independent of the past of the queue, so the state an arrival sees has the time-stationary distribution.
  3. 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.
This is "Poisson arrivals see time averages". It fails when the arrival rate depends on the state: then arrivals sample states in proportion to νnλn, not νn.

A birth–death chain on {0,…,K} has every λn and μn positive. Is it reversible (does detailed balance hold)?

  1. Always.
  2. Only when λn=μn+1 for all n.That is the special case of a uniform ν. Detailed balance only needs νnλn=νn+1μn+1, which can always be arranged.
  3. Only for the finite queue.The cut argument uses nothing about the particular rates.
Since the chain lives on a path graph, each cut is crossed only by n→n+1 and n+1→n, so zero net flow across every cut is detailed balance. Chains with cycles, like the cyclic generator of Module 2, need not be reversible.

Practice

A tiny queue by handLittle's law

Take K=2, λ=1, μ=2. Find ν, the mean number in the system L, the throughput, and the mean time a customer who gets in spends in the system.

Solution

ρ=12, so ν∝(1,12,14), giving ν=17(4,2,1). L=17(0+2+2)=47. Accepted customers arrive at rate λ(1−ν2)=67, which is also the throughput. Little's law: W=L/67=23.

Zero flow across a cutDeriving detailed balance

For a birth–death chain with stationary ν, add up the equations (νQ)k=0 for k=0,…,n and conclude νnλn=νn+1μn+1.

Solution

∑k≤n(νQ)k=∑iνi∑k≤nqik. For i≤n, the inner sum is minus the rate of leaving {0,…,n} from i, which is −λn for i=n and 0 otherwise. For i>n it is the rate of entering {0,…,n}, which is μn+1 for i=n+1 and 0 otherwise. So the sum is −νnλn+νn+1μn+1=0.

InteractiveYin–Zhang, Ch. 4: Asymptotic Expansions of Solutions for Forward Equations

A fast chain: outer expansion and initial layer

Speed a chain up by a factor 1/ε while its rates drift in ordinary time. Its distribution snaps to the quasi-stationary distribution within a time of order ε, then follows it. A matched asymptotic expansion describes both phases, with an error you can watch shrink in proportion to ε.

The idea

Let αε(t) be generated by Q(t)/ε, with Q(t) weakly irreducible and smooth on [0,T]. Its distribution solves

dpε(t)dt=1εpε(t)Q(t),pε(0)=p0.
Two-part expansion. Look for pε(t)=∑i=0nεiφi(t)+∑i=0nεiψi(t/ε)+enε(t). The outer terms φi describe t away from 0; the initial-layer terms ψi(τ), in the stretched time τ=t/ε, repair the start and decay exponentially in τ.

Outer terms. Substitute and match powers of ε:

φ0(t)Q(t)=0,φk(t)Q(t)=dφk−1(t)dt(k≥1),

with φ01=1 and φk1=0 for k≥1. So φ0(t)=ν(t), the quasi-stationary distribution, and each later equation is solvable by the Fredholm alternative because φk−1′1=0.

Initial layer. In the stretched time, dψ0dτ=ψ0(τ)Q(0) and ψ0(0)=p0−ν(0), so

ψ0(τ)=(p0−ν(0))eQ(0)τ,

which decays like e−κτ because (p0−ν(0))1=0.

Error bound. Under these assumptions (with Q smooth enough for the order n),  sup0≤t≤T|pε(t)−∑i≤nεiφi(t)−∑i≤nεiψi(t/ε)|≤Kεn+1. For n=0: pε(t)=ν(t)+ψ0(t/ε)+O(ε), and pε(t)→ν(t) for every t>0.
Watch out. The convergence is not uniform near t=0 unless p0=ν(0), and even then the higher initial-layer terms ψ1,ψ2,… need not vanish.

Explore

Two states. Rates λ(t)/ε for 1→2 and μ/ε for 2→1, with λ(t)=1.5+sin⁡πt and μ=1, so ν1(t)=1/(λ(t)+1).

p1ε(t), exact ν1(t) ν1(t)+ψ0(t/ε), on 0≤t≤2
The initial layer in stretched time τ=t/ε. Here ψ0(τ)=(p1(0)−0.4)e−2.5τ for state 1.

Worked example

For the two-state chain of the explorer, with rates λ(t)/ε and μ(t)/ε, find φ0, ψ0 and the first outer correction φ1, and evaluate them at t=1.

  1. What is φ0(t)?

    The quasi-stationary distribution: φ0(t)=ν(t)=(μ,λ)/(λ+μ). With μ=1, ν1(t)=1/(λ(t)+1).

  2. Find ψ0(τ).

    A zero-sum row vector (x,−x) times Q(0) is −(λ(0)+μ(0))(x,−x), so

    ψ0(τ)=(p10−ν1(0))(1,−1)e−(λ(0)+μ(0))τ.

    In the explorer λ(0)+μ=2.5 and ν1(0)=0.4.

  3. Solve φ1Q=φ0′ with φ11=0.

    Write φ1=(c,−c). Then φ1Q=−c(λ+μ)(1,−1) and φ0′=ν1′(1,−1), so

    φ1(t)=−ν1′(t)λ(t)+μ(t)(1,−1).

    When ν1 rises, p1ε sits slightly below it: the chain lags behind its moving target by about εν1′/(λ+μ), as in Module 2.

  4. Evaluate at t=1, where λ=1.5 and λ′=πcos⁡π=−π.

    ν1(1)=1/2.5=0.4 and ν1′=−λ′/(λ+1)2=π/6.25≈0.5027, so φ1,1(1)≈−0.5027/2.5≈−0.2011. For ε=0.05: p1ε(1)≈0.4−0.0101=0.3899. The explorer's last two boxes compare this with the exact value.

Check your understanding

Why can't the outer expansion ∑εiφi(t) alone match the initial condition pε(0)=p0?

  1. φ0(0)=ν(0) is forced by φ0Q=0; it is not free to equal p0.
  2. It can, if enough terms are kept.Every φk with k≥1 carries a factor εk. No combination of them can close an O(1) gap p0−ν(0).
  3. Because the outer terms are not smooth at t=0.They are as smooth as Q. The trouble is their value at 0, not their smoothness.
The outer equations are algebraic at leading order, so they lose the initial condition. The initial-layer term, which lives on the fast time τ=t/ε, carries the mismatch and dies out within a few multiples of ε.

Q(0) is a 3-state generator with nonzero eigenvalues −2 and −5. For small ε, how does the initial layer ψ0(t/ε) decay?

  1. Like e−2t.The layer lives on the fast time t/ε.
  2. Like e−5t/ε.The fast mode dies first. What is left after that?
  3. Like e−2t/ε (for a typical p0).
ψ0(τ)=(p0−ν(0))eQ(0)τ is a combination of e−2τ and e−5τ, and the slower mode dominates. With ε=0.01 the layer is gone, to a few percent, by t≈0.02.

Suppose p0=ν(0). Which is true?

  1. pε(t)=ν(t) exactly for all t.Only if ν(t) is constant. Otherwise the chain lags behind its moving target.
  2. ψ0≡0, but pε(t)−ν(t) is still of order ε.
  3. The error becomes O(ε2).The εφ1 term is still there; only the zeroth-order layer disappeared.
With p0=ν(0) the zeroth-order layer vanishes, but εφ1(t) does not, and φ1(0)≠0 when ν′(0)≠0, so ψ1(0)=−φ1(0) is nonzero too. In the explorer, set p1(0)=0.40: the gold curve coincides with the green one, but the blue one still lags by O(ε).

Practice

Constant generatorsWhen the expansion terminates

If Q does not depend on t, show that pε(t)=ν+(p0−ν)eQt/ε exactly. Which terms of the expansion are nonzero?

Solution

pε(t)=p0eQt/ε=νeQt/ε+(p0−ν)eQt/ε, and νeQs=ν since νQ=0. So φ0=ν, ψ0(τ)=(p0−ν)eQτ, and all other terms vanish: φ1Q=ν′=0 with φ11=0 forces φ1=0, and so on.

Uniform away from zeroReading the error bound

Use the n=0 bound to show that supδ≤t≤T|pε(t)−ν(t)|=O(ε) for each fixed δ>0, while sup0≤t≤T|pε(t)−ν(t)| does not tend to 0 unless p0=ν(0).

Solution

|pε−ν|≤|ψ0(t/ε)|+Kε≤K′e−κδ/ε+Kε on [δ,T], and e−κδ/ε=o(ε). At t=0 the difference is |p0−ν(0)| for every ε.

InteractiveYin–Zhang, Ch. 4: Asymptotic Expansions of Solutions for Forward Equations

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

Setup. Qε(t)=Q~(t)/ε+Q^(t) with Q~=diag(Q~1,…,Q~l). Block Q~k acts on the group Mk={sk1,…,skmk}, is weakly irreducible, and has quasi-stationary distribution νk(t). Q^(t) is any generator on all m=m1+⋯+ml states.
Aggregated generator. With 1~=diag(1m1,…,1ml), an m×l matrix,
Q¯(t)=diag(ν1(t),…,νl(t))Q^(t)1~.
Entry q¯kj is the slow rate from group k into group j, averaged over the states of group k with weights νk.
Leading-order behaviour. Uniformly on [0,T],
pε(t)=(ϑ1(t)ν1(t),…,ϑl(t)νl(t))+ψ0(t/ε)+O(ε),
where ϑ=(ϑ1,…,ϑl) solves ϑ′(t)=ϑ(t)Q¯(t) with ϑ(0)=p01~, the vector of initial group weights. The initial layer ψ0(τ)=(p0−φ0(0))eQ~(0)τ, where φ0(0)=(ϑ1(0)ν1(0),…,ϑl(0)νl(0)), decays exponentially.

So P(αε(t)∈Mk)→ϑk(t), and given the group, the chain is spread according to νk(t). The group weights have no zeroth-order layer: eQ~τ only moves probability inside groups, so ψ0(τ)1~=0.

What survives the limit. Q^ enters only through Q¯. Slow rates between two states of the same group change nothing at leading order, and two slow generators with the same Q¯ give the same ϑ.

Explore

Start
Dashed curves include ψ₀

Fast rates: s11→s12 2, s12→s11 1, s21→s22 1, s22→s21 3 (all divided by ε). Slow rates: s11→s21 0.9, s12→s22 0.3, s21→s12 0.4, s22→s11 1.2.

Solid: P(αε(t)=skj). Dashed: ϑk(t)νjk, with or without the initial layer.
P(αε(t)∈M1) P(αε(t)∈M2); dashed: ϑ(t) from ϑ′=ϑQ¯

Worked example

Compute everything the explorer uses: ν1,ν2, Q¯, and ϑ(t) when the chain starts in s11. Then find the long-run distribution of the full chain to leading order.

  1. Find ν1 and ν2.

    For a two-state block with rates a (first to second) and b (back), ν=(b,a)/(a+b). So ν1=(1,2)/3 and ν2=(3,1)/4.

  2. Compute q¯12 and q¯21.

    q¯12=ν11⋅0.9+ν21⋅0.3=0.3+0.2=0.5 and q¯21=ν12⋅0.4+ν22⋅1.2=0.3+0.3=0.6. So

    Q¯=(−0.50.50.6−0.6).
  3. Solve for ϑ(t) with ϑ(0)=(1,0).

    By the two-state formula from Module 1, ϑ1(t)=611+511e−1.1t and ϑ2=1−ϑ1.

  4. What is the stationary distribution of the full chain, to leading order in ε?

    Let t→∞ in the leading term: ϑ→(611,511), so

    νε≈(611⋅13, 611⋅23, 511⋅34, 511⋅14)=(211,411,1544,544).

    A direct computation with ε=0.01 gives (0.1817,0.3637,0.3410,0.1136), against (0.1818,0.3636,0.3409,0.1136) 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 ν1=(12,12). From s11 the slow rate into group 2 is 2; from s12 it is 0. What is q¯12?

  1. 2That is the rate from s11 only. The chain spends half of its group-1 time in s12, where it cannot leave.
  2. 1
  3. 0, the smaller rateThe aggregated rate is an average, not a minimum.
q¯12=12⋅2+12⋅0=1. Because the fast chain visits both states many times between slow jumps, the slow clock sees the time-averaged exit rate.

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?

  1. Q~ is block diagonal, so the fast dynamics only move probability inside a group; each group's total changes at rate O(1).
  2. Because νk sums to 1.That is true but says nothing about time evolution. What does eQ~τ do to the total mass of a group?
  3. They do have one, it is just too small to see.At leading order it is exactly zero: ψ01~=(p0−φ0(0))eQ~τ1~=(p0−φ0(0))1~=0.
The initial layer reshuffles mass within each group toward νk; the group totals ϑk start at their correct values p01~ and evolve slowly. (An O(ε) layer can remain.)

What happens if Q^=0?

  1. pε(t) converges to a unique stationary distribution.With Q^=0 the groups never communicate, so the chain is not irreducible.
  2. ϑ stays at its initial value: the group weights are frozen, and inside each group the distribution tends to νk.
  3. The theorem fails.It still applies, with Q¯=0.
Q¯=0 gives ϑ(t)=ϑ(0). The weak interaction Q^ is what lets probability move between groups, on the slow time scale.

Practice

Q¯ is a generatorTwo lines

Show that Q¯=diag(ν1,…,νl)Q^1~ has nonnegative off-diagonal entries and zero row sums.

Solution

For k≠j, q¯kj=∑iνik∑s∈Mjq^ski,s≥0, a nonnegative combination of off-diagonal entries of Q^. Row sums: Q¯1l=diag(νk)Q^1~1l=diag(νk)Q^1m=0.

Where Q¯ comes fromAveraging the forward equation

Multiply the forward equation pε′=pε(Q~/ε+Q^) on the right by 1~. Assuming pε≈(ϑ1ν1,…,ϑlνl), derive ϑ′=ϑQ¯.

Solution

Since Q~1~=0, the 1/ε term drops out: (pε1~)′=pεQ^1~. The left side is the vector of group weights, approximately ϑ. On the right, (ϑ1ν1,…,ϑlνl)=ϑdiag(ν1,…,νl), so the right side is ϑdiag(νk)Q^1~=ϑQ¯.

InteractiveYin–Zhang, Ch. 4: Asymptotic Expansions of Solutions for Forward Equations

Transient and absorbing states

Add states that the fast dynamics leaves and never returns to. Their probability dies out within a time of order ε, and the mass they held is handed to the recurrent groups in proportions that one linear solve gives. Absorbing states are the simplest recurrent groups of all.

The idea

Setup. After relabelling, the fast generator has the form
Q~=(Q~1⋱Q~lQ~∗1⋯Q~∗lQ~∗),
where each Q~k is a weakly irreducible generator on a recurrent group Mk, the last block row belongs to the transient states M∗, and Q~∗ is Hurwitz: all its eigenvalues have negative real part. A group with one state and Q~k=(0) is an absorbing state, with νk=1.
Exit probabilities. ak=−Q~∗−1Q~∗k1mk∈Rm∗. Its entry for a transient state s is the probability that the fast chain started at s first enters Mk. Since Q~1=0, ∑kak=1m∗.
Leading order. pε(t)=(ϑ1(t)ν1,…,ϑl(t)νl, 0m∗)+ψ0(t/ε)+O(ε), where
ϑk(0)=p0,k1mk+p0,∗ak,ϑ′=ϑQ¯∗,Q¯∗=diag(ν1,…,νl)(Q^111~+Q^12(a1,…,al)).
Here Q^11 holds the slow rates among recurrent states and Q^12 the slow rates from recurrent into transient states.

Read Q¯∗ as a routing rule. A slow jump straight into another group counts as it is. A slow jump into a transient state is followed, within time O(ε), by a fast exit into group k with probability given by ak; only the part that lands in a different group is a real change of group.

Explore

Start

Recurrent group M1={s11,s12} (fast rates 1 and 2 between them), absorbing state M2={s21}, transient states s1∗,s2∗. Fast: s1∗→s11 2, s1∗→s2∗ 1, s2∗→s1∗ 1, s2∗→s12 0.5, s2∗→s21 1. Slow: s11→s21 0.3, s12→s1∗ 0.4, s21→s2∗ 0.5.

P(M1) P(M2) P(M∗); dashed: ϑ(t)
The start in stretched time τ=t/ε. Dashed: the predicted split ϑ(0).

Worked example

For the chain in the explorer, compute the exit probabilities a1,a2 and the aggregated generator Q¯∗.

  1. Write Q~∗ and check that it is Hurwitz.

    On (s1∗,s2∗): Q~∗=(−311−2.5). Its row sums are −2 and −1.5, so each diagonal entry outweighs the rest of its row and, by Gershgorin's theorem, every eigenvalue has negative real part. (They are ≈−1.72 and −3.78.)

  2. Find h(s)=P(enter M1 first∣s) by a first-step argument.

    From s1∗: with probability 23 go straight to s11, with 13 to s2∗. From s2∗: 0.52.5=15 to s12, 25 to s21, 25 to s1∗. So h1=23+13h2 and h2=15+25h1, giving h1=1113, h2=713. This is a1=−Q~∗−1Q~∗11 written out; and a2=1−a1=(213,613).

  3. Starting in s1∗, what is ϑ(0)?

    ϑ(0)=(1113,213)≈(0.846,0.154). The explorer's right panel shows the mass settling to these levels within a few multiples of ε.

  4. Compute q¯12 and q¯21.

    ν1=(23,13). From M1: s11→s21 is a direct change of group, weight 23⋅0.3=0.2; s12→s1∗ changes group only if the chain then exits to M2, weight 13⋅0.4⋅213=0.839. So q¯12=43195≈0.2205. From M2: s21→s2∗, then on to M1 with probability 713: q¯21=0.5⋅713=726≈0.2692.

Check your understanding

A transient state s∗ has fast rate 3 into group 1 and fast rate 1 into group 2, and no other moves. The chain starts at s∗. What is ϑ(0)?

  1. (12,12)The two exits are not equally likely: they race at rates 3 and 1.
  2. (34,14)
  3. (3,1)These are rates; ϑ(0) is a probability vector.
Q~∗=(−4), so a1=−(−4)−1⋅3=34 and a2=14: the first exit clock to ring decides.

Transient states have probability O(ε) after the initial layer. Why not simply delete them and use diag(νk)Q^111~ as the aggregated generator?

  1. 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 O(1).
  2. Slow jumps into transient states happen at rate O(1), and a fraction of them end in a different group; dropping them loses real group changes.
  3. Because Q~∗ would no longer be invertible.Deleting the states removes Q~∗ altogether. The problem is what happens to Q¯.
In the explorer, all slow movement from M2 back to M1 goes through s2∗. Delete the transient states and q¯21 would be 0 instead of 7/26.

For t≫ε, the total probability of the transient states is:

  1. exactly 0.The slow part keeps feeding the transient states.
  2. of order ε: fed at rate O(1) by slow jumps, drained at rate O(1/ε).
  3. decaying like e−t.The drain is fast, on the scale t/ε, but the feed never stops.
A balance of flows: inflow ≈c per unit time, mean stay ≈ε/κ, so the mass is ≈cε/κ. The explorer's "max P(transient) ÷ ε" stays roughly constant as you change ε.

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 b1 and state 2 jumps to 3 at rate b2. Find Q¯∗ and the long-run fraction of time in state 1 as ε→0.

Solution

a=(13,23). From state 1, a slow jump leads to state 2 with probability 23: q¯12=23b1. Similarly q¯21=13b2. The stationary weight of state 1 is q¯21/(q¯12+q¯21)=b2/(2b1+b2).

The exit probabilities add upUsing the row sums

Show that ∑kak=1m∗.

Solution

The transient rows of Q~1=0 say ∑kQ~∗k1mk+Q~∗1m∗=0. Multiply by −Q~∗−1: ∑kak=−Q~∗−1(−Q~∗1m∗)=1m∗. Starting from a transient state, the fast chain leaves M∗ with probability 1.

SimulationYin–Zhang, Ch. 5: Occupation Measures: Asymptotic Properties and Ramification

Occupation measures and their fluctuations

The forward equation tells us P(αε(t)=i). Applications usually need something about one path: how much time it actually spent in state i. That time, minus its expected share, goes to zero like ε, and divided by ε it becomes Gaussian.

The idea

Occupation measure. For αε generated by Q(t)/ε (weakly irreducible), set
Oiε(t)=∫0t(I{αε(s)=i}−νi(s))ds,
or more generally with a bounded weight βi(s) inside the integral, as needed when a control multiplies the indicator.
Size. sup0≤t≤TE|Oε(t)|2=O(ε). There is also an exponential bound: for a small enough constant θ (depending on T), Eexp⁡(θsupt≤T|Oε(t)|/ε) stays bounded as ε→0. So large values of Oε/ε are exponentially rare.
Central limit theorem. nε(t)=Oε(t)/ε converges weakly to a Gaussian process with independent increments, mean 0 and covariance ∫0tA(s)ds, where
Aij(t)=νi(t)∫0∞qij0(r,t)dr+νj(t)∫0∞qji0(r,t)dr,Q0(r,t)=eQ(t)r−1ν(t).

For a constant Q this is Aii=2νiZii, with the deviation matrix Z=∫0∞(eQr−1ν)dr=(1ν−Q)−1−1ν.

Why ε. In time t the fast chain goes through about t/ε nearly independent cycles, each contributing a centered amount of size ε to Oε. A sum of t/ε such terms has standard deviation εt/ε=εt.

Explore

State i
ε

Generator Q/ε with Q=(−2112−3112−3), so ν=(716,516,14). Time runs over [0,1].

24 paths of Oiε(t). Note the vertical scale: it is set by ε.
400 values of nε(1) normal density, variance A

Worked example

A two-state chain has rates λ/ε (1→2) and μ/ε (2→1). Find the limiting variance of n1ε(t), and use it to estimate the spread of the time spent in state 1 during [0,1] when λ=μ=1 and ε=0.01.

  1. What is p11(r)−ν1 for the unscaled generator?

    From Module 1, p11(r)=ν1+λλ+μe−(λ+μ)r, with ν1=μλ+μ.

  2. Compute Z11.

    Z11=∫0∞λλ+μe−(λ+μ)rdr=λ(λ+μ)2.
  3. Find A11.

    A11=2ν1Z11=2λμ(λ+μ)3.

    Check against renewal theory: on and off periods with means 1/λ, 1/μ and variances 1/λ2, 1/μ2 give variance per unit time moff2σon2+mon2σoff2(mon+moff)3, which is the same expression.

  4. Now λ=μ=1, ε=0.01. How spread out is the time spent in state 1 during [0,1]?

    A=14, so VarO1ε(1)≈εA=0.0025, a standard deviation of 0.05. The time in state 1 is 0.5±0.05 or so, even though the chain makes about 100 jumps. Fluctuations of order ε are much larger than the O(ε) errors of the forward equation.

Check your understanding

You divide ε by 4. The typical size of Oiε(1) is:

  1. divided by 4.That is how the mean EOε, of order ε, scales. The fluctuations are larger.
  2. divided by 2.
  3. unchanged.That is true of nε=Oε/ε, not of Oε.
The standard deviation is ≈εA. Step ε from 0.01 to 0.003 or so in the explorer and watch the vertical scale of the left panel.

Which statement about EOiε(t) and the typical value of |Oiε(t)| is right?

  1. Both are O(ε).The mean is. A random quantity can be much larger than its mean in absolute value.
  2. The mean is O(ε); the typical size is of order ε.
  3. The mean is of order ε.EOiε(t)=∫0t(piε(s)−νi(s))ds, and Module 4 bounds the integrand by |ψ0(s/ε)|+O(ε).
The mean comes from the forward equation: an initial layer of width ε and an O(ε) outer error. The spread comes from the randomness of the path and is of order ε. The explorer's sample mean of nε(1) is close to 0.

The explorer starts each chain from ν. If instead every chain started in state 1, would the limit of nε(1) change?

  1. 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 Oε?
  2. No: the starting state matters only for a time of order ε, which changes Oε by O(ε) and nε by O(ε).
This is why the theorem needs no assumption on p0. The initial layer is invisible after the ε scaling.

Practice

The deviation matrixA closed form

Let Q be irreducible and Π=1ν. Show that ∫0∞(eQr−Π)dr=(Π−Q)−1−Π, and that this matrix Z satisfies Z1=0 and νZ=0.

Hint

QΠ=ΠQ=0 and Π2=Π. Compute e(Q−Π)r.

Solution

Since Q and Π commute, e(Q−Π)r=eQre−Πr=eQr(I+(e−r−1)Π)=eQr+(e−r−1)Π, using eQrΠ=Π. The eigenvalues of Q−Π are −1 (on 1) and the nonzero eigenvalues of Q, all with negative real part, so ∫0∞e(Q−Π)rdr=(Π−Q)−1. Hence ∫0∞(eQr−Π)dr=∫0∞(e(Q−Π)r−e−rΠ)dr=(Π−Q)−1−Π. Finally (eQr−Π)1=0 and ν(eQr−Π)=0 for every r.

A tail estimateUsing the Gaussian limit

With λ=μ=1 and ε=0.01 as in the worked example, estimate the probability that the chain spends more than 0.55 time units in state 1 during [0,1].

Solution

We need O1ε(1)>0.05, i.e. n1ε(1)>0.5. With limiting standard deviation 1/4=0.5, that is one standard deviation: probability ≈0.16.

SimulationYin–Zhang, Ch. 5: Occupation Measures: Asymptotic Properties and Ramification

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 Q¯. Where it is inside the group becomes a fast blur, whose time fractions are given by νk.

The idea

Aggregated process. α¯ε(t)=k when αε(t)∈Mk. For fixed ε it is usually not Markov: how soon it leaves a group depends on the state inside the group.
Weak convergence. Under the assumptions of Module 5, α¯ε(⋅) converges weakly (in the space of right-continuous paths with left limits) to a Markov chain α¯(⋅) generated by Q¯(t).
Occupation inside a group. For every state skj, uniformly in t≤T,
E(∫0t(I{αε(s)=skj}−νjk(s)I{α¯ε(s)=k})ds)2=O(ε).
Time in skj is νjk times time in Mk, along each path, up to O(ε).

The centering uses the random indicator I{α¯ε=k}, not a deterministic function: the time spent in a group stays random in the limit, because α¯ itself is random. Scaled by 1/ε, these occupation errors converge to a switching diffusion, a Brownian motion whose variance rate depends on the current value of α¯(t); its one-time distributions are Gaussian mixtures rather than Gaussian.

Explore

The four-state chain of Module 5: q¯12=0.5, q¯21=0.6, ν1=(13,23), ν2=(34,14).

Top: which state αε(t) is in (blue band: group M1; gold band: M2). Bottom: the group α¯ε(t).

Worked example

In the explorer's chain, show that α¯ε is not a Markov chain for fixed ε, and explain why it becomes one in the limit.

  1. Through which states can the chain enter M1?

    The slow moves into M1 are s21→s12 (rate 0.4) and s22→s11 (rate 1.2). So it enters at s12 or at s11, depending on where it was in M2.

  2. Just after entering, what is the rate of leaving M1?

    0.9 if it entered at s11, 0.3 if at s12. The future of α¯ε depends on more than its present value 1, so α¯ε is not Markov.

  3. How long does the chain remember its entry point?

    The block Q~1/ε has nonzero eigenvalue −3/ε. After a time of a few times ε/3 the position inside M1 has distribution close to ν1, whatever the entry point.

  4. What does a stay in M1 look like in the limit?

    Over a stay of order 1, the exit rate is averaged against ν1 and equals q¯12=13⋅0.9+23⋅0.3=0.5. The memory lasts only O(ε), 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 [0,T], as ε→0:

  1. both the number of jumps and the number of group switches grow like 1/ε.Group switches are driven by Q^, whose rates do not depend on ε.
  2. the number of jumps grows like 1/ε but the number of group switches stays of order 1.
  3. both stay of order 1.Inside a group the rates are of order 1/ε.
Compare the first two statistics in the explorer as you move ε: jumps explode, switches do not.

Why is time in skj compared with νjkI{α¯ε(s)=k} rather than with νjkϑk(s)?

  1. The two give the same limit.∫0t(I{αε=skj}−νjkϑk)ds does not go to 0: the time spent in Mk is random even in the limit.
  2. The time the path spends in Mk stays random as ε→0, so only the split inside the group becomes deterministic.
  3. Because ϑk is not known explicitly.It is: it solves ϑ′=ϑQ¯. The issue is randomness, not computability.
Contrast Module 7: with a single irreducible group there is nothing slow left to be random, and the centering is deterministic.

When is α¯ε exactly a Markov chain for every ε?

  1. Never.It can be, under a condition on Q^.
  2. When, for each pair of groups k≠j, every state of Mk has the same total slow rate into Mj.
  3. When every Q~k is irreducible.The explorer's blocks are irreducible, and α¯ε still is not Markov there.
This is lumpability. Then the exit rate does not depend on the position inside the group, and α¯ε is Markov with generator Q¯, for every ε.

Practice

Long-run time in one stateCombining the two scales

For the explorer's chain, find the limit as ε→0 of the long-run fraction of time spent in s12.

Solution

The aggregated chain spends a fraction q¯21/(q¯12+q¯21)=6/11 of the time in M1, and inside M1 a fraction ν21=2/3 is in s12. Answer: 4/11≈0.364, the same as in the worked example of Module 5.

Lumpability exactlyChecking the Markov property

Change the explorer's slow rates so that α¯ε becomes Markov for every ε while Q¯ stays the same.

Solution

Give both states of M1 slow rate 0.5 into M2 (say s11→s21 at 0.5 and s12→s22 at 0.5), and both states of M2 rate 0.6 into M1. The averages with ν1 and ν2 are still 0.5 and 0.6, and now the exit rate does not depend on the state inside the group.

Drag the payoffYin–Zhang, Ch. 6: Asymptotic Expansions of Solutions for Backward Equations

Backward equations and the terminal layer

An expected payoff collected at a final time T solves the backward equation, which runs from T back toward 0. The two-time-scale picture holds in reverse: a thin layer just before T where values inside a group merge, then a slow evolution governed by the same Q¯ as before.

The idea

Backward equation. For a payoff vector f (a column), the conditional expectations uε(t,i)=E[f(αε(T))∣αε(t)=i] form the column vector uε(t)=Pε(T,t)f, which solves
duε(t)dt=−Qε(t)uε(t),uε(T)=f.
A running reward g adds −g(t) to the right side.
Expansion. uε(t)=∑i≤nεiφi(t)+∑i≤nεiψi((T−t)/ε)+O(εn+1): an outer part, and a terminal layer in the stretched backward time τ=(T−t)/ε.
Leading terms (block-diagonal Q~, groups Mk). φ0(t)=1~u¯(t): constant on each group, with
du¯dt=−Q¯(t)u¯(t),u¯k(T)=νk(T)fk=∑jνjk(T)f(skj),
and the terminal layer ψ0(τ)=eQ~(T)τ(f−1~u¯(T)), which decays exponentially in τ.

Duality. Forward equations act on row vectors (distributions), and the leading term has the form ϑdiag(νk). Backward equations act on column vectors (functions), and the leading term has the form 1~u¯. In both, Q¯=diag(νk)Q^1~ governs the slow evolution. Value functions of control problems are backward objects, so Chapters 7 to 10 rest on this expansion.

Explore

Payoff presets:
Drag the four dots at t=T to set f. s11 s12 s21 s22; bands: u¯1,u¯2
The terminal layer: the last 2.5ε before T, in units of ε. Dashed: 1~u¯+ψ0.

Worked example

Use the four-state chain of Module 5 with f=I{s11}, so uε(t,i)=P(αε(T)=s11∣αε(t)=i). Find the leading-order answer for t well before T.

  1. What does the terminal layer do to f=(1,0,0,0)?

    Inside M1, the values 1 and 0 merge into their ν1-average 13⋅1+23⋅0=13; inside M2 both are 0. So u¯(T)=(13,0).

  2. Solve du¯/dt=−Q¯u¯ backward from T, writing s=T−t.

    u¯(t)=eQ¯su¯(T). With q¯12=0.5 and q¯21=0.6, the first column of eQ¯s is 11.1(0.6+0.5e−1.1s, 0.6−0.6e−1.1s), so

    u¯1=13⋅0.6+0.5e−1.1s1.1,u¯2=13⋅0.6−0.6e−1.1s1.1.
  3. What do both tend to as T−t→∞? Interpret.

    13⋅0.61.1=211≈0.182, the long-run probability of s11 found in Module 5. Far from T, the starting state is forgotten.

  4. Is there a terminal layer when f is constant on each group, say f=(0,0,1,1)?

    No: f−1~u¯(T)=0, so ψ0=0. The answer is P(α¯(T)=2∣α¯(t)=k) to leading order. Try the "indicator of M2" preset: the curves leave T without any fast transient.

Check your understanding

Near t=T the values uε(t,s11) and uε(t,s12) differ. Going back from T, how long until they agree to within 1%?

  1. A time of order ε (here about ε3ln⁡100).
  2. A time of order 1.The merging is done by the fast part Q~/ε, not the slow part.
  3. They never agree: their payoffs differ.The payoffs differ only at T. Starting slightly earlier, the chain has time to mix inside its group.
The difference is multiplied by e−3(T−t)/ε, 3 being the mixing rate of block Q~1. Look at the zoomed panel.

Which average of the payoff over a group enters u¯(T)?

  1. The plain average over the states of the group.States are not visited equally often by the fast chain.
  2. The νk-weighted average ∑jνjkf(skj).
  3. The value at the state the chain is in at time t.That state is forgotten within a time of order ε.
At time T the chain is, given its group, distributed close to νk, whatever state it was in a little earlier.

Why is the boundary layer at T for the backward equation, but at 0 for the forward equation?

  1. Each equation has a layer where its data are given: p0 at time 0 for the forward equation, f at time T for the backward one.
  2. Because Qε changes fastest near T.The layer appears even for constant generators. It is about the side condition.
  3. The backward equation has layers at both ends.Its condition is imposed only at T; at t=0 nothing has to be matched.
In both cases the data need not have the shape of the leading term (ϑdiag(νk) or 1~u¯), and the layer is where the mismatch is absorbed.

Practice

A maximum principleBounds on expected payoffs

Show that minif(i)≤uε(t,j)≤maxif(i) for all t≤T and all j, in two ways: probabilistically, and from the matrix form uε(t)=Pε(T,t)f.

Solution

Probabilistically, uε(t,j) is an expectation of f(αε(T)), which lies between the min and max. In matrix form, each row of Pε(T,t) is a probability vector, so uε(t,j) is a convex combination of the f(i). In the explorer, no curve ever leaves the range of the four dots.

Probability of ending in a groupNo layer at all

For f=(0,0,1,1) in the explorer's chain, find u¯(t) and the leading-order value of uε(0,s11) when T=3.

Solution

u¯(T)=(0,1), and u¯=eQ¯s(0,1)T with s=T−t: u¯1=0.5−0.5e−1.1s1.1, u¯2=0.5+0.6e−1.1s1.1. At t=0, s=3 and e−3.3≈0.0369, so uε(0,s11)≈0.5⋅0.96311.1≈0.438.

CalculatorYin–Zhang, Ch. 7: Markov Decision Problems

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 O(ε), and its decisions give a policy that is nearly optimal for the original problem.

The idea

The problem. The generator depends on an action: Qε(u)=Q~(u)/ε+Q^(u), with Q~(u) block diagonal as before. A stationary feedback policy picks an action u(i)∈Γ in each state. Its cost is
Jε(i,u)=E∫0∞e−ρtG(αε(t),u(αε(t)))dt,αε(0)=i,
and vε(i)=minuJε(i,u). For a fixed policy, Jε=(ρI−Qε(u))−1G(u).
Dynamic programming. ρvε(i)=mina∈Γ{G(i,a)+∑j≠iqijε(a)(vε(j)−vε(i))}.
Limit problem. Its states are the groups. In group k a decision is a whole tuple Uk=(uk1,…,ukmk), one action per state of the group. It fixes the fast block Q~k(Uk) and hence its quasi-stationary distribution νk(Uk), which gives the averaged cost and rates
G¯(k,Uk)=∑jνjk(Uk)G(skj,ukj),Q¯(U)=diag(ν1(U1),…,νl(Ul))Q^(U)1~.
Let v(k) be the optimal value of this l-state problem.
Asymptotic optimality. vε(i)→v(k) for i∈Mk. With finitely many actions, vε(i)−v(k)=O(ε), and the policy uc(skj)=u∗kj read off an optimal limit decision satisfies Jε(i,uc)−vε(i)=O(ε).

Explore

s₁₁fast (÷ε): →s₁₂: 2 / 1slow: →s₂₁: 0.2 / 0.05cost rate: 0 / 2
Your action
s₁₂fast (÷ε): →s₁₁: 1 / 3slow: →s₂₂: 1 / 0.5cost rate: 1 / 4
Your action
s₂₁fast (÷ε): →s₂₂: 1 / 1slow: →s₁₁: 0.1 / 1cost rate: 4 / 6.5
Your action
s₂₂fast (÷ε): →s₂₁: 2 / 4slow: →s₁₂: 0.3 / 1.5cost rate: 6 / 7.5
Your action

Each entry reads action 0 / action 1. Group M1={s11,s12} is the cheap regime, M2 the expensive one. Action 1 ("maintain") costs more; it slows the drift into M2 or speeds the return. Discount rate ρ=0.5.

Solid: optimal vε for s11 s12 s21 s22. Dashed: your policy. Dotted lines: the limit values v(1),v(2). ε is on a log scale. Every value is computed exactly by a linear solve.

Worked example

Solve the explorer's limit problem for the decision U1=(0,1), U2=(0,1), and compare it with U1=(0,0), U2=(0,1).

  1. With U1=(0,1), what are ν1, G¯(1) and q¯12?

    Fast rates: s11→s12 at 2, s12→s11 at 3, so ν1=(35,25). Then G¯(1)=35⋅0+25⋅4=1.6 and q¯12=35⋅0.2+25⋅0.5=0.32.

  2. Same for group 2 with U2=(0,1).

    s21→s22 at 1, s22→s21 at 4, so ν2=(45,15), G¯(2)=45⋅4+15⋅7.5=4.7 and q¯21=45⋅0.1+15⋅1.5=0.38.

  3. Solve ρv=G¯+Q¯v.

    0.82v1−0.32v2=1.6 and −0.38v1+0.88v2=4.7. The determinant is 0.82⋅0.88−0.32⋅0.38=0.6, so

    v1=1.6⋅0.88+0.32⋅4.70.6≈4.853,v2=0.82⋅4.7+0.38⋅1.60.6≈7.437.
  4. Now try U1=(0,0) with the same U2. Is it better?

    ν1=(13,23), G¯(1)=23, q¯12=13⋅0.2+23⋅1=1115≈0.733. Solving gives v=(5.00,7.50): cheaper to run, but the chain drifts into the expensive group more than twice as fast. Checking all 16 decisions shows (0,1),(0,1) is optimal, so uc=(0,1,0,1), and the explorer confirms it is exactly optimal for the full problem once ε≲0.4.

Check your understanding

Why is a decision in the limit problem a whole tuple Uk, one action per state of the group, rather than a single action for the group?

  1. Different states of the group can use different actions, and the mix determines νk, hence both G¯ and Q¯.
  2. Because the limit problem has more states than the original.It has fewer: one per group.
  3. A single action per group would give the same value.Not here: the optimal uc=(0,1,0,1) uses both actions in each group.
The controller still sees the fast state, so it can act differently in each one. In the limit the effect of that local policy is summarised by νk(Uk).

At ε=1 the optimal policy is (0,0,1,1), not uc=(0,1,0,1). Does this contradict the theorem?

  1. Yes: uc should be optimal.The theorem promises near-optimality as ε→0, not optimality at a given ε.
  2. No: the theorem says Jε(uc)−vε=O(ε), which at ε=1 allows a visible gap.
At ε=1 the "fast" moves are not fast and the chain does not mix inside a group, so the averaging behind the limit problem is rough. In the explorer the gap vanishes once ε is below about 0.4.

As ε→0, vε(s11)−vε(s12)→0, although the running costs in those states differ. Why?

  1. Because the optimal actions in the two states are equal.In the limit policy they are not: 0 in s11, 1 in s12.
  2. The chain moves between s11 and s12 within a time of order ε, so the starting state affects the cost only over a time of order ε.
  3. Because discounting makes all values equal.The values of the two groups stay different, about 4.85 and 7.44.
So vε(i) depends at leading order only on the group of i, which is why the limit problem has one state per group.

Practice

Discounted costs are averagesThe resolvent

Show that (ρI−Q)−1=∫0∞e−ρteQtdt for a generator Q and ρ>0. Conclude that it has nonnegative entries with row sums 1/ρ, so ρJ is a weighted average of running costs.

Solution

e−ρteQt=e(Q−ρI)t, and ddte(Q−ρI)t=(Q−ρI)e(Q−ρI)t. Integrating over [0,∞) (the integrand decays since eQt is stochastic) gives (Q−ρI)∫0∞e(Q−ρI)tdt=−I. Entries are nonnegative because eQt is, and row sums are ∫0∞e−ρtdt=1/ρ.

The long-run average cost of ucLetting ρ → 0

In the limit, what is the long-run average cost per unit time of the policy uc in the explorer?

Solution

The aggregated chain under uc has q¯12=0.32, q¯21=0.38, so it spends fractions 0.380.70 and 0.320.70 of the time in the two groups. The average cost is 0.38⋅1.6+0.32⋅4.70.70=2.1120.70≈3.017.

SimulationYin–Zhang, Ch. 8: Stochastic Control of Dynamical Systems

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 ε, and the problem reduces to a deterministic one in which the machine has its average capacity.

The idea

Controlled system. A state xε(t)∈Rn driven by a two-time-scale chain: x˙ε=f(xε,αε(t),u(t)), with u(t)∈Γ chosen from the past of αε, and cost Jε=E∫0∞e−ρtG(xε(t),αε(t),u(t))dt (or over a finite horizon). The book assumes f affine in u, G convex, and Q~ block diagonal with irreducible blocks.
Limit problem. Take one irreducible fast block, for simplicity. A limit control is a tuple U=(u1,…,um), one control per machine state, and everything is averaged against ν:
x˙=∑iνif(x,i,ui),cost ∫0∞e−ρt∑iνiG(x,i,ui)dt.
With several groups, the averaging is done within each group, and the limit system still switches between groups according to Q¯.
Near optimality. The value functions converge: |vε(x,α)−v0(x)|≤K(1+|x|κ)ε for α in the group. A control built from a limit control U(t) as uε(t)=∑iI{αε(t)=i}ui(t) is asymptotically optimal. The occupation-measure bounds of Module 7 are what make the comparison work.

The example. One machine, up or down: breakdown rate λ/ε, repair rate μ/ε. Surplus (inventory minus backlog) x˙=u−z, with 0≤u≤k when up and u=0 when down; cost c+x++c−x− per unit time, long-run average. A hedging-point policy with level θ produces at full rate below θ, exactly z at θ, and nothing above. This is the classical setting where such policies are known to be optimal.

Average capacity is kμ/(λ+μ), and the limit problem is a reliable machine of that capacity. If that exceeds z, the limit plan keeps x=0 forever at zero cost.

Explore

λ=1, μ=2 (up two thirds of the time), capacity k=3, demand z=1.5, inventory cost c+=1, backlog cost c−=5.

The surplus x(t), starting from 0. Shaded: machine down.
exact J(θ) your θ best θ∗. Ring: J(θ) estimated by simulation.

Worked example

Find the long-run behaviour of the surplus under a hedging-point policy, the optimal θ, and how it scales with ε. Assume kμ/(λ+μ)>z.

  1. Which levels does x visit in the long run, and with which velocities?

    Once below θ, x never goes above it. Up and below θ: x˙=k−z>0. Up at θ: x˙=0. Down: x˙=−z. So the stationary law lives on (−∞,θ], with an atom at θ (machine up and waiting).

  2. Let fup(x),fdown(x) be the stationary densities below θ. Why is (k−z)fup=zfdown, and what form must they have?

    In equilibrium the net flow of probability across any level x<θ is zero: mass crosses upward at rate (k−z)fup(x) and downward at rate zfdown(x). The balance equation for the up state, ddx[(k−z)fup]=−λεfup+μεfdown, then gives f∝eβ(x−θ) with

    β=1ε(μz−λk−z)>0.

    So x−θ has a law that does not depend on θ: an atom at 0 and an exponential tail of mean depth of order 1/β, proportional to ε.

  3. Differentiate J(θ)=Eh(θ+Y), where Y=x−θ and h(x)=c+x++c−x−. What is the optimality condition?

    Since the law of Y is free of θ, J′(θ)=Eh′(θ+Y)=c+P(x>0)−c−P(x<0) (x has no atom at 0 when θ>0). So at the optimum

    P(x<0)=c+c++c−,

    a "critical fractile": backlog should occur a fraction 1/6 of the time with c+=1, c−=5.

  4. With the explorer's numbers, find θ∗.

    β=1ε(21.5−11.5)=23ε. Normalising the densities and the atom shows P(x<θ)=23 for every θ and ε, so P(x<0)=23e−βθ. Setting this to 16: e−βθ=14, so

    θ∗=ln⁡4β=1.5εln⁡4≈2.08ε.

    Both θ∗ and the optimal cost are proportional to ε, and tend to the limit problem's answers, 0 and 0.

Check your understanding

Keep θ=1 fixed and let ε→0. What does the long-run cost J(1) tend to?

  1. 0, the value of the limit problem.Only if θ shrinks too. With θ=1 you keep one unit of stock.
  2. c+⋅1=1: excursions below θ are only O(ε) deep, so x≈1 nearly all the time.
  3. ∞.The average capacity exceeds demand, so the surplus is stable for every θ.
Set θ=1 in the explorer and slide ε down: the cost at the gold dot approaches 1 while the minimum of the curve slides toward θ=0.

In the limit problem, why does the capacity enter only through kνup=kμ/(λ+μ)?

  1. 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.
  2. The machine state switches so fast that production averages out: over any interval of order 1 it is up a fraction νup of the time.
  3. Because the policy produces at full speed k all the time.It cannot produce when the machine is down.
The dynamics are linear in u, so ∫(u−z)dt depends on the path of αε only through occupation times, which concentrate at ν (Module 7).

In the explorer, doubling ε doubles θ∗. Why?

  1. Down periods last O(ε), so the dips below θ are O(ε) deep, and the safety stock that guards against them scales the same way.
  2. Because the cost rates c± are proportional to ε.The cost rates do not change with ε.
  3. It is a coincidence of these parameter values.It holds for any parameters: the whole stationary law of x−θ is a rescaling by ε.
Rescaling time by ε maps the problem with parameter ε onto the one with ε=1, with x scaled by ε. Watch "θ* ÷ ε" in the stats: it is always 1.5ln⁡4≈2.079.

Practice

When is the surplus stable?The sign of β

Show that β>0 exactly when the average capacity exceeds demand, kμ/(λ+μ)>z. What happens to the surplus otherwise?

Solution

εβ=μ(k−z)−λzz(k−z), and μ(k−z)−λz>0⟺μk>(λ+μ)z. If the inequality fails, the average drift below θ, νup(k−z)−νdownz=νupk−z, is ≤0; the surplus drifts to −∞ (or is null recurrent at equality) and the long-run cost is infinite.

The limit problem from a backlogA deterministic plan

In the limit problem with the explorer's numbers, start from x(0)=−2 and ignore discounting over the transient. What is the optimal plan, how long does it take to clear the backlog, and what does it cost?

Solution

Produce at the full average rate kνup=2 until x=0: x˙=0.5, so it takes 4 time units. Then hold x=0, producing z/νup=2.25≤3 whenever the machine is up. The cost is c−∫04(2−t/2)dt=5⋅4=20.

SimulationYin–Zhang, Ch. 9: Numerical Methods for Control and Optimization

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

Solving the HJB equation numerically. One route to an optimal control is to discretise the dynamic-programming (HJB) equation on a grid of mesh Δ, replacing each derivative by a one-sided difference taken in the direction of the drift. The discrete equations are themselves the dynamic-programming equations of a controlled Markov chain on the grid, and their solutions converge to the value function as Δ→0 (in the viscosity sense).
Threshold policies. Often the control is of threshold type with parameters θ: the action depends only on which side of some levels the state lies, as with the hedging point. The long-run average cost J(θ) becomes a function of finitely many numbers, to be minimised.
Stochastic approximation. Update θn+1=θn−ηgn, where gn is an estimate of ∇J(θn) computed from the simulated system over the n-th time window. Here, with window length W and a small δ,
gn=J^n(θn+δ)−J^n(θn−δ)2δ,
where J^n is the time-average cost over the window. Both runs use the same machine history (common random numbers): it does not depend on θ, so only the effect of the policy differs.
ODE method. Interpolate the iterates in time steps of η. As η→0 the interpolated path converges weakly to the solution of θ˙=−∇J(θ) (up to the bias of the gradient estimate), and over long times it concentrates near a stable point θ∗ of that ODE. With a constant step the iterates keep fluctuating around θ∗; the fluctuations shrink as η does.

Explore

Step size η
Window W
Common random numbers

The machine of Module 11 with ε=1; finite-difference step δ=0.25. Each step simulates the next window of length W twice, at θn+δ and at θn−δ, continuing from where the previous window ended.

θn exact θ∗
Exact J(θ), with the last 30 iterates (darker is more recent).
Press Run. With η = 0.3 and W = 20 the iterates reach θ* = 2.08 within a few dozen steps and then jitter around it (on average slightly to the right, where J is flatter; that offset shrinks with η). Turn common random numbers off: the two cost estimates now have independent noise, the slope estimates become much noisier, and the iterates wander, mostly into the flat region to the right of θ*. A short window W = 5 also makes each slope estimate noisier. A smaller η is steadier but slower.

Worked example

The finite difference has its own bias: even with perfect cost estimates, the recursion settles where the difference quotient vanishes, not where J′ does. Compute that point for the explorer's machine (ε=1).

  1. From Module 11, write J′(θ) for θ>0.

    J′(θ)=c+−(c++c−)P(x<0)=1−6⋅23e−βθ=1−4e−βθ, with β=23.

  2. For θ≥δ, compute the exact central difference J(θ+δ)−J(θ−δ)2δ.

    Integrate J′ over [θ−δ,θ+δ] and divide by 2δ:

    J(θ+δ)−J(θ−δ)2δ=1−4e−βθsinh⁡βδβδ.
  3. Where does it vanish?

    At e−βθ=14⋅βδsinh⁡βδ, i.e.

    θδ=θ∗+1βln⁡sinh⁡βδβδ≈θ∗+βδ26.
  4. Evaluate the bias for δ=0.25 and δ=1.

    δ=0.25: βδ=16, bias ≈0.0069, invisible next to the noise. δ=1: βδ=23, sinh⁡(23)/23≈1.0757, bias ≈1.5ln⁡1.0757≈0.109. A large δ gives quieter estimates but a biased answer: the usual trade-off of finite differences.

Check your understanding

Why run θn+δ and θn−δ on the same machine history?

  1. Otherwise the gradient estimate would be biased.Independent runs give an estimate with the same mean. The difference is in its variance.
  2. The noise in the two cost estimates is then largely shared and cancels in the difference, so the slope estimate has much smaller variance.
  3. To save simulation time.Both runs still have to be simulated; only the machine history is shared.
Var(J^+−J^−)=VarJ^++VarJ^−−2Cov, and sharing the randomness makes the covariance large. Toggle it off in the explorer and compare.

With a constant step size η, what do the iterates do in the long run?

  1. Converge to θ∗ exactly.Each step adds noise of size η× (noise in gn), which never stops.
  2. Fluctuate in a neighbourhood of θ∗ whose size shrinks as η→0.
  3. Drift away, because the noise accumulates.Near θ∗ the mean step −ηJ′(θ) pulls them back.
To converge exactly you need decreasing steps, typically ∑nηn=∞ and ∑nηn2<∞. A constant step can track a slowly changing optimum, which decreasing steps cannot.

Which ODE describes the iterates for small η, ignoring the finite-difference bias?

  1. θ˙=−J′(θ), the gradient flow of the long-run cost.
  2. θ˙=−J^n′(θ), with the noisy estimates.In the limit the noise averages out; the ODE involves only its mean.
  3. θ˙=−J(θ).The recursion moves against the slope, not against the cost itself.
Over a stretch of 1/η iterations, many independent windows are averaged. This is the same averaging idea as in the two-time-scale chains: here the "fast" variable is the simulated system and the "slow" one is θ.

Practice

A pathwise derivativeNo finite differences needed

Start the surplus at x(0)=θ and keep the machine history fixed. Show that xθ(t)−θ does not depend on θ, and derive the unbiased slope estimate 1W∫0W(c+I{x(t)>0}−c−I{x(t)<0})dt for ddθJ^.

Solution

The dynamics of y=x−θ involve only y and the machine state (full speed when y<0, match demand at y=0), and y(0)=0. So xθ(t)=θ+y(t) with y free of θ. Then J^(θ)=1W∫0Wh(θ+y(t))dt, and differentiating under the integral gives 1W∫0Wh′(x(t))dt, which is the formula. This is infinitesimal perturbation analysis; it uses one run instead of two.

A Markov chain approximationDiscretising a drift

For x˙=b with constant b, build a continuous-time chain on the grid ΔZ with the right mean drift and a variance per unit time that vanishes as Δ→0.

Solution

Jump x→x+Δ at rate b+/Δ and x→x−Δ at rate b−/Δ. The mean drift is Δ(b+−b−)/Δ=b and the variance per unit time is Δ2|b|/Δ=|b|Δ→0. With the machine state added, the grid chain jumps also as α does, and its DP equation is the upwind discretisation of the HJB equation.

InteractiveYin–Zhang, Ch. 10: Hybrid LQG Problems

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

Hybrid LQG problem. dx=(A(α(t))x+B(α(t))u)dt+σdw on [s,T], with α independent of the Brownian motion w, and cost
J=E[∫sT(xTM(α)x+uTN(α)u)dt+x(T)TDx(T)],
with M(i)≥0 and N(i),D>0.
Coupled Riccati equations. The value is v(s,x,i)=xTK(s,i)x+q(s,i), where for each state i
K˙i=−KiAi−AiTKi−Mi+KiBiNi−1BiTKi−∑jqijKj,Ki(T)=D,
and the optimal control is u=−Ni−1BiTKix in regime i. The term ∑jqijKj=∑j≠iqij(Kj−Ki) is the generator acting on the value function: it accounts for future switches.
Two-time-scale limit. With qij=qijε from Q~/ε+Q^, Kε(s,skj)→K¯(s,k) for every state of group k, where K¯ solves the Riccati system of the averaged problem:
K¯˙k=−K¯kA¯k−A¯kTK¯k−M¯k+K¯kBN−1BT―kK¯k−∑lq¯klK¯l,
each bar being a νk-average over the group. The control uε=−N−1(αε)BT(αε)K¯(t,α¯ε(t))x is nearly optimal: its cost approaches the optimal one as ε→0.

Only the Riccati part is shared within a group. The feedback still uses the B and N of the current state.

Explore

Scalar system, the four-state chain of Module 5. a=(1.2,−0.6,0.5,−1), b=(1,0.5,1.5,1), m=n=1, D=0.5, T=3. Averages: a¯=(0, 0.125), b2―=(0.5, 1.9375).

Thin lines: Kε(t,i) for the four states. Wide bands: K¯(t,1) (blue) and K¯(t,2) (gold).
maxt,i|Kε−K¯| against ε, log–log; dashed: slope 1. Gold dot: the current ε.
The four Riccati equations are integrated backward from K(T)=D. With ε large they spread out, each regime pricing its own dynamics; as ε shrinks the two states of each group are pulled together by the 1/ε coupling, and the pair follows the averaged equation. The error falls along the slope-1 line: it is O(ε). Note state s11 alone is unstable (a=1.2), but its group averages to a¯=0.

Worked example

A scalar system switches very fast between two regimes, a1=2 and a2=−1, spending fractions ν=(13,23) of the time in them; b=m=n=1 in both, D=0. Find the limiting Riccati solution and its long-horizon gain, and check the closed loop.

  1. Write the scalar Riccati equations for the two regimes.

    K˙i=−2aiKi−1+Ki2−1ε∑jq~ijKj, Ki(T)=0.

  2. Why are K1 and K2 nearly equal for small ε?

    The coupling term 1εq~12(K2−K1) is huge unless K1≈K2. Any difference is damped at rate O(1/ε), so K1−K2=O(ε).

  3. Average the two equations with weights ν to get an equation for the common value K¯.

    The 1/ε terms cancel because νQ~=0. What remains is K¯˙=−2a¯K¯−1+K¯2 with a¯=13⋅2+23⋅(−1)=0: K¯˙=K¯2−1, K¯(T)=0. Its solution is K¯(t)=tanh⁡(T−t).

  4. Far from T the gain is K¯≈1, so u≈−x. Is the closed loop stable?

    In regime 1 the closed loop is x˙=(2−1)x=x, unstable on its own. In regime 2 it is x˙=−2x. With fast switching, x(t)≈x(0)exp⁡∫0t(a(αε(s))−1)ds≈x(0)e(a¯−1)t=x(0)e−t: stable. The averaged design stabilises the switched system though it would not stabilise regime 1 alone.

Check your understanding

Where does the term ∑jqijKj in the Riccati equation for regime i come from?

  1. From the Brownian noise σdw.The noise only enters the equation for q(s,i), through tr(σσTKi).
  2. From the chance of switching to regime j: it is the generator of α acting on the value function xTK(s,⋅)x.
  3. From the terminal cost D.D enters only through the terminal condition.
In the HJB equation the chain contributes ∑j≠iqij(v(s,x,j)−v(s,x,i)). With v=xTKx+q this is xT(∑jqijKj)x+…, since ∑jqij=0.

In the nearly optimal feedback uε=−N−1(αε)BT(αε)K¯(t,α¯ε)x, which part no longer depends on the state inside the group?

  1. K¯, the Riccati solution; B and N are still those of the current state.
  2. All of it: the feedback depends only on the group.The controller still knows the current state and uses its B and N.
  3. None of it.The Riccati part is shared within a group, as the explorer shows.
If B and N happen to be the same within each group, the whole feedback depends only on the group. Otherwise only the value-function part is shared.

To form the averaged equation, a student averages b first and then squares: (∑jνjbj)2/n. What is wrong?

  1. Nothing; it gives the same answer.In the explorer's group 2, (0.75⋅1.5+0.25⋅1)2=1.89, while 0.75⋅2.25+0.25⋅1=1.94.
  2. The control enters the cost quadratically, so the right average is b2/n―=∑jνjbj2/nj, which is larger by Jensen's inequality.
  3. One should average K instead of the coefficients.K is the unknown being solved for; the coefficients are what get averaged.
In each state the best control removes bj2K2/nj from the cost rate, and the fast chain averages those reductions. Equivalently, the limit control is a tuple U=(uk1,…) and the averaged control effect is ∑jνjBjukj.

Practice

From HJB to RiccatiThe scalar case

For a scalar system with one regime, substitute v=K(s)x2+q(s) into 0=vs+minu{(ax+bu)vx+mx2+nu2}+12σ2vxx and derive the equations for K and q.

Solution

The minimum over u is at u=−bvx/(2n)=−bKx/n, with minimum value axvx+mx2−b2K2x2/n. Matching the x2 terms: K˙+2aK+m−b2K2/n=0; the constant terms: q˙+σ2K=0. Terminal conditions K(T)=D, q(T)=0.

The long-horizon gainAn algebraic Riccati equation

For one scalar regime, find the limit of K(t) as T−t→∞, and check it against the worked example.

Solution

Set K˙=0: b2nK2−2aK−m=0, whose positive root is K=nb2(a+a2+b2m/n). With a=0 and b=m=n=1, K=1, the limit of tanh⁡(T−t). The closed loop rate is a−b2K/n=−a2+b2m/n<0: always stable.