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

Chambaz, Antoine; Matias, Catherine

doi:10.1051/ps:2007048

Chambaz, Antoine ; Matias, Catherine

ESAIM: Probability and Statistics, Tome 13 (2009), pp. 38-50.

Résumé

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).

DOI : 10.1051/ps:2007048

Classification : 62B10, 62B15, 62M07
Mots-clés : Markov regime, order estimation, hidden states, conditional memory, hidden Markov model

@article{PS_2009__13__38_0,
     author = {Chambaz, Antoine and Matias, Catherine},
     title = {Number of hidden states and memory : a joint order estimation problem for {Markov} chains with {Markov} regime},
     journal = {ESAIM: Probability and Statistics},
     pages = {38--50},
     publisher = {EDP-Sciences},
     volume = {13},
     year = {2009},
     doi = {10.1051/ps:2007048},
     mrnumber = {2493854},
     language = {en},
     url = {https://www.numdam.org/articles/10.1051/ps:2007048/}
}

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
PY  - 2009
SP  - 38
EP  - 50
VL  - 13
PB  - EDP-Sciences
UR  - https://www.numdam.org/articles/10.1051/ps:2007048/
DO  - 10.1051/ps:2007048
LA  - en
ID  - PS_2009__13__38_0
ER  -

%0 Journal Article
%A Chambaz, Antoine
%A Matias, Catherine
%T Number of hidden states and memory : a joint order estimation problem for Markov chains with Markov regime
%J ESAIM: Probability and Statistics
%D 2009
%P 38-50
%V 13
%I EDP-Sciences
%U https://www.numdam.org/articles/10.1051/ps:2007048/
%R 10.1051/ps:2007048
%G en
%F PS_2009__13__38_0

Chambaz, Antoine; Matias, Catherine. Number of hidden states and memory : a joint order estimation problem for Markov chains with Markov regime. ESAIM: Probability and Statistics, Tome 13 (2009), pp. 38-50. doi : 10.1051/ps:2007048. https://www.numdam.org/articles/10.1051/ps:2007048/

Bibliographie
Cité par

[1] D. Blackwell and L. Koopmans, On the identifiability problem for functions of finite Markov chains. Ann. Math. Stat. 28 (1957) 1011-1015. | MR | Zbl

[2] 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). | MR

[3] R.J. Boys and D.A. Henderson, A Bayesian approach to DNA sequence segmentation. Biometrics 60 (2004) 573-588. | MR

[4] O. Cappé, E. Moulines and T. Rydén (Eds.), Inference in hidden Markov models. Springer Series in Statistics (2005). | MR | Zbl

[5] I. Csiszár and Z. Talata, Context tree estimation for not necessarily finite memory processes, via BIC and MDL. IEEE Trans. Info. Theory 52 (2006) 1007-1016. | MR

[6] L.D. Davisson, R.J. Mceliece, M.B. Pursley and M.S. Wallace, Efficient universal noiseless source codes. IEEE Trans. Inf. Theory 27 (1981) 269-279. | MR | Zbl

[7] A.P. Dempster, N.M. Laird and D.B. Rubin, Maximum likelihood from incomplete data via the EM algorithm. J. Roy. Stat. Soc. Ser. B 39 (1977) 1-38. With discussion. | MR | Zbl

[8] Y. Ephraim and N. Merhav, Hidden Markov processes. IEEE Trans. Inform. Theory, special issue in memory of Aaron D. Wyner 48 (2002) 1518-1569. | MR | Zbl

[9] L. Finesso, Consistent estimation of the order for Markov and hidden Markov chains. Ph.D. Thesis, University of Maryland, ISR, USA (1991).

[10] C-D. Fuh, Efficient likelihood estimation in state space models. Ann. Stat. 34 (2006) 2026-2068. | MR

[11] E. Gassiat and S. Boucheron, Optimal error exponents in hidden Markov model order estimation. IEEE Trans. Info. Theory 48 (2003) 964-980. | MR | Zbl

[12] E.J. Hannan, The estimation of the order of an ARMA process. Ann. Stat. 8 (1980) 1071-1081. | MR | Zbl

[13] H. Ito, S.I. Amari and K. Kobayashi, Identifiability of hidden Markov information sources and their minimum degrees of freedom. IEEE Trans. Inf. Theory 38 (1992) 324-333. | MR | Zbl

[14] J.C. Kieffer, Strongly consistent code-based identification and order estimation for constrained finite-state model classes. IEEE Trans. Inf. Theory 39 (1993) 893-902. | MR | Zbl

[15] B.G. Leroux, Maximum-likelihood estimation for hidden Markov models. Stochastic Process. Appl. 40 (1992) 127-143. | MR | Zbl

[16] 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. Theory 40 (1994) 1167-1180. | Zbl

[17] R.J. Mackay, Estimating the order of a hidden markov model. Canadian J. Stat. 30 (2002) 573-589. | MR | Zbl

[18] 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.

[19] P. Nicolas, A.S. Tocquet and F. Muri-Majoube, SHOW User Manual. URL: http://www-mig.jouy.inra.fr/ssb/SHOW/show_doc.pdf (2004). Software available at URL: http://www-mig.jouy.inra.fr/ssb/SHOW/.

[20] 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. | MR | Zbl

[21] 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. | MR | Zbl

[22] T. Rydén, Estimating the order of hidden Markov models. Statistics 26 (1995) 345-354. | MR | Zbl

[23] Y.M. Shtar'Kov, Universal sequential coding of single messages. Probl. Inf. Trans. 23 (1988) 175-186. | Zbl

Cité par Sources :