# Markov chain getting stuck due to insufficient data samples

There is a lot of theory on Markov models and output generation out there, but I cannot locate any information on models getting stuck.

I'm trying to create a model of a data set using a Markov model. The data can look like this "abc abb acc baa bcc...", and I want to make an n-gram model. Accordingly, I sampled the data set at random, so I get a model like this (example of 2-gram model):

• abc abb -> acc with probability p1
• acc baa -> bcc with probability p2
• ...

The problem occurs when I try to generate an output from the model. Say I initialize the model like this:

• First: abc abb => acc, so the output is now "abc abb acc"
• Second (taking the last two words of the output): abb acc => ???

The model gets stuck, because the data set is not complete, and therefore does not cover every possible combination. When making the model, the sample "abb acc" was never reached, and thus the output cannot be determined. Is my sampling method wrong?

Just because you have never seen the sequence "abb acc abc" in your data set does not mean that it has probability 0. Indeed, in some sense, a probability of 0 is awfully unlikely (unless we have some prior knowledge); it is much more likely that the probability is $\epsilon$, for some small value of $\epsilon$.