Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 36 · Continuous-Time Markov Chains

The Generator Matrix of a Continuous-Time Markov Chain

Learn continuous-time Markov chains through the generator matrix Q: rates, zero row sums, and the matrix exponential P(t) = exp(Qt), with runnable code.

A discrete-time Markov chain moves at fixed steps: 1, 2, 3, … Many systems do not wait for a clock. A machine breaks at a random moment, a molecule changes state, a call ends. A continuous-time Markov chain (CTMC) lets the process jump at any time, while keeping the Markov property: given the present state, the future is independent of the past.

All the information about a CTMC with finitely many states sits in one matrix, the generator matrix Q. This lesson shows how to read it, build it, and turn it into transition probabilities.

States, rates and the Markov property

A process X(t) on states 1, …, m is a CTMC if, for all s, t ≥ 0,

Text
P(X(s+t) = j | X(s) = i, history before s) = P(X(s+t) = j | X(s) = i)

We also assume it is time-homogeneous: this probability depends only on t. Write it as Pᵢⱼ(t) and collect these in the matrix P(t). Naturally P(0) = I, the identity.

The transition rate qᵢⱼ (for i ≠ j) is the number of jumps from i to j per unit time while in state i:

Text
P_ij(h) ≈ q_ij · h        for small h, i ≠ j

If a machine in state "working" fails at rate 0.2 per day, q = 0.2 and the chance it fails in the next hour (h = 1/24 day) is about 0.2/24 ≈ 0.0083.

The generator matrix Q

Q has the off-diagonal rates qᵢⱼ ≥ 0. The diagonal entries are chosen so every row sums to zero:

Text
q_ii = -(sum of q_ij over j ≠ i) = -q_i

where qᵢ is the total rate of leaving state i. So off-diagonal entries are non-negative and diagonal entries are non-positive.

Example: a machine with states Working (1), Broken (2), Under repair (3):

  • Working to Broken at rate 0.2 per day.
  • Broken to Repair at rate 2 per day (a technician arrives).
  • Repair to Working at rate 1 per day.
Text
        W     B     R
W  [ -0.2   0.2   0.0 ]
B  [  0.0  -2.0   2.0 ]
R  [  1.0   0.0  -1.0 ]
flowchart LR
  W["Working"] -->|"0.2"| B["Broken"]
  B -->|"2"| R["Repair"]
  R -->|"1"| W

The machine chain. Arrows carry transition rates per day.

From Q to P(t): the matrix exponential

The transition matrices satisfy P(t) = exp(Qt), where the matrix exponential is defined by the same series as the ordinary one:

Text
exp(Qt) = I + Qt + (Qt)²/2! + (Qt)³/3! + …

For large entries, a practical trick is scaling and squaring: compute the series for Qt/2^k (small, so the series converges fast) and then square the result k times. The code below does exactly this and compares with scipy.

Python Build Q and compute P(t) = exp(Qt)

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.

Each row of P(t) is a probability distribution (non-negative, summing to 1), and the series agrees with the library to high precision.

Semigroup property

Because the process forgets its past, going from i to j in time s + t means going to some intermediate state k at time s:

Text
P(s + t) = P(s) P(t)        (the Chapman-Kolmogorov equations)

This is the continuous-time version of "multiply the one-step matrix by itself". In terms of Q it is just exp(Q(s+t)) = exp(Qs) exp(Qt).

Python Check Chapman-Kolmogorov and convergence

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.

For very large t the rows become the same: the machine "forgets" where it started. That limit is the stationary distribution, which you will compute exactly in the next lessons.

Quick sanity checks on any generator: off-diagonal entries are at least 0, each diagonal entry is minus the sum of the rest of its row, and every row sums to 0. A matrix that fails one of these is not a generator.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What must the row sums of a generator matrix Q equal?

    Diagonal entries are minus the total leaving rate, so each row sums to zero.
  2. 2. A state has outgoing rates 0.5 to state B and 1.5 to state C. What is its diagonal entry in Q?

    q_ii = -(0.5 + 1.5) = -2.
  3. 3. Which formula gives the transition probability matrix at time t?

    P(t) = exp(Qt), the matrix exponential.
  4. 4. What does the Chapman-Kolmogorov equation P(s+t) = P(s)P(t) express?

    It conditions on the state at time s and uses the Markov property.

Summary

  • A CTMC jumps at random times and has the Markov property; time-homogeneous chains have Pᵢⱼ(t) depending only on t.
  • The generator Q has non-negative off-diagonal rates and each diagonal entry equal to minus the total leaving rate, so rows sum to 0.
  • P(t) = exp(Qt) and P(s+t) = P(s)P(t).
  • Matrix exponentials can be computed by scaling and squaring or with scipy.linalg.expm.

Next: Holding Times and the Jump Chain