Why First-Step Hitting Equations Are Valid

From the First Transition to an Equation

Hitting probabilities describe events about an entire future path, but their equations involve only one transition at a time. The reason is the Markov property: once the first state is known, the remaining probability of hitting a target before another target is the corresponding probability for a chain started at that state. Making this reasoning precise requires care with transitions of probability zero, because conditioning on such a transition is not defined.

Let $(X_n)_{n\ge0}$ be a discrete-time Markov chain on a finite state space $S$, defined on a probability space $(\Omega,\mathcal{F},\mathbb{P})$, with transition matrix $P=(p_{ij})$. The entries are nonnegative and each row sums to $1$. We use the natural filtration $\mathcal{F}_n=\sigma(X_0,\ldots,X_n)$. For disjoint sets $A,B\subseteq S$, define $T_A=\inf\{n\ge0:X_n\in A\}$ and $T_B=\inf\{n\ge0:X_n\in B\}$, taking the infimum of the empty set to be $\infty$. For $i\in S$, let $h_i=\mathbb{P}_i(T_A<T_B)$, where $\mathbb{P}_i$ means the chain starts at $i$. If $i\in A$, then $h_i=1$; if $i\in B$, then $h_i=0$. These boundary values use the strict comparison $T_A<T_B$.

Theorem (First-step equations): For every $i\in S\setminus(A\cup B)$, $$ h_i=\sum_{j\in S}p_{ij}h_j, $$ with boundary values $h_i=1$ on $A$ and $h_i=0$ on $B$. No assumption that $A\cup B$ is reached almost surely is needed for these equations.

Proof. Fix $i\notin A\cup B$. The events $\{X_1=j\}$, for states $j$ with $p_{ij}>0$, partition the possible first transitions under $\mathbb{P}_i$. For each such $j$, the conditional probability $\mathbb{P}_i(T_A<T_B\mid X_1=j)$ is defined. If $j\in A$, the target $A$ has been reached at time $1$ before $B$, so this conditional probability is $1=h_j$. If $j\in B$, it is $0=h_j$. If $j\notin A\cup B$, then after the first step the event of reaching $A$ before $B$ is exactly the same event for the chain’s future, viewed as a chain started at $j$. The Markov property therefore gives conditional probability $h_j$. Summing over the positive-probability first transitions gives $$ h_i=\sum_{j:p_{ij}>0}\mathbb{P}_i(X_1=j)\,h_j =\sum_{j:p_{ij}>0}p_{ij}h_j =\sum_{j\in S}p_{ij}h_j, $$ because terms with $p_{ij}=0$ contribute zero. This argument does not condition on any null event. The stated boundary values follow from the definitions of the hitting times when the chain starts in $A$ or $B$. $\square$

The theorem supplies a solution: the actual probabilities $h_i$. But equations alone need not determine a unique solution. To see when they do, consider a general finite boundary-value system. Let $C\subseteq S$ be a nonempty boundary set and $D=S\setminus C$. Prescribe a real value $g_i$ for each $i\in C$, and seek values $u_i$ satisfying $u_i=g_i$ on $C$ and $u_i=\sum_j p_{ij}u_j$ on $D$. The condition we need is that every $i\in D$ has a positive-probability path to $C$: for each such $i$, there is a finite sequence $i=i_0,i_1,\ldots,i_m$ with $i_m\in C$ and $p_{i_{r-1}i_r}>0$ for every $1\le r\le m$. If $D$ is empty, there are no interior equations and the boundary values already specify the solution.

Uniqueness by a Maximum Principle

Theorem (Uniqueness of the finite boundary system): Suppose $S$ is finite, $C$ is nonempty, and every state in $D=S\setminus C$ has a positive-probability path to $C$. For any prescribed finite real boundary values $g_i$, there is at most one function $u:S\to\mathbb{R}$ satisfying $u_i=g_i$ on $C$ and $u_i=\sum_jp_{ij}u_j$ on $D$.

