Can a 1st Order Model capture information that a 2nd Order model can't? Let's say we have some sequence $y_1 \ldots y_n$. By definition, a 2nd order Markov model can capture more information from the sequence than a first or zeroth order Markov model. What I'm interested in, however, is if the first order model can capture some information that the second order model can't.
The reason I ask is the following. I have a procedure where, given a sequence with certain annotations, I learn a second order model from that sequence and use it to make predictions. These predictions are then used as input to the same procedure, and the process continues until the predictions don't change.
It turns out, however, that if I first do the above process using a first order model for several iterations, then use that output as an input for the same process with a second order model, I get even better results.
If I also add a zeroth order model before that, I get even better results.
My intuition tells me that the lower order models somehow filter out noise (i.e. false correlations that the second order model might capture), but I can't seem to find a good reason as to why this would happen.
Any suggestions? To those interested, the specific application is gene-start prediction.
 A: This is a typical overfitting situation. Your 2nd order class model contains the 1st order model, so in theory it should do better, but due to the finiteness of your training data, you are getting 'noisy' parameters that should have been zeros. This happens all the time, and the usual solution is to regularize the model (unless you are already doing so).
A: The answer will be clearer if we address the two parts of your question separately.
The first is whether a first order model is capable of capturing information that a second order model cannot. The answer to this is, demonstrably, no, since we can write any first order model as a (degenerate) second order model.
The second, somewhat subtler issue is about performance of an estimated model. The more complex a model, the more noise will affect the estimates. Indeed, even a simpler, wrong, model* can outperform a more complex, correct model. For example parameter estimates of a simpler model may have substantially lower variance, which may be more than enough to overcome the greater bias (i.e. there's a bias-variance tradeoff). This would mean that in (say) mean-square-error terms, a simple model can outperform a complex one, even though the complex one subsumes the simple one within it.
* (even one known a priori to be wrong may nevertheless be a better choice, from a prediction point of view) 
