Uniqueness of Expected Hitting-Time Solutions

Why Uniqueness Requires More Than Writing the Equations

First-step analysis expresses an expected hitting time as one step, followed by the expected remaining time from the state reached. These equations are useful only if their solutions are mathematically determined: an equation system might have no finite solution or might fail to distinguish among several candidates. For a finite chain, the key condition is that the target is reached almost surely from every starting state. Under that condition, the equations have exactly one finite solution, and the solution is given by the fundamental matrix of the states outside the target.

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 row-stochastic transition matrix \(P=(p_{ij})\). Thus \(\sum_{j\in S}p_{ij}=1\) for every \(i\). Let \(A\subseteq S\) be a nonempty target set, and define \(T_A=\inf\{n\ge0:X_n\in A\}\), with \(\inf\varnothing=\infty\). Write \(\mathbb P_i\) and \(\mathbb E_i\) for probabilities and expectations when \(X_0=i\). The standing assumption in the main result is \(\mathbb P_i(T_A<\infty)=1\) for every \(i\in S\). In particular, starting in \(A\) gives \(T_A=0\).

Set \(B=S\setminus A\), and let \(Q=(p_{ij})_{i,j\in B}\) be the submatrix for transitions that remain outside the target. This matrix is substochastic: its entries are nonnegative and its row sums are at most \(1\). For \(i\in B\), write \(k_i=\mathbb E_i[T_A]\). The first-step equations, with the boundary values \(k_i=0\) for \(i\in A\), reduce to \(k_i=1+\sum_{j\in B}p_{ij}k_j\) for \(i\in B\). In vector form, using \(\mathbf 1\) for the all-ones column vector indexed by \(B\), they are \((I-Q)\mathbf k=\mathbf 1\).

Proof. For \(i\in B\), the entry \((Q^n)_{ij}\) is the probability of being at \(j\in B\) at time \(n\) without having visited \(A\) by time \(n\). Therefore the \(i\)th row sum of \(Q^n\) is \(\mathbb P_i(T_A>n)\). Almost-sure reachability implies \(\mathbb P_i(T_A>n)\to0\) for every \(i\in B\). Since \(B\) is finite, choose an integer \(N\ge1\) large enough that \(\mathbb P_i(T_A>N)<1\) for every \(i\in B\), and let \(c=\max_{i\in B}\mathbb P_i(T_A>N)\). The maximum is over finitely many numbers strictly below \(1\), so \(c<1\). Thus the row sums of \(Q^N\) are at most \(c\).

For a nonnegative matrix \(M\), let \(\|M\|_\infty\) denote its largest row sum. For nonnegative matrices \(M,L\), \(\|ML\|_\infty\le\|M\|_\infty\|L\|_\infty\): for each row \(i\), \(\sum_j(ML)_{ij}=\sum_k M_{ik}\sum_jL_{kj}\le\|L\|_\infty\sum_kM_{ik}\). Since \(Q\) is substochastic, \(\|Q^r\|_\infty\le1\) for every integer \(r\ge0\). Writing \(n=kN+r\), where \(k\ge0\) and \(0\le r<N\), gives \(\|Q^n\|_\infty\le\|(Q^N)^k\|_\infty\|Q^r\|_\infty\le c^k\). Hence \(\sum_{n\ge0}\|Q^n\|_\infty\le N\sum_{k\ge0}c^k=N/(1-c)<\infty\). Each entry of the matrix series is bounded by its row sum, so the series converges entry by entry. \(\square\)

Proof. First suppose \(B\ne\varnothing\). By the lemma, the series \(N=\sum_{n=0}^{\infty}Q^n\) converges. For finite partial sums, \((I-Q)\sum_{n=0}^{m}Q^n=I-Q^{m+1}\) and \(\big(\sum_{n=0}^{m}Q^n\big)(I-Q)=I-Q^{m+1}\). The geometric bound in the lemma implies \(Q^{m+1}\to0\) entry by entry. Taking limits in both identities shows that \(N\) is a two-sided inverse of \(I-Q\).

For a nonnegative integer-valued random variable \(T_A\), the tail-sum identity gives \(\mathbb E_i[T_A]=\sum_{n\ge0}\mathbb P_i(T_A>n)\). This identity also holds initially with the value \(+\infty\), since \(T_A=\sum_{n\ge0}\mathbf 1_{\{T_A>n\}}\) and expectations of nonnegative sums equal the sum of expectations. The \(i\)th row sum of \(Q^n\) is \(\mathbb P_i(T_A>n)\), so \(\sum_{n\ge0}\mathbb P_i(T_A>n)=\sum_{j\in B}N_{ij}\), which is finite by convergence of the matrix series. Thus every \(k_i\) is finite, and \(\mathbf k=N\mathbf 1\).

The identity \((I-Q)N=I\) now gives \((I-Q)\mathbf k=\mathbf 1\), which is precisely the first-step system on \(B\). To prove uniqueness, let \(\mathbf x\) be any finite real-valued solution. Then \((I-Q)\mathbf x=\mathbf 1\), and multiplying by \(N\) gives \(\mathbf x=N\mathbf 1=\mathbf k\). This proves both existence and uniqueness. If \(B=\varnothing\), every state is in \(A\), so \(T_A=0\) from every starting state; there are no equations outside \(A\), and the empty vector is the unique vector of unknowns. \(\square\)

The matrix \(N\) is called the fundamental matrix because \(N_{ij}=\sum_{n\ge0}(Q^n)_{ij}\) counts the expected number of visits to state \(j\) before reaching \(A\), when starting at \(i\). The count includes time \(0\): if the chain starts at \(i\in B\), that initial visit is included. Summing these expected visit counts over all \(j\in B\) gives the expected number of time instants spent outside \(A\), which is the hitting time \(T_A\).

When the Condition Fails

Almost-sure reachability is not a cosmetic assumption. For a concrete failure, take \(S=\{1,2\}\), target \(A=\{2\}\), and \(P=\begin{bmatrix}1&0\\0&1\end{bmatrix}\). Both rows sum to \(1\), but starting at state \(1\) never reaches the target. Here \(B=\{1\}\), \(Q=[1]\), and the putative equation is \(k_1=1+k_1\), which has no finite solution. Correspondingly, \(I-Q=[0]\) has no inverse. This example shows why row sums at most \(1\) alone do not guarantee that \(I-Q\) is invertible.

Common mistake. A tempting but incorrect argument is: “\(Q\) is substochastic, so its row sums are at most \(1\); therefore the powers \(Q^n\) decay and \(I-Q\) is invertible.” The example above has a row sum equal to \(1\) and \(Q^n=[1]\) for every \(n\), so the series \(\sum_{n\ge0}Q^n\) does not converge. The correction is to use the almost-sure reachability condition and the finiteness of \(B\): together they give a common integer \(N\) and a strict bound \(c<1\) for every row sum of \(Q^N\). That strict bound, not substochasticity alone, yields geometric decay and the inverse.

In applications, uniqueness means that solving the linear system is justified: once a candidate satisfies every equation and boundary condition, it must be the expected hitting-time vector. The fundamental matrix gives a direct computation, while the step-by-step equations can be simpler for small systems. Either route relies on the same reachability check. If the target is not reached almost surely from all states in \(B\), first determine which states can avoid it; the theorem proved here cannot be applied without that condition.