Proof. Suppose $u$ and $v$ both satisfy the system, and put $w_i=u_i-v_i$. Then $w_i=0$ on $C$, and $w_i=\sum_jp_{ij}w_j$ on $D$. Since $S$ is finite, $w$ attains its maximum and minimum. If $w$ is not identically zero, then either its maximum $M$ is positive or its minimum $m$ is negative. Consider first $M>0$. A state $i$ attaining $M$ must lie in $D$, because $w=0$ on $C$. The equation at $i$ expresses $M$ as a weighted average of values no greater than $M$: $$ M=w_i=\sum_jp_{ij}w_j\le\sum_jp_{ij}M=M. $$ Equality forces $w_j=M$ for every $j$ with $p_{ij}>0$: if any such value were smaller than $M$, its positive weight would make the average strictly smaller. Apply the same argument at each such interior successor. Along a positive-probability path from $i$ to $C$, this forces the value at the boundary endpoint to be $M$, contradicting that boundary values of $w$ are zero. If instead $m<0$, take a state attaining $m$. Its weighted average can equal $m$ only if every positive-probability successor also has value $m$. Propagating along a path to $C$ contradicts the zero boundary value. Both possibilities are impossible, so $w=0$ everywhere and $u=v$. $\square$

This is a maximum-principle argument: an interior value that is an average cannot be a strict maximum unless all states it can move to share that maximum. Accessibility carries the forced value to the boundary, where it conflicts with the prescribed data. The result establishes uniqueness, not existence for arbitrary boundary data. For hitting probabilities, existence is already supplied by their definition and the first-step theorem; under the accessibility condition, the uniqueness theorem says that the equations identify those probabilities completely.

Worked Example: A Symmetric Walk Between Two Boundaries

Consider a chain on $S=\{0,1,2,3,4\}$. States $0$ and $4$ are absorbing. From each of $1,2,3$, the chain moves one step left or right with probability $\tfrac12$. Find the probability of hitting $A=\{4\}$ before $B=\{0\}$, starting from each interior state.

In the state order $0,1,2,3,4$, the transition matrix is $$ P=\begin{bmatrix} 1&0&0&0&0\\ \tfrac12&0&\tfrac12&0&0\\ 0&\tfrac12&0&\tfrac12&0\\ 0&0&\tfrac12&0&\tfrac12\\ 0&0&0&0&1 \end{bmatrix}. $$ The row sums are respectively $1$, $\tfrac12+\tfrac12=1$, $\tfrac12+\tfrac12=1$, $\tfrac12+\tfrac12=1$, and $1$, so each row is a probability distribution. Every interior state has a positive-probability path to a boundary. The equations and boundary values are $$ h_0=0,\qquad h_4=1,\qquad h_1=\tfrac12h_0+\tfrac12h_2,\quad h_2=\tfrac12h_1+\tfrac12h_3,\quad h_3=\tfrac12h_2+\tfrac12h_4. $$

Take the candidate values $h_1=\tfrac14,\ h_2=\tfrac12,\ h_3=\tfrac34$. Substitution gives $\tfrac12(0)+\tfrac12(\tfrac12)=\tfrac14$ in the first interior equation, $\tfrac12(\tfrac14)+\tfrac12(\tfrac34)=\tfrac12$ in the second, and $\tfrac12(\tfrac12)+\tfrac12(1)=\tfrac34$ in the third. The boundary values also hold. The uniqueness theorem therefore proves these are the hitting probabilities. As a check, each is between $0$ and $1$, and the probability increases with distance from $0$, as the equations and boundary values suggest.

Worked Example: Two Interior States and Exact Substitution

Let $S=\{a,b,c,d\}$, with $A=\{a\}$ and $B=\{b\}$. States $a,b$ are absorbing. From $c$, move to $a,b,d$ with probabilities $\tfrac14,\tfrac14,\tfrac12$; from $d$, move to $a,c,d$ with probabilities $\tfrac12,\tfrac14,\tfrac14$. Compute the probability of hitting $A$ before $B$ from $c$ and $d$.

In the order $a,b,c,d$, the transition matrix is $$ P=\begin{bmatrix} 1&0&0&0\\ 0&1&0&0\\ \tfrac14&\tfrac14&0&\tfrac12\\ \tfrac12&0&\tfrac14&\tfrac14 \end{bmatrix}. $$ Its row sums are $1$, $1$, $\tfrac14+\tfrac14+\tfrac12=1$, and $\tfrac12+\tfrac14+\tfrac14=1$. Both interior states can reach a boundary with positive probability. The first-step equations are $$ h_a=1,\qquad h_b=0,\qquad h_c=\tfrac14+\tfrac12h_d,\qquad h_d=\tfrac12+\tfrac14h_c+\tfrac14h_d. $$

