  We consider the problem of estimating the number of hidden states (the order)
of a nonparametric hidden Markov model (HMM). We propose two different methods
and prove their almost sure consistency without any prior assumption, be it on
the order or on the emission distributions. This is the first time a
consistency result is proved in such a general setting without using
restrictive assumptions such as a priori upper bounds on the order or
parametric restrictions on the emission distributions. Our main method relies
on the minimization of a penalized least squares criterion. In addition to the
consistency of the order estimation, we also prove that this method yields rate
minimax adaptive estimators of the parameters of the HMM - up to a logarithmic
factor. Our second method relies on estimating the rank of a matrix obtained
from the distribution of two consecutive observations. Finally, numerical
experiments are used to compare both methods and study their ability to select
the right order in several situations.
