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.

For discrete time finite Markov chain, the first passage time $T_j$ to visit state $j$, is determined from the recurrence equation: $$ p^{(n)}_{ij} = \sum_{k=0}^n f_{ij}^{(k)} p^{(n-k)}_{jj} = \sum_{k=0}^n \mathbb{P}(T_j = k ; X_0 = i) \mathbb{P}(X_{n-k} = j ; X_0 = j) $$ where $p^{(n)}_{ij} = \mathbb{P}(X_n = j ; X_0 = i)$ and $f^{(k)}_{ij} = \mathbb{P}(T_j = k ; X_0 = i)$. This recurrence equation allows to find probability generating function for the first passage time distribution (exerices 1.5.3 of J.R. Norris's book on "Markov Chains", relevant chapter 1.5 is available from Norris's website).

It strikes me odd that no book I have seen discusses first passage time distribution for continuous time finite Markov chain.

Can anyone suggest a reference where this is discussed/worked-out, or hint me at how to do this for myself.

I suspect a similar integral equation would be set-up, and moment generating function for the first-passage-time distribution would satisfy some simple equation.

Thanks for reading.

share|improve this question
add comment

2 Answers 2

up vote 2 down vote accepted

First of all, I wonder if $T_j$ refers to the first return time, or to the first hitting time. Since if you're talking about the latter case then $\mathsf P\{T_j = n-k|X_0 = j\} = 1_{\{k=n\}}$.

About continuous time case some insights are the following. I know results only for first hitting time. Let us introduce CTMC (continuous time Markov Chain) through its finite state space $\mathscr X$, transition matrix $R:\mathscr X\times \mathscr X\to[0,1]$ and exit-rate function $r:\mathscr X\to[0,\infty)$. For any initial point $x\in \mathscr X$ and target point $y\in \mathscr X$, the time-bounded reachability probability (or a cumulative distribution function for the first passage time) which we denote as $$ F(x,y,t) = \mathsf P_x\{\tau_y \leq t\} $$ is a least solution for $$ F(x,y,t) = 1_{\{y=x\}}+1_{\{y\neq x\}}\sum\limits_{z\in \mathscr X}R(x,z)\int\limits_0^t\mathrm e^{-r(x)s}F(z,y,t-s)\mathrm ds. $$

Assuming that $F$ has a density $f$ and recalling that $F(y,y,t) = 1$ we obtain: $$ f(x,y,t) = R(x,y)\mathrm e^{-r(x)t}+\sum\limits_{z\neq y}R(x,z)\int\limits_0^t\mathrm e^{-r(x)s}f(z,y,t-s)\mathrm ds $$ for any $x\neq y$.

With regards to the references - the only person whom I've found to work on that topic is he. The equation above I saw in his paper, but I do not remember which one. The problem may be also that his paper are focused on verification of general properties, usually much more complex that just reachability and it may be not so easy to go through the notation. However, I haven't seen something I can suggest you in the classical literature on Probability Theory. If you find it, please tell me.

Regards,

share|improve this answer
    
Thank you very much for the post. The first passage times $T_j$ is defined by J.R. Norris in his book as Markov processes as $T_j(\omega) = \inf \{ n \ge 1 : X_n(\omega) = j \}$. –  Sasha Nov 10 '11 at 15:53
    
You are welcome. So in some literature it is also called the first return time. For CTMCs you can show that it is a.s. equal to the first hitting time since the path is cadlag. I don't have an access to the whole J. Norrison's book, but didn't he discuss it in Ch.3.3? –  Ilya Nov 10 '11 at 15:56
    
In Ch.3.3, Norris defines hitting time of a subset $A$, $D^A(\omega) = \int\{t \ge 0: X_t(\omega) \int A \}$, and computes hitting probabilities $h_i^A = \mathbb{P}(D^A < \infty; X_0 = i)$ and expected hitting times $k_i^A = \mathbb{E}(D^A ; X_0 = i)$, but does not discuss the distribution of $D^A(\omega)$. –  Sasha Nov 10 '11 at 16:42
    
@Sasha: your $\inf$ and $\in$ turned to integrals. Infinite horizon hitting probabilities satisfy the same equation as for DTMC (Theorem 1.3.2 in Norris) as I remember, don't they? –  Ilya Nov 10 '11 at 16:43
    
Too bad I can no longer edit the comment. Yes, you are correct. The infinite horizon probabilities equal to those of the embedded Markov chain. –  Sasha Nov 10 '11 at 17:04
show 5 more comments

Concerning references, I've seen the problem of first passage time distributions treated in two books, unfortunately both are in German:

  • Nollau, V.: Semi-Markovsche Prozesse, H. Deutsch (1981).
  • Störmer, H.: Semi-Markoff-Prozesse mit endlich vielen Zuständen, Springer Lecture Notes in Operations Research and Math. Systems, Vol. 34 (1970).

As the titles imply, these references discuss the problem for semi-Markov processes, which of course includes the continuous time Markov chain case. For example, Nollau treats a more general problem: he provides a Markov renewal type equation, similar to the one posted by Ilya, for the probability $\Psi_{x,ABC}(t)$ of a transition from $A$ to $B$ not later than $t$, without leaving $C$, where $A$, $B$ and $C$ are subsets of states, $A\subseteq C$, and $x\in C$ is the initial state.

share|improve this answer
add comment

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.