# Use Discrete Markov Chain to predict n steps ahead

I modeled a Markov Chain with M states. Assuming that the process is homogeneous in time. But, each state has a differente resident time. Moreover, each state has a self-loop transition and a transition to other state. I assume that transition happens in one second. Then, I have built the transition matriz by count processes. In the transition matrix, the probability to keep in the same state is 98%. Using the steady state probabilities formula $\pi^{n} = \pi P^{n}$, I try to find what will be the probability to be in the next state for N steps ahead.

• Why is that a problem? What do you get if you just let $\pi=e_k$ (where $k$ is the current state and $e_k$ is a vector with $1$ at index $k$ and the other elements $0$) and calculate $\pi P^n$? Commented Mar 22, 2012 at 3:12
• Hi, thank you for the response. Commented Mar 22, 2012 at 9:16
• Yes, with a $0.98$ probability of staying in the same state, it takes about 35 steps for the process to have a greater than $0.5$ chance of moving anywhere. So? Commented Mar 22, 2012 at 16:10

I suspect the confusion may be in what you mean by "step" in the phrase "$N$ steps ahead".

If you mean the one-second time step of your discrete time Markov process, then what you're calculating is exactly correct — with a $0.98$ self-loop transition probability, the process has a less than $0.5$ probability of moving anywhere within $N < 35$ steps.

If, however, by "step" you mean a transition in which the process does not stay in the same state, then you need to eliminate the self-loop transitions from your matrix (since you don't count them as steps) by setting their probability to $0$ and normalizing the remaining transition probabilities for each state so that they again sum to $1$.

Of course, what you lose by doing so is the information about the residence time in each state. If you wanted to know where the process will be after $N$ non-self-loop steps and how long it'll take to get there, that would require a rather more complicated calculation, and the resulting discrete phase-type distribution would, in general, be unlikely to have a simple form (although it might be possible to approximate it with some nicer distributions).

In the comments, you write that your transition matrix is (approximately) $$P=\pmatrix{0.99&0.0208&0&0\\0.0019&0.9792&0.0104&0\\0&0&0.9896&0.0108\\0‌​.0028&0&0&0.9907}$$ and that "second option it is what I'm looking for", i.e. that you want to calculate the probability distribution after $N$ steps, a step denoting a transition between two distinct states. If so, what you need to do is to calculate another stochastic matrix $P'$ which describes the same process, but which does not include the self-loop transitions (i.e. whose diagonal entries are zero).

To obtain $P'$ from $P$, simply zero out the diagonal entries and re-normalize each row so that the matrix stays stochastic (i.e. so that each row sums to $1$). Since most of the rows in $P$ only have one non-zero off-diagonal element to begin with, that element becomes $1$, leaving row 2 as the only non-trivial case: $$P' = \pmatrix{0&1&0&0\\0.1545&0&0.8455&0\\0&0&0&1\\1&0&0&0}$$ From this, you can calculate the state distribution $\pi_n = \pi P'^n$ after $n$ steps, given a starting distribution $\pi$.

However, note that, whereas the original transition matrix $P$ was ergodic, $P'$ isn't — in particular, a process in an even-numbered state always ends up in an odd-numbered state after one step and vice versa, so all states have an even period. This lack of ergodicity doesn't really affect the calculation of $\pi_n$ as such, but it does mean e.g. that $\pi_n$ won't generally converge to a stationary distribution as $n \to \infty$.

• Ok, thank for the clarify. The second option it is what I'm looking for. I need to know when the states will be reached, so with the first option (self-loop) this is not possible? If is not possible I need to migrate my model to semi-markov approach? By the way, the distribution of my process is a unkown distribution, so it is specific for this scenario. Commented Mar 22, 2012 at 17:48
• My transition matrix is like this: $$P=\pmatrix{0.99&;0.0208&;0&;0\\0.0019&;0.9792&;0.0104&;0\\0&;0&;0.9896&;0.0108\\0.0028&;0&;0&;0.9907}$$ Commented Mar 22, 2012 at 17:55
• Ok, thank you again. But for use the second P' do I need to know the resident time in each state in order to guess correctly the next state after N steps ahead? How can I proceed? Commented Mar 22, 2012 at 20:11
• If I'm understanding you correctly, and if you're understanding me correctly, then the answer to your first question is "no" (and the answer to the second is "just like I wrote above"). But that should be kind of obvious, so the fact that you're asking it makes me suspect that there's some kind of miscommunication somewhere. Commented Mar 22, 2012 at 20:39