An EM algorithm for estimation in the mixture transition distribution model

Abstract

The mixture transition distribution (MTD) model was introduced by Raftery to face the need for parsimony in the modeling of high-order Markov chains in discrete time. The particularity of this model comes from the fact that the effect of each lag upon the present is considered separately and additively, so that the number of parameters required is drastically reduced. However, the efficiency for the MTD parameter estimations proposed up to date still remains problematic on account of the large number of constraints on the parameters. In this article, an iterative procedure, commonly known as expectation–maximization (EM) algorithm, is developed cooperating with the principle of maximum likelihood estimation (MLE) to estimate the MTD parameters. Some applications of modeling MTD show the proposed EM algorithm is easier to be used than the algorithm developed by Berchtold. Moreover, the EM estimations of parameters for high-order MTD models led on DNA sequences outperform the corresponding fully parametrized Markov chain in terms of Bayesian information criterion. A software implementation of our algorithm is available in the library seq++at http://stat.genopole.cnrs.fr/seqpp.

Keywords:

• Markov chain
• Mixture transition distribution (MTD)
• Parsimony
• Maximum likelihood
• EM algorithm

Acknowledgements

We thank Bernard Prum and Catherine Matias for their very constructive suggestions, and Vincent Miele for his implementation of the EM algorithm in the seq++ library. Moreover, we thank the referees for their comments and suggestions which improve this article.