Skip to content
Tutorials Center
My learning

Topics

Lesson 24 of 36 · Continuous-Time Markov Chains

Holding Times and the Jump Chain

A CTMC stays in each state for an exponential time, then jumps by a discrete chain. Simulate it, and find the long-run fraction of time by solving πQ = 0.

The generator matrix packs a continuous-time Markov chain into a single table. To simulate one, or to understand a path of it, a second picture is better: the chain waits in a state for a random time, then jumps to a new state, then waits again. This lesson makes that precise and shows how to find the long-run behavior.

Holding times are exponential

Suppose the chain is in state i, which it leaves at total rate qᵢ = -qᵢᵢ. The time until it leaves, the holding time, is exponentially distributed:

Text
holding time in state i ~ Exponential(q_i),   mean 1/q_i

The reason is the memoryless property: the Markov property forces the remaining holding time to be independent of the time already spent, and only the exponential has that property.

So a state with a high exit rate is left quickly. In the machine example, "Broken" has q = 2 per day and a mean stay of 0.5 days, while "Working" has q = 0.2 and a mean stay of 5 days.

The jump chain

When the chain does leave state i, where does it go? To state j with probability

Text
P_ij = q_ij / q_i        (j ≠ i)

These probabilities form the transition matrix of an ordinary discrete-time chain, the embedded jump chain, whose diagonal entries are 0 (it never "jumps" to itself). For the machine, each state has only one exit, so the jump chain goes W to B to R to W in a fixed order.

A CTMC is therefore described by two things: the jump chain P (where to go) and the exit rates qᵢ (how long to wait). The holding times are independent of the jump destinations.

flowchart LR
  A["In state i"] -->|"wait Exp(q_i)"| B["Choose next state j with prob q_ij / q_i"]
  B --> A2["In state j"]

One cycle of the simulation: wait, then jump.

Simulating a path

Python Simulate the machine chain

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.

Every simulated visit to Working lasts about 5 days on average and to Broken about half a day, as the rates say.

The stationary distribution πQ = 0

Many chains settle into a stationary distribution π, a row vector with πᵢ ≥ 0, Σ πᵢ = 1, which stays unchanged over time. Setting the rate of change of π P(t) to zero gives the balance equations

Text
π Q = 0

Read column j: the flow into state j (Σᵢ πᵢ qᵢⱼ) equals the flow out of j (πⱼ qⱼ). For an irreducible finite chain there is exactly one solution, and πⱼ is also the long-run fraction of time spent in state j.

To solve it numerically, replace one balance equation by the normalizing condition Σ π = 1 and solve the linear system.

Python Solve pi Q = 0 and compare with the simulation

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 two vectors agree because the jump chain cycles through the three states equally often, so the time share is proportional to the mean stay 1/qᵢ. In general the relationship between the jump chain's stationary vector ν and π is πᵢ ∝ νᵢ / qᵢ. You can compare the output with the simulation above.

If a CTMC has a state it can never leave (an absorbing state, with qᵢ = 0), the generator has a zero row and π Q = 0 has the mass concentrated on absorbing states instead of a unique answer.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. A state has total exit rate q = 4 per hour. What is the mean holding time?

    The holding time is Exponential(4), with mean 1/4 = 0.25 hours.
  2. 2. From a state with rates 1 to state B and 3 to state C, what is the probability that the next jump goes to C?

    q_ij / q_i = 3 / (1 + 3) = 0.75.
  3. 3. What does the equation πQ = 0 express?

    It is the set of balance equations: in-flow equals out-flow for every state.
  4. 4. What else is πⱼ for an irreducible finite CTMC?

    Stationary probabilities equal the long-run time fractions.

Summary

  • A CTMC waits an Exponential(qᵢ) time in state i, then jumps to j with probability qᵢⱼ/qᵢ.
  • Together, the jump chain and exit rates describe the process and give a simple simulation recipe.
  • The stationary distribution solves π Q = 0, Σ π = 1, and gives long-run time fractions.

Next: Birth-Death Processes