[proofplan] We prove two claims: that $(h_i^A)$ satisfies the given system, and that it is the minimal non-negative solution. The first claim follows from first-step analysis: for $i \in A$ the result is immediate, and for $i \notin A$ we condition on $X_1$ and apply the Markov property to express $h_i^A$ as a weighted sum of $h_j^A$ over all $j \in S$. The second claim uses an iterative expansion of any competing non-negative solution $(x_i)$, showing by induction that $x_i \geq \mathbb{P}_i(H^A \leq n)$ for every $n$, and passing to $n \to \infty$. [/proofplan]

[step:Verify $h_i^A = 1$ for $i \in A$] If $i \in A$, the chain starts in $A$ at time $0$, so $H^A = 0$ and \begin{align*} h_i^A = \mathbb{P}_i(H^A < \infty) = \mathbb{P}_i(H^A = 0) = 1. \end{align*} [/step]

[step:Condition on $X_1$ to derive the recurrence for $i \notin A$]Suppose $i \notin A$. Since $X_0 = i \notin A$, we have $H^A \geq 1$, and the chain must take at least one step before reaching $A$. Partition the event $\{H^A < \infty\}$ according to the value of $X_1$. By the law of total probability, \begin{align*} h_i^A = \mathbb{P}_i(H^A < \infty) = \sum_{j \in S} \mathbb{P}_i(H^A < \infty \mid X_1 = j)\, \mathbb{P}_i(X_1 = j). \end{align*} Since $\mathbb{P}_i(X_1 = j) = p_{i,j}$, it remains to evaluate $\mathbb{P}_i(H^A < \infty \mid X_1 = j)$. By the Markov property, given $X_1 = j$, the future of the chain $(X_1, X_2, \ldots)$ is a Markov chain started at $j$ with the same transition matrix $P$. Since $i \notin A$, the event $\{H^A < \infty\}$ depends only on $(X_1, X_2, \ldots)$. Therefore \begin{align*} \mathbb{P}_i(H^A < \infty \mid X_1 = j) = \mathbb{P}_j(H^A < \infty) = h_j^A. \end{align*} Substituting: \begin{align*} h_i^A = \sum_{j \in S} p_{i,j}\, h_j^A. \end{align*} This confirms that $(h_i^A)$ satisfies the stated system.[/step]

[guided]The strategy is **first-step analysis**: we do not try to compute $h_i^A$ by summing over all paths of all lengths. Instead, we condition on the very first transition $X_0 \to X_1$. Because $i \notin A$, the chain has not yet hit $A$ at time $0$, so it must take at least one step, and the hitting event $\{H^A < \infty\}$ depends entirely on the trajectory from time $1$ onward. By the law of total probability, conditioning on $X_1 = j$: \begin{align*} h_i^A = \mathbb{P}_i(H^A < \infty) = \sum_{j \in S} \mathbb{P}_i(H^A < \infty \mid X_1 = j)\, p_{i,j}. \end{align*} Now we need to evaluate $\mathbb{P}_i(H^A < \infty \mid X_1 = j)$. The Markov property states that given $X_1 = j$, the process $(X_1, X_2, \ldots)$ is a Markov chain with the same transition matrix $P$ started at $j$, independent of $X_0$. Since $i \notin A$, the event $\{H^A < \infty\}$ is determined entirely by $(X_1, X_2, \ldots)$ — whether the chain hits $A$ at any time $n \geq 1$. Under the conditional law given $X_1 = j$, this is exactly $\mathbb{P}_j(H^A < \infty) = h_j^A$. Substituting: \begin{align*} h_i^A = \sum_{j \in S} p_{i,j}\, h_j^A. \end{align*} This confirms that $(h_i^A)$ satisfies the system. The key point is that the Markov property converts the conditional probability into the hitting probability from the new starting state $j$.[/guided]

