Ferkans — Interactive Telecom Tutor

From Discrete Time to Continuous Time

In Chapter 17, the Markov chain $\{X_n\}$ evolves at integer time steps. Many systems — a queue with random arrivals, a channel that switches between states, a molecule transitioning between energy levels — change state at random continuous-time instants. The continuous-time Markov chain (CTMC) is the natural extension: a process $\{X(t) : t \geq 0\}$ that holds in each state for an exponentially distributed time, then jumps to a new state according to a fixed probability distribution.

The memoryless property of the exponential distribution is what makes the CTMC Markovian: knowing $X(t)$ tells you everything about the future, regardless of when the current state was entered.

Definition:
Continuous-Time Markov Chain

A stochastic process $\{X(t) : t \geq 0\}$ with countable state space $\mathcal{S}$ is a continuous-time Markov chain (CTMC) if for all $0 \leq s < t$ and all states $i, j \in \mathcal{S}$ : $\mathbb{P}(X(t) = j \mid X(s) = i, X(u) = x(u), 0 \leq u < s) = \mathbb{P}(X(t) = j \mid X(s) = i).$ The chain is time-homogeneous if $\mathbb{P}(X(t) = j \mid X(s) = i)$ depends only on $t - s$ . In this case, define the transition probabilities: $P_{ij}(t) = \mathbb{P}(X(t) = j \mid X(0) = i), \qquad \mathbf{P}(t) = [P_{ij}(t)].$

,

Definition:
Generator (Rate) Matrix

The generator matrix (also called the rate matrix or $Q$ -matrix) of a time-homogeneous CTMC is the matrix $\mathbf{G} = [g_{ij}]$ defined by: $g_{ij} = \lim_{h \to 0^+} \frac{P_{ij}(h)}{h}, \quad i \neq j, \qquad g_{ii} = -\sum_{j \neq i} g_{ij}.$ The off-diagonal entries $g_{ij} \geq 0$ are transition rates from state $i$ to state $j$ . The diagonal entry $g_{ii} \leq 0$ ensures that each row sums to zero: $\mathbf{G}\mathbf{1} = \mathbf{0}$ .

The holding time in state $i$ is $\text{Exp}(q_i)$ where $q_i = -g_{ii} = \sum_{j \neq i} g_{ij}$ . Upon leaving state $i$ , the chain jumps to state $j \neq i$ with probability $g_{ij}/q_i$ .

The generator matrix plays the same role for CTMCs that the transition matrix $\mathbf{P}$ plays for DTMCs. The key structural property is that rows sum to zero (not to one): $\mathbf{G}$ generates probability flow rather than directly assigning probabilities.

,

Theorem: Kolmogorov Forward and Backward Equations

Let $\mathbf{P}(t)$ be the transition matrix and $\mathbf{G}$ the generator of a time-homogeneous CTMC with finite or countably infinite state space. Then:

Forward equation (Kolmogorov): $\mathbf{P}'(t) = \mathbf{P}(t) \mathbf{G}.$

Backward equation (Kolmogorov): $\mathbf{P}'(t) = \mathbf{G} \mathbf{P}(t).$

Both hold with the initial condition $\mathbf{P}(0) = \mathbf{I}$ .

The forward equation describes how the state probabilities evolve by looking at what happens in the last infinitesimal interval before time $t$ . The backward equation conditions on the first infinitesimal step from the initial state. In both cases, $\mathbf{G}$ plays the role of a "derivative" of the transition probability at $t=0$ .

Proof

Derive the forward equation

For $h > 0$ : $\mathbf{P}(t+h) = \mathbf{P}(t)\mathbf{P}(h).$ This is the Chapman-Kolmogorov (semigroup) property. Rearranging: $\frac{\mathbf{P}(t+h) - \mathbf{P}(t)}{h} = \mathbf{P}(t)\frac{\mathbf{P}(h) - \mathbf{I}}{h}.$ Taking $h \to 0^+$ : $\mathbf{P}'(t) = \mathbf{P}(t)\mathbf{G}$ , since $\lim_{h \to 0^+}(\mathbf{P}(h)-\mathbf{I})/h = \mathbf{G}$ by definition.

Derive the backward equation

Similarly, writing $\mathbf{P}(t+h) = \mathbf{P}(h)\mathbf{P}(t)$ : $\frac{\mathbf{P}(t+h) - \mathbf{P}(t)}{h} = \frac{\mathbf{P}(h) - \mathbf{I}}{h}\mathbf{P}(t).$ Taking $h \to 0^+$ : $\mathbf{P}'(t) = \mathbf{G}\mathbf{P}(t)$ . $\blacksquare$

