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.

In Markov chains, if I was given a transition probability matrix with each of the probabilities specified, then how do I determine the following:

1- Probability that state y is visited at least n times given that you start in state x. I know that I can solve it using $P_x$(# of visits to state y $\ge$ n) = $\rho_{xy} (\rho_{yy})^{n-1}$ where $\rho_{xy}$ is the probability that starting at state x, I will be in state y in some positive time (i.e. $\rho_{xy} = P_x(T_y< \infty ) $). But I am not sure how to calculate $\rho_{xy}$ and I have spent so much time trying to figure it out!

2- Expected number of visits to state y starting from state x. Again, I know that we can use $E_x$(# of visits to state y) = $\rho_{xy}/(1-\rho_{yy})$. But I have the same problem trying to figure out how to calculate the $\rho$ values.

Any help would be appreciated, and you could use the following transition prob. matrix to illustrate your method if necessary: $$ \begin{bmatrix} 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 \\ 0.2 & 0 & 0.7 & 0.1 & 0 & 0 \\ 0 & 0.2 & 0.1 & 0.7 & 0 & 0 \\ 0 & 0 & 0.2 & 0 & 0.7 & 0.1 \\ 0 & 0 & 0 & 0.2 & 0.1 & 0.7 \\ \end{bmatrix} $$

Thanks.

share|improve this question
    
To calculate $\rho_{xy}$ you could make $y$ an absorbing state in a markov chain with an modified transition matrix. Calculate the probability that the new markov chain gets absorbed in $y$ (since it can either do that or get absorbed in your other absorbing states that the originar markov chain had). You can do this calculation by seeking the steady state distribution of the modified matrix. –  Kai Sikorski Apr 15 at 15:07

1 Answer 1

Here is an answer to your question 2.

Let $P$ be your transition matrix in canonical form.

Then $$P = \left(\begin{array}{ccc} J & | & O \\ \hline R & | & Q \end{array} \right)$$ where $J$ is an identity matrix, and $O$ is a matrix of zeros.
Let $$ N = (I-Q)^{-1}.$$ Then the $ij$-th entry of $N$ is the expected number of times that the chain will be in state $j$ after starting in state $i$.

The matrix you give as an example is already in canonical form, with $$ Q = \left( \begin{array}{cccc} 0.7 & 0.1 & 0 & 0 \\ 0.1 & 0.7 & 0 & 0 \\ 0.2 & 0 & 0.7 & 0.1 \\ 0 & 0.2 & 0.1 & 0.7 \\ \end{array}\right)$$ and $N=(I-Q)^{-1}=$ $$ \left( \begin{array}{cccc} 3.75 & 1.25 & 0 & 0 \\ 1.25 & 3.75 & 0 & 0 \\ 3.125 & 1.875 & 3.75 & 1.25 \\ 1.875 & 3.125 & 1.25 & 3.75 \end{array}\right) $$ For example, the chain will be in state 2 (i.e., the second non-absorbing state) 1.875 times on average after starting in state 3.

share|improve this answer

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.