Markov Chain Prediction with unknown states

down vote favorite

I want to make a prediction of the next state based on a training and test dataset. So I split my data into a train and test set and calculate the MLE on the train set and want to predict the next state on the test dataset.

The problem now is, that there can be states in the test set, that never have been learned via the train set. How would I cope with that?

A similar problem occurs, if I have a similar train/test setup, and want to calculate the log-likelihood on the test dataset, with states never occuring in the train set.

Hope someone can help me out with that!

Regards, Philipp