Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

There exists an absorbing $(M \times M)$Markov chain with the following transition matrix:

$$ \begin{array}{ccccccc} p_{11} & p_{12}&0&\cdots&\cdots&\cdots&0\\ p_{21} & p_{22}&p_{23}&0&\cdots&\cdots&0\\ 0 & p_{32}&p_{33}&p_{34}&0&\cdots&0\\ \cdots&\cdots&\cdots&\cdots&\cdots&\cdots&0\\ 0&0&0&0&p_{M-1,M-2}&p_{M-1,M-1}&p_{M-1,M}\\ 0&0&0&0&0&0&1 \end{array} $$

I'd like to find $m_{1M}$, the expected first hitting time of the absorbing state given that the first state is $1$. In a simple case I'd use the system of linear equations, of course: $$ \begin{eqnarray} &m_{1M}=1+p_{11}m_{1M}+p_{12}m_{2M} \\ m_{2M}&=1+p_{21}m_{1M}+p_{22}m_{2M} +p_{33}m_{3M} \end{eqnarray} $$ and so on. Of course, this case is more complicated, and this approach is intractable.

I'll be grateful for the suggestions on how to find the approximation/upper bound on $m_{1M}$, becuase I'm quite sure the exact expression is probably impossible to find.

share|cite|improve this question
The transition matrix has a block diagonal structure $P = \begin{pmatrix} P_{11} & P_{12} \cr 0 & 1 \end{pmatrix}$. It is easily seen from your equations, that $m_{1M} = \left(\left( \mathbb{1}_{M-1} - P_{11} \right)^{-1} \mathbf{1}\right)_{1}$, where $\mathbf{1}$ is $M-1$ dimensional vector with elements equal to 1, and $\mathbb{1}_{M-1}$ is $M-1$-dimensional identity matrix. – Sasha Jan 10 '12 at 22:35
up vote 1 down vote accepted

The equations can be solved with a tractable approach - $O(n)$ - using backwards recursion.

I will use $m_k$ rather than $m_{k,M}$ to save space. Suppose $m_k=a_k+b_k m_{k-1}$: then $a_M=0$ and $b_M=0$ and looking at $m_k=1+p_{k,k-1}m_{k-1}+p_{k,k}m_k+p_{k,k+1}m_{k+1}$ you find

$$a_k = \frac{1+p_{k,k+1}a_{k+1}}{1- p_{k,k} -p_{k,k+1}b_{k+1}}$$ $$b_k = \frac{p_{k,k-1}}{1- p_{k,k} -p_{k,k+1}b_{k+1}}$$

so you can calculate back to $a_2$ and $b_2$. But you also have $m_1=1+p_{1,1}m_1+p_{1,2}m_2$ so $b_1=0$ and $a_1$ is


which is what you asked for. You can now use forward recursion to find all $m_k$.

share|cite|improve this answer
thanks. this means I seem to end up with some sequence of continuants both in the numerator and denominator of expression for $m_1$, which looks quite hard, so some 'closed-form' is pretty much intractable. Is there any way to simplify it? – sigma.z.1980 Jan 11 '12 at 23:45

Your Answer


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.