From Transition Rates to Change in a Function
A generator matrix records how quickly a continuous-time Markov chain moves between states. Often the quantity of interest is not the destination state itself, but a function of that state: a cost, score, population size, or indicator that the chain lies in a specified set. The generator acting on that function gives its instantaneous expected rate of change, conditional on the current state. The key calculation is to include every possible destination, including the current state in the matrix expression, and then use the zero row sums to express the answer using only actual moves to different states.
Let \((X_t)_{t\ge0}\) be a time-homogeneous continuous-time Markov chain on a nonempty finite state space \(S\), defined on a probability space \((\Omega,\mathcal F,\mathbb P)\). Its natural filtration is \(\mathcal F_t=\sigma(X_s:0\le s\le t)\). Write \(\mathbb P_i\) and \(\mathbb E_i\) for probability and expectation when \(X_0=i\). Let \(P(t)=(p_{ij}(t))\) be its transition matrix at time \(t\), with rows summing to \(1\). The generator matrix is \(Q=(q_{ij})\), where \(q_{ij}\), for \(i\ne j\), is the transition rate from \(i\) to \(j\), and \(q_{ii}=-\sum_{j\ne i}q_{ij}\). Thus \(q_{ij}\ge0\) for \(i\ne j\), and every row of \(Q\) sums to zero.
The definition asks how fast the expected value of \(f(X_h)\) changes over a short interval, given that the chain starts at \(i\). It is not a derivative of an individual sample path: a path can remain at \(i\) for a random holding time and then jump. Rather, it is a derivative of an expectation. No irreducibility assumption is needed for this calculation; a finite-state chain may have several communicating classes or states with no possible outgoing jumps.
The Off-Diagonal Formula
Proof. By the definition of the transition rates, for each pair \(i,j\) the transition probabilities satisfy \(p_{ij}(h)=\mathbf 1_{\{i=j\}}+h q_{ij}+o(h)\) as \(h\downarrow0\). Since \(S\) is finite, we can sum these expansions over \(j\). In particular, using \(\sum_jp_{ij}(h)=1\) and taking the derivative at zero gives \(\sum_jq_{ij}=0\), so \(q_{ii}=-\sum_{j\ne i}q_{ij}\). Also, $$ \mathbb E_i[f(X_h)]=\sum_{j\in S}p_{ij}(h)f(j). $$ Subtract \(f(i)=\sum_j\mathbf 1_{\{i=j\}}f(j)\), divide by \(h\), and take the limit. The finite sum allows the limit to pass through the sum, giving \(Lf(i)=\sum_jq_{ij}f(j)\). Substituting \(q_{ii}=-\sum_{j\ne i}q_{ij}\) yields $$ Lf(i)=q_{ii}f(i)+\sum_{j\ne i}q_{ij}f(j) =\sum_{j\ne i}q_{ij}\bigl(f(j)-f(i)\bigr). $$ If the state space has only one state, the off-diagonal sum is empty, \(q_{ii}=0\), and both expressions equal zero. Thus the formula also holds in that case. \(\square\)
The off-diagonal form separates a possible move from its effect on the function. Each term is a rate \(q_{ij}\) multiplied by the change \(f(j)-f(i)\). Moves that increase \(f\) contribute positively, moves that decrease \(f\) contribute negatively, and moves to a state with the same function value contribute zero. The diagonal entry is not an additional jump rate: it makes the matrix row sum zero and, in the matrix product, subtracts the current value at the appropriate total rate.
Worked Example: Applying a Three-State Generator
Consider \(S=\{1,2,3\}\) and $$ Q= \begin{bmatrix} -3&2&1\\ 1&-4&3\\ 0&2&-2 \end{bmatrix}. $$ The off-diagonal entries are nonnegative. The row sums are \(-3+2+1=0\), \(1-4+3=0\), and \(0+2-2=0\), so the matrix has the required generator form. Let \(f(1)=2\), \(f(2)=-1\), and \(f(3)=4\).
At state \(1\), the possible moves are to \(2\) at rate \(2\) and to \(3\) at rate \(1\). Therefore $$ Lf(1)=2(-1-2)+1(4-2)=2(-3)+1(2)=-6+2=-4. $$ At state \(2\), the changes are \(f(1)-f(2)=3\) and \(f(3)-f(2)=5\), so $$ Lf(2)=1(3)+3(5)=3+15=18. $$ At state \(3\), the rate to \(1\) is \(0\), and the rate to \(2\) is \(2\). Hence $$ Lf(3)=0(2-4)+2(-1-4)=0+2(-5)=-10. $$
Check by matrix multiplication: With \(f=(2,-1,4)^{\mathsf T}\), the three entries of \(Qf\) are \(-3(2)+2(-1)+1(4)=-6-2+4=-4\), \(1(2)-4(-1)+3(4)=2+4+12=18\), and \(0(2)+2(-1)-2(4)=0-2-8=-10\). They agree with the off-diagonal calculation at every state.
Indicator Functions and Rates Across a Set
For a set \(A\subseteq S\), its indicator function is \(\mathbf 1_A(i)=1\) when \(i\in A\), and \(0\) otherwise. Applying the formula gives $$ L\mathbf 1_A(i)=\sum_{j\ne i}q_{ij}\bigl(\mathbf 1_A(j)-\mathbf 1_A(i)\bigr). $$ If \(i\notin A\), only transitions into \(A\) contribute, and the value is the total rate of entering \(A\) from \(i\). If \(i\in A\), only transitions to \(A^c=S\setminus A\) contribute, with a minus sign; the value is the negative of the total rate of leaving \(A\). This interpretation counts transitions across the boundary of the set, not all transitions from a state in the set.
Worked Example: An Indicator for a Two-State Set
Use the state space \(S=\{1,2,3\}\) and generator $$ Q= \begin{bmatrix} -2&1&1\\ 3&-5&2\\ 0&1&-1 \end{bmatrix}. $$ The row sums are \(-2+1+1=0\), \(3-5+2=0\), and \(0+1-1=0\), and all off-diagonal entries are nonnegative. Take \(A=\{2,3\}\), so \(\mathbf 1_A=(0,1,1)^{\mathsf T}\).
State \(1\) is outside \(A\). It enters \(A\) at rate \(q_{12}+q_{13}=1+1=2\), and $$ L\mathbf 1_A(1)=1(1-0)+1(1-0)=2. $$ State \(2\) is in \(A\). Its only transition out of \(A\) is to state \(1\), at rate \(q_{21}=3\); the transition to state \(3\), at rate \(q_{23}=2\), stays in \(A\). Thus $$ L\mathbf 1_A(2)=3(0-1)+2(1-1)=-3+0=-3. $$ State \(3\) is also in \(A\). Its transition to state \(2\) stays in \(A\), and its rate to state \(1\) is \(q_{31}=0\). Consequently, $$ L\mathbf 1_A(3)=0(0-1)+1(1-1)=0+0=0. $$
Check by matrix multiplication: The product \(Q\mathbf 1_A\) is the column vector with entries \(-2(0)+1(1)+1(1)=2\), \(3(0)-5(1)+2(1)=-3\), and \(0(0)+1(1)-1(1)=0\). In particular, the third entry is zero: the transition from state \(3\) to state \(2\) is internal to \(A\), so it does not change the indicator.
Proof. Since \(i\) is a maximizer, \(f(j)-f(i)\le0\) for every \(j\in S\). For \(j\ne i\), the rate \(q_{ij}\) is nonnegative, so each term \(q_{ij}(f(j)-f(i))\) in the generator formula is nonpositive. Their finite sum is therefore at most zero. If every destination with \(q_{ij}>0\) has \(f(j)=f(i)\), every term is zero and \(Lf(i)=0\). Conversely, suppose \(Lf(i)=0\). A finite sum of nonpositive terms can equal zero only if every term is zero. For any \(j\ne i\) with \(q_{ij}>0\), this forces \(f(j)-f(i)=0\). This proves both directions, including the case where there are no positive outgoing rates: then the sum is empty and equality holds vacuously. \(\square\)
The corresponding minimum principle follows by applying the proved result to \(-f\): if \(f\) has a minimum at \(i\), then \(L(-f)(i)\le0\), and linearity of the finite sum gives \(L(-f)(i)=-Lf(i)\). Hence \(Lf(i)\ge0\). These sign checks are useful when assessing a calculation: at a maximizing state the generator cannot be positive, and at a minimizing state it cannot be negative.
Worked Example: A Two-State Function and Its Instantaneous Drift
Let \(S=\{1,2\}\) with $$ Q= \begin{bmatrix} -2&2\\ 3&-3 \end{bmatrix}. $$ The row sums are \(-2+2=0\) and \(3-3=0\), and the off-diagonal rates \(2\) and \(3\) are nonnegative. Set \(f(1)=4\) and \(f(2)=-2\). From state \(1\), the only possible destination other than itself is \(2\), so $$ Lf(1)=2\bigl(f(2)-f(1)\bigr)=2(-2-4)=2(-6)=-12. $$ From state \(2\), the only possible destination is \(1\), so $$ Lf(2)=3\bigl(f(1)-f(2)\bigr)=3(4-(-2))=3(6)=18. $$
Check by matrix multiplication: \(Qf\) has first entry \(-2(4)+2(-2)=-8-4=-12\) and second entry \(3(4)-3(-2)=12+6=18\). The signs also agree with the maximum principle: state \(1\) is the maximizer and its generator value is negative, while state \(2\) is the minimizer and its value is positive. If \(f\) were constant instead, each difference \(f(j)-f(i)\) would be zero, so the generator would vanish at both states.
Reading and Checking Generator Calculations
For any \(f\), \(Lf(i)\) is the instantaneous expected change in \(f(X_t)\) when the chain starts at \(i\). For example, when \(f\) is an indicator, this rate describes whether the chain is instantaneously gaining or losing probability of being in the indicated set, conditional on its current state. For a general function, the same rate-and-increment calculation applies: list possible destinations \(j\ne i\), multiply each rate by its change in \(f\), and add.
A reliable calculation has two checks. First, verify that every row of the proposed \(Q\) sums to zero and that its off-diagonal entries are nonnegative; otherwise it is not a generator matrix under these conventions. Second, calculate \(Qf\) directly as a matrix product and compare each entry with the off-diagonal sum. The diagonal is essential in this second check, even though it disappears from the final rate-and-increment formula.
Common mistake. A frequent error is to count every transition out of a state in \(A\) as a departure from \(A\). In the indicator example, that would assign state \(3\) an exit rate \(q_{31}+q_{32}=0+1=1\), and incorrectly conclude \(L\mathbf 1_A(3)=-1\). But \(3\in A\), and the transition from \(3\) to \(2\) remains inside \(A\). Only transitions to \(A^c=\{1\}\) change the indicator; the rate is \(q_{31}=0\), giving \(L\mathbf 1_A(3)=0\). The difference formula prevents this error because the internal move has increment \(\mathbf 1_A(2)-\mathbf 1_A(3)=1-1=0\).
Check Your Understanding
For each question, use the off-diagonal formula and, where possible, verify the result with a matrix product.
- For \(Q=\begin{bmatrix}-1&1\\2&-2\end{bmatrix}\) and \(f=(0,3)^{\mathsf T}\), calculate \(Lf(1)\) and \(Lf(2)\).
- Why does a constant function have generator zero at every state of a finite-state chain?
- If \(i\) maximizes \(f\), can \(Lf(i)\) be positive? Justify your answer from the generator formula.
- For a set \(A\), which transitions contribute to \(L\mathbf 1_A(i)\) when \(i\in A\), and what sign do they have?
- What does the off-diagonal formula give at a state whose row of \(Q\) is entirely zero?