Skip to content
Tutorials Center
My learning

Topics

Lesson 26 of 36 ยท Continuous-Time Markov Chains

Kolmogorov Equations and Transient Behavior

Derive the forward and backward Kolmogorov equations, solve them numerically with Euler steps and uniformization, and watch a chain approach equilibrium.

The stationary distribution describes where a chain ends up. Often you need the opposite: the distribution at a specific time t, starting from a known state. This is the transient behavior. The tool is a pair of differential equations named after Andrey Kolmogorov. You already know the solution, P(t) = exp(Qt); here you see where it comes from and meet other ways to compute it.

Where the equations come from

Condition on what happens in the first tiny interval h of a total time t + h. Using P(h) โ‰ˆ I + Qh, the Chapman-Kolmogorov identity P(t+h) = P(t) P(h) gives

Text
P(t+h) โ‰ˆ P(t)(I + Qh)     so     (P(t+h) - P(t)) / h โ‰ˆ P(t) Q

Letting h โ†’ 0:

Text
P'(t) = P(t) Q      (forward equation)
P'(t) = Q P(t)      (backward equation)

Both have P(0) = I. The forward equation looks at the last small step and is usually the one used for distributions. If p(t) is the row vector of state probabilities at time t, then

Text
p'(t) = p(t) Q        so     p(t) = p(0) exp(Qt)

Entry by entry, the forward equation says "the change of probability in state j is inflow minus outflow":

Text
d p_j / dt = sum over iโ‰ j of p_i q_ij  -  p_j q_j

Method 1: Euler steps

The simplest numerical scheme replaces the derivative by a finite difference: p(t+h) = p(t) (I + Qh). It is accurate only for small h, and it needs h < 1 / max qแตข to keep probabilities non-negative. Below it is compared with the exact matrix exponential.

Python Euler steps versus the matrix exponential

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The error shrinks roughly in proportion to the step size: a first-order method. It is good for understanding, not for precision.

Method 2: Uniformization

A cleverer method turns the CTMC into a discrete chain run at random Poisson times. Pick a rate ฮ› โ‰ฅ max qแตข and define the stochastic matrix

Text
P_u = I + Q / ฮ›

All entries are non-negative and rows sum to 1, so P_u is a valid transition matrix. Imagine events of a Poisson process with rate ฮ›; at each event, the chain takes one step of P_u (including possible "self-jumps" that do nothing). Then

Text
p(t) = ฮฃ over k โ‰ฅ 0 of  [ e^(-ฮ›t) (ฮ›t)^k / k! ] ยท p(0) P_u^k

This is a Poisson-weighted average of discrete-time distributions. Every term is a probability, so there are no cancellations between large positive and negative numbers, which is why uniformization is the standard numerical method.

Python Uniformization

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Even for t = 10, a few dozen terms reach a tolerance of about 10โปยนยฒ.

Convergence to equilibrium

For an irreducible finite chain, p(t) โ†’ ฯ€ as t โ†’ โˆž, whatever the starting state. How quickly depends on the eigenvalues of Q. One eigenvalue is 0 (belonging to ฯ€), and the others have negative real parts. The slowest non-zero decay rate, the spectral gap, controls the speed: โ€–p(t) - ฯ€โ€– shrinks like e^(-gap ยท t).

flowchart LR
  A["p(0)"] -->|"forward equation p' = pQ"| B["p(t)"]
  B -->|"t grows, gap decays"| C["ฯ€"]

Transient distributions flow toward the stationary vector.

Backward equations are the natural tool for questions of the type "starting from state i, what is the probability of ever hitting state j?" or "what is the expected value of some function at time t?", because they treat the starting state as the variable.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Which is the forward Kolmogorov equation for P(t)?

    Forward: P'(t) = P(t) Q (the backward equation is P'(t) = Q P(t)).
  2. 2. Euler stepping with p(t+h) = p(t)(I + Qh) needs h to be small enough. What is a safe condition?

    If h is too big, diagonal entries 1 - q_i h can turn negative, producing negative probabilities.
  3. 3. In uniformization, what is the matrix P_u = I + Q/ฮ›?

    For ฮ› at least max q_i, entries are non-negative and rows sum to 1.
  4. 4. As t becomes large, what does p(t) approach for an irreducible finite CTMC?

    p(t) converges to the unique stationary distribution ฯ€.

Summary

  • Forward equation P'(t) = P(t) Q, backward equation P'(t) = Q P(t); the solution is exp(Qt).
  • For a distribution p(t), p' = pQ: inflow minus outflow for each state.
  • Euler steps are simple but low accuracy; uniformization gives stable Poisson-weighted sums of discrete steps.
  • Convergence to ฯ€ is governed by the spectral gap of Q.

Next: The Simple Random Walk