Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Let $X_n$ be a Markov chain on a countable state space $E$. For $x\in E$ let $\tau_x:=\inf\{n\geq 1\vert X_n=x\}$ be the first hitting time.

What can be said about the relation between the transition matrix $p(x,y)$ of the Markov chain and the probability of the first hitting time $\mathbb P(\tau_x =k\vert X_0=y)$?

Is there a general explicit relation or is there a non-trivial class of Markov chains for which the relation can be calculated explicitly?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

For every $k\geqslant1$ and $x$ and $y$ in $E$, let $h_k(x,y)=\mathbb P(\tau_y=k\mid X_0=x)$, then $h_1(x,y)=p(x,y)$ and, for every $k\geqslant1$, $h_{k+1}(x,y)=\sum\limits_{z\ne y}p(x,z)h_k(z,y)$.

Consider the matrices $p=(p(x,y))_{(x,y)\in E\times E}$, $h_k=(h_k(x,y))_{(x,y)\in E\times E}$ for every $k\geqslant1$, and $d_k$ the diagonal matrix with the diagonal of $h_k$. Then, $h_1=p$ and, for every $k\geqslant1$, $h_{k+1}=ph_k-pd_k$.

share|improve this answer
    
I hope I understand correctly that $h_k(x,y)$ is the probability that a random walk starting from $x$ first hits $y$ in $k$ steps. Does not the formula $\sum_{z \neq y} p(x,z) h_k(z,y)$ give the probability that $x$ reaches $y$ for the first time in $k+1$ steps, but with the $k^{th}$ vertex in the walk only repeated once if it is not the vertex $x$. However, shouldn't computing $h_{k+1}(x,y)$ consider the probability of taking any path $(x,v_2, \dots, v_k, y)$ from $x$ to $y$ where $y \notin \{v_2, v_3, \dots, v_k\}$? –  Ryder Bergerud May 9 at 17:07
    
edit: Does not the formula $\sum_{z \neq y} p(x,z) h_k(z,y)$ give the probability that $x$ reaches $y$ for the first time in $k+1$ steps, but with the $k^{th}$ vertex in the walk, v_k, not repeated in the walk if it is not the vertex $x$ (i.e. $v_k \neq v_i$ $i \neq 1$) –  Ryder Bergerud May 9 at 17:13
1  
@RyderBergerud No. The sum enumerates the paths from x to y hitting y for the first time at time k+1 according to the vertex z on the path at time 1. –  Did May 9 at 18:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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