Equivalence relations and inference for sparse Markov models

Equivalence relations can be useful for statistical inference. This is demonstrated for modeling and statistical inference using sparse Markov models (SMMs). SMMs arise as a mapping of higher-order Markov models, based on the equivalence relation of conditioning histories having equal conditional probability distributions. After discussing advantages of SMMs for statistical modeling, we give two algorithms for their fitting, and highlight their use in modeling and classification applications. We also show through an application to alignment of DNA sequences that equivalence relations can greatly reduce the number of states of an auxiliary Markov chain used for computing the distribution of a pattern statistic, an important inference task for categorical time series.