Computational methods for discrete hidden semi-Markov chains

We propose a computational approach for implementing discrete hidden semi-Markov chains. A discrete hidden semi-Markov chain is composed of a non-observable or hidden process which is a finite semi-Markov chain and a discrete observable process. Hidden semi-Markov chains possess both the flexibility of hidden Markov chains for approximating complex probability distributions and the flexibility of semi-Markov chains for representing temporal structures. Efficient algorithms for computing characteristic distributions organized according to the intensity, interval and counting points of view are-described. The proposed computational approach in conjunction with statistical inference algorithms previously proposed makes discrete hidden semi-Markov chains a powerful model for the analysis of samples of non-stationary discrete sequences. Copyright (C) 1999 John Wiley & Sons, Ltd.