From a Target Event to an Equation
Suppose a Markov chain moves among states until it reaches one of two sets. The question “Which target is reached first?” is about the whole future path, but its probability can be expressed in terms of a single transition and the probabilities from the states reached next. The resulting equations are called first-step equations. Their construction is simple; care is needed with the boundary values and with paths that reach neither target.
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_{ij})\). The matrix is row-stochastic: \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for each \(i\). Let \(\mathcal{F}_n=\sigma(X_0,\ldots,X_n)\) be the natural filtration. For a set \(C\subseteq S\), define \(T_C=\inf\{n\ge0:X_n\in C\}\), with \(\inf\varnothing=\infty\). Take two disjoint target sets \(A,B\subseteq S\), and define \(h_i=\mathbb{P}_i(T_A<T_B)\), where \(\mathbb{P}_i\) means that \(X_0=i\).
The boundary values follow from the definition of the hitting times, not from an equation for states outside the targets. If \(i\in A\), then \(T_A=0\), while \(T_B\ge1\) or \(T_B=\infty\), so \(T_A<T_B\). If \(i\in B\), then \(T_B=0\) and \(T_A\ge1\) or \(T_A=\infty\), so the strict inequality fails. In particular, the definition uses a strict comparison: the event is not “hit \(A\) no later than \(B\).”
For a state \(i\notin A\cup B\), the next state can be in \(A\), in \(B\), or outside both. A transition into \(A\) contributes its full probability to success; a transition into \(B\) contributes zero; and a transition to \(j\notin A\cup B\) contributes \(p_{ij}h_j\). The compact sum over all \(j\in S\) includes all three possibilities because the boundary values have already been defined.
Why Conditioning on One Transition Works
Proof. The boundary values follow from \(T_A=0\) when the chain starts in \(A\), and \(T_B=0\) when it starts in \(B\), as described above. Now fix \(i\notin A\cup B\). The events \(\{X_1=j\}\), for \(j\in S\), are disjoint and have total probability one. On \(\{X_1=j\}\), the chain has not yet hit either target at time zero. By the Markov property, conditional on \(X_1=j\), the probability of subsequently hitting \(A\) strictly before \(B\) is \(h_j\). If \(p_{ij}=0\), the event \(\{X_1=j\}\) contributes zero and no conditioning on a probability-zero event is needed. Summing over the possible first states gives \(h_i=\sum_{j\in S}\mathbb{P}_i(X_1=j)h_j=\sum_{j\in S}p_{ij}h_j\). For a countable state space this is a sum of nonnegative terms bounded above by \(\sum_jp_{ij}=1\), so it is well-defined. The argument does not require eventual arrival at \(A\cup B\); paths that reach neither target simply do not belong to \(\{T_A<T_B\}\). \(\square\)
The equation is a statement about the actual hitting probability. It does not, by itself, assert that an arbitrary collection of numbers satisfying the same equations must be that probability. In particular, a state from which neither target is ever reached can leave an equation such as \(h_i=h_i\). The examples below show both how to use the equations and why this distinction matters.
Worked Example: A Biased Walk Between Two Boundaries
Let \(S=\{0,1,2,3,4\}\). From each interior state \(i\in\{1,2,3\}\), the chain moves to \(i+1\) with probability \(\tfrac23\) and to \(i-1\) with probability \(\tfrac13\). States \(0\) and \(4\) are absorbing. Find the probability of hitting \(4\) before \(0\), starting from each interior state.
In the state order \(0,1,2,3,4\), the transition matrix is
The row sums are \(1\); for the interior rows, they are respectively \(\tfrac13+\tfrac23=1\), \(\tfrac13+\tfrac23=1\), and \(\tfrac13+\tfrac23=1\). Set \(A=\{4\}\) and \(B=\{0\}\). The boundary values are \(h_0=0\) and \(h_4=1\). The equations for the interior states are
To solve, define \(d_i=h_i-h_{i-1}\) for \(i=1,2,3,4\). Rearranging the equation at each interior state gives \(\tfrac23(h_{i+1}-h_i)=\tfrac13(h_i-h_{i-1})\), so \(d_{i+1}=\tfrac12d_i\). Thus \(d_2=\tfrac12d_1\), \(d_3=\tfrac14d_1\), and \(d_4=\tfrac18d_1\). Since \(h_4-h_0=1\), the increments sum to \(1\): \(d_1(1+\tfrac12+\tfrac14+\tfrac18)=1\). The parenthetical sum is \(\tfrac{15}{8}\), so \(d_1=\tfrac{8}{15}\). It follows that \(h_1=\tfrac{8}{15}\), \(h_2=d_1+d_2=\tfrac{12}{15}=\tfrac45\), and \(h_3=d_1+d_2+d_3=\tfrac{14}{15}\).
Check: The three equations give \(\tfrac23h_2=\tfrac23\cdot\tfrac45=\tfrac{8}{15}=h_1\); \(\tfrac13h_1+\tfrac23h_3=\tfrac{8}{45}+\tfrac{28}{45}=\tfrac{36}{45}=\tfrac45=h_2\); and \(\tfrac13h_2+\tfrac23h_4=\tfrac4{15}+\tfrac{10}{15}=\tfrac{14}{15}=h_3\). The boundary values also hold.
Transitions Into the Targets Must Be Counted
Worked Example: Two Interior States and Two Targets
Consider \(S=\{a,b,x,y\}\) with targets \(A=\{a\}\) and \(B=\{b\}\), both absorbing. From \(x\), move to \(a,b,y\) with probabilities \(\tfrac12,\tfrac14,\tfrac14\). From \(y\), move to \(a,b,x\) with probabilities \(\tfrac14,\tfrac14,\tfrac12\). Find \(h_x\) and \(h_y\).
In the order \(a,b,x,y\), the rows of \(P\) are \((1,0,0,0)\), \((0,1,0,0)\), \((\tfrac12,\tfrac14,0,\tfrac14)\), and \((\tfrac14,\tfrac14,\tfrac12,0)\). The absorbing rows sum to \(1\), and the other row sums are \(\tfrac12+\tfrac14+\tfrac14=1\) and \(\tfrac14+\tfrac14+\tfrac12=1\). The boundary values are \(h_a=1\) and \(h_b=0\), so the first-step equations are \(h_x=\tfrac12+\tfrac14h_y\) and \(h_y=\tfrac14+\tfrac12h_x\). Substitute the second equation into the first: \(h_x=\tfrac12+\tfrac14(\tfrac14+\tfrac12h_x)=\tfrac9{16}+\tfrac18h_x\). Therefore \(\tfrac78h_x=\tfrac9{16}\), giving \(h_x=\tfrac9{14}\). Then \(h_y=\tfrac14+\tfrac12\cdot\tfrac9{14}=\tfrac14+\tfrac9{28}=\tfrac47\).
Check: \(\tfrac12+\tfrac14\cdot\tfrac47=\tfrac12+\tfrac17=\tfrac9{14}\), and \(\tfrac14+\tfrac12\cdot\tfrac9{14}=\tfrac14+\tfrac9{28}=\tfrac47\), so both first-step equations hold.
When Neither Target Is Ever Reached
Proof. Because \(A\) and \(B\) are disjoint, the chain cannot be in both at the same time. On the event \(T_A\wedge T_B<\infty\), at least one hitting time is finite. If both are finite, they cannot be equal, since equality would put \(X_n\) in both disjoint sets at that time. Thus exactly one of \(T_A<T_B\) and \(T_B<T_A\) occurs. These two events are disjoint, and their union has probability one under the stated assumption. Adding their probabilities gives the result. \(\square\)
The assumption matters. Without it, there can be positive probability of hitting neither target, so the two “first” probabilities need not add to one.
Worked Example: A State That Avoids Both Targets
Let \(S=\{a,b,c,d\}\), with \(A=\{a\}\) and \(B=\{b\}\). States \(a\) and \(b\) are absorbing. From \(c\), move to \(a,b,d\) with probabilities \(\tfrac13\) each. State \(d\) is absorbing but belongs to neither target. Find the probability of hitting \(A\) before \(B\) from \(c\).
In the order \(a,b,c,d\), the rows of \(P\) are \((1,0,0,0)\), \((0,1,0,0)\), \((\tfrac13,\tfrac13,0,\tfrac13)\), and \((0,0,0,1)\). Each row sums to \(1\), including the row for \(c\), whose entries sum to \(\tfrac13+\tfrac13+\tfrac13=1\). The boundary values are \(h_a=1\) and \(h_b=0\). At \(d\), the equation is \(h_d=h_d\); the probability itself is \(h_d=0\), because a chain started at \(d\) stays there forever and never hits \(A\). At \(c\), the equation gives \(h_c=\tfrac13h_a+\tfrac13h_b+\tfrac13h_d=\tfrac13\).
Check: Starting from \(c\), the first transition goes to \(a\) with probability \(\tfrac13\), to \(b\) with probability \(\tfrac13\), and to \(d\) with probability \(\tfrac13\). Only the first outcome hits \(A\) before \(B\), so the probability is indeed \(\tfrac13\). The probability of hitting \(B\) first is also \(\tfrac13\); the remaining \(\tfrac13\) is the probability of hitting neither. Thus the two target probabilities do not sum to one here.
A Common Mistake and a Practical Checklist
Common mistake: omitting transitions directly into a target. In the two-interior-state example, an incorrect equation would be \(h_x=\tfrac14h_y\), because it counts only the transition from \(x\) to \(y\). That calculation would give \(h_x=0\) when combined with \(h_y=\tfrac12h_x\). It is wrong because the transition from \(x\) to \(a\), with probability \(\tfrac12\), succeeds immediately. The correct equation is \(h_x=\tfrac12+\tfrac14h_y\); the transition to \(b\) contributes zero, and the transition to \(y\) contributes \(\tfrac14h_y\).
For a new problem, identify the two disjoint target sets first, then write the boundary values before any interior equations. For each remaining state, list every possible next state and multiply its transition probability by the appropriate boundary value or unknown. Check that the transition row sums to one, and check computed probabilities by substitution. Finally, ask whether the chain reaches one of the two targets almost surely. That condition determines whether the two competing hitting probabilities must add to one; it is not needed to write the first-step equations themselves.
Check Your Understanding
Use the definition of the strict hitting event and the first-step equations to answer these questions.
- For disjoint targets \(A\) and \(B\), what are \(h_i\) when \(i\in A\) and when \(i\in B\), and why?
- A state \(i\notin A\cup B\) moves to \(A\) with probability \(\tfrac25\), to \(B\) with probability \(\tfrac15\), and to \(j\notin A\cup B\) with probability \(\tfrac25\). Write its first-step equation.
- In the finite walk example, verify the first-step equation at state \(2\) using \(h_1=\tfrac{8}{15}\), \(h_2=\tfrac45\), and \(h_3=\tfrac{14}{15}\).
- Why can the probabilities of hitting \(A\) first and hitting \(B\) first sum to less than one?
- What is wrong with an equation that omits the transition probability of moving directly into \(A\)?