Turning Return Questions into Linear Systems
To calculate the probability of returning to a state, separate the first transition from what happens afterward. A first step directly back to the starting state counts as a return at time \(1\). A first step elsewhere leaves a hitting-probability problem: from the new state, what is the probability of ever reaching the original state? In a finite chain, these hitting probabilities can be found by solving a finite system of linear equations.
Let \((X_n)_{n\ge0}\) be a Markov chain on a finite state space \(S\), defined on a probability space \((\Omega,\mathcal{F},\mathbb{P})\), with transition matrix \(P=(p_{jk})\). The matrix is row-stochastic, so \(\sum_{k\in S}p_{jk}=1\) for each \(j\). Fix a state \(i\). Its first return time is \(T_i^+=\inf\{n\ge1:X_n=i\}\). We seek \(f_i=\mathbb{P}_i(T_i^+<\infty)\), where \(\mathbb{P}_i\) means the chain starts at \(i\).
For \(j\ne i\), define \(h_j=\mathbb{P}_j(T_{\{i\}}<\infty)\), the probability of ever hitting \(i\) when the chain starts at \(j\). Set \(h_i=1\) as a boundary value. Conditioning on one transition gives the first-step equations \(h_j=p_{ji}+\sum_{k\ne i}p_{jk}h_k\) for \(j\ne i\). Conditioning on the first transition from \(i\) then gives \(f_i=p_{ii}+\sum_{j\ne i}p_{ij}h_j\). These equations are useful, but they need care: on a state that cannot reach \(i\), the equation may not determine the hitting probability on its own.
Proof. For a state \(j\notin R_i\), no positive-probability path from \(j\) reaches \(i\); therefore the probability of ever hitting \(i\) is zero. For \(j\in R_i\), partition the event of eventually hitting \(i\) according to the first transition. A transition directly to \(i\) contributes \(p_{ji}\); a transition to \(k\in R_i\) contributes \(p_{jk}\mathbb{P}_k(T_{\{i\}}<\infty)\); a transition to a state outside \(R_i\) contributes zero. This proves that the hitting probabilities solve the displayed equations. For uniqueness, write \(Q_R=(p_{jk})_{j,k\in R_i}\). For every \(j\in R_i\), choose a positive-probability path from \(j\) to \(i\). Since \(R_i\) is finite, there is a common integer \(N\) at least as large as all chosen path lengths, and the minimum \(\delta\) of their positive path probabilities satisfies \(\delta>0\). Starting from any \(j\in R_i\), the probability of hitting \(i\) within \(N\) steps is at least \(\delta\). The row sum of \(Q_R^N\) is the probability of remaining in \(R_i\) for those \(N\) steps, so it is at most \(1-\delta\). If two solutions differ by a vector \(x\), then \(x=Q_Rx\), hence \(x=Q_R^Nx\). With \(\|x\|_\infty=\max_{j\in R_i}|x_j|\), the row-sum bound gives \(\|x\|_\infty\le(1-\delta)\|x\|_\infty\), forcing \(x=0\). Thus the solution is unique. Finally, from \(i\), a first transition to \(i\) returns immediately, and a transition to \(j\ne i\) leads to a return exactly when \(i\) is eventually hit from \(j\). Summing these disjoint cases gives the formula for \(f_i\). \(\square\)
The theorem gives a reliable order of operations: first identify the states that can reach the target, then solve only for their hitting probabilities, and finally calculate the return probability from the starting state. The reachability check is part of the mathematics, not an optional simplification.
Worked Calculations
Worked Example: A Three-State Chain with an Absorbing State
Consider \(S=\{1,2,3\}\) and $$ P=\begin{bmatrix} \tfrac14&\tfrac12&\tfrac14\\ \tfrac13&\tfrac13&\tfrac13\\ 0&0&1 \end{bmatrix}. $$ Each row sums to \(1\): \(\tfrac14+\tfrac12+\tfrac14=1\), \(\tfrac13+\tfrac13+\tfrac13=1\), and \(0+0+1=1\). Find the probability of returning to state \(1\).
From state \(3\), the chain stays at \(3\), so there is no positive-probability path from \(3\) to \(1\). Thus \(h_3=0\). From state \(2\), a first step goes to \(1\), \(2\), or \(3\), each with probability \(\tfrac13\). The first-step equation is $$ h_2=\tfrac13+\tfrac13h_2+\tfrac13h_3 =\tfrac13+\tfrac13h_2. $$ Therefore \(\tfrac23h_2=\tfrac13\), and \(h_2=\tfrac12\). Starting from \(1\), the return probability is $$ f_1=\tfrac14+\tfrac12h_2+\tfrac14h_3 =\tfrac14+\tfrac14+0 =\tfrac12. $$ Check: Substitution gives \(h_2=\tfrac13+\tfrac13(\tfrac12)+\tfrac13(0)=\tfrac12\), and the return equation gives \(f_1=\tfrac14+\tfrac12(\tfrac12)+\tfrac14(0)=\tfrac12\).
Worked Example: Solving a Coupled Two-Unknown System
Let \(S=\{1,2,3,4\}\), with transition matrix $$ P=\begin{bmatrix} 0&1&0&0\\ \tfrac14&0&\tfrac12&\tfrac14\\ \tfrac13&\tfrac13&0&\tfrac13\\ 0&0&0&1 \end{bmatrix}. $$ The row sums are \(0+1+0+0=1\), \(\tfrac14+0+\tfrac12+\tfrac14=1\), \(\tfrac13+\tfrac13+0+\tfrac13=1\), and \(0+0+0+1=1\). Find the return probability to state \(1\).
State \(4\) is absorbing and cannot reach \(1\), so \(h_4=0\). States \(2\) and \(3\) can each reach \(1\), so their equations are $$ h_2=\tfrac14+\tfrac12h_3+\tfrac14h_4 =\tfrac14+\tfrac12h_3, \qquad h_3=\tfrac13+\tfrac13h_2+\tfrac13h_4 =\tfrac13+\tfrac13h_2. $$ Substitute the second equation into the first: $$ h_2=\tfrac14+\tfrac12\left(\tfrac13+\tfrac13h_2\right) =\tfrac5{12}+\tfrac16h_2. $$ Hence \(\tfrac56h_2=\tfrac5{12}\), so \(h_2=\tfrac12\). Then \(h_3=\tfrac13+\tfrac13(\tfrac12)=\tfrac12\). From state \(1\), the first step goes to state \(2\) with probability \(1\), giving \(f_1=h_2=\tfrac12\).
Check: The two equations give \(\tfrac14+\tfrac12(\tfrac12)=\tfrac12=h_2\) and \(\tfrac13+\tfrac13(\tfrac12)=\tfrac12=h_3\). The first transition from \(1\) is certainly to \(2\), so the return probability is indeed \(\tfrac12\).
Worked Example: Resolving an Undetermined Equation
Consider $$ P=\begin{bmatrix} \tfrac12&\tfrac12&0\\ \tfrac14&\tfrac12&\tfrac14\\ 0&0&1 \end{bmatrix}. $$ The row sums are \(\tfrac12+\tfrac12+0=1\), \(\tfrac14+\tfrac12+\tfrac14=1\), and \(0+0+1=1\). Find the return probability to state \(1\).
State \(3\) cannot reach state \(1\), so the actual hitting probability is \(h_3=0\). The first-step equation written without this reachability information is \(h_3=h_3\), which is satisfied by every number. For state \(2\), $$ h_2=\tfrac14+\tfrac12h_2+\tfrac14h_3. $$ Using \(h_3=0\) gives \(\tfrac12h_2=\tfrac14\), hence \(h_2=\tfrac12\). Therefore $$ f_1=\tfrac12+\tfrac12h_2 =\tfrac12+\tfrac14 =\tfrac34. $$ Check: The equations give \(h_3=0=0+0+1(0)\), \(h_2=\tfrac14+\tfrac12(\tfrac12)+\tfrac14(0)=\tfrac12\), and \(f_1=\tfrac12+\tfrac12(\tfrac12)=\tfrac34\).
Why the Probabilistic Solution Is the Right One
The preceding example shows why simply solving every first-step equation can be insufficient. At state \(3\), the equation \(h_3=h_3\) has many algebraic solutions, but the probability of hitting state \(1\) is fixed by the chain: it is zero. More generally, the hitting probabilities are the smallest nonnegative solution of the equations with boundary value \(h_i=1\). This gives another precise way to identify the intended solution when equations have free values on closed regions that avoid \(i\).
Proof. For \(n\ge0\), let \(a_n(j)=\mathbb{P}_j(T_{\{i\}}\le n)\). We prove by induction that \(a_n(j)\le g_j\) for every state \(j\). At \(n=0\), \(a_0(i)=1=g_i\), while \(a_0(j)=0\le g_j\) for \(j\ne i\). Suppose the inequality holds at \(n\). For \(j\ne i\), conditioning on the first transition gives \(a_{n+1}(j)=p_{ji}+\sum_{k\ne i}p_{jk}a_n(k)\). Since \(g_i=1\) and \(g_j=\sum_k p_{jk}g_k\), the induction hypothesis and nonnegativity of the transition probabilities imply \(a_{n+1}(j)\le p_{ji}+\sum_{k\ne i}p_{jk}g_k=g_j\). The inequality also holds at \(i\), where both sides equal \(1\). The events \(\{T_{\{i\}}\le n\}\) increase to \(\{T_{\{i\}}<\infty\}\); taking their probabilities to the limit gives \(h_j\le g_j\). Since the hitting probabilities themselves satisfy the equations by first-step conditioning, they are the pointwise minimal nonnegative solution. \(\square\)
Common mistake. In the third example, assigning \(h_3=1\) just because \(h_3=h_3\) is an equation solution would give \(h_2=\tfrac14+\tfrac12h_2+\tfrac14\), hence \(h_2=1\), and then \(f_1=1\). This is wrong: state \(3\) is absorbing and cannot reach \(1\). The correction is to use the event being measured to set \(h_3=0\), after which the return probability is \(\tfrac34\). A harmonic equation alone does not always identify a probability; reachability and the probabilistic boundary conditions matter.
Finally, \(f_i\) is a probability of at least one return, not the expected time until return. It records whether the return ever occurs, with no weighting for how long it takes. The practical checks are to confirm that every row used is stochastic, set hitting probabilities to zero for states that cannot reach the target, solve the remaining equations, and substitute the result into both the hitting and return equations.
Check Your Understanding
For each question, identify any states that cannot reach the target before solving equations, and verify the resulting probabilities by substitution.
- For the three-state matrix in the first worked example, what is the probability of returning to state \(2\) when the chain starts at \(2\)?
- If \(h_j=\tfrac25\) and a chain started at \(i\) moves to \(j\) with probability \(\tfrac34\), to \(i\) with probability \(\tfrac14\), and nowhere else, what is its return probability?
- Explain why the equation \(h_3=h_3\) in the third example does not determine the hitting probability.
- In the second worked example, substitute \(h_2=h_3=\tfrac12\) into each first-step equation.
- What is the distinction between the return probability and the expected first return time?