Markov Chains - How to calculate prob. a state is visited at least N times? what about Expectation?

Question

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.

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.