Solving Hitting-Probability Systems Exactly

From First-Step Equations to Exact Answers

First-step analysis turns a hitting-probability question into a system of linear equations. The equations describe the probability of success after conditioning on the first transition; solving them is a separate task. Exact fractions matter: they make elimination auditable and let us check the resulting probabilities without rounding.

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})\). Its transition matrix \(P=(p_{ij})\) is row-stochastic: \(p_{ij}\ge0\) and \(\sum_{j\in S}p_{ij}=1\) for every \(i\in S\). Let \(A,F\subseteq S\) be disjoint boundary sets, and write \(C=S\setminus(A\cup F)\). We seek the probability of hitting \(A\) before \(F\). Define \(T_A=\inf\{n\ge0:X_n\in A\}\) and \(T_F=\inf\{n\ge0:X_n\in F\}\), with \(\inf\varnothing=\infty\). For \(i\in C\), set \(h_i=\mathbb{P}_i(T_A<T_F)\); on the boundary, \(h_i=1\) for \(i\in A\) and \(h_i=0\) for \(i\in F\).

Assume that from every state in \(C\), the chain has positive probability of reaching \(A\cup F\) in finitely many steps. This assumption ensures that the boundary is eventually reached with probability one. If \(C=\varnothing\), there are no unknowns: the unique solution is the empty vector, and only the prescribed boundary values remain. For nonempty \(C\), the first-step equations, as established by the first-step analysis of hitting probabilities, are

The contribution from \(F\) is zero, while each transition into \(A\) contributes its transition probability because the hitting probability there is one. The next result explains why, under the stated assumption, solving this system determines the desired probabilities uniquely.

Proof. If \(C=\varnothing\), there are no coordinates to solve for, so the unique vector indexed by \(C\) is the empty vector. Now suppose \(C\ne\varnothing\). By the assumption, for each \(i\in C\) there is an integer \(n_i\ge1\) such that \(\mathbb{P}_i(T_A\wedge T_F\le n_i)>0\). Let \(N=\max_{i\in C}n_i\). Since reaching the boundary by time \(n_i\) implies reaching it by time \(N\), the finite minimum \[ \delta=\min_{i\in C}\mathbb{P}_i(T_A\wedge T_F\le N) \] is positive. Thus, for every \(i\in C\), \(\mathbb{P}_i(X_1,\ldots,X_N\in C)\le1-\delta\).

For a chain started at any \(i\in C\), let \(r_k=\mathbb{P}_i(X_0,\ldots,X_{kN}\in C)\). The Markov property gives \[ r_{k+1}=\sum_{j\in C}\mathbb{P}_i(X_0,\ldots,X_{kN}\in C,\ X_{kN}=j)\, \mathbb{P}_j(X_1,\ldots,X_N\in C) \le (1-\delta)r_k. \] This calculation conditions only through the state \(X_{kN}=j\); it does not condition on the event of still being in \(C\), which might have probability zero. Iterating yields \(r_k\le(1-\delta)^k\), so the probability of remaining in \(C\) forever is zero.

The vector \(h\) defined by the hitting probabilities satisfies the boundary conditions and the first-step equations by conditioning on \(X_1\). To show uniqueness, let \(u\) and \(v\) be two solutions and put \(d_i=u_i-v_i\) on \(C\), with \(d_i=0\) on \(A\cup F\). Their equations imply \(d_i=\sum_{j\in S}p_{ij}d_j\) for \(i\in C\). Iterating this relation for \(m\) steps gives \[ |d_i|\le \left(\max_{j\in C}|d_j|\right)\mathbb{P}_i(X_1,\ldots,X_m\in C). \] The maximum is finite because \(C\) is finite. Taking \(m=kN\), the probability on the right is at most \((1-\delta)^k\), which tends to zero. Hence \(d_i=0\) for every \(i\in C\), proving uniqueness. Finally, \(h_i\) is a probability, so \(0\le h_i\le1\). \(\square\)

A Reliable Exact-Solving Procedure

Write one equation for each unknown state, substitute the known boundary values, and keep all coefficients as fractions. Substitution is often fastest for one or two equations. Gaussian elimination is more systematic for larger systems. In elimination, an equation may be multiplied by a nonzero number, two equations may be interchanged, or a multiple of one equation may be added to another: each operation preserves the set of solutions. Because the theorem gives a unique solution, a correctly completed elimination must recover that solution. After solving, substitute every value into the original equations and check that each lies between zero and one, inclusive.

Common Errors and Final Checks

A frequent error is to drop self-loop terms because they do not change the state. They still contribute to the probability of eventually hitting the target: the chain may spend one or more steps there before moving on. In the last example, omitting both self-loop terms gives the incorrect equations \(h_1=\tfrac13h_2+\tfrac13\) and \(h_2=\tfrac14h_1\). These imply \(h_1=\tfrac4{11}\) and \(h_2=\tfrac1{11}\). Substitution into the correct first equation gives \[ \tfrac13\cdot\tfrac4{11}+\tfrac13\cdot\tfrac1{11}+\tfrac13 =\tfrac4{33}+\tfrac1{33}+\tfrac{11}{33} =\tfrac{16}{33}\ne\tfrac4{11}. \] The proposed values fail the original equation. The correction is to include every transition within \(C\), including transitions back to the current state.

For a dependable calculation, check the row sums before using \(P\), retain exact fractions during elimination, substitute the answer into every original equation, and verify \(0\le h_i\le1\) for each unknown state. The bounds are a useful diagnostic, but they do not replace substitution: a number can lie between zero and one and still fail the equations.