,

Theorem: Matrix Exponential Solution

The unique solution to both Kolmogorov equations with $\mathbf{P}(0) = \mathbf{I}$ is: $\mathbf{P}(t) = e^{\mathbf{G} t} = \sum_{k=0}^{\infty} \frac{(\mathbf{G} t)^k}{k!}.$ If $\mathbf{G}$ has a spectral decomposition $\mathbf{G} = \mathbf{S}\boldsymbol{\Lambda}\mathbf{S}^{-1}$ (where $\boldsymbol{\Lambda} = \text{diag}(\mu_1, \ldots, \mu_n)$ are the eigenvalues), then: $\mathbf{P}(t) = \mathbf{S}\,\text{diag}(e^{\mu_1 t}, \ldots, e^{\mu_n t})\,\mathbf{S}^{-1}.$ Since $\mathbf{G}\mathbf{1} = \mathbf{0}$ , one eigenvalue is always $\mu = 0$ , and all other eigenvalues have non-positive real part.

The matrix exponential $e^{\mathbf{G} t}$ is the continuous-time analog of the matrix power $\mathbf{P}^{n}$ for DTMCs. The eigenvalue $\mu = 0$ corresponds to the stationary distribution; the remaining eigenvalues govern the rate of convergence to stationarity.

Proof

Verify the matrix exponential solves the ODE

Differentiate term by term: $\frac{d}{dt}e^{\mathbf{G} t} = \frac{d}{dt}\sum_{k=0}^{\infty}\frac{(\mathbf{G} t)^k}{k!} = \sum_{k=1}^{\infty}\frac{\mathbf{G}^{k} t^{k-1}}{(k-1)!} = \mathbf{G}\sum_{k=0}^{\infty}\frac{(\mathbf{G} t)^k}{k!} = \mathbf{G} e^{\mathbf{G} t}.$ At $t=0$ : $e^{\mathbf{G}\cdot 0} = \mathbf{I}$ . $\blacksquare$

,

Example: Two-State CTMC (On-Off Channel)

A wireless channel alternates between "good" (state 0) and "bad" (state 1). The channel stays good for an $\text{Exp}(\alpha)$ time, then switches to bad; it stays bad for an $\text{Exp}(\beta)$ time, then returns to good. (a) Write the generator matrix $\mathbf{G}$ . (b) Find the transition matrix $\mathbf{P}(t) = e^{\mathbf{G} t}$ . (c) Find the stationary distribution.

Solution

(a) Generator matrix

State 0 (good) has leaving rate $\alpha$ with all transitions going to state 1. State 1 (bad) has leaving rate $\beta$ with all transitions going to state 0. $\mathbf{G} = \begin{pmatrix} -\alpha & \alpha \\ \beta & -\beta \end{pmatrix}.$

(b) Matrix exponential via eigendecomposition

The eigenvalues of $\mathbf{G}$ are $\mu_1 = 0$ and $\mu_2 = -(\alpha+\beta)$ . After diagonalization: $\mathbf{P}(t) = \frac{1}{\alpha+\beta}\begin{pmatrix} \beta + \alpha e^{-(\alpha+\beta)t} & \alpha - \alpha e^{-(\alpha+\beta)t} \\ \beta - \beta e^{-(\alpha+\beta)t} & \alpha + \beta e^{-(\alpha+\beta)t} \end{pmatrix}.$ As $t \to \infty$ , this converges to a matrix with identical rows (the stationary distribution).

(c) Stationary distribution

Solve $\boldsymbol{\pi}\mathbf{G} = \mathbf{0}$ with $\pi_0 + \pi_1 = 1$ : $-\alpha\pi_0 + \beta\pi_1 = 0 \implies \pi_0 = \beta/(\alpha+\beta)$ , $\pi_1 = \alpha/(\alpha+\beta)$ .

The fraction of time the channel is good is $\beta/(\alpha+\beta)$ . For a channel with mean good duration $1/\alpha = 10$ ms and mean bad duration $1/\beta = 2$ ms: $\pi_0 = 500/(100+500) = 5/6 \approx 0.833$ .

Example: Three-State CTMC: Channel Quality Levels

A channel has three quality levels: excellent (0), good (1), poor (2). The generator matrix is: $\mathbf{G} = \begin{pmatrix} -2 & 1 & 1 \\ 3 & -5 & 2 \\ 1 & 2 & -3 \end{pmatrix}.$ Find the stationary distribution $\boldsymbol{\pi}$ .

Solution

Set up the balance equations

