I have a four-state, discrete time Markov process with time-dependent transition matrices such that after a given time T the matrices become constant. The idea is people in a program leaving the program in a variety of ways. Everyone starts in state 1, and states 2, 3 and 4 are absorbing, but state 4 represents the fairly small percentage of people who are 'lost in the system' - in other words state 4 represents our ignorance of what happens to people rather than a genuine outcome.

I would like to use lumping to put those in state 4 in with those in state 1 and run this as a three-state system, and compare this with the naive approach of running this as a four-state system then apportioning those who are asymptotically in state 4 into states 2 and 3 according to their relative proportions. (in other words, p_2/(p_2 + p_3) of those in state 4 go into state 2 after the system is run to infinite time and similar for state 3)

From some rough scribblings it doesn't seem that these two methods give the same results, so it would be good to get an idea on the error involved. To this end, here's my question:

Can I have pointers to the literature on lumping in Markov chains (or related) that would apply - even roughly - in this example? Or otherwise some words of advice on how to approach this.

  • $\begingroup$ I'm trying to imagine a situation that is matching your model. Maybe a physician checks their patients weekly to see if they are (1) still sick, (2) dead, (3) cured or (4) lost to follow-up. Are you trying to estimate the dead/cured ratio assuming that the transition probabilities of LFU patients are the same? $\endgroup$ – GaBorgulya Apr 3 '11 at 23:24
  • $\begingroup$ That's exactly analogous to my situation. It is about apprentices, who can be continuing, quit, completed or unknown outcome. $\endgroup$ – David Roberts Apr 4 '11 at 3:08

If the transition matrix was constant, then your two approaches would yield the same results. So this question is of interest in the non-constant case.

The inf-time redistribution of state 4 into state 2 and 3 is inappropriate. Consider that from time $1$ to time $T$ your matrix was $1 \rightarrow 1$ with probability $0.5$, $1 \rightarrow 2$ with probability $0.25$ and $1 \rightarrow 4$ with probability $0.25$, then after time $T$ your matrix was $1 \rightarrow 3$ with probability $1$. Clearly assuming state $4$ would distribute as the inf-time stable state would be weird in this case.

On the other hand, simple lumping state $1$ and $4$ together, would correspond to saying that loosing track of an apprentice at time-step $t$ is the same as assuming they remained in the program; also probably not what you want.

What you probably want to say is that "if we lost track of a student at time $t$ then that student had the same probability as any other student at time $t$ of continuing, quiting, or completing the program." To capture this, you can simply eliminate the transition to state 4 and re-normalize the resultant matrix (i.e. $p_{ij}' = \frac{p_{ij}}{1 - p_{14}}$) and proceed as usual.

| cite | improve this answer | |
  • $\begingroup$ That's pretty close. The problem is that students end up in state 4 at around the point at which the chain becomes time independent, and not too much before. I haven't looked at this problem in a while, and this has just occurred to me. $\endgroup$ – David Roberts Aug 19 '11 at 7:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.