# 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$? – Ilmari Karonen Mar 22 '12 at 3:12
Hi, thank you for the response. – Gustavo Mar 22 '12 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? – Ilmari Karonen Mar 22 '12 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. – Gustavo Mar 22 '12 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}$$ – Gustavo Mar 22 '12 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? – Gustavo Mar 22 '12 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. – Ilmari Karonen Mar 22 '12 at 20:39