Why the Matrix Exponential Appears
For a finite-state continuous-time Markov chain, the generator records the instantaneous rates of movement between states. The Kolmogorov equations turn those rates into differential equations for transition probabilities. Their solution is not merely a convenient formula: the matrix exponential is the unique solution, and its entries really are transition probabilities. We establish both facts, including the nonnegativity and row-sum conditions that a transition matrix must satisfy.
Let \((X_t)_{t\ge0}\) be a continuous-time Markov chain on a finite state space \(S=\{1,\ldots,m\}\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\). Write \(P(t)=(p_{ij}(t))\), where \(p_{ij}(t)=\mathbb{P}(X_t=j\mid X_0=i)\). A transition matrix has nonnegative entries and each row sums to one. Its generator \(Q=(q_{ij})\) has \(q_{ij}\ge0\) for \(i\ne j\), and \(\sum_jq_{ij}=0\) for every \(i\). In particular, \(q_{ii}=-\sum_{j\ne i}q_{ij}\). These are the finite-state generator conditions used below.
The forward and backward Kolmogorov equations, with this row-stochastic convention, are respectively \(P'(t)=P(t)Q\) and \(P'(t)=QP(t)\). The forward equation describes the time evolution through right multiplication; the backward equation describes it through left multiplication. Both use the initial condition \(P(0)=I\), where \(I\) is the \(m\times m\) identity matrix.
The series defining \(e^{tQ}\) converges for every real \(t\). For example, in any submultiplicative matrix norm, \(\|(tQ)^n/n!\|\le |t|^n\|Q\|^n/n!\), and the scalar series on the right converges. On every bounded interval of \(t\), the series and its term-by-term derivative converge uniformly by the same comparison with exponential series. Thus it may be differentiated term by term.
Existence and Uniqueness
Proof. Differentiating the convergent series gives \((e^{tQ})'=\sum_{n\ge1}n t^{n-1}Q^n/n!=Q\sum_{r\ge0}t^rQ^r/r!=Qe^{tQ}\). Each power \(Q^n\) commutes with \(Q\), so the same calculation also gives \((e^{tQ})'=e^{tQ}Q\). At \(t=0\), the series is \(I\). This proves existence for both equations.
For uniqueness in the left-multiplication equation, suppose \(U'=QU\) and \(U(0)=I\). The matrix \(e^{-tQ}\) commutes with \(Q\), as follows term by term from its series. The product rule therefore gives \((e^{-tQ}U(t))'=-Qe^{-tQ}U(t)+e^{-tQ}QU(t)=0\). Every entry of this product has derivative zero, so it is constant; at \(t=0\) it equals \(I\). Also \(e^{-tQ}e^{tQ}=I\): the derivative of this product is zero by the same product-rule calculation, and its value at zero is \(I\). Hence \(e^{-tQ}U(t)=I\) implies \(U(t)=e^{tQ}\). For the right-multiplication equation, if \(V'=VQ\), then \((V(t)e^{-tQ})'=V(t)Qe^{-tQ}-V(t)Qe^{-tQ}=0\). This product equals \(I\) at zero, so \(V(t)e^{-tQ}=I\), and multiplying by \(e^{tQ}\) gives \(V(t)=e^{tQ}\). Each equation thus has exactly the stated solution. \(\square\)
For a generator \(Q\), this theorem says that both Kolmogorov equations give the same transition matrix. The remaining point is important: an exponential of a matrix is not automatically a transition matrix. The generator conditions are what guarantee nonnegative entries and unit row sums.
Proof. Let \(\mathbf{1}\) denote the column vector whose entries are all one. The zero row sums of \(Q\) say \(Q\mathbf{1}=0\). Consequently \(Q^n\mathbf{1}=0\) for every integer \(n\ge1\), and the exponential series gives \(e^{tQ}\mathbf{1}=\mathbf{1}+\sum_{n\ge1}t^nQ^n\mathbf{1}/n!=\mathbf{1}\). This proves that all row sums are one.
To prove nonnegativity, set \(c=\max_i(-q_{ii})\), which is nonnegative. If \(c=0\), then \(q_{ii}=0\) for every \(i\). Since the other entries in each row are nonnegative and the row sum is zero, every entry is zero; hence \(Q=0\) and \(e^{tQ}=I\), which is nonnegative. If \(c>0\), put \(A=Q+cI\). For \(i\ne j\), \(a_{ij}=q_{ij}\ge0\); on the diagonal, \(a_{ii}=q_{ii}+c\ge0\) by the definition of \(c\). Thus \(A\) is entrywise nonnegative, and each power \(A^n\) is entrywise nonnegative, because each entry of a product of nonnegative matrices is a sum of nonnegative terms.
Since \(Q=A-cI\) and \(A\) commutes with \(I\), the exponential series (or its binomial expansion) gives \(e^{tQ}=e^{-ct}e^{tA}\). For \(t\ge0\), \(e^{-ct}>0\), and \(e^{tA}=\sum_{n\ge0}t^nA^n/n!\) is entrywise nonnegative. Therefore \(e^{tQ}\) is entrywise nonnegative as well. Together with its row sums of one, this proves the claim. \(\square\)
Worked Computations
Worked Example: A One-State Chain
Consider \(S=\{1\}\), with the only state absorbing. Its generator is the \(1\times1\) matrix \(Q=[0]\). The generator row sums to zero, and the off-diagonal nonnegativity condition has no entries to check. Compute the solution and verify it is a transition matrix.
Every positive power of \(Q\) is zero, so the series gives \(e^{tQ}=[1]+\sum_{n\ge1}t^n[0]/n!=[1]\). The initial value is \([1]\), and the derivative is \([0]=Qe^{tQ}=e^{tQ}Q\). The sole entry is nonnegative and the only row sums to \(1\).
Check: the chain remains in state \(1\) with probability one, exactly as the exponential solution states. This degenerate case also shows why the argument for nonnegativity must allow \(c=0\).
Worked Example: Symmetric Switching Between Two States
Let \(S=\{1,2\}\), with rate \(1\) from state \(1\) to state \(2\) and rate \(1\) in the reverse direction. The generator is \(Q=\begin{bmatrix}-1&1\\1&-1\end{bmatrix}\). Both rows sum to \(-1+1=0\), and both off-diagonal entries are nonnegative. Compute \(e^{tQ}\).
Direct multiplication gives \(Q^2=\begin{bmatrix}(-1)(-1)+(1)(1)&(-1)(1)+(1)(-1)\\(1)(-1)+(-1)(1)&(1)(1)+(-1)(-1)\end{bmatrix} =\begin{bmatrix}2&-2\\-2&2\end{bmatrix}=-2Q\). By induction, \(Q^n=(-2)^{n-1}Q\) for every \(n\ge1\): it holds for \(n=1\), and multiplying the formula by \(Q\) replaces the factor by \((-2)^n\). Thus \(e^{tQ}=I+\sum_{n\ge1}t^n(-2)^{n-1}Q/n!=I+\frac{1-e^{-2t}}2Q\), where the coefficient follows from \(\sum_{n\ge1}(-2)^{n-1}t^n/n!=(1-e^{-2t})/2\).
Substituting the entries of \(Q\) gives \(P(t)=\begin{bmatrix}(1+e^{-2t})/2&(1-e^{-2t})/2\\(1-e^{-2t})/2&(1+e^{-2t})/2\end{bmatrix}\). For \(t\ge0\), \(0<e^{-2t}\le1\), so every entry is nonnegative. Each row sums to \((1+e^{-2t}+1-e^{-2t})/2=1\). At \(t=0\), the matrix is \(I\); differentiating the expression gives \(P'(t)=e^{-2t}Q\), while \(QP(t)=P(t)Q=e^{-2t}Q\), since \(Q^2=-2Q\). This verifies both equations directly.
Worked Example: Two Transient States and an Absorbing State
Let \(S=\{1,2,3\}\), with state \(1\) moving to state \(3\) at rate \(1\), state \(2\) moving to state \(3\) at rate \(2\), and state \(3\) absorbing. Then \(Q=\begin{bmatrix}-1&0&1\\0&-2&2\\0&0&0\end{bmatrix}\). The row sums are \(-1+0+1=0\), \(0-2+2=0\), and \(0+0+0=0\); all off-diagonal entries are nonnegative.
Write the rows of \(Q\) as \(r_1=(-1,0,1)\), \(r_2=(0,-2,2)\), and \(r_3=(0,0,0)\). Multiplying each by \(Q\) gives \(r_1Q=(1,0,-1)=-r_1\), \(r_2Q=(0,4,-4)=-2r_2\), and \(r_3Q=(0,0,0)\). Thus for \(n\ge1\), row \(1\) of \(Q^n\) is \((-1)^{n-1}r_1\), row \(2\) is \((-2)^{n-1}r_2\), and row \(3\) is zero. Summing the exponential series row by row yields \(P(t)=\begin{bmatrix}e^{-t}&0&1-e^{-t}\\0&e^{-2t}&1-e^{-2t}\\0&0&1\end{bmatrix}\).
For a direct check, the first row of \(QP(t)\) is minus row \(1\) of \(P(t)\) plus row \(3\), namely \((-e^{-t},0,e^{-t})\). The second row is minus twice row \(2\) plus twice row \(3\), namely \((0,-2e^{-2t},2e^{-2t})\), and the third row is zero. These are exactly the derivatives of the displayed rows of \(P(t)\), so \(P'=QP\). Also \(P(0)=I\). Its first row sums to \(e^{-t}+1-e^{-t}=1\), its second to \(e^{-2t}+1-e^{-2t}=1\), and its third to \(1\). Since \(t\ge0\), all its entries are nonnegative.
Conventions, Uses, and a Common Pitfall
The two equations and their solutions can be summarized as follows. The initial condition and the position of \(Q\) matter when writing an equation; the equality of the two solutions follows because the same fixed matrix \(Q\) appears on both sides of the exponential.
| Initial-value problem | Unique solution | Interpretation with row distributions |
|---|---|---|
| \(U'=QU,\ U(0)=I\) | \(U(t)=e^{tQ}\) | Backward Kolmogorov equation |
| \(V'=VQ,\ V(0)=I\) | \(V(t)=e^{tQ}\) | Forward Kolmogorov equation |
| \(Q\) is a finite-state generator | \(e^{tQ}\) is nonnegative with row sums \(1\) | Transition probabilities |
For an initial distribution \(\mu_0\), written as a row vector, the distribution at time \(t\) is \(\mu_t=\mu_0P(t)\). Differentiating gives \(\mu_t'=\mu_tQ\), consistent with the forward equation. The matrix exponential therefore converts instantaneous transition rates into finite-time transition probabilities, while the uniqueness result ensures that another differentiable solution with the same initial condition cannot produce different probabilities.
Common pitfall: mixing row and column conventions. For the asymmetric three-state generator above, take the initial row distribution \(\mu_0=(1,0,0)\). The correct instantaneous derivative is \(\mu_0Q=(-1,0,1)\). Treating the same entries as a column and multiplying on the left gives \(Q\mu_0^{\mathsf T}=(-1,0,0)^{\mathsf T}\), which incorrectly omits the rate of movement into state \(3\). With row distributions, multiply on the right: \(\mu_t=\mu_0P(t)\), not \(P(t)\mu_0^{\mathsf T}\).
A second error is to assume that every matrix exponential is a transition matrix. The stochastic conclusion required the generator conditions: nonnegative off-diagonal entries, zero row sums, and \(t\ge0\). Without those conditions, the exponential can have negative entries or rows whose sums are not one. For a finite-state generator, the two checks in the proof—\(e^{tQ}\mathbf{1}=\mathbf{1}\) and nonnegativity—are what justify interpreting its entries as probabilities.
Check Your Understanding
Use the definitions and arguments above to answer each question.
- For a finite matrix \(Q\), why may the series for \(e^{tQ}\) be differentiated term by term on a bounded interval?
- Which product is used to prove uniqueness for \(U'=QU\), and why is its derivative zero?
- If a generator has zero exit rate in every state, what are \(Q\) and \(e^{tQ}\)?
- For \(Q=\begin{bmatrix}-1&1\\1&-1\end{bmatrix}\), verify the first row sum of the worked transition matrix at \(t=0\).
- With row-vector distributions, write the derivative of \(\mu_t=\mu_0P(t)\) using the forward equation.