From a Return Event to a First-Step Equation
Whether a chain returns to a state depends on its entire future path. Conditioning on the first transition separates off one step and leaves a hitting-probability question. The resulting equations are compact, but the value assigned at the target is crucial: once the chain has reached the target, the target has been hit, even if the question originally concerned a return after time zero.
Let \((X_n)_{n\ge0}\) be a discrete-time Markov chain on a finite or countable state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{jk})\). Each row of \(P\) is a probability distribution. When conditioning on the chain's history, use its natural filtration \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\). Write \(\mathbb{P}_j\) for probabilities when \(X_0=j\). For a fixed target state \(i\), the hitting time is \(T_i=\inf\{n\ge0:X_n=i\}\), and the first return time from \(i\) is \(T_i^+=\inf\{n\ge1:X_n=i\}\), with the infimum of the empty set defined as \(\infty\).
The Markov property says that, conditional on the current state and history, the distribution of the next state is given by the corresponding row of \(P\). Applying this at the first transition gives the hitting equations away from the target. For the return probability, the first transition may already land at \(i\), which counts as a return at time \(1\).
Proof. First take \(j\ne i\). The events \(\{X_1=k\}\), for \(k\in S\), partition the possible first transitions. Given \(X_0=j\) and \(X_1=k\), the probability of ever hitting \(i\) from that point onward is \(h_k\), by the Markov property. If \(k=i\), this conditional probability is \(h_i=1\), since the target has already been reached at time \(1\). Summing over the countable set of possible next states gives \(h_j=\sum_k p_{jk}h_k\). Starting instead at \(i\), a return occurs if and only if the chain, after its first transition, hits \(i\) at or after that point. Conditional on \(X_1=k\), this has probability \(h_k\), including probability \(1\) when \(k=i\). Thus \(f_i=\sum_k p_{ik}h_k\), and separating the \(k=i\) term gives the second expression.
It remains to prove the minimality assertion, which also explains what the equations mean on an infinite state space. For each integer \(m\ge0\), let \(h_j^{(m)}=\mathbb{P}_j(T_i\le m)\). Then \(h_i^{(m)}=1\) for every \(m\), while \(h_j^{(0)}=0\) for \(j\ne i\). For \(j\ne i\), conditioning on the first transition gives \(h_j^{(m+1)}=\sum_k p_{jk}h_k^{(m)}\). The events \(\{T_i\le m\}\) increase to \(\{T_i<\infty\}\), so \(h_j^{(m)}\) increases to \(h_j\). Passing to the limit in the nonnegative countable sum yields \(h_j=\sum_k p_{jk}h_k\). Now let \(u\) satisfy the stated boundary condition and equations. At \(m=0\), \(h_j^{(0)}\le u_j\) for all \(j\): away from \(i\), this is \(0\le u_j\), and at \(i\) both sides equal \(1\). If \(h_k^{(m)}\le u_k\) for every \(k\), then for \(j\ne i\), $$ h_j^{(m+1)}=\sum_k p_{jk}h_k^{(m)} \le\sum_k p_{jk}u_k=u_j. $$ At \(i\), \(h_i^{(m+1)}=u_i=1\). Induction gives \(h_j^{(m)}\le u_j\) for all \(m,j\); taking limits gives \(h_j\le u_j\). This proves the equations and the minimality claim. \(\square\)
The boundary condition is not \(h_i=f_i\). The two quantities answer different questions: \(h_i\) asks whether the chain hits \(i\) when it is already there at time zero, while \(f_i\) asks whether it visits \(i\) again at a strictly positive time. In the return equation, \(h_i=1\) is used only after conditioning on a first step that lands at \(i\).
Worked Example: A Return Probability Below One
Consider \(S=\{0,1,2,3\}\) and the transition matrix, with rows and columns ordered \(0,1,2,3\), $$ P= \begin{bmatrix} 0&1&0&0\\ \tfrac14&0&\tfrac34&0\\ 0&\tfrac12&0&\tfrac12\\ 0&0&0&1 \end{bmatrix}. $$ Every row sums to \(1\): the row sums are \(1\), \(\tfrac14+\tfrac34=1\), \(\tfrac12+\tfrac12=1\), and \(1\). Find the probability of returning to \(0\) when starting at \(0\).
State \(3\) is absorbing and is not \(0\), so \(h_3=0\). The target boundary is \(h_0=1\). The equations at states \(1\) and \(2\) are $$ h_1=\tfrac14h_0+\tfrac34h_2,\qquad h_2=\tfrac12h_1+\tfrac12h_3. $$ Using the boundary values gives \(h_2=\tfrac12h_1\), and hence \(h_1=\tfrac14+\tfrac38h_1\). Therefore \(\tfrac58h_1=\tfrac14\), so \(h_1=\tfrac25\) and \(h_2=\tfrac15\). Since the first transition from \(0\) goes to \(1\) with probability \(1\), \(f_0=h_1=\tfrac25\).
Check: Substitution gives \(\tfrac14h_0+\tfrac34h_2=\tfrac14+\tfrac34\cdot\tfrac15=\tfrac14+\tfrac3{20}=\tfrac25=h_1\), and \(\tfrac12h_1+\tfrac12h_3=\tfrac12\cdot\tfrac25+\tfrac12\cdot0=\tfrac15=h_2\). The return equation gives \(f_0=0\cdot h_0+1\cdot h_1=\tfrac25\). The missing probability, \(\tfrac35\), is the probability of moving into the absorbing state \(3\) before returning.
Worked Example: A Self-Loop at the Starting State
Let \(S=\{0,1,2\}\), with rows and columns in that order, and $$ P= \begin{bmatrix} \tfrac14&\tfrac34&0\\ \tfrac13&\tfrac23&0\\ 0&0&1 \end{bmatrix}. $$ The row sums are \(\tfrac14+\tfrac34=1\), \(\tfrac13+\tfrac23=1\), and \(1\). Find the return probability to \(0\).
The target boundary is \(h_0=1\). From state \(1\), the chain moves to \(0\) with probability \(\tfrac13\) and stays at \(1\) with probability \(\tfrac23\), so $$ h_1=\tfrac13h_0+\tfrac23h_1 =\tfrac13+\tfrac23h_1. $$ Subtracting \(\tfrac23h_1\) gives \(\tfrac13h_1=\tfrac13\), hence \(h_1=1\). Starting from \(0\), the first transition stays at \(0\) with probability \(\tfrac14\), which is an immediate return, or moves to \(1\) with probability \(\tfrac34\), from which \(0\) is eventually hit with probability \(h_1=1\). Thus \(f_0=\tfrac14+\tfrac34h_1=1\).
Common mistake and correction. A tempting but incorrect calculation is to substitute \(f_0\) for \(h_0\) and write \(f_0=\tfrac14+\tfrac34f_0\), which gives \(f_0=\tfrac13\). This uses the return probability as though it were the probability of hitting the target when already at the target. The correct boundary value is \(h_0=1\), so the return equation is \(f_0=\tfrac14+\tfrac34h_1\), with \(h_1=1\); the correct value is \(1\). Substitution into the correct equation verifies it: \(\tfrac14+\tfrac34\cdot1=1\).
Why the Boundary Value May Not Be Enough
In a finite chain, the first-step equations are often used as a finite system to compute hitting probabilities. On a countably infinite state space, the boundary condition \(h_i=1\) and the equations away from \(i\) need not identify a unique solution. The minimality part of the theorem is therefore substantive: among nonnegative solutions, the hitting probabilities are the smallest. A solution of the equations is not automatically the desired probability unless it is known to be minimal or uniqueness has been established by an appropriate argument.
Worked Example: Equations with More Than One Solution
Take \(S=\{0,1,2,\ldots\}\). From \(0\), the chain moves to \(1\) with probability \(1\); from each \(n\ge1\), it moves to \(n+1\) with probability \(1\). Each transition row has a single entry equal to \(1\), so every row sums to \(1\). For target \(0\), the chain starting from any \(n\ge1\) moves deterministically to larger states and never hits \(0\). Thus \(h_n=0\) for \(n\ge1\), \(h_0=1\), and \(f_0=0\).
The equations away from \(0\) are \(h_n=h_{n+1}\) for every \(n\ge1\). For any fixed \(c\ge0\), the assignment \(u_0=1\) and \(u_n=c\) for all \(n\ge1\) satisfies the boundary condition and every equation away from the target. Therefore those equations alone have many nonnegative solutions. The actual hitting probabilities correspond to \(c=0\), the minimal one. The return equation confirms the result: \(f_0=p_{00}h_0+p_{01}h_1=0\cdot1+1\cdot0=0\).
The same logic applies to any fixed target state, not only state \(0\). First define the hitting probabilities with \(h_i=1\); then use the equations only for states outside the target; finally compute the return probability using the row of \(P\) corresponding to the starting state. In a finite setting, solving those equations is a separate computational task. Here the main point is to derive the correct equations and interpret their boundary condition before attempting that task.
These equations also connect return probabilities with recurrence. The return probability \(f_i\) is the probability of at least one return, not the expected number of visits or the distribution of the return time. In the standard classification, state \(i\) is recurrent exactly when \(f_i=1\), and transient when \(f_i<1\). The first-step equation calculates the probability relevant to that distinction; it does not by itself assert a mean return time or a limit law.
Check Your Understanding
For each question, distinguish the probability of hitting the target from the probability of returning after time zero.
- State the first-step equation for \(h_j=\mathbb{P}_j(T_i<\infty)\) when \(j\ne i\), and explain the boundary value at \(i\).
- Write the first-step formula for \(f_i=\mathbb{P}_i(T_i^+<\infty)\), separating the \(k=i\) term.
- In the first worked example, why is \(h_3=0\), and what part of the transition from state \(1\) makes \(h_1\) less than \(1\)?
- In the self-loop example, identify the incorrect substitution in \(f_0=\tfrac14+\tfrac34f_0\) and give the correct equation.
- For the countable deterministic chain, give two distinct nonnegative solutions to the equations away from \(0\) with boundary value \(u_0=1\), and identify which one equals the hitting probabilities.