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).

  • $\begingroup$ 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? $\endgroup$ – Mike Feb 23 at 13:27
  • 1
    $\begingroup$ 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. $\endgroup$ – Benjamin Wang Feb 23 at 14:12
  • $\begingroup$ Can you explain more about 1)? I still do not quite understand your point. $\endgroup$ – Mike Feb 23 at 14:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.