[step:Prove minimality by induction on the truncated hitting probability]Let $(x_i : i \in S)$ be any non-negative solution to the system. We must show $x_i \geq h_i^A$ for all $i \in S$. For $i \in A$, the system requires $x_i = 1 = h_i^A$, so the inequality holds. For $i \notin A$, we prove by induction on $n \geq 0$ that $x_i \geq \mathbb{P}_i(H^A \leq n)$. **Base case** ($n = 0$): Since $i \notin A$, we have $\mathbb{P}_i(H^A \leq 0) = \mathbb{P}_i(X_0 \in A) = 0$, and $x_i \geq 0$ by hypothesis. **Inductive step**: Suppose $x_j \geq \mathbb{P}_j(H^A \leq n)$ for all $j \in S$. Since $(x_i)$ satisfies the recurrence, for $i \notin A$: \begin{align*} x_i = \sum_{j \in S} p_{i,j}\, x_j. \end{align*} Split the sum over $j \in A$ and $j \notin A$. For $j \in A$, $x_j = 1$, and for $j \notin A$, $x_j \geq \mathbb{P}_j(H^A \leq n)$ by the inductive hypothesis. Therefore: \begin{align*} x_i &\geq \sum_{j \in A} p_{i,j} \cdot 1 + \sum_{j \notin A} p_{i,j}\, \mathbb{P}_j(H^A \leq n). \end{align*} The first sum equals $\mathbb{P}_i(X_1 \in A) = \mathbb{P}_i(H^A = 1)$. For the second sum, since $j \notin A$, the event $\{H^A \leq n\}$ under $\mathbb{P}_j$ corresponds, when the chain starts at $i$ and takes its first step to $j$, to hitting $A$ by time $n + 1$ (one additional step has elapsed). By the Markov property: \begin{align*} \sum_{j \notin A} p_{i,j}\, \mathbb{P}_j(H^A \leq n) = \mathbb{P}_i(H^A \leq n + 1,\, X_1 \notin A). \end{align*} Combining: \begin{align*} x_i \geq \mathbb{P}_i(H^A = 1) + \mathbb{P}_i(H^A \leq n + 1,\, X_1 \notin A) = \mathbb{P}_i(H^A \leq n + 1). \end{align*} This completes the inductive step. Taking $n \to \infty$ and using the monotone convergence of events $\{H^A \leq n\} \uparrow \{H^A < \infty\}$: \begin{align*} x_i \geq \lim_{n \to \infty} \mathbb{P}_i(H^A \leq n) = \mathbb{P}_i(H^A < \infty) = h_i^A. \end{align*}[/step]

[guided]Why is minimality needed? The system of equations can have multiple non-negative solutions. For instance, in the gambler's ruin with $p > q$, the constant function $x_i = 1$ satisfies the recurrence but overestimates the true hitting probability $h_i^{\{0\}} = (q/p)^i$. Minimality identifies the actual hitting probability among all non-negative solutions. The proof strategy is to show that any non-negative solution $(x_i)$ dominates the truncated hitting probability $\mathbb{P}_i(H^A \leq n)$ for every $n$, then send $n \to \infty$. For $i \in A$, the system forces $x_i = 1 = h_i^A$, so there is nothing to prove. For $i \notin A$, we proceed by induction on $n$. The base case $n = 0$ is immediate: $\mathbb{P}_i(H^A \leq 0) = 0$ since $i \notin A$, and $x_i \geq 0$ by hypothesis. For the inductive step, assume $x_j \geq \mathbb{P}_j(H^A \leq n)$ for all $j \in S$. Using the recurrence $x_i = \sum_j p_{i,j}\, x_j$ and splitting over $j \in A$ (where $x_j = 1$) and $j \notin A$ (where $x_j \geq \mathbb{P}_j(H^A \leq n)$ by the inductive hypothesis): \begin{align*} x_i \geq \sum_{j \in A} p_{i,j} + \sum_{j \notin A} p_{i,j}\, \mathbb{P}_j(H^A \leq n). \end{align*} The first term equals $\mathbb{P}_i(X_1 \in A) = \mathbb{P}_i(H^A = 1)$. The second term uses the Markov property: given $X_1 = j \notin A$, the probability of hitting $A$ within $n$ more steps from $j$ corresponds to hitting $A$ by time $n+1$ from $i$ along paths whose first step avoids $A$. Combining these gives $x_i \geq \mathbb{P}_i(H^A \leq n + 1)$, completing the induction. Taking $n \to \infty$: the events $\{H^A \leq n\}$ form an increasing sequence with union $\{H^A < \infty\}$, so by continuity of probability: \begin{align*} x_i \geq \lim_{n \to \infty} \mathbb{P}_i(H^A \leq n) = \mathbb{P}_i(H^A < \infty) = h_i^A. \end{align*} The non-negativity of $(x_i)$ is essential at the base case: it ensures that discarding the terms from $j \notin A$ at each iteration step is a valid lower bound. Without this, the iterative argument could produce negative intermediate quantities and the induction would fail.[/guided]