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

Reset to default
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$
    – Ryder Bergerud
    Commented 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$
    – Ryder Bergerud
    Commented 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
    Commented May 9, 2014 at 18:17

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .