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?


1 Answer 1


You'll probably need to do some kind of Bayesian smoothing on the probabilities in the transition matrix that you build, based upon the data.

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

You might want to read about Laplace smoothing, Good-Turing smoothing, Kneser-Ney smoothing, and similar topics. You are more likely to get good answers on the Statistics sister site.

  • $\begingroup$ Thanks for the response. Of course the entire space of combinations cannot be explored - and especially not for larger n-grams, so the smoothing function is a good idea. I'll look at the smoothing theory for more info, and ask the question in the stats forum. Thanks $\endgroup$
    – rasole
    May 28, 2013 at 16:35
  • $\begingroup$ @rasole, glad it helped. One request: rather than re-posting your question on the Statistics site, please click the "flag" button to ask the moderators to migrate your question to Statistics. Cross-posting the same question on multiple StackExchange sites is frowned upon. $\endgroup$
    – D.W.
    May 28, 2013 at 16:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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