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 Answer 1

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$
3
  • $\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$ May 9, 2014 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$ May 9, 2014 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, 2014 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.