0
$\begingroup$

I'm having trouble understanding what hitting times are in Markov chain processes and how they are calculated. An example follows:

A Markov process on $E = \{1, 2, 3\}$ has the following generator matrix

$$\begin{pmatrix}−2 & 1 & 1 \\ 2 & −4 & 2 \\ 0 & 3 & −3\end{pmatrix}$$

Given that the process starts from state $3$, what is the distribution of the time until it hits state $2$?

Given that the process starts either from state $1$ or state $3$ with equal probability $0.5$, what is the distribution of the time until it hits state $2$?

Any help?

$\endgroup$

1 Answer 1

1
$\begingroup$

In continuous time, in general you need the jump matrix in addition to the generator matrix. The jump matrix will tell you the probability of each path from $i$ to $j$, while the generator will then tell you the distribution of the holding times for each step of a specified path.

Assuming none of rows of the generator are zero, the jump matrix $\Pi$ has off-diagonal entries $\Pi_{ij}=\frac{L_{ij}}{\sum_{j=1,j \neq i}^n L_{ij}}$, and diagonal entries of zero. So your generator has a jump matrix of

$$\Pi = \begin{bmatrix} 0 & 1/2 & 1/2 \\ 1/2 & 0 & 1/2 \\ 0 & 1 & 0 \end{bmatrix}.$$

In the particular case you asked, one always transitions from $3$ to $2$, so the hitting time for $2$ from $3$ is just the holding time at $3$. In a continuous time Markov chain the holding time at $i$ is exponentially distributed with parameter $-\frac{1}{L_{ii}}$. Intuitively, $-L_{ii}$ measures the frequency of transitions, so its reciprocal measures the time of transitions. There is a natural analogy to electric networks here: at a node $i$ you have $n-1$ parallel resistors extending to each state $j$, each of which has resistance $\frac{1}{L_{ij}}$ (which is understood as $+\infty$ if $L_{ij}=0$).

It is an interesting exercise to prove that the holding times are exponentially distributed. It follows from the more elementary fact that the only random variables with the "memoryless property" $P(X>t+s | X>s)=P(X>t)$ are exponential variables.

For the second question, there are a couple possible paths, which you might describe as a tree. Let's instead assume that you start at 1 with probability 1. Now you will either go to 2 with probability 1/2 or go to 3 with probability 1/2. If you do the latter then you will go to 2 with probability 1 after that. So there are two possible paths, each with probability 1/2. If you take the first one, you arrive in a time which is exponentially distributed with parameter $\frac{1}{2}$ (corresponding to the holding time at 1). If you take the second one, you arrive in a time which is exponentially distributed with parameter $\frac{1}{2}+\frac{1}{3}=\frac{5}{6}$ (corresponding to the holding time at 1 followed by the holding time at 3). Do you see how to combine these?

$\endgroup$
5
  • $\begingroup$ I get what you are saying here, it makes sense that the hitting time would be the holding time at 3 and since L(3)=3 it would be equal to 1/3. But if I am asked for the distribution of time until it hits state 2 wouldn't that affect the answer? $\endgroup$ Commented Apr 16, 2015 at 13:56
  • $\begingroup$ @kullapparos As I said, the holding time at $3$ is exponentially distributed with parameter $-\frac{1}{L_{33}}=\frac{1}{3}$. $\endgroup$ Commented Apr 16, 2015 at 14:43
  • $\begingroup$ @kullapparos Also (if it isn't clear), in your case the holding time at $3$ is exactly the hitting time of $2$, since the chain at $3$ always goes to $2$. $\endgroup$ Commented Apr 16, 2015 at 15:03
  • $\begingroup$ Thank you Ian, any ideas for the second part of the question? $\endgroup$ Commented Apr 17, 2015 at 12:53
  • $\begingroup$ @kullapparos See my edit. $\endgroup$ Commented Apr 17, 2015 at 13:02

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.