[Math] Use Discrete Markov Chain to predict n steps ahead

markov chains

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.

Best Answer

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$.

Related Question