# Number of hidden states and memory: a joint order estimation problem for Markov chains with Markov regime

Antoine Chambaz; Catherine Matias

ESAIM: Probability and Statistics (2009)

- Volume: 13, page 38-50
- ISSN: 1292-8100

## Access Full Article

top## Abstract

top## How to cite

topChambaz, Antoine, and Matias, Catherine. "Number of hidden states and memory: a joint order estimation problem for Markov chains with Markov regime." ESAIM: Probability and Statistics 13 (2009): 38-50. <http://eudml.org/doc/250627>.

@article{Chambaz2009,

abstract = {
This paper deals with order identification for Markov chains with Markov
regime (MCMR) in the context of finite alphabets. We define the joint order
of a MCMR process in terms of the number k of states of the hidden Markov
chain and the memory m of the conditional Markov chain. We study the
properties of penalized maximum likelihood estimators for the unknown order
(k, m) of an observed MCMR process, relying on information theoretic
arguments. The novelty of our work relies in the joint estimation of two
structural parameters. Furthermore, the different models in competition are
not nested. In an asymptotic framework, we prove that a penalized maximum
likelihood estimator is strongly consistent without prior bounds on k and
m. We complement our theoretical work with a simulation study of its
behaviour. We also study numerically the behaviour of the BIC criterion. A
theoretical proof of its consistency seems to us presently out of reach for
MCMR, as such a result does not yet exist in the simpler case where m = 0
(that is for hidden Markov models).
},

author = {Chambaz, Antoine, Matias, Catherine},

journal = {ESAIM: Probability and Statistics},

keywords = {Markov regime; order estimation; hidden states; conditional memory; hidden Markov model},

language = {eng},

month = {2},

pages = {38-50},

publisher = {EDP Sciences},

title = {Number of hidden states and memory: a joint order estimation problem for Markov chains with Markov regime},

url = {http://eudml.org/doc/250627},

volume = {13},

year = {2009},

}

TY - JOUR

AU - Chambaz, Antoine

AU - Matias, Catherine

TI - Number of hidden states and memory: a joint order estimation problem for Markov chains with Markov regime

JO - ESAIM: Probability and Statistics

DA - 2009/2//

PB - EDP Sciences

VL - 13

SP - 38

EP - 50

AB -
This paper deals with order identification for Markov chains with Markov
regime (MCMR) in the context of finite alphabets. We define the joint order
of a MCMR process in terms of the number k of states of the hidden Markov
chain and the memory m of the conditional Markov chain. We study the
properties of penalized maximum likelihood estimators for the unknown order
(k, m) of an observed MCMR process, relying on information theoretic
arguments. The novelty of our work relies in the joint estimation of two
structural parameters. Furthermore, the different models in competition are
not nested. In an asymptotic framework, we prove that a penalized maximum
likelihood estimator is strongly consistent without prior bounds on k and
m. We complement our theoretical work with a simulation study of its
behaviour. We also study numerically the behaviour of the BIC criterion. A
theoretical proof of its consistency seems to us presently out of reach for
MCMR, as such a result does not yet exist in the simpler case where m = 0
(that is for hidden Markov models).

LA - eng

KW - Markov regime; order estimation; hidden states; conditional memory; hidden Markov model

UR - http://eudml.org/doc/250627

ER -

## References

top- D. Blackwell and L. Koopmans, On the identifiability problem for functions of finite Markov chains. Ann. Math. Stat.28 (1957) 1011–1015. Zbl0080.34901
- S. Boucheron and E. Gassiat, Order estimation and model selection, in Inference in hidden Markov models, Olivier Cappé, Eric Moulines, and Tobias Rydén (Eds.), Springer Series in Statistics. New York, NY: Springer (2005). Zbl1065.62148
- R.J. Boys and D.A. Henderson, A Bayesian approach to DNA sequence segmentation. Biometrics60 (2004) 573–588. Zbl1274.62728
- O. Cappé, E. Moulines and T. Rydén (Eds.), Inference in hidden Markov models. Springer Series in Statistics (2005). Zbl1080.62065
- I. Csiszár and Z. Talata, Context tree estimation for not necessarily finite memory processes, via BIC and MDL. IEEE Trans. Info. Theory52 (2006) 1007–1016. Zbl1284.94027
- L.D. Davisson, R.J. McEliece, M.B. Pursley and M.S. Wallace, Efficient universal noiseless source codes. IEEE Trans. Inf. Theory27 (1981) 269–279. Zbl0458.94030
- A.P. Dempster, N.M. Laird and D.B. Rubin, Maximum likelihood from incomplete data via the EM algorithm. J. Roy. Stat. Soc. Ser. B39 (1977) 1–38. With discussion. Zbl0364.62022
- Y. Ephraim and N. Merhav, Hidden Markov processes. IEEE Trans. Inform. Theory, special issue in memory of Aaron D. Wyner48 (2002) 1518–1569. Zbl1061.94560
- L. Finesso, Consistent estimation of the order for Markov and hidden Markov chains. Ph.D. Thesis, University of Maryland, ISR, USA (1991).
- C-D. Fuh, Efficient likelihood estimation in state space models. Ann. Stat.34 (2006) 2026–2068. Zbl1246.62185
- E. Gassiat and S. Boucheron, Optimal error exponents in hidden Markov model order estimation. IEEE Trans. Info. Theory48 (2003) 964–980. Zbl1065.62148
- E.J. Hannan, The estimation of the order of an ARMA process. Ann. Stat.8 (1980) 1071–1081. Zbl0451.62068
- H. Ito, S.I. Amari and K. Kobayashi, Identifiability of hidden Markov information sources and their minimum degrees of freedom. IEEE Trans. Inf. Theory38 (1992) 324–333. Zbl0742.60041
- J.C. Kieffer, Strongly consistent code-based identification and order estimation for constrained finite-state model classes. IEEE Trans. Inf. Theory39 (1993) 893–902. Zbl0784.94005
- B.G. Leroux, Maximum-likelihood estimation for hidden Markov models. Stochastic Process. Appl.40 (1992) 127–143. Zbl0738.62081
- C.C. Liu and P. Narayan, Order estimation and sequential universal data compression of a hidden Markov source by the method of mixtures. IEEE Trans. Inf. Theory40 (1994) 1167–1180. Zbl0811.94022
- R.J. MacKay, Estimating the order of a hidden markov model. Canadian J. Stat.30 (2002) 573–589. Zbl1018.62062
- P. Nicolas, L. Bize, F. Muri, M. Hoebeke, F. Rodolphe, S.D. Ehrlich, B. Prum and P. Bessières, Mining bacillus subtilis chromosome heterogeneities using hidden Markov models. Nucleic Acids Res.30 (2002) 1418–1426.
- P. Nicolas, A.S. Tocquet and F. Muri-Majoube, SHOW User Manual. URL: (2004). Software available at URL: . URIhttp://www-mig.jouy.inra.fr/ssb/SHOW/show_doc.pdf
- B.M. Pötscher, Estimation of autoregressive moving-average order given an infinite number of models and approximation of spectral densities. J. Time Ser. Anal.11 (1990) 165–179. Zbl0703.62099
- C.P. Robert, T. Rydén and D.M. Titterington, Bayesian inference in hidden Markov models through the reversible jump Markov chain Monte Carlo method. J. R. Stat. Soc., Ser. B, Stat. Methodol.62 (2000) 57–75. Zbl0941.62090
- T. Rydén, Estimating the order of hidden Markov models. Statistics26 (1995) 345–354. Zbl0836.62057
- Y.M. Shtar'kov, Universal sequential coding of single messages. Probl. Inf. Trans.23 (1988) 175–186.

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.