Continuous-Time Markov Chains — Mathematics Knowledge System

Overview

A continuous-time Markov chain (CTMC) is a stochastic process {X(t), t >= 0} with a countable state space that satisfies the Markov property in continuous time: the future, given the present state, is independent of the past. The process spends an exponentially distributed amount of time in each state before jumping to another state according to a transition rate matrix Q (the generator). CTMCs generalize discrete-time Markov chains and are used in queueing theory, epidemiology, population dynamics, and reliability engineering.

Intuition

Imagine a system that can be in one of several states. While in state i, a 'clock' for each possible next state j rings at rate q_{ij}. The process jumps to whichever clock rings first -- and because exponential waiting times are memoryless, the process has no memory of when it entered the current state. This is the continuous-time analog of choosing the next state from a transition matrix, but now time is continuous and exponential holding times replace discrete steps.

Formal Definition

Definition

A CTMC on a countable state space S is a right-continuous process {X(t)} satisfying the Markov property. It is characterized by a rate matrix (generator) Q = (q_{ij}) where q_{ij} >= 0 for i != j and q_{ii} = -sum_{j != i} q_{ij}. The transition probabilities P(t) = (p_{ij}(t)) satisfy the Kolmogorov equations.

q_{ij} \ge 0 \text{ for } i \ne j, \quad q_{ii} = -\sum_{j \ne i} q_{ij}

Generator matrix Q

P'(t) = P(t)Q \quad \text{(Kolmogorov forward equations)}

Forward equations

P'(t) = QP(t) \quad \text{(Kolmogorov backward equations)}

Backward equations

P(t) = e^{Qt} = \sum_{n=0}^\infty \frac{(Qt)^n}{n!}

Matrix exponential solution

\pi Q = 0, \quad \sum_i \pi_i = 1 \implies \pi \text{ is the stationary distribution}

Stationary distribution

Notation

Notation	Meaning
$Q$	Generator (rate) matrix: off-diagonals are transition rates, diagonal is negative row sum
$q_{ij}$	Rate of jumping from state i to state j (i != j)
$P(t)$	Transition probability matrix: p_{ij}(t) = P(X(t)=j \| X(0)=i)
$\pi$	Stationary distribution: pi * Q = 0, sum pi_i = 1

Theorems

Theorem 1: Theorem 1 (Exponential Holding Times)

\text{In state } i, \text{ the holding time } H_i \sim \text{Exp}(|q_{ii}|). \text{ On leaving state } i, \text{ the process jumps to state } j \ne i \text{ with probability } q_{ij}/|q_{ii}|.

Theorem 2: Theorem 2 (Detailed Balance / Reversibility)

\text{A CTMC with stationary distribution } \pi \text{ is time-reversible if and only if } \pi_i q_{ij} = \pi_j q_{ji} \text{ for all } i \ne j. \text{ (detailed balance)}

Worked Examples

1
The generator matrix has off-diagonal rates alpha and beta, with diagonal entries being the negative row sums.
$Q = \begin{pmatrix} -\alpha & \alpha \\ \beta & -\beta \end{pmatrix}$
2
Solve pi * Q = 0 with pi_0 + pi_1 = 1. The equations are: -pi_0 * alpha + pi_1 * beta = 0.
$\pi_0 \alpha = \pi_1 \beta \implies \pi_0 = \frac{\beta}{\alpha+\beta},\quad \pi_1 = \frac{\alpha}{\alpha+\beta}$

✓ Answer

The stationary distribution is pi_0 = beta/(alpha+beta), pi_1 = alpha/(alpha+beta).

Practice Problems

Mediumfree response

A machine can be in states {working, broken}. It breaks at rate lambda and is repaired at rate mu. Write the generator Q and find the long-run fraction of time the machine is working.

Mediumfree response

Verify detailed balance for the two-state chain with rates alpha and beta when pi_0 = beta/(alpha+beta) and pi_1 = alpha/(alpha+beta).

Common Mistakes

Common Mistake

Confusing the rate matrix Q with a transition matrix

Q has negative diagonal entries (not between 0 and 1). The transition probabilities are given by P(t) = exp(Qt), not by Q directly.

Common Mistake

Forgetting that the holding time rate is |q_{ii}|, not q_{ii}

The diagonal entries q_{ii} are negative. The holding time rate is -q_{ii} = |q_{ii}| = sum_{j!=i} q_{ij}.

Quiz

Summary

A CTMC is characterized by a generator Q: off-diagonals are jump rates, diagonals are negative row sums.
Holding times are exponential: time in state i ~ Exp(|q_{ii}|).
Transition probabilities satisfy P(t) = exp(Qt), the matrix exponential.
Stationary distribution satisfies pi * Q = 0 with sum pi_i = 1.
Detailed balance pi_i q_{ij} = pi_j q_{ji} characterizes time-reversible chains.

References

BookNorris, J. R. -- Markov Chains, Chapter 2
BookKarlin, S. and Taylor, H. -- A First Course in Stochastic Processes, Chapter 4
WebsiteWikipedia -- Continuous-time Markov chain