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

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.

• 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. Apr 15, 2014 at 15:07

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.