2
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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\}$? $\endgroup$ – Ryder Bergerud May 9 '14 at 17:07
  • $\begingroup$ 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$) $\endgroup$ – Ryder Bergerud May 9 '14 at 17:13
  • 1
    $\begingroup$ @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. $\endgroup$ – Did May 9 '14 at 18:17

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.