# options for doing future state prediction for a state machine based on past state transitions

I want to predict future state sequence w.r.t. time of a state machine using information of past state transitions along the time axis. Take a state machine of 5 states 0,1,2,3,4 as an example, the past state transitions can look like below: The x-axis is time in some unit.

The current state has a large dependence on what the previous state is, but may have some dependence on earlier states as well.

An observable thing is that, for every state, the frequency distribution of lengths of time durations of stay in that state is very right-skewed. i.e. vast majority of staying times are much shorter than a small portion that is much longer.

I'm new to ML and I'm looking for approaches to this problem. Based on the nature of the problem and my observation, I think this can be modeled as a continuous time (hidden?) Markov Model, probably with Poisson distributed staying time for each state.

I have a few questions:

1. Is there a specific name for that kind of CT Markov Model, in which the time of stay in each state is Poisson distributed.
2. If there is, how do I train it and make future state predictions with it? Say I have state transition information of past 2 months and I want to predict state transitions for next 7 days. I'm confused on how to make future predictions with Markov Model in general. Just train the model and let it generate sequence from the last observation to use as future prediction?
3. Can I simply chop each time duration into equally small pieces and apply discrete Markov model on it? What's the essential difference between a CT Markov Model and DT Markov Model of very small state transition time steps?
4. Are there other reasonable models for this forecasting problem? I heard RNN.

Thanks a lot!

## 1 Answer

1. By looking at your plot, and because it is a Continuous Time Markov Model (CTMM) I think the holding time in each state is exponentially distributed. There is no specific name for it. It is probably the simplest case for a CTMM (simplest in the sense, that fitting the model and computing future states is more simple vs some other distribution).

2. For CTMM you still have many variants.
2.a. In the simplest case you can assume, there is a common distribution for holding time that does not depend on the state. You can just fit an exponential distribution to the holding times (exponential distribution has only one parameter: lambda). Then you also need to estimate transition probabilities of the Markov Chain. This is also easy, because you just need the count of state transitions for that (0->1; 1->0,1->2; 2->1,2->3; etc.) Let's call this the training/fitting of the MM. As a result you get the transition probability matrix.
2.b. The model becomes more complicated if you assume a different holding time distribution for each state.

3. Depending on the application/data/requirements you can work with discretized times. If within-day transitions are not important, or perhaps granularity of your data is just daily/hourly use a DTMM. One essential difference is that now you don't have to fit/calculate the holding time distribution only the state transition matrix (this time probability of 0->0; 1->1; 2->2 state transitions will be non zero). But now of course your state predictions are on a daily/hourly granularity.

4. Based on your description first I would go with a simple DTMM. No hidden states (DT HMM). You mention next state "may have some dependence on earlier states". This might be an indicator of hidden state, but I suggest to start with a simple model. RNNs are hidden state models, but require lot's of data, the model is a black box (as opposed to a MM, which is well interpretable).

• Predictions: Yes, after training the model you can just generate/simulate many sequences. Note, that since MM are stochastic models, predictions are not certain. In the simplest cases you can also analytically compute the probability of a certain state (or all states) at a specific time point. Or you can compute the probability of a certain state sequence. For these computations you just need the initial state and the transition probability matrix (which you estimated when you trained/fitted the model). More detailes here: Markov Chain Wikipedia Page
Check carefully what is the requirement. "Predicting future state sequence" can mean lots of things. Maybe you just need something very simple. Like "the probability, that state 4 will be reached within 7 days".