# What can I do with NA values in my second-order Markov chain?

I have states A, B, C, I have developed both a 1st and 2nd Order Markov Chain for them.

Each state represents a status that an individual can be in, and the transitions represents the probability of them moving to a different status in the next 3 months (the problem explained below is also the same when I look at a 6 month window).

When developing my 2nd-order, the transition probability BA is 0: ($P(x_t = A | x_{t-1} = B) = 0$)

So it looks something like this:

  A     B     C
A p11   p12   p13
B 0     p22   p23
C p31   p32   p33


Consequently, transition probabilities BAA, BAB, BAC for the 2nd-order chain all end up giving me NA values since I am dividing 0 by 0; since nobody moves from status B to A at the first time step, logically nobody moves from status A to anywhere else in the second time step (given that they started in status B).

The second order looks something like this:

   A     B     C
AA p11   p12   p13
AB p21   p22   p23
AC p31   p32   p33
BA NA    NA    NA
BB p51   p52   p53
BC p61   p62   p63
CA p71   p72   p73
CB p81   p82   p83
CC p91   p92   p93


So what do I do with these NA values? Do I replace them with the transition probabilities from the 1st-order? Do I replace them with 0?

Note: p11 is a probability.

• +1 It comes down to finding estimators of probabilities for which there are no data. The only objective and generally defensible ways I know of making such estimates take into account the purpose of your investigation and the consequences of deriving erroneous results. Perhaps if you could share such contextual information it might help people formulate focused, useful answers. – whuber May 24 '16 at 16:20
• In general you should have enough data to try a more complex model, i.e., second order Markov Model. If not, may be the first order Markov model is sufficient enough. Why do you want to try 2nd order model? Does that overfitting? – Haitao Du May 25 '16 at 15:11
• @whuber Thanks for your feedback, I have now made some edits and given more context. But to do with what you said, I don't really know how to find these estimators; how would I calculate them? Or what methodology would I have to use? – EhsanF May 25 '16 at 15:14
• @hxd1011 I have looked at both first-order and second-order and doing a chi-square test of assiciation (and making the assumption that the NA values were 0) I found that I was in a second-order rather than first. Sadly, the status the individual goes to next depends on the past two statuses. – EhsanF May 25 '16 at 15:16

In real world you do not want to set the probability for unseen event to be 0, because you could see very unlikely events in the future. One way is trying set all possible outcomes with a very small value and such idea can be interpreted as "incorporating the zero order model".

please check Variable length makrov model, page 3, with p order 0. The final prediction combines all the orders and order 0 will make sure unseen events will not have 0 probability.

• Thank you very much, I am pretty sure this is the solution to my problem, I have to get down to reading it properly now! – EhsanF May 26 '16 at 9:32
• So this explains quite a bit, but here is my current problem with it, my data is time series but I have 1000 individuals in my data. For example, let's say that with 3 statuses A, B and C, I have 16 time points (each point representing a month). In other words, I have 1000 rows and 16 columns. How can I use vlmc with this? Or more precisely, how can I input all of the data into vlmc? Keeping in mind that I am making a prediction on individual level. Thanks. – EhsanF May 26 '16 at 15:48
• Picking a model for your data or tell you exactly what to do is always hard. Hopefully I convey the idea and intuition of how to deal with the 0 probability. But have limited ability to help you this comment. Good luck... – Haitao Du May 26 '16 at 16:10
• Yes, I completely agree; sadly this is the reality of life. Thank you very much for your help anyway! :) – EhsanF May 27 '16 at 8:29