From One Step to an Expected Hitting Time
To find the expected time until a chain reaches a target, track what happens on its first transition. If the chain starts outside the target, one step is used immediately; after that, the expected remaining time depends on the state reached. This gives a linear equation for each state outside the target. States in the target have a different role: their hitting time is already zero, so they supply boundary values rather than unknowns.
Let \((X_n)_{n\ge0}\) be a time-homogeneous Markov chain on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal F,\mathbb P)\). Its transition matrix is \(P=(p_{ij})\), with \(p_{ij}=\mathbb P(X_{n+1}=j\mid X_n=i)\); each row sums to \(1\). Use the natural filtration \(\mathcal F_n=\sigma(X_0,\ldots,X_n)\). For a nonempty target set \(A\subseteq S\), define \(T_A=\inf\{n\ge0:X_n\in A\}\), with \(\inf\varnothing=\infty\). Write \(\mathbb P_i\) and \(\mathbb E_i\) for probability and expectation when \(X_0=i\), and set \(k_i=\mathbb E_i[T_A]\), allowing \(k_i=\infty\).
Proof. If \(i\in A\), then \(T_A=0\) under \(\mathbb P_i\), proving the boundary statement. Now fix \(i\notin A\), and define the remaining hitting time after the first step by \(R=\inf\{r\ge0:X_{1+r}\in A\}\). Path by path, \(T_A=1+R\). For each \(j\) with \(p_{ij}>0\), the Markov property gives the conditional law of the future after time \(1\), given \(X_1=j\), as that of a chain started at \(j\). Thus \(\mathbb E_i[R\mid X_1=j]=k_j\); this includes \(j\in A\), where the remaining time is zero. We condition only on states with \(p_{ij}>0\), so no conditional expectation on a probability-zero event is used. The states form a finite set, and the omitted states have zero probability; consequently \(\mathbb E_i[R]=\sum_{j:p_{ij}>0}p_{ij}k_j=\sum_{j\in S}p_{ij}k_j\), with the equality interpreted in the extended sense if a positive-probability term is infinite. Taking expectations in \(T_A=1+R\) proves the equation. \(\square\)
The \(1\) counts the step just taken, including a step that lands directly in \(A\). The sum accounts for the expected time still to come from the state reached. Since target states have zero remaining time, they may be included in the sum without changing its value.
Writing and Solving the System
Let \(B=S\setminus A\). For each \(i\in B\), substitute the boundary values into the first-step equation to obtain $$ k_i=1+\sum_{j\in B}p_{ij}k_j. $$ The terms for states in \(A\) vanish because their \(k_j\) values are zero. If \(B\) is nonempty and the expected hitting times are finite, let \(Q=(p_{ij})_{i,j\in B}\) and let \(\mathbf{k}\) be the column vector of those expected times. Then the equations take the form \((I-Q)\mathbf{k}=\mathbf{1}\), where \(\mathbf{1}\) is the all-ones column vector. The row sums of \(Q\) are at most \(1\), because they omit transitions into \(A\).
Proof. For \(i\in B\), the first-step equation is \(k_i=1+\sum_{j\in B}p_{ij}k_j\), since \(k_j=0\) on \(A\). The \(i\)th coordinate of \(Q\mathbf{k}\) is exactly \(\sum_{j\in B}p_{ij}k_j\), so collecting the coordinates gives \(\mathbf{k}=\mathbf{1}+Q\mathbf{k}\), equivalently \((I-Q)\mathbf{k}=\mathbf{1}\). Conversely, the \(i\)th coordinate of this matrix equation gives the first-step equation for \(i\); extending the vector by zero on \(A\) gives the stated boundary values. If \(B\) is empty, \(T_A=0\) from every state, so the conclusion follows directly. \(\square\)
This equivalence sets up a linear system; it does not by itself say that a finite solution exists or that a solution is unique. Before interpreting a computed solution as an expected hitting time, check that the chain reaches the target with enough regularity to make the expectation finite. In the examples below, a uniform positive chance of hitting the target within a fixed number of steps gives that finiteness.
Worked Example: A Target State with Two Routes to It
Consider \(S=\{0,1,2\}\), with target \(A=\{2\}\) and transition matrix, in the order \(0,1,2\), $$ P=\begin{bmatrix} \tfrac12&\tfrac13&\tfrac16\\ \tfrac14&\tfrac14&\tfrac12\\ 0&0&1 \end{bmatrix}. $$ The row sums are \(\tfrac12+\tfrac13+\tfrac16=1\), \(\tfrac14+\tfrac14+\tfrac12=1\), and \(0+0+1=1\). From either state outside \(A\), the probability of entering \(A\) on the next step is at least \(\tfrac16\). Hence the probability of avoiding \(A\) for \(n\) steps is at most \((\tfrac56)^n\), by applying the Markov property at successive steps. The tail probabilities have a finite sum, so the expected hitting times are finite.
The boundary value is \(k_2=0\). The equations for states \(0\) and \(1\) are $$ k_0=1+\tfrac12 k_0+\tfrac13 k_1,\qquad k_1=1+\tfrac14 k_0+\tfrac14 k_1. $$
Rearranging gives \(3k_0-2k_1=6\) and \(-k_0+3k_1=4\). The second equation gives \(k_0=3k_1-4\). Substitution into the first yields \(3(3k_1-4)-2k_1=6\), so \(7k_1=18\), \(k_1=\tfrac{18}{7}\), and \(k_0=3\cdot\tfrac{18}{7}-4=\tfrac{26}{7}\). These eliminations also show this system has only one solution.
Check: For state \(0\), \(1+\tfrac12\cdot\tfrac{26}{7}+\tfrac13\cdot\tfrac{18}{7}=1+\tfrac{13}{7}+\tfrac{6}{7}=\tfrac{26}{7}\). For state \(1\), \(1+\tfrac14\cdot\tfrac{26}{7}+\tfrac14\cdot\tfrac{18}{7}=1+\tfrac{13}{14}+\tfrac{9}{14}=\tfrac{18}{7}\). Both equations and the boundary value hold.
Worked Example: Hitting Either of Two Target States
Let \(S=\{a,b,c,d\}\), \(A=\{c,d\}\), and use the state order \(a,b,c,d\): $$ P=\begin{bmatrix} \tfrac14&\tfrac12&\tfrac14&0\\ \tfrac13&\tfrac13&0&\tfrac13\\ 0&0&1&0\\ 0&0&0&1 \end{bmatrix}. $$ The row sums are \(\tfrac14+\tfrac12+\tfrac14=1\), \(\tfrac13+\tfrac13+\tfrac13=1\), \(1\), and \(1\). From \(a\), the chance of hitting the target in one step is \(\tfrac14\); from \(b\), it is \(\tfrac13\). Thus the chance of avoiding the target through \(n\) steps is at most \((\tfrac34)^n\), and the expected hitting times are finite.
The boundary values are \(k_c=k_d=0\). The equations for the other states are $$ k_a=1+\tfrac14k_a+\tfrac12k_b,\qquad k_b=1+\tfrac13k_a+\tfrac13k_b. $$ Rearrangement gives \(3k_a-2k_b=4\) and \(-k_a+2k_b=3\). Adding these equations gives \(2k_a=7\), so \(k_a=\tfrac72\). Substituting into \(-k_a+2k_b=3\) gives \(2k_b=3+\tfrac72=\tfrac{13}{2}\), hence \(k_b=\tfrac{13}{4}\). The elimination yields a unique solution.
Check: The right side for \(a\) is \(1+\tfrac14\cdot\tfrac72+\tfrac12\cdot\tfrac{13}{4}=1+\tfrac78+\tfrac{13}{8}=\tfrac72\). The right side for \(b\) is \(1+\tfrac13\cdot\tfrac72+\tfrac13\cdot\tfrac{13}{4}=1+\tfrac76+\tfrac{13}{12}=\tfrac{39}{12}=\tfrac{13}{4}\). The target values remain zero.
Worked Example: A Target That Is Not Absorbing
Take \(S=\{u,v,z\}\), target \(A=\{z\}\), and transition matrix in the order \(u,v,z\): $$ P=\begin{bmatrix} 0&1&0\\ \tfrac12&0&\tfrac12\\ 1&0&0 \end{bmatrix}. $$ The row sums are \(0+1+0=1\), \(\tfrac12+0+\tfrac12=1\), and \(1+0+0=1\). State \(z\) is not absorbing, but this does not affect the time to hit it when starting there: \(k_z=0\). From \(u\), the target is reached within two steps with probability \(\tfrac12\); from \(v\), it is reached within two steps with probability at least \(\tfrac12\). Applying the Markov property in blocks of two steps bounds the probability of avoiding the target for \(2r\) steps by \((\tfrac12)^r\), so the expectations are finite.
The equations are \(k_u=1+k_v\) and \(k_v=1+\tfrac12k_u\). Substitution gives \(k_u=1+1+\tfrac12k_u\), hence \(\tfrac12k_u=2\) and \(k_u=4\). Then \(k_v=1+\tfrac12\cdot4=3\). Substitution determines a unique solution to this two-equation system.
Check: \(1+k_v=1+3=4=k_u\), and \(1+\tfrac12k_u=1+\tfrac12\cdot4=3=k_v\). Also \(k_z=0\) by definition, even though the next transition from \(z\) leaves the target.
Why the Boundary Values and the Extra Step Matter
A hitting time measures the first entrance into \(A\), not the time spent there. Therefore its boundary value is zero at every target state, whether or not that state is absorbing. Likewise, a transition into \(A\) contributes one step to the hitting time from outside \(A\), followed by zero remaining steps. The \(+1\) in each equation records that first transition.
A common error is to omit the \(+1\) and write \(k_u=k_v\) in the last example. Together with \(k_v=\tfrac12k_u\), this gives \(k_u=k_v=0\), which cannot be right: starting from \(u\), at least one transition is needed to reach \(v\), and another is needed before reaching \(z\). Restoring the step gives \(k_u=1+k_v\); solving the corrected equations gives \(k_u=4\) and \(k_v=3\). The substitution check confirms both values.
Another error is to condition on \(X_1=j\) when \(p_{ij}=0\). Such an event has probability zero, so that conditional statement is not needed. The valid argument conditions on \(X_1\) through its distribution and sums over states with \(p_{ij}>0\); zero-probability states contribute zero to the equation.
Finally, solving a displayed system is not a substitute for checking its assumptions. If the target cannot be reached, the expected hitting time may be infinite, and an ordinary finite linear system may not represent it. When the expectations are finite, solve the equations together with the zero boundary values, then substitute every value back into its equation. That check tests both the arithmetic and the placement of the transition probabilities.
Check Your Understanding
For each question, state the boundary values and check any computed answer by substitution.
- A chain on \(\{x,y\}\) has \(p_{xx}=\tfrac23\), \(p_{xy}=\tfrac13\), and target \(A=\{y\}\). Write the first-step equation for \(k_x\) and solve it.
- Why is it unnecessary—and potentially invalid—to condition on \(X_1=j\) when \(p_{ij}=0\)?
- In the four-state example, explain why both \(k_c\) and \(k_d\) are zero even though the target states have different transition rows.
- For a chain with target \(A\), define \(B=S\setminus A\) and write the matrix equation using \(Q=(p_{ij})_{i,j\in B}\).
- In the three-state example with states \(u,v,z\), identify the missing term in the incorrect equation \(k_u=k_v\), then verify the corrected value of \(k_u\).