2
$\begingroup$

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.

  • 0
    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.2012-01-10

1 Answers 1

1

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

$m_1=\frac{1+p_{1,2}a_2}{1-p_{1,1}-p_{1,2}b_2}$

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

  • 0
    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?2012-01-11