From the equation for $d$, subtract $\tfrac14h_d$ from both sides to obtain $\tfrac34h_d=\tfrac12+\tfrac14h_c$, or $3h_d=2+h_c$. The equation for $c$ gives $4h_c=1+2h_d$, so $h_c=\tfrac14+\tfrac12h_d$. Substituting this into $3h_d=2+h_c$ gives $3h_d=2+\tfrac14+\tfrac12h_d$, hence $\tfrac52h_d=\tfrac94$ and $h_d=\tfrac9{10}$. Then $h_c=\tfrac14+\tfrac12(\tfrac9{10})=\tfrac14+\tfrac9{20}=\tfrac7{10}$.

Check by substitution: The right side for $c$ is $\tfrac14+\tfrac12(\tfrac9{10})=\tfrac{10}{40}+\tfrac{18}{40}=\tfrac7{10}$. The right side for $d$ is $\tfrac12+\tfrac14(\tfrac7{10})+\tfrac14(\tfrac9{10})=\tfrac12+\tfrac7{40}+\tfrac9{40}=\tfrac{36}{40}=\tfrac9{10}$. Both equations hold, and uniqueness confirms the solution.

Zero-Probability Transitions and the Role of Accessibility

Worked Example: A Transition That Cannot Be Conditioned On

Let $S=\{a,b,c\}$, $A=\{a\}$, and $B=\{b\}$. States $a,b$ are absorbing, while from $c$ the chain moves to $a$ or stays at $c$, each with probability $\tfrac12$. Find $h_c$, and identify the correct treatment of state $b$ in the first-step argument.

In the order $a,b,c$, the matrix is $$ P=\begin{bmatrix} 1&0&0\\ 0&1&0\\ \tfrac12&0&\tfrac12 \end{bmatrix}. $$ The row sums are $1$, $1$, and $\tfrac12+\tfrac12=1$. Starting from $c$, the positive-probability first transitions lead to $a$ and $c$. Thus $$ h_c=\tfrac12 h_a+\tfrac12 h_c=\tfrac12+\tfrac12h_c. $$ Subtracting $\tfrac12h_c$ gives $\tfrac12h_c=\tfrac12$, so $h_c=1$. Substitution checks the equation: $\tfrac12+\tfrac12(1)=1$. The chain reaches $a$ eventually with probability $1$, consistent with this value.

Common mistake: One might write $\mathbb{P}_c(T_A<T_B\mid X_1=b)=h_b=0$ and then include that conditional probability in a sum. But $p_{cb}=0$, so $\mathbb{P}_c(X_1=b)=0$; the elementary conditional probability given $X_1=b$ is undefined. The correction is to partition only over positive-probability first transitions, as in $h_c=\tfrac12h_a+\tfrac12h_c$. Equivalently, one may write a sum over all states with terms $p_{cj}h_j$, whose $j=b$ term is zero, without asserting a conditional probability on that null event.

The accessibility condition in the uniqueness theorem matters. For example, take $S=\{a,b,c\}$, let $a$ and $b$ be absorbing boundary states with values $1$ and $0$, and let $c$ be absorbing as well. Every row of the transition matrix is the corresponding unit vector, so every row sums to $1$. The interior equation is $u_c=u_c$, which allows any real value for $u_c$. The actual probability of hitting $a$ before $b$ from $c$ is $0$, because neither boundary is ever reached, but the boundary-value equations do not uniquely identify it. State $c$ has no path to the boundary, exactly where the maximum-principle proof would fail.

For hitting probabilities, the first-step equations are therefore valid regardless of whether the boundary is reached almost surely, while uniqueness requires a separate check. In a finite chain, it is enough for each interior state to have some positive-probability path to the boundary: the maximum-principle proof uses each such path to rule out a nonzero extremum. Without that condition, a closed region away from the boundary can support additional solutions. When using first-step equations, keep these questions separate: first derive the equations from the Markov property, then verify whether the boundary conditions and accessibility make their solution unique.

Check Your Understanding

For each question, write the relevant boundary values and justify any first-step equation using only transitions with positive probability.

If $i\notin A\cup B$, why does partitioning over $X_1$ give the first-step equation for $h_i$?
In a chain with $p_{ij}=0$, is $\mathbb{P}_i(T_A<T_B\mid X_1=j)$ defined as an elementary conditional probability? What expression can be used safely instead?
State the accessibility condition in the uniqueness theorem, and explain where it enters the maximum-principle proof.
For the four-state example, substitute $h_c=\tfrac7{10}$ and $h_d=\tfrac9{10}$ into both interior equations.
Give the interior equation for an absorbing state $c$ outside the boundary. Why does it show that uniqueness can fail when the boundary is inaccessible?

Why First-Step Hitting Equations Are Valid

What You'll Learn