$\boldsymbol{\pi}\mathbf{G} = \mathbf{0}$ gives three equations (one redundant): $-2\pi_0 + 3\pi_1 + \pi_2 = 0$ , $\pi_0 - 5\pi_1 + 2\pi_2 = 0$ , plus the normalization $\pi_0 + \pi_1 + \pi_2 = 1$ .

Solve

From equation 1: $\pi_2 = 2\pi_0 - 3\pi_1$ . Substituting into equation 2: $\pi_0 - 5\pi_1 + 2(2\pi_0 - 3\pi_1) = 0$ , so $5\pi_0 - 11\pi_1 = 0$ , giving $\pi_0 = 11\pi_1/5$ . Then $\pi_2 = 22\pi_1/5 - 3\pi_1 = 7\pi_1/5$ . Normalization: $\pi_1(11/5 + 1 + 7/5) = 1$ , so $\pi_1(23/5) = 1$ , giving $\pi_1 = 5/23$ .

$\boldsymbol{\pi} = \left(\frac{11}{23}, \frac{5}{23}, \frac{7}{23}\right) \approx (0.478, 0.217, 0.304).$

CTMC State Probabilities: $\mathbf{P}(t) = e^{\mathbf{G} t}$

Visualize the evolution of state probabilities $P_{ij}(t)$ for a two-state or three-state CTMC. Adjust the generator rates and starting state to see how the transition probabilities converge to the stationary distribution.

Parameters

CTMC model

\alpha

(rate 0→1)2

\beta

(rate 1→0)3

Starting state0

T

(time horizon)5

Quick Check

Which of the following is a valid generator matrix $\mathbf{G}$ ?

$\begin{pmatrix} -3 & 1 & 2 \\ 2 & -4 & 2 \\ 1 & 1 & -2 \end{pmatrix}$

$\begin{pmatrix} -3 & 1 & 2 \\ 2 & -3 & 2 \\ 1 & 1 & -2 \end{pmatrix}$

$\begin{pmatrix} 0.5 & 0.3 & 0.2 \\ 0.1 & 0.6 & 0.3 \\ 0.2 & 0.2 & 0.6 \end{pmatrix}$

Correction:

\begin{pmatrix} -3 & 1 & 2 \\ 2 & -4 & 2 \\ 1 & 1 & -2 \end{pmatrix}

Off-diagonal entries are non-negative, and each row sums to zero. This is a valid generator.

Common Mistake: Generator Matrix vs. Transition Matrix

Mistake:

Confusing the generator $\mathbf{G}$ (rows sum to 0, diagonal entries negative) with the transition matrix of the embedded DTMC (rows sum to 1, all entries non-negative). Students sometimes try to find $\boldsymbol{\pi}$ by solving $\boldsymbol{\pi}\mathbf{G} = \boldsymbol{\pi}$ instead of $\boldsymbol{\pi}\mathbf{G} = \mathbf{0}$ .

Correction:

The balance equations for a CTMC are $\boldsymbol{\pi}\mathbf{G} = \mathbf{0}$ (not $\boldsymbol{\pi}\mathbf{G} = \boldsymbol{\pi}$ ). The latter is the DTMC equation $\boldsymbol{\pi}\mathbf{P} = \boldsymbol{\pi}$ . Also note: the stationary distribution of the embedded DTMC is generally different from the CTMC stationary distribution (they are related by weighting with the holding times).

Historical Note: Kolmogorov's 1931 Paper

20th century

Andrey Kolmogorov derived the forward and backward equations in his landmark 1931 paper "Über die analytischen Methoden in der Wahrscheinlichkeitsrechnung" (On analytical methods in probability theory). This paper, written when Kolmogorov was 28, laid the foundation for the theory of continuous-time Markov processes and, more broadly, for the general theory of diffusion processes. The forward equation is sometimes called the Fokker-Planck equation in the physics literature, where it was discovered independently. The backward equation is uniquely associated with Kolmogorov.

Continuous-time Markov chain (CTMC)

A continuous-time stochastic process with countable state space satisfying the Markov property: the future depends on the past only through the present state. Characterized by a generator matrix $\mathbf{G}$ with rows summing to zero.

Related: Generator matrix

Generator matrix

The matrix $\mathbf{G} = [g_{ij}]$ where $g_{ij} \geq 0$ ( $i \neq j$ ) are transition rates and $g_{ii} = -\sum_{j \neq i} g_{ij}$ . Determines all finite-time transition probabilities via $\mathbf{P}(t) = e^{\mathbf{G} t}$ .

Continuous-Time Markov Chains