# Show that the probability that first passage time is finite satisfies this BVP

I am doing some exercises in E-Li-Vanden-Eijnden's Applied Stochastic Analysis and I meet this problem:

(Exercise 3.19) Consider an irreducible Markov chain $$\{X_n\}$$ on a finite state space $$S$$. Let $$H\subset S$$ and define the first passage time $$T_H=\inf\{n:X_n\in H\}$$, $$h_i=P_i(T_H<\infty)$$. Prove that $$\boldsymbol{h}=\{h_i\}_{i\in S}$$ (column vector) satisfies $$(\boldsymbol{I}-\boldsymbol{P})\cdot\boldsymbol{h}=0$$ with boundary condition $$h_i=1$$ for $$i\in H$$, where $$\boldsymbol{P}$$ is the transition matrix, and $$\boldsymbol{I}$$ is the identity matrix.

I have been struggling for this problem for hours and do not have much progress. The only thing that I can do currently is, as suggested by the book, to define the Laplace matrix $$\boldsymbol{L}=-(\boldsymbol{I}-\boldsymbol{P})$$ by acting on any function $$(\boldsymbol{L}f)(i)=\sum_{j\in S}p_{ij}(f(j)-f(i))$$, where $$p_{ij}$$ are entries of $$\boldsymbol{P}$$.

According to this, I write $$(\boldsymbol{I}-\boldsymbol{P})\cdot\boldsymbol{h}=(-\boldsymbol{L}h)(i)=\sum_{i,j\in S}p_{ij}(h(i)-h(j))$$

but starting from here, I get stuck. Can anyone provide any solutions regarding this? Thank you.

You want to prove that the vector of hitting probabilities satisfies $$h = Ph$$, with the boundary condition $$h_i=1$$ for $$i\in H$$.

If the chain starts in $$H$$, you're guaranteed to hit it, so the boundary condition follows.

If you start outside $$H$$, you can condition on the first step (notation $$P_i(\cdot) = P(\cdot | X_0 = i)$$):

$$h_i=P_i(T_H < \infty) = \sum_{j\in S}P_i(T_H<\infty, X_1 = j)=\sum_{j\in S}P_i(T_H<\infty| X_1 = j)P(X_1=j) = \sum_{j\in S}h_jp_{ij}=\sum_{j\in S}p_{ij}h_j,$$

where we have used that $$P_i(T_H<\infty| X_1 = j)=P_j(T_H<\infty)=h_j$$ by the Markov property.

If you're interested, $$h$$ is in fact the minimal solution to this system (in the sense that each vector component is minimal).

• Thank you for the answer. I have some questions to follow up, since I am completely new to Markov chain. Can you provide more details to the first case? I tried but cannot express it using $p_{ij}$'s. For the second case, is it true that the events $\{T_H<\infty\}$ and $\{X_i=j\}$ are independent? Can you provide more details explaining that $\boldsymbol{h}$ is the minimal solution to the BVP? And did you use Chapman-Kolmogorov in the second case? – Mike Feb 23 at 13:27
• 1) I don't think $(I-P)h=0$ is guaranteed to be satisfied for those indexed $h_i$ with $i\in H$ (the chain already starts in $H$). 2) See edit. 3) You should ask another question for this. 4) I just looked up C-K now, and it looks like a simple "marginalisation" / "integration" / "summation" over something, which is basically what I used in the 2nd "=" in the 2nd case. – Benjamin Wang Feb 23 at 14:12
• Can you explain more about 1)? I still do not quite understand your point. – Mike Feb 23 at 14:34