Elisabeth Gassiat
email: elisabeth.gassiat@math.u-psud.fr

Judith Rousseau
email: rousseau@ceremade.dauphine.fr

About the posterior distribution in hidden Markov models with unknown number of states

Keywords: Hidden Markov models, number of components, order selection, Bayesian statistics, posterior distribution

On the asymptotic behaviour of the posterior distribution in hidden Markov Models with unknown number of states

Introduction

Finite state space hidden Markov models (which will be shortened to HMMs throughout the paper) are stochastic processes (X j , Y j ) j≥1 where (X j ) j≥1 is a Markov chain living in a finite state space X and conditionally on (X j ) j≥1 the Y j 's are independent with a distribution depending only on X j and living in Y. HMMs are useful tools to model time series where the observed phenomenon is driven by a latent Markov chain. They have been used successfully in a variety of applications, the books [START_REF] Macdonald | Hidden Markov and other models for discretevalued time series[END_REF], [START_REF] Macdonald | Hidden Markov models for time series: an introduction using R[END_REF] and [START_REF] Cappé | Hidden Markov Models[END_REF] provide several examples of applications of HMMs and give a recent (for the latter) state of the art in the statistical analysis of HMMs. Finite state space HMMs may also be seen as a dynamic extension of finite mixture models and may be used to do unsupervised clustering. The hidden states often have a practical interpretation in the modelling of the underlying phenomenon. It is thus of importance to be able to infer both the number of hidden states (which we call the order of the HMM) from the data, and the associated parameters.

The aim of this paper is to provide a frequentist asymptotic analysis of Bayesian methods used for statistical inference in finite state space HMMs when the order is unknown. Let us first review what is known on the subject and important questions that still stay unsolved.

In the frequentist literature, penalized likelihood methods have been proposed to estimate the order of a HMM, using for instance Bayesian information criteria (BIC for short). These methods were applied for instance in [START_REF] Leroux | Maximum-penalised-likelihood estimation for independent and Markov dependent mixture models[END_REF], [START_REF] Rydén | Stylized facts of daily return series and the hidden Markov model[END_REF], but without theoretical consistency results. Later, it has been observed that the likelihood ratio statistics is unbounded, in the very simple situation where one wants to test between 1 or 2 hidden states, see [START_REF] Gassiat | The likelihood ratio test for the number of components in a mixture with Markov regime[END_REF]. The question whether BIC penalized likelihood methods lead to consistent order estimation stayed open. Using tools borrowed from information theory, it has been possible to calibrate heavier penalties in maximum likelihood methods to obtain consistent estimators of the order, see [START_REF] Gassiat | Optimal error exponents in hidden Markov model order estimation[END_REF], [START_REF] Chambaz | A MDL approach to HMM with Poisson and Gaussian emissions. Application to order indentification[END_REF]. The use of penalized marginal pseudo likelihood was also proved to lead to weakly consistent estimators by [START_REF] Gassiat | Likelihood ratio inequalities with applications to various mixtures[END_REF].

On the Bayesian side, various methods were proposed to deal with an unknown number of hidden states, but no frequentist theoretical result exists for these methods. Notice though that, if the number of states is known, de [START_REF] De Gunst | Asymptotic behavior of Bayes estimators for hidden Markov models with application to ion channels[END_REF] obtain a Bernstein -von Mises theorem for the posterior distribution, under additional (but usual) regularity conditions. When the order is unknown, reversible jump methods have been built, leading to satisfactory results on simulation and real data, see [START_REF] Boys | A Bayesian approach to DNA sequence segmentation (with discussion)[END_REF], [START_REF] Green | Hidden Markov models and disease mapping[END_REF], [START_REF] Robert | Jump Markov chain Monte Carlo algorithms for Bayesian inference in hidden Markov models[END_REF], [START_REF] Spezia | Bayesian analysis of multivariate Gaussian hidden Markov models with an unknown number of regimes[END_REF]. The ideas of variational Bayesian methods were developed in [START_REF] Mcgrory | Variational bayesian analysis for hidden Markov models[END_REF]. Recently, one of the authors proposed a frequentist asymptotic analysis of the posterior distribution for overfitted mixtures when the observations are i.i.d., see [START_REF] Rousseau | Asymptotic behaviour of the posterior distribution in overfitted models[END_REF]. In this paper, it is proved that one may choose the prior in such a way that extra components are emptied, or in such a way that extra components merge with true ones. More precisely, if a Dirichlet prior D(α 1 , . . . , α k ) is considered on the k weights of the mixture components, small values of the α j 's imply that the posterior distribution will tend to empty the extra components of the mixture when the true distribution has a smaller number, say k 0 < k of true components. One aim of our paper is to understand if such an analysis may be extended to HMMs.

As is well known in the statistical analysis of overfitted finite mixtures, the difficulty of the problem comes from the non identifiability of the parameters. But what is specific to HMMs is that the non identifiability of the parameters leads to the fact that neighbourhoods of the "true" parameter values contain transition matrices arbitrarily close to imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013 non ergodic transition matrices. To understand this on a simple example, just consider the case of HMMs with two hidden states, say p is the probability of going from state 1 to state 2 and q the probability of going from state 2 to state 1. If the observations are in fact independently distributed, their distribution may be seen as a HMM with two hidden states where q = 1 -p. Neighbourhoods of the "true" values (p, 1 -p) contain parameters such that p is small or 1 -p is small, leading to hidden Markov chains having mixing coefficients very close to 1. Imposing a prior condition such as δ ≤ p ≤ 1 -δ for some δ > 0 is not satisfactory.

Our first main result Theorem 1 gives concentration rates for the posterior distribution of the marginal densities of a fixed number of consecutive observations. First, under mild assumptions on the densities and the prior, we obtain the asymptotic posterior concentration rate √ n, n the number of observations, up to a log n factor, when the loss function is the L 1 norm between densities multiplied by some function of the ergodicity coefficient of the hidden Markov chain. Then, with more stringent assumptions on the prior, we give posterior concentration rates for the marginal densities in L 1 norm only (without the ergodicity coefficient). For instance, consider a finite state space HMM, with k states and with independent Dirichlet prior distributions D(α 1 , . . . , α k ) on each row of the transition matrix of the latent Markov chain. Then our theorem says that if the sum of the parameters α j 's is large enough, the posterior distribution of the marginal densities in L 1 norm concentrates at a polynomial rate in n. These results are obtained as applications of a general theorem we prove about concentration rates for the posterior distribution of the marginal densities when the state space of the HMM is not constrained to be a finite set, see Theorem 4.

A byproduct of the non identifiability for overfitted mixtures or HMMs is the fact that, going back from marginal densities to the parameters is not easy. The local geometry of finite mixtures has been understood by [START_REF] Gassiat | The local geometry of finite mixtures[END_REF], and following their approach in the HMM context we can go back from the L 1 norm between densities to the parameters. We are then able to propose a Bayesian consistent estimator of the number of hidden states, see Theorem 2, under the same conditions on the prior as in Theorem 1. To our knowledge, this is the first consistency result on Bayesian order estimation in the case of HMMs.

Finally, obtaining posterior concentration rates for the parameters themselves seems to be very difficult, and we propose a more complete analysis in the simple situation of HMMs with 2 hidden states and independent observations. In such a case, we prove that, if all the parameters (not only the sum of them) of the prior Dirichlet distribution are large enough, then extra components merge with true ones, see Theorem 3. We believe this to be more general but have not been able to prove it.

The organization of the paper is the following. In section 2, we first set the model and notations. In subsequent subsections, we give Theorems 1, 2 and 3. In section 3, we give the posterior concentration theorem for general HMMs, Theorem 4, on which Theorem 1 is based. All proofs are given in section 4.

Finite state space hidden Markov models

Model and notations

Recall that finite state space HMMs model pairs (X i , Y i ) i≥1 where (X i ) i≥1 is the unobserved Markov chain living on a finite state space X = {1, • • • , k} and the observations (Y i ) i≥1 are conditionally independent given the (X i ) i≥1 . The observations take value in Y, which is assumed to be a Polish space endowed with its σ-field. Throughout the paper we denote x 1:n = (x 1 , . . . , x n ).

The hidden Markov chain (X i ) i≥1 has a Markov transition matrix Q = (q ij ) 1≤i,j≤k . The conditional distribution of Y i given X i has a density with respect to some given measure ν on Y. We denote by g γj (y), j = 1, . . . , k, the conditional density of Y i given X i = j. Here, γ j ∈ Γ ⊂ R d for j = 1, . . . , k, the γ j 's are called the emission parameters. In the following we parametrize the transition matrices on {1, . . . , k} as (q ij ) 1≤i≤k,1≤j≤k-1 (implying that q ik = 1-k-1 j=1 q ij for all i ≤ k) and we denote by ∆ k the set of probability mass functions ∆ k = {(u 1 , . . . , u k-1 ) :

u 1 ≥ 0, . . . , u k-1 ≥ 0, k-1 i=1 u i ≤ 1}.
We shall also use the set of positive probability mass functions ∆ 0 k = {(u 1 , . . . , u k-1 ) :

u 1 > 0, . . . , u k-1 > 0, k-1 i=1 u i < 1}
. Thus, we may denote the overall parameter by θ =

(q ij , 1 ≤ i ≤ k, 1 ≤ j ≤ k -1; γ 1 , . . . , γ k ) ∈ Θ k where Θ k = ∆ k k × Γ k . To alleviate notations we will write θ = (Q; γ 1 , . . . , γ k ), where Q = (q ij ) 1≤i,j≤k , q ik = 1 - k-1 j=1 q ij for all i ≤ k.
Throughout the paper ∇ θ h denotes the gradient vector of the function h when considered as a function of θ, and D i θ h its i-th derivative operator with respect to θ, for i ≥ 1. We denote by B d (γ, ) the d dimensional ball centered at γ with radius , when γ ∈ R d . The notation a n b n means that a n is larger than b n up to a positive constant that is fixed throughout.

Any Markov chain on a finite state space with transition matrix Q admits a stationary distribution which we denote by µ Q , if it admits more than one we choose one of them. Then for any finite state space Markov chain with transition matrix Q it is possible to define real numbers ρ Q ≥ 1 such that, for any integer m, any j ≤ k

k j=1 |(Q m ) ij -µ Q (j)| ≤ ρ -m Q , ρ Q =   1 - k j=1 min 1≤i≤k q ij   -1 (1)
where Q m is the m-step transition matrix of the Markov chain. If ρ Q > 1, the Markov chain (X n ) n≥1 is uniformly geometrically ergodic and µ Q is its unique stationary distribution. In the following we shall also denote µ θ and ρ θ in the place of µ Q and ρ Q when θ = (Q; γ 1 , . . . , γ k ). We write P θ for the probability distribution of the stationary HMM (X j , Y j ) j≥1 with imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013 parameter θ. That is, for any integer n, any set A in the Borel σ-field of X n × Y n :

P θ ((X 1 , . . . , X n , Y 1 , . . . , Y n ) ∈ A) = k x1,...,xn=1 Y n 1l A (x 1:n , y 1:n )µ Q (x 1 ) n-1 i=1 q xixi+1 n i=1 g γx i (y i ) ν(dy 1 ) . . . ν(dy n ). ( 2
)
Thus for any integer n, under P θ , Y 1:n = (Y 1 , . . . , Y n ) has a probability density with respect to ν(dy

1 ) • • • ν(dy n ) equal to f n,θ (y 1 , . . . , y n ) = k x1,...,xn=1 µ Q (x 1 ) n-1 i=1 q xixi+1 n i=1 g γx i (y i ) . (3)
We note E θ for the expectation under P θ . We denote Π k the prior distribution on Θ k . As is often the case in Bayesian analysis of HMMs, instead of computing the stationary distribution µ Q of the hidden Markov chain with transition matrix Q, we consider a probability distribution π X on the unobserved initial state X 0 . Denote n (θ, x 0 ) the log-likelihood starting from x 0 , for all x 0 ∈ {1, . . . , k}, we have

n (θ, x 0 ) = log k x1,...,xn=1 n-1 i=0 q xixi+1 n i=1 g γx i (y i ) .
The log-likelihood starting from a probability distribution π X on X is then given by log k x0=1 e n (θ,x0) π X (x 0 ) . This may also be interpreted as taking a prior Π = Π k ⊗ π X over Θ k × {1, . . . , k}. The posterior distribution can then be written as

P Π (A|Y 1:n ) = k x0=1 A e n(θ,x0) Π k (dθ) π X (x 0 ) k x0=1 Θ e n(θ,x0) Π k (dθ) π X (x 0 ) (4) for any Borel set A ⊂ Θ k .
Let M k be the set of all possible probability distributions P θ for all θ ∈ Θ k . We say that the HMM P θ has order k 0 if the probability distribution of (Y n ) n≥1 under P θ is in M k0 and not in M k for all k < k 0 . Notice that a HMM of order k 0 may be represented as a HMM of order k for any k > k 0 . Indeed, let Q 0 be a k 0 × k 0 transition matrix, and (γ 0 1 , ...., γ 0 k0 ) ∈ Γ k0 be parameters that define a HMM of order k 0 . Then, θ = (Q; γ 0 1 , ...., γ 0 k0 , . . . , γ 0 k0 ) ∈ Θ k with Q = (q ij , 1 ≤ i, j ≤ k) such that :

q ij = q 0 ij i, j < k 0 q ij = q 0 k0j i ≥ k 0 , j < k 0 , k l=k0 q il = q 0 ik0 i ≤ k 0 , and k l=k0 q il = q 0 k0k0 , i ≥ k 0 (5)
imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013

gives P θ = P θ0 . Indeed, let (X n ) n≥1 be a Markov chain on {1, . . . , k} with transition matrix Q. Let Z be the function from {1, . . . , k} to {1, . . . , k 0 } defined by

Z(x) = x if x ≤ k 0 and Z(x) = k 0 if x ≥ k 0 . Then (Z(X n )) n≥1 is a Markov chain on {1, . . . , k 0 } with transition matrix Q 0 .
2.2. Posterior convergence rates for the finite marginal densities

Let θ 0 = (Q 0 ; γ 0 1 , ...., γ 0 k0 ) ∈ Θ k0 , Q 0 = (q 0 ij ) 1≤i≤k0,1≤j≤k0
, be the parameter of a HMM of order k 0 ≤ k. We now assume that P θ0 is the distribution of the observations. In this section we fix an integer l and study the posterior distribution of the density of l consecutive observations, that is f l,θ , given by (3) with n = l. We study the posterior concentration rate around f l,θ0 in terms of the L 1 loss function, when P θ0 is possibly of order k 0 < k. In this case, Theorem 2.1 of de [START_REF] De Gunst | Asymptotic behavior of Bayes estimators for hidden Markov models with application to ion channels[END_REF] does not apply and there is no result in the literature about the frequentist asymptotic properties of the posterior distribution. The interesting and difficult feature of this case is that even though θ 0 is parameterized as an ergodic Markov chain Q 0 with k states and some identical emission parameters as described in (5), f l,θ0 can be approached by marginals f l,θ for which ρ θ is arbitrarily close to 1, which deteriorates the posterior concentration rate, see Theorem 1.

Let π(u 1 , . . . , u k-1 ) be a prior density with respect to the Lebesgue measure on ∆ k , and let ω(γ) be a prior density on Γ (with respect to the Lebesgue measure on R d ). We consider prior distributions such that the rows of the transitions matrix Q are independently distributed from π and independent of the component parameters γ i , i = 1, ..., k, which are independently distributed from ω. Hence the prior density of Π k (with respect to the Lebesgue measure) is equal to π k = π ⊗k ⊗ω ⊗k . We still denote by π X a probability on {1, . . . , k}, we assume that π X (x) > 0 for all x ∈ {1, . . . , k} and set Π = Π k ⊗ π X . We shall use the following assumptions. ∇ γ log g γ (y) 2 g γ (y) ν(dy) < +∞, sup

• A0 q 0 ij > 0, 1 ≤ i ≤ k 0 , 1 ≤ j ≤ k 0 • A1 The function γ → g γ (
γ ∈B d (γ, ) D 2 γ log g γ (y) 2 g γ (y) ν(dy) < +∞, sup γ ∈B d (γ, ) ∇ γ g γ (y) ∈ L 1 (ν) and sup γ ∈B d (γ, ) D 2 γ g γ (y) ∈ L 1 (ν) • A2 There exist a > 0 and b > 0 such that sup γ ≤n b ∇ γ g γ (y) dν(y) ≤ n a .
• A3 π is continuous and positive on ∆ 0 k , and there exists C, α 1 > 0, . . ., α k > 0 such that (Dirichlet type priors): and ω is continuous and positive on Γ and satisfies

∀(u 1 , . . . , u k-1 ) ∈ ∆ 0 k , u k = 1 - k-1 i=1 u i , 0 < π (u 1 , . . . , u k-1 ) ≤ Cu α1-1 1 • • • u α k -1 k imsart-
x ≥n b ω(x)dx = o(n -k(k-1+d)/2 ), (6)
with b defined in assumption A2.

We will alternatively replace A3 by

• A3bis π is continuous and positive on ∆ 0 k , and there exists C such that (exponential type priors):

∀(u 1 , . . . , u k-1 ) ∈ ∆ 0 k , u k = 1 - k-1 i=1 u i , 0 < π (u 1 , . . . , u k-1 ) ≤ C exp(-C/u 1 ) • • • exp(-C/u k )
and ω is continuous and positive on Γ and satisfies (6).

Theorem 1 Assume A0-A3. Then, there exists K large enough such that

P Π θ : f l,θ -f l,θ0 1 (ρ θ -1) ≥ K log n n Y 1:n = o P θ 0 (1) (7)
where

ρ θ = 1 - k j=1 inf 1≤i≤k q ij -1 . If moreover ᾱ := 1≤i≤k α i > k(k -1 + d), then P Π θ : f l,θ -f l,θ0 1 ≥ 2Kn -ᾱ-k(k-1+d) 2 ᾱ (log n) Y 1:n = o P θ 0 (1) . ( 8
)
If we replace A3 by A3bis, then there exists K large enough such that

P Π θ : f l,θ -f l,θ0 1 ≥ 2Kn -1/2 (log n) 3/2 Y 1:n = o P θ 0 (1) . ( 9
)
Theorem 1 is proved in Section 4.1 as a consequence of Theorem 4 stated in Section 3, which gives posterior concentration rates for general HMMs.

Assumption A0 is the usual ergodic condition on the finite state space Markov chain. Assumptions A1 and A2 are mild usual regularity conditions on the emission densities g γ and hold for instance for multidimensional Gaussian distributions, Poisson distributions, or any regular exponential families. Assumption A3 on the prior distribution of the transition matrix Q is satisfied for instance if each row of Q follows a Dirichlet distribution or a mixture of Dirichlet distributions, as used in [START_REF] Nur | Bayesian hidden Markov model for DNA sequence segmentation : A prior sensitivity analysis[END_REF], and assumption ( 6) is verified for densities ω that have at most polynomial tails.

The constraint on ᾱ = i α i or condition A3bis are used to ensure that (8) and (9) hold respectively. The posterior concentration result (7) implies that the posterior distribution might put non negligible mass on values of θ for which ρ θ -1 is small and f l,θ -f l,θ0 1 is not. These are parameter values associated to nearly non ergodic latent Markov chains. Since ρ θ -1 is small is equivalent to j min i q ij is small, the condition ᾱ > k(k -1 + d) prevents such pathological behaviour by ensuring that the prior mass of such sets is small enough. This condition is therefore of a different nature than [START_REF] Rousseau | Asymptotic behaviour of the posterior distribution in overfitted models[END_REF]'s condition on the prior, which characterizes the asymptotic behaviour of the posterior distribution on the parameter θ. In other words, their condition allows in (static) mixture models to go from a posterior concentration result on f l,θ to a posterior concentration result on θ whereas, here, the constraint on ᾱ is used to obtain a posterior concentration result on f l,θ . Going back from f l,θ -f l,θ0 1 to the parameters requires a deeper understanding of the geometry of finite HMMs, similar to the one developed in [START_REF] Gassiat | The local geometry of finite mixtures[END_REF]. This will be needed to estimate the order of the HMM in Section 2.3, and fully explored when k 0 = 1 and k = 2 in Section 2.4.

For general priors, we do not know whether the √ log n factor appearing in ( 7) could be replaced or not by any sequence tending to infinity. In the case where the α i 's are large enough (Dirichlet type priors), and when k 0 = 1 and k = 2, we obtain a concentration rate without the √ log n factor, see Lemma 2 in Section 3. To do so, we prove Lemma 3 in Section 3 for which we need to compute explicitely the stationary distribution and the predictive probabilities to obtain a precise control of the likelihood, for θ's such that P θ is near P θ0 , and to control local entropies of slices for θ's such that P θ is near P θ0 and where ρ θ -1 might be small. It is not clear to us that extending such computations to the general case is possible in a similar fashion. The log n terms appearing in ( 8) and ( 9) are consequences of the √ log n term appearing in (7).

Consistent Bayesian estimation of the number of states

To define a Bayesian estimator of the number of hidden states k 0 , we need to decide how many states have enough probability mass, and are such that their emission parameters are different enough. We will be able to do it under the assumptions of Theorem 1. Set w n = n -( ᾱ-k(k+d-1))/(2 ᾱ) log n if A3 holds and ᾱ > k(k + d -1), and set w n = n -1/2 (log n) 3/2 if instead A3bis holds. Let (u n ) n≥1 and (v n ) n≥1 be sequences of positive real numbers tending to 0 as n tends to infinity such that w n = o(u n v n ). As in [START_REF] Rousseau | Asymptotic behaviour of the posterior distribution in overfitted models[END_REF], in the case of a misspecified model with k 0 < k, f l,θ0 can be represented by merging components or by emptying extra components. For any θ ∈ Θ k , we thus define J (θ) as

J (θ) = {j : P θ (X 1 = j) ≥ u n } ,
i.e. J(θ) corresponds to the set of non empty components. To cluster the components that have similar emission parameters we define for all j ∈ J(θ)

A j (θ) = i ∈ J (θ) : γ j -γ i 2 ≤ v n .
and the clusters are defined by : for all j 1 , j 2 ∈ J(θ), j 1 and j 2 belong to the same cluster (noted j 1 ∼ j 2 ) if and only if there exist r > 1 and i 1 , . . . , i r ∈ J(θ) with i 1 = j 1 and imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013

i r = j 2 such that for all 1 ≤ l ≤ r -1 A i l (θ) ∩ A i l+1 (θ) = ∅.
We then define the effective order of the HMM at θ as the number L (θ) of different clusters, i.e. as the number of equivalent classes with respect to the equivalence relation ∼ defined above. By a good choice of u n and v n , we construct a consistent estimator of k 0 by considering either the posterior mode of L(θ) or its posterior median. This is presented in Theorem 2.

To prove that this gives a consistent estimator, we need an inequality that relates the L 1 distance between the l-marginals, f l,θ -f l,θ0 1 , to a distance between the parameter θ and parameters θ0 in Θ k such that f l, θ0 = f l,θ0 . Such an inequality will be proved in section 4.2, under the following structural assumption.

Let

T = {t = (t 1 , . . . , t k0 ) ∈ {1, . . . , k} k0 : t i < t i+1 , i = 0, . . . , k 0 -1}. If b is a vector, b T denotes its transpose. • A4 For any t = (t 1 , . . . , t k0 ) ∈ T , any (π i ) k-t k 0 i=1 ∈ (R + ) k-t k 0 (if t k0 < k), any (a i ) k0 i=1 , (c i ) k0 i=1 ∈ R k0 , (b i ) k0 i=1 ∈ (R d ) k0 , any z i,j ∈ R d , α i,j ∈ R, i = 1, . . . , k 0 , j = 1, . . . , t i -t i-1 , (with t 0 = 0), such that z i,j = 1, α i,j ≥ 0 and ti-ti-1 j=1 α i,j = 1, for any (γ i ) k-t k 0 i=1 which belong to Γ \ {γ 0 i , i = 1, . . . , k 0 }, k-t k 0 i=1 π i g γi + k0 i=1 a i g γ 0 i + b T i D 1 g γ 0 i + k0 i=1 c 2 i ti-ti-1 j=1 α i,j z T i,j D 2 g γ 0 i z i,j = 0, (10)
if and only if

a i = 0, b i = 0, c i = 0 ∀i = 1, . . . , k 0 , π i = 0 ∀i = 1, . . . , k -t k0 .
Assumption A4 is a weak identifiability condition for situations when k 0 < k. Notice that A4 is the same condition as in [START_REF] Rousseau | Asymptotic behaviour of the posterior distribution in overfitted models[END_REF], it is satisfied in particular for Poisson mixtures, location-scale Gaussian mixtures and any mixtures of regular exponential families.

The following theorem says that the posterior distribution of L (θ) concentrates on the true number k 0 of hidden states.

Theorem 2 Assume that assumptions A0-A2 and A4 are verified. If either of the following two situations holds

• Under assumption A3 (Dirichlet type prior), if ᾱ > k(k + d -1) and u n v n n ( ᾱ-k(k+d-1))/(2 ᾱ) log n → +∞ • Under assumption A3bis (exponential type prior), if u n v n n 1/2 /(log n) 3/2 → +∞, then P Π [ θ : L (θ) = k 0 |Y 1:n ] = o P θ 0 (1) . ( 11
)
imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013

If kn is either the mode or the median of the posterior distribution of L(θ), then

kn = k 0 + o P θ 0 (1) (12)
One of the advantages of using such an estimate of the order of the HMM, is that we do not need to consider a prior on k and use reversible-jump methods, see [START_REF] Richardson | On Bayesian analysis of mixtures with an unknown number of components (with discussion)[END_REF], which can be tricky to implement. In particular we can consider a two -stage procedure where kn is computed based on a model with k components where k is a reasonable upper bound on k 0 and then, fixing k = kn an empirical Bayes procedure is defined on (Q i,j , i, j ≤ kn , γ 1 , . . . γ kn ). On the event kn = k 0 , which has probability going to 1 under P θ0 the model is regular and using the Bernstein -von Mises theorem of de [START_REF] De Gunst | Asymptotic behavior of Bayes estimators for hidden Markov models with application to ion channels[END_REF], we obtain that with probability P θ0 going to 1, the posterior distribution of √ n(θ -θn ) converges in distribution to the centered Gaussian with variance V 0 , the inverse of Fisher information at parameter θ 0 , where θn is an efficient estimator of θ 0 when the order is known to be k 0 , and √ n( θn -θ 0 ) converges in distribution to the centered Gaussian with variance V 0 under P θ0 .

The main point in the proof of Theorem 2 is to prove an inequality that relates the L 1 distance between the l-marginals, to a distance between the parameters of the HMM. Under condition A4, we prove that there exists a constant c(θ 0 ) > 0 such that for any small enough positive ε,

f l,θ -f l,θ0 1 c(θ 0 ) ≥ 1≤j≤k:∀i, γj -γ 0 i >ε P θ (X 1 = j) + k0 i=1 |P θ (X 1 ∈ B(i)) -P θ0 (X 1 = i)| + k0 i=1   j∈B(i) P θ (X 1 = j) (γ j -γ 0 i ) + 1 2 j∈B(i) P θ (X 1 = j) γ j -γ 0 i 2   (13)
where

B(i) = {j : γ j -γ 0 i ≤ ε}.
The above lower bound essentially corresponds to a partition of {1, . . . , k} into k 0 + 1 groups, where the first k 0 groups correspond to the components that are close to true distinct components in the multivariate mixture and the last corresponds to components that are emptied. The first term on the right hand side controls the weights of the components that are emptied (group k 0 + 1), the second term controls the sum of the weights of the components belonging to the i-th group, for i = 1, . . . , k 0 (components merging with the true i-th component), the third term controls the distance between the mean value over the group i and the true value of the i-th component in the true mixture while the last term controls the distance between each parameter value in group i and the true value of the i-th component. A general inequality implying (13), obtained under a weaker condition, namely A4bis, holds and is stated and proved in Section 4.2.

As we have seen with Theorem 2, we can recover the true parameter θ 0 using a twostage procedure where first kn is estimated. However it is also of interest to understand better the behaviour of the posterior distribution in the first stage procedure and see if some behaviour similar to what was observed in [START_REF] Rousseau | Asymptotic behaviour of the posterior distribution in overfitted models[END_REF] holds imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013 in the case of HMMs. From Theorem 1, it appears that HMMs present an extra difficulty due to the fact that, when the order is overestimated, the neighbourhood of θ's such that P θ = P θ0 contains parameters leading to non ergodic HMMs. To have a more refined understanding of the posterior distribution we restrict our attention in Section 2.4 to the case where k = 2 and k 0 = 1 which is still non trivial, see also [START_REF] Gassiat | The likelihood ratio test for the number of components in a mixture with Markov regime[END_REF] for the description of pathological behaviours of the likelihood in such a case.

2.4.

Posterior concentration for the parameters: the case k 0 = 1 and k = 2

In this section we restrict our attention to the simpler case where k 0 = 1 and k = 2. In Theorem 3 below we prove that if a Dirichlet type prior is considered on the rows of the transition matrix with parameters α j 's that are large enough the posterior distribution concentrates on the configuration where the two components (states) are merged (γ 1 and γ 2 are close to one another). When k = 2, we can parameterize θ as θ = (p, q, γ 1 , γ 2 ), with 0 ≤ p ≤ 1, 0 ≤ q ≤ 1, so that

Q θ = 1 -p p q
1 -q , µ θ = q p + q , p p + q when p = 0 or q = 0. If p = 0 and q = 0, set µ θ = 1 2 , 1 2 for instance. Also, we may take

ρ θ -1 = (p + q) ∧ (2 -(p + q)) .
When k 0 = 1, the observations are i.i.d. with distribution g γ 0 dν, so that one may take θ 0 = (p, 1 -p, γ 0 , γ 0 ) for any 0 < p < 1, or θ 0 = (0, q, γ 0 , γ) for any 0 < q ≤ 1 and any γ, or θ 0 = (p, 0, γ, γ 0 ) for any 0 < p ≤ 1 and any γ. Also, for any x ∈ X , P θ0,x = P θ0 and n (θ, x)n (θ 0 , x 0 ) = n (θ, x)n (θ 0 , x).

We take independent Beta priors on (p, q) :

Π 2 (dp, dq) = C α,β p α-1 (1 -p) β-1 q α-1 (1 -q) β-1 1l 0<p<1 1l 0<q<1 dpdq,
thus satisfying A3. Then the following holds:

Theorem 3 Assume that assumptions A0-A2 together with assumption A4 are verified and consider the prior described above with ω(.) verifying A3. Assume moreover that for all x, γ → g γ (x) is four times continuously differentiable on Γ, and that for any γ ∈ Γ there exists > 0 such that for any i ≤ 4,

sup γ ∈B d (γ, ) D i γ g γ g γ (y) 4 g γ (y) ν(dy) < +∞. ( 14
)
Then, as soon as α > 3d/4 and β > 3d/4, for any sequence n tending to 0, imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013

P Π p p + q ≤ n or q p + q ≤ n |Y 1:n = o P θ 0 (1),
and for any sequence M n going to infinity,

P Π γ 1 -γ 0 + γ 2 -γ 0 ≤ M n n -1/4 |Y 1:n = 1 + o P θ 0 (1).
Theorem 3 says that the extra component cannot be emptied at rate n , where the sequence n can be chosen to converge to 0 as slowly as we want, so that asymptotically, under the posterior distribution neither p/(p+q) nor q/(p+p) are small, and the posterior distribution concentrates on the configuration where the components merge, with the emission parameters merging at rate n -1/4 . Similarly in [START_REF] Rousseau | Asymptotic behaviour of the posterior distribution in overfitted models[END_REF] the authors obtain that, for independent variables, under a Dirichlet D(α 1 , . . . , α k ) prior on the weights of the mixture and if min α i > d/2, the posterior distribution concentrates on configurations which do not empty the extra-components but merge them to true components. The threshold here is 3d/2 instead of d/2. This is due to the fact that there are more parameters involved in a HMM model associated to k states than in a kcomponents mixture model. No result is obtained here in the case where the α i 's are small. This is due to the existence of non ergodic P θ in the vicinity of P θ0 that are not penalized by the prior in such cases. Our conclusion is thus to favour large values of the α i 's.

A general theorem

In this section, we present a general theorem which is used to prove Theorem 1 but which can be of interest in more general HMMs. We assume here that the unobserved Markov chain (X i ) i≥1 lives in a Polish space X and the observations (Y i ) i≥1 are conditionally independent given (X i ) i≥1 and live in a Polish space Y. X , Y are endowed with their Borel σ-fields. We denote by θ ∈ Θ, where Θ is a subset of an Euclidian space, the parameter describing the distribution of the HMM, so that Q θ , θ ∈ Θ is the Markov kernel of (X i ) i≥1 and the conditional distribution of Y i given X i has density with respect to some given measure ν on Y denoted by g θ (y|x), x ∈ X , θ ∈ Θ. We assume that the Markov kernels Q θ admit a (not necessarily unique) stationary distribution µ θ , for each θ ∈ Θ. We still write P θ for the probability distribution of the stationary HMM (X j , Y j ) j≥1 with parameter θ. That is, for any integer n, any set A in the Borel σ-field of X n × Y n :

P θ ((X 1 , . . . , X n , Y 1 , . . . , Y n ) ∈ A) = A µ θ (dx 1 ) n-1 i=1 Q θ (x i , dx i+1 ) n i=1 g θ (y i |x i ) ν(dy 1 ) . . . ν(dy n ). ( 15
)
imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013

Thus for any integer n, under P θ , Y 1:n = (Y 1 , . . . , Y n ) has a probability density with respect to ν(dy 1 )

• • • ν(dy n ) equal to f n,θ (y 1 , . . . , y n ) = X n µ θ (dx 1 ) n-1 i=1 Q θ (x i , dx i+1 ) n i=1 g θ (y i |x i ) . ( 16
)
We denote by Π Θ the prior distribution on Θ and by π X the prior probability on the unobserved initial state, which might be different from the stationary distribution µ θ .

We set Π = Π Θ ⊗ π X . Similarly to before denote n (θ, x) the log-likelihood starting from x, for all x ∈ X .

We assume that we are given a stationary HMM (X j , Y j ) j≥1 with distribution P θ0 for some θ 0 ∈ Θ.

For any θ ∈ Θ, it is possible to define real numbers ρ θ ≥ 1 and 0 < R θ ≤ 2 such that, for any integer m, any x ∈ X

Q m θ (x, .) -µ θ T V ≤ R θ ρ -m θ ( 17
)
where • T V is the total variation norm. If it is possible to set ρ θ > 1, the Markov chain (X n ) n≥1 is uniformly ergodic and µ θ is its unique stationary distribution. The following theorem provides a posterior concentration result in a general HMM setting, be it parametric or nonparametric and is an adaptation of [START_REF] Ghosal | Convergence rates of posterior distributions for non iid observations[END_REF] to the setup of HMMs. We present the assumptions needed to derive the posterior concentration rate.

• C1 There exists A > 0 such that for any (x 0 , x 1 ) ∈ X 2 , P θ0 almost surely, ∀n ∈ N, | n (θ 0 , x 0 )n (θ 0 , x 1 )| ≤ A, and there exist S n ⊂ Θ × X , C n > 0 and ˜ n > 0 a sequence going to 0 with n˜ 2 n → +∞ such that sup (θ,x)∈Sn

P θ0 n (θ, x) -n (θ 0 , x 0 ) ≤ -n˜ 2 n = o(1), Π[S n ] e -Cnn˜ 2 n • C2 There exists a sequence (F n ) n≥1 of subsets of Θ Π Θ (F c n ) = o(e -n˜ 2 n (1+Cn) )
• C3 There exists a sequence n ≥ ˜ n going to 0, such that (n˜

2 n (1 + C n ))/(n 2 n ) goes to 0 and N n 12 , F n , d l (., .) ≤ e n 2 n (ρ θ 0 -1) 2 16l(2R θ 0 +ρ θ 0 -1) 2
where N (δ, F n , d l (., .)) is the smallest number of θ j ∈ F n such that for all θ ∈ F n there exists a θ j with d l (θ j , θ) ≤ δ.

Here

d l (θ, θ j ) = f l,θ -f l,θj 1 := Y l |f l,θ -f l,θj |(y)dν ⊗l (y). • C3bis There exists a sequence n ≥ ˜ n going to 0 such that m≥1 Π Θ (A n,m ( n )) Π (S n ) e -nm 2 2 n 32l = o(e -n˜ 2 n )
imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013

and

N m n 12 , A n,m ( n ) , d l (., .) ≤ e nm 2 2 n (ρ θ 0 -1) 2 16l(2R θ 0 +ρ θ 0 -1) 2 .
where

A n,m ( ) = F n ∩ θ : m ≤ f l,θ -f l,θ0 1 ρ θ -1 2R θ + ρ θ -1 ≤ (m + 1) .
Theorem 4 Assume that ρ θ0 > 1 and that assumptions C1-C2 are satisfied, together with either assumption C3 or C3bis. Then

P Π θ : f l,θ -f l,θ0 1 ρ θ -1 2R θ + ρ θ -1 ≥ n |Y 1:n = o P θ 0 (1) .
Theorem 4 gives the posterior concentration rate of f l,θ -f l,θ0 1 up to the parameter

ρ θ -1
2R θ +ρ θ -1 . In [START_REF] Ghosal | Convergence rates of posterior distributions for non iid observations[END_REF], for models of non independent variables, the authors consider a parameter space where the mixing coefficient term (for us ρ θ -1) is uniformly bounded from below by a positive constant over Θ (see their assumption (4.1) for the application to Markov chains or their assumption on F in Theorem 7 for the application to Gaussian time series), or equivalently they consider a prior whose support in Θ is included in a set where ρ θ -1 2R θ +ρ θ -1 is uniformly bounded from below, so that their posterior concentration rate is directly expressed in terms of f l,θ -f l,θ0 1 . Since we do not restrict ourselves to such frameworks the penalty term ρ θ -1 is incorporated in our result. However Theorem 4 is proved along the same lines as Theorem 1 of [START_REF] Ghosal | Convergence rates of posterior distributions for non iid observations[END_REF].

The assumption ρ θ0 > 1 implies that the hidden Markov chain X is uniformly ergodic. Assumptions C1-C2 and either C3 or C3bis are similar in spirit to those considered in general theorems on posterior consistency or posterior convergence rates, see for instance [START_REF] Ghosh | Bayesian Nonparametrics[END_REF] and [START_REF] Ghosal | Convergence rates of posterior distributions for non iid observations[END_REF]. Assumption C3bis is often used to eliminate some extra log n term which typically appear in nonparametric posterior concentration rates and is used in particular in the proof of Theorem 3.

Proofs

Proof of Theorem 1

The proof consists in showing that the assumptions of Theorem 4 are satisfied. Following the proof of Lemma 2 of [START_REF] Douc | Asymptotic properties of the maximum likelihood estimator in the autoregressive models with Markov regime[END_REF] we find that, since ρ θ0 > 1, for any

x 0 ∈ X , | n (θ 0 , x 0 ) -n (θ 0 , x 1 ) | ≤ 2 ρ θ0 ρ θ0 -1 2 .
imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013 so that setting A = 2 ρ θ 0 ρ θ 0 -1 2 the first point of C1 holds.

We shall verify assumption C1 with ˜ n = M n / √ n for some M n tending slowly enough to infinity and that will be chosen later. Note that the assumption A0 and the construction (5) allow to define a θ0 ∈ Θ k such that , writing θ0 = ( Q0 , γ0 1 , . . . , γ0 k ) with Q0 = (q 0 i,j , i,

j ≤ k), if V is a bounded subset of {θ = (Q, γ 1 , . . . , γ k ); |q i,j -q0 i,j | ≤ ˜ n }, then inf θ∈V ρ θ > 1, (18)
for large enough n, and

sup θ∈V sup x,x0∈X | n (θ, x) -n (θ, x 0 )| ≤ 2 sup θ∈V ρ θ ρ θ -1 2 .
Following the proof of Lemma 2 of [START_REF] Douc | Asymptotic properties of the maximum likelihood estimator in the autoregressive models with Markov regime[END_REF] gives that, if A0 and A1 hold, for all θ ∈ V P θ0 -a.s.,

n (θ, x 0 ) -n (θ 0 , x 0 ) = (θ -θ 0 ) T ∇ θ n (θ 0 , x 0 ) + 1 0 (θ -θ 0 ) T D 2 θ n (θ 0 + u(θ -θ 0 ), x 0 ) (θ -θ 0 ) (1 -u)du. (19)
Following Theorem 2 in [START_REF] Douc | Asymptotic properties of the maximum likelihood estimator in the autoregressive models with Markov regime[END_REF], n -1/2 ∇ θ n (θ 0 , x) converges in distribution under P θ0 to N (0, V 0 ) for some positive definite matrix V 0 , and following Theorem 3 in [START_REF] Douc | Asymptotic properties of the maximum likelihood estimator in the autoregressive models with Markov regime[END_REF], we get that sup θ∈V n -1 D 2 θ n (θ, x 0 ) converges P θ0 a.s. to V 0 . Thus, we may set:

S n = θ ∈ V ; γ j -γ 0 j ≤ 1/ √ n ∀j ≤ k × X so that sup (θ,x)∈Sn P θ0 [ n (θ, x) -n (θ 0 , x 0 ) < -M n ] = o(1). (20) Moreover, letting D = k(k -1 + d), we have Π ⊗ Π X (S n ) n -D/2 and C1 is then satisfied setting C n = D log n/(2M 2 n ). Let now v n = n -D/(2 min 1≤i≤k αi) / √ log n and u n = n -D/(2 1≤i≤k
αi) / √ log n, and define

F n = {θ = (q ij , 1 ≤ i ≤ k, 1 ≤ j ≤ k -1; γ 1 , ...., γ k ) : q ij ≥ v n , 1 ≤ i ≤ k, 1 ≤ j ≤ k, k j=1 inf 1≤i≤k q ij ≥ u n , γ i ≤ n b , 1 ≤ i ≤ k    . Now, if θ ∈ F c n , then there exist 1 ≤ i, j ≤ k such that q ij ≤ v n , or k j=1 inf 1≤i≤k q ij ≤ u n , or there exists 1 ≤ i ≤ k such that γ i ≥ n b .
Using A3 we easily obtain that for fixed i and j, Π({θ :

q ij ≤ v n }) = O(v αj n ) and Π({θ : γ i ≥ n b }) = o(n -D/2
). Also, imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013 if k j=1 inf 1≤i≤k q ij ≤ u n , then there exists a function i(•) from {1, . . . , k} to {1, . . . , k} whose image set has cardinality at least 2 such that k j=1 q i(j)j ≤ u n . This gives, using A3, Π({θ :

k j=1 inf 1≤i≤k q ij ≤ u n }) = O(u 1≤i≤k αi n ). Thus, Π(F c n ) = O(v min 1≤i≤k αi n + u 1≤i≤k αi n ) + o n -D/2 .
We may now choose M n tending to infinity slowly enough so that v

min 1≤i≤k αi n +u 1≤i≤k αi n = o(e -Mn n -D/2 ) and Π(F c n ) = o(e -Mn n -D/2
). Then, C2 holds. Now, using the definition of f l,θ , we obtain that

f l,θ1 -f l,θ2 1 ≤ k j=1 |µ θ1 -µ θ2 | + l k i,j=1 |Q 1 i,j -Q 2 i,j | + l max j≤k g γ 1 j -g γ 2 j 1
so that using Lemma 1 below, A1 and A2 we get that for some constant B,

∀(θ 1 , θ 2 ) ∈ F 2 n f l,θ1 -f l,θ2 1 ≤ B 1 v 2c n + n a θ 1 -θ 2 .
Thus for some other constant B,

N (δ, F n , d(., .)) ≤ B δ 1 v 2c n + n a k(k-1)+kd
and C3 holds when setting n = K log n n with K large enough. We have proved that under assumptions A0, A1, A2, A3, Theorem 4 applies with n = K log n n so that

P Π f l,θ -f l,θ0 1 (ρ θ -1) ≥ K log n n Y 1:n = o P θ 0 (1)
and the first part of Theorem 1 is proved. Now

o P θ 0 (1) = P Π f l,θ -f l,θ0 1 (ρ θ -1) ≥ K log n n Y 1:n = P Π θ ∈ F n and f l,θ -f l,θ0 1 (ρ θ -1) ≥ K log n n Y 1:n + o P θ 0 (1) . Since ρ θ -1 ≥ k j=1 min 1≤i≤k q ij , for all θ ∈ F n , ρ θ -1 ≥ u n , P Π f l,θ -f l,θ0 1 (ρ θ -1) ≥ K log n n |Y 1:n ≥ P Π f l,θ -f l,θ0 1 ≥ 2K 1 u n log n n |Y 1:n , imsart-
= v n = h/ log n, with h > 2C/(k + d -1) Π(F c n ) = O(v n exp(-C/v n )) + o n -D/2 = o(e -Mn n -D/2 )
by choosing M n increasing to infinity slowly enough so that C2 and C3 hold. The end of the proof follows similarly as before.

To finish the proof of Theorem 1 we need to prove

Lemma 1 The function θ → µ θ is continuously differentiable in (∆ 0 k ) k × Γ k
and there exists an integer c > 0 and a constant C > 0 such that for any

1 ≤ i ≤ k, 1 ≤ j ≤ k -1, any m = 1, . . . , k, ∂µ θ (m) ∂q ij ≤ C (inf i =j q i j ) 2c . One may take c = k -1. Let θ = (q ij , 1 ≤ i ≤ k, 1 ≤ j ≤ k -1; γ 1 , ...., γ k ) be such that (q ij , 1 ≤ i ≤ k, 1 ≤ j ≤ k -1) ∈ ∆ k 0 , Q θ = (q ij , 1 ≤ i ≤ k, 1 ≤ j ≤ k) is a k × k stochastic matrix
with positive entries, and µ θ is uniquely defined by the equation

µ T θ Q θ = µ T θ if µ θ is the vector (µ θ (m)) 1≤m≤k
. This equation is solved by linear algebra as

µ θ (m) = P m (q ij , 1 ≤ i ≤ k, 1 ≤ j ≤ k -1) R(q ij , 1 ≤ i ≤ k, 1 ≤ j ≤ k -1) , m = 1, . . . , k -1, µ θ (k) = 1 - k-1 m=1 µ θ (m) , (21)
where P m , l = 1, . . . , k -1 and R are polynomials where the coefficients are integers (bounded by k) and the monomials are all of degree k -1, each variable q ij , 1 ≤ i ≤ k, 1 ≤ j ≤ k -1 appearing with power 0 or 1. Now, since the equation has a unique solution as soon as (q ij , 1 ≤ i ≤ k, 1 ≤ j ≤ k -1) ∈ ∆ k 0 , then R is never 0 on ∆ k 0 , so it may be 0 only at the boundary. Thus, as a fraction of polynomials with non zero denominator, θ → µ θ is infinitely differentiable in (∆ 0 k ) k × Γ k , and the derivative has components all of form

P (q ij , 1 ≤ i ≤ k, 1 ≤ j ≤ k -1) R(q ij , 1 ≤ i ≤ k, 1 ≤ j ≤ k -1) 2
where again P is a polynomial where the coefficients are integers (bounded by 2k) and the monomials are all of degree k -1, each variable q ij , 1 ≤ i ≤ k, 1 ≤ j ≤ k -1 appearing with power 0 or 1. Thus, since all q ij 's are bounded by 1 there exists a constant C such that for all m = 1, . . . , k, i = 1, . . . , k, j = 1, . . . , k -1,

∂µ θ (m) ∂q ij ≤ C R(q ij , 1 ≤ i ≤ k, 1 ≤ j ≤ k -1) 2 . ( 22
)
We shall now prove that

R (q ij , 1 ≤ i ≤ k, 1 ≤ j ≤ k -1) ≥ ( inf 1≤i≤k,1≤j≤k,i =j q ij ) k-1 , (23)
which combined with ( 22) and ( 23) implies Lemma 1. Note that we can express R as a polynomial function of

Q = q ij , 1 ≤ i ≤ k, 1 ≤ j ≤ k, i = j. Indeed, µ := (µ θ (i)) 1≤i≤k-1 is solution of µ T • M = V T
where V is the (k -1)-dimensional vector (q kj ) 1≤j≤k-1 , and M is the (k -1) × (k -1)matrix with components M i,j = q kj -q ij + 1l i=j . Since R is the determinant of M , this leads to, for any k ≥ 2 :

R = σ∈S k-1 ε (σ) 1≤i≤k-1,σ(i)=i   q ki + 1≤j≤k-1,j =i q ij   1≤i≤k-1,σ(i) =i q ki -q σ(i)i
(24) where for any integer n, S n is the set of permutations of {1, . . . , n}, and for each permutation σ, ε (σ) is its signature. Thus R is a polynomial in the components of Q where each monomial has integer coefficient and has k -1 different factors. The possible monomials are of form

β i∈A q ki i∈B q ij(i)
where (A, B) is a partition of {1, . . . , k -1}, and for all i ∈ B, j(i) ∈ {1, . . . , k -1} and j(i) = i. In case B = ∅, the coefficient β of the monomial is σ∈S k-1 ε (σ) = 0, so that we only consider partitions such that B = ∅ . Fix such a monomial with non nul coefficient, let (A, B) be the associated partition. Let Q be such that, for all i ∈ A, q ki > 0, for all i / ∈ A, q ki = 0 and q kk > 0 (used to handle the case A = ∅). Fix also q ij(i) = 1 for all i ∈ B. Then, if (A , B ) is another partition of {1, . . . , k -1} with B = ∅, the monomial i∈A q ki i∈B q ij(i) = 0. Thus, R(Q) equals i∈A q ki i∈B q ij(i) times the coefficient of the monomial. But R(Q) ≥ 0, so that this coefficient is a positive integer and (23) follows.

Proof of Theorem 2

Applying Theorem 1, we get that under the assumptions of Theorem 2, there exists K such that 13) holds, then as soon as

P θ0 f l,θ -f l,θ0 1 ≤ 2Kw n |Y 1:n = 1 + o P θ 0 (1). But if inequality (
f l,θ -f l,θ0 1 w n ( 25
)
we get that, for any j ∈ {1, . . . , k}, either

P θ (X 1 = j) w n , or ∃i ∈ {1, . . . , k 0 }, P θ (X 1 = j) γ j -γ 0 i 2 w n .
imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013

Let us choose ≤ min i =j γ 0 i -γ 0 j /4 in the definition of B(i) in ( 13). We then obtain that for large enough n, all j 1 , j 2 ∈ J(θ), we have j 1 ∼ j 2 if and only if they belong to the same B(i), i = 1, . . . , k 0 , so that L(θ) ≤ k 0 . On the other hand, L(θ) < k 0 would mean that at least one B(i) would be empty which contradicts the fact that

|P θ (X 1 ∈ B(i)) -P θ0 (X 1 = i)| ≤ w n .
Thus, for large enough n, if (25) holds, then L(θ) = k 0 , so that

P Π [L(θ) = k 0 |Y n ] = 1 + o P θ 0 (1).
To finish the proof we now prove that (13) holds under the assumptions of Theorem 2. This will follow from Proposition 1 below which is slightly more general. An inequality that relates the L 1 distance of the l-marginals to the parameters of the HMM is proved in [START_REF] Gassiat | The local geometry of finite mixtures[END_REF] for translation mixture models, with the strength of being uniform over the number (possibly infinite) of populations in the mixture. However for our purpose, we do not need such a general result, and it is possible to obtain it for more general situations than families of translated distributions, under the structural assumption A4. The inequality following Theorem 3.10 of [START_REF] Gassiat | The local geometry of finite mixtures[END_REF] says that there exists a constant c(θ 0 ) > 0 such that for any small enough positive ε,

f l,θ -f l,θ0 1 c(θ 0 ) ≥ 1≤j≤k:∀i, γj -γ 0 i >ε P θ (X 1 = j) + 1≤i1,...,i l ≤k0 [|P θ (X 1:l ∈ A(i 1 , . . . , i l )) -P θ0 (X 1:l = i 1 • • • i l )| + (j1,...,j l )∈A(i1,...,i l ) P θ (X 1:l = j 1 • • • j l )      γ j1 • • • γ j l   -   γ 0 i1 • • • γ 0 i l      + 1 2 (j1,...,j l )∈A(i1,...,i l ) P θ (X 1:l = j 1 • • • j l )   γ j1 • • • γ j l   -   γ 0 i1 • • • γ 0 i l   2    (26)
where A(i 1 , . . . , i l ) = {(j 1 , . . . , j l ) :

γ j1 -γ 0 i1 ≤ ε, . . . , γ j l -γ 0 i l ≤ ε}.
The above lower bound essentially corresponds to a partition of {1, . . . , k} l into k l 0 + 1 groups, where the first k l 0 groups correspond to the components that are close to true distinct components in the multivariate mixture and the last corresponds to components that are emptied. The first term on the right hand side controls the weights of the components that are emptied (group k l 0 + 1), the second term controls the sum of the weights of the components belonging to the i-th group, for i = 1, . . . , k l 0 (components merging with the true i-th component), the third term controls the distance between the mean value over the group i and the true value of the i-th component in the true mixture while the last term controls the distance between each parameter value in group i and the true value of the i-th component. Notice that ( 13) is a consequence of (26). We shall prove that (26) holds under an assumption slightly more general than A4. For this we need to introduce some notations. For all I = (i 1 , . . . , i l ) ∈ {1, • • • , k} l , define γ I = (γ i1 , . . . , γ i l ), G γ I = l t=1 g γi t (y t ), D 1 G γ I the vector of first derivatives of G γ I with respect to each of the distinct elements in γ I , note that it has dimension d×|I|, where |I| denotes the number of distinct indices in I, and similarly define D 2 G γ I the symmetric matrix in R d|I|×d|I| made of second derivatives of G γ I with respect to the distinct elements (indices) in γ I . For any t = (t 1 , . . . , t k0 ) ∈ T , define for all i ∈ {1, . . . , k 0 } the set J(i) = {t i-1 + 1, . . . , t i }, using t 0 = 0.

We then consider the following condition :

• Assumption A4bis For any t = (t 1 , . . . , t k0 ) ∈ T , for all collections (π I ) I , (γ

I ) I , I / ∈ {1, . . . , t k0 } l satisfying π I ≥ 0, γ I = (γ i1 , . . . , γ i l ) such that γ ij = γ 0 i when i j ∈ J(i) for some i ≤ k 0 and γ ij ∈ Γ \ {γ 0 i , i = 1, . . . , k 0 } when i j / ∈ {1, . . . , t k0 }, for all collections (a I ) I , (c I ) I , (b I ) I , I ∈ {1, . . . , k 0 } l , a I ∈ R, c I ≥ 0 and b I ∈ R d|I| , for all collection of vectors z I,J ∈ R d|I| with I ∈ {1, . . . , k 0 } l and J ∈ J(i 1 ) × • • • × J(i l ) satisfying z I,J = 1,
and all sequences (α I,J ), satisfying α I,J ≥ 0 and

J∈J(i1)ו••×J(i l ) α I,J = 1, I / ∈{1,...,t k 0 } l π I G γ I + I∈{1,...,k0} l a I G γ 0 I + b T I D 1 G γ 0 I + I∈{1,...,k0} l c I J∈J(i1)ו••×J(i l ) α I,J z T I,J D 2 G γ 0 I z I,J = 0 ⇔ I / ∈{1,...,t k 0 } l π I + I∈{1,...,k0} l (|a I | + b I + c I ) = 0 (27)
We have:

Proposition 1 Assume that the function γ → g γ (y) is twice continuously differentiable in Γ and that for all y, g γ (y) vanishes as γ tends to infinity. Then, if Assumption A4bis is verified, (26) holds. Moreover, condition A4bis is verified as soon as condition A4 (corresponding to l = 1) is verified.

Let us now prove Proposition 1. To prove the first part of the Proposition we follow the ideas of the beginning of the proof of Theorem 5.11 in [START_REF] Gassiat | The local geometry of finite mixtures[END_REF]. If (26) does not hold, there exist a sequence of l-marginals (f l,θ n ) n≥1 with parameters (θ n ) n≥1 such that for some positive sequence ε n tending to 0, f l,θ n -f l,θ0 1 /N n (θ n ) imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013 tends to 0 as n tends to infinity, with

N n (θ) = 1≤j≤l:∀i, γj -γ 0 i >εn P θ (X 1 = j) + 1≤i1,...,i l ≤k0   | (j1,...,j l )∈An(i1,...,i l ) P θ (X 1:l = j 1 • • • j l ) -P θ0 (X 1:l = i 1 • • • i l ) | + (j1,...,j l )∈An(i1,...,i l ) P θ (X 1:l = j 1 . . . j l )      γ j1 • • • γ j l   -   γ 0 i1 • • • γ 0 i l      + 1 2 (j1,...,j l )∈An(i1,...,i l ) P θ (X 1:l = j 1 • • • j l )   γ j1 • • • γ j l   -   γ 0 i1 • • • γ 0 i l   2    with A n (i 1 , . . . , i l ) = {(j 1 , . . . , j l ) : γ j1 -γ 0 i1 ≤ ε n , . . . , γ j l -γ 0 i l ≤ ε n }. Now, f l,θ n = I∈{1,...,k} l P θ n (X 1 , . . . , X l = I) G γ n I where θ n = (Q n , (γ n 1 , . . . , γ n k )),
Q n a transition matrix on {1, . . . , k}. It is possible to extract a subsequence along which, for all i = 1, . . . , k, either γ n i converges to some limit γ i or γ n i tends to infinity. Choose now the indexation such that for i = 1, . . . , t 1 , γ n i converges to γ 0 1 , for i = t 1 + 1, . . . , t 2 , γ n i converges to γ 0 2 , and so on, for i = t k0-1 + 1, . . . , t k0 , γ n i converges to γ 0 k0 , and if t k0 < k, for some k ≤ k, for i = t k0 + 1, . . . , k, γ n i converges to some γ i / ∈ {γ 0 1 , . . . , γ 0 k0 }, and for i = k + 1, . . . , k, γ n i tends to infinity. It is possible that k = t k0 in which case no γ n i converges to some γ i / ∈ {γ 0 1 , . . . , γ 0 k0 }. Such a t = (t 1 , . . . , t k0 ) ∈ T exists, because if f l,θ n -f l,θ0 1 /N n (θ n ) tends to 0 as n tends to infinity, f l,θ n -f l,θ0 1 , and N n (θ n ) tends to 0 as n tends to infinity (if it was not the case, using the regularity of θ → f l,θ we would have a contradiction). Now along the subsequence we may write, for large enough n:

N n (θ n ) = I / ∈{1,...,t k 0 } l P θ (X 1:l = I)+ I∈{1,...,k0} l   J∈J(i1)ו••×J(i l ) P θ (X 1:l = J) -P θ0 (X 1:l = I) + J∈J(i1)ו••×J(i l ) P θ (X 1:l = J) γ J -γ 0 I + 1 2 J∈J(i1)ו••×J(i l ) P θ (X 1:l = J) γ J -γ 0 I 2   .
We shall use a Taylor expansion till order 2. To be perfectly rigorous in the following, we need to express explicitely I in terms of its distinct indices, ( ĩ1

, • • • , ĩ|I| ), so that G γ I = |I| t=1 j:ij = ĩt g γĩ t (y j
), but to keep notations concise we do not make such a distinction and for instance (γ n J -

γ 0 I ) T D 1 G γ 0 I means |I| t=1 (γ ĩt -γ 0 ĩt ) T ∂G γ I ∂γ ĩt ,
imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013

and similarly for the second derivatives. We have

f l,θ n -f l,θ0 = I / ∈{1,...,t k 0 } l P θ (X 1:l = I) G γ n I + I∈{1,...,k0} l      J∈J(i1)ו••×J(i l ) P θ (X 1:l = J) -P θ0 (X 1:l = I)   G γ 0 I + J∈J(i1)ו••×J(i l ) P θ (X 1:l = J) γ J -γ 0 I T D 1 G γ 0 I + 1 2 J∈J(i1)ו••×J(i l ) P θ (X 1:l = J) γ J -γ 0 I T D 2 G γ * I γ J -γ 0 I    with γ * I ∈ (γ n I , γ 0 I
). Thus, using the fact that for all y, g γ (y) vanishes as γ tends to infinity, f l,θ n -f l,θ0 /N n (θ n ) converges pointwise along a subsequence to a function h of form

h = I / ∈{1,...,t k 0 } l π I G γ I + I∈{1,...,k0} l a I G γ 0 I + b T I D 1 G γ 0 I + I∈{1,...,k0} l c I J∈J(i1)ו••×J(i l ) α I,J z T I,J D 2 G γ 0 I z I,J
as in condition L(l), with I / ∈{1,...,t k 0 } l π I + I∈{1,...,k0} l (|a

I | + b I + c I ) = 1. But as f l,θ n -f l,θ0 1 /N n (θ n
) tends to 0 as n tends to infinity, we have h 1 = 0 by Fatou's lemma, and thus h = 0, contradicting the assumption.

Let us now prove that A4 implies A4bis.

Let I / ∈{1,...,t k 0 } l π I G γ I + I∈{1,...,k0} l a I G γ 0 I + b T I D 1 G γ 0 I + I∈{1,...,k0} l c I J∈J(i1)ו••×J(i l ) α I,J z T I,J D 2 G γ 0 I z I,J = 0 ⇔ I / ∈{1,...,t k 0 } l π I + I∈{1,...,k0} l (|a I | + b I + c I ) = 0
with π I , a I , b I , α I,J and z I,J be as in assumption A4bis. We group the terms depending imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013 only on y 1 and we can rewrite the equation as

k i=t k 0 +1 π i (y 2 , • • • , y l )g γi (y 1 ) + k0 i=1 a i (y 2 , • • • , y l )g γ 0 i (y 1 ) + b T i (y 2 , • • • , y l )D 1 g γ 0 i (y 1 ) + k0 i=1 ti-ti-1 j=1 k0 i2,••• ,i l =1 c I (j2,••• ,j l )∈J(i2)ו••×J(i l ) α I,J z I,J (i) T D 2 g γ 0 i (y 1 )z I,J (i) = 0 (28)
where we have written

z I,J = (z I,J (i 1 ), • • • , z I,J (i l )), with I = (i, i 2 , • • • , i l ) J = (j 1 , • • • , j l ), z I,J (i) ∈ R d and c I = c I l t=2 g γ 0 i t (y t ) Note that if for i = 1, • • • , k 0 and j = 1, • • • , t i -t i-1 , there exists w i,j ∈ R d such that k0 i2,••• ,i l =1 c I (j2,••• ,j l )∈J(i2)ו••×J(i l ) α I,J z I,J (i) T D 2 g γ 0 i (y 1 )z I,J (i) = w T i,j D 2 g γ 0 i (y 1 )w i,j
where possibly w i,j = 0. Let α i,j = w i,j 2 /( ti-ti-1 j=1

w i,j 2 ) if there exists j such that

w i,j 2 > 0 and c i = i2,••• ,i l c I ti-ti-1 j=1 w i,j 2 , then ti-ti-1 j=1 k0 i2,••• ,i l =1 c I (j2,••• ,j l )∈J(i2)ו••×J(i l )
α I,J z I,J (i) T D 2 g γ 0 i (y 1 )z I,J (i) = c i ti-ti-1 j=1 α i,j w T i,j D 2 g γ 0 i (y 1 )w i,j .

and (10) implies that

a i = c i = 0, b i = 0 i = 1, • • • , k 0 , π i = 0, i = t k0 + 1, • • • k Simple calculations imply that π i = k i2,••• ,i l =1 π I l t=2 g γ 0 i t (y t ) = 0 ⇔ ∀(i 2 , • • • , i l ) ∈ {1, • • • , k} l-2 π i,i2,••• ,i l = 0
and similarly if i is such that there exists j = 1,

• • • , t i -t i-1 , I = (i, i 2 , • • • , i l ) and J = (j, j 2 , • • • , j l ) ∈ J(i) × • • • × J(i l ) such that c I > 0, α J > 0 and z I,J (i) > 0, then c i,i2,••• ,i l = 0 for all i 2 , • • • , i l .
Else, by considering y t for some other t, we obtain that (28) implies that π I = 0 ∀I / ∈ {1, . . . , t k0 } l , c I = 0 ∀I ∈ {1, . . . , t k0 } l .

imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013

• If γ 1 -γ 0 ≤ η and γ 1 -γ 0 + γ 2 -γ 0 > 2η, f 2,θ -f 2,θ0 1 ≥ c(θ 0 ) p p + q + q p + q γ 1 -γ 0 , • If γ 2 -γ 0 ≤ η and γ 1 -γ 0 + γ 2 -γ 0 > 2η, f 2,θ -f 2,θ0 1 ≥ c(θ 0 ) q p + q + p p + q γ 2 -γ 0 , • If γ 1 -γ 0 > η and γ 2 -γ 0 > η, f 2,θ -f 2,θ0 1 ≥ c(θ 0 ).
Similar upper bounds hold also by Taylor expansion. Thus, for any m, A n,m ( n ) is a subset of the set of θ's such that min (p + q) ∧ (2 -(p + q)) p + q q(γ 1 -γ 0 ) + p(γ 2 -γ 0 ) + q γ 1 -γ 0 2 + p γ 2 -γ 0 2 ;

(p + q) ∧ (2 -(p + q)) p + q p + q γ 1 -γ 0 ; (p + q) ∧ (2 -(p + q)) p + q q + p γ 2 -γ 0 ; (p + q) ∧ (2 -(p + q))} (m + 1) n .
This leads to

Π 2 (A n,m ( n )) [(m + 1) n ] 2α + [(m + 1) n ] 2β + [(m + 1) n ] α+d
so that if α, β > 3d/4 and (29) holds, there exists δ > 0 such that

Π 2 (A n,m ( n )) e -nm 2 2 n 32l Π(S n ) n -δ [(M n m) 2α + (M n m) 2β + (M n m) α+d ]e -M 2
n m 2 32l

.

Also for all > 0 small enough A n,m ( ) contains the set of θ's such that max (p + q) ∧ (2 -(p + q)) p + q q(γ 1 -γ 0 ) + p(γ 2 -γ 0 ) + q γ 1 -γ 0 2 + p γ 2 -γ 0 2 ;

(p + q) ∧ (2 -(p + q)) p + q p + q γ 1 -γ 0 ; (p + q) ∧ (2 -(p + q)) p + q q + p γ 2 -γ 0 ; (p + q) ∧ (2 -(p + q))} (m + 1) therefore N ( m n 12 , A n,m ( n ) , d l (., .)) m 2+2d e n 2 n m 2 (ρ θ 0 -1) 2 16l(2+ρ θ 0 -1) 2 ,
so that assumption C3bis is verified.

imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013

We now prove Theorem 3. Notice first that, by setting D n = Θ×X e n(θ,x)-n (θ0,x0) Π 2 (dθ)π X (dx), as in the proof of Theorem 4 we get that for any sequence C n tending to infinity,

P θ0 D n ≤ C n n -D/2 = o (1) (30)
with

D = d + d/2.
Let now n be any sequence going to 0 and let A n = p p+q ≤ n or q p+q ≤ n . For some sequence M n going to infinity and

δ n = M n / √ n, let B n = {(p + q)∧(2 -(p + q)) f 2,θ -f 2,θ0 1 ≤ δ n }.
We then control with D = d + d/2, using Lemma 2

E θ0 P Π (A n |Y 1:n ) = E θ0 P Π (A n ∩ B n |Y 1:n ) + o (1) = E θ0 An∩Bn×X e n (θ,x)-n (θ0,x0) Π 2 (dθ)π X (dx) Θ×X e n (θ,x)-n (θ0,x0) Π 2 (dθ)π X (dx) + o (1) := E θ0 N n D n + o (1) ≤ P θ0 D n ≤ C n n -D/2 + n D/2 C n Π 2 (A n ∩ B n ) + o (1) .
Thus using (30) the first part of Theorem 3 is proved by showing that

Π 2 (A n ∩ B n ) δ 2α n + δ α+d n + δ d+d/2 n α-d/2 n . (31)
Then, the second part of Theorem 3 follows from its first part and Lemma 2.

We now prove that (31) holds. Define

B 1 n = (p + q) ∧ (2 -(p + q)) p + q q(γ 1 -γ 0 ) + p(γ 2 -γ 0 ) + q γ 1 -γ 0 2 + p γ 2 -γ 0 2 ≤ δ n , B 2 n = (p + q) ∧ (2 -(p + q)) p + q p + q γ 1 -γ 0 ] ≤ δ n , B 3 n = (p + q) ∧ (2 -(p + q)) p + q q + p γ 2 -γ 0 ≤ δ n and B 4 n = {(p + q) ∧ (2 -(p + q)) ≤ δ n } . Then Π 2 (A n ∩ B n ) ≤ Π 2 (A n ∩ B 1 n ) + Π 2 (A n ∩ B 2 n ) + Π 2 (A n ∩ B 3 n ) + Π 2 (A n ∩ B 4 n ).
Notice that on A n , if p + q ≥ 1, then p ≤ n and q ≥ 1n , or q ≤ n and p ≥ 1n , so that also 2 -(p + q) ≥ 1n .

imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013

• On A n ∩B 1 n , q(γ 1 -γ 0 ) + p(γ 2 -γ 0 ) δ n , q γ 1 -γ 0 2 δ n , p γ 2 -γ 0 2 δ n , and p n or q n . This gives Π

2 (A n ∩ B 1 n ) δ d+d/2 n α-d/2 n . • On A n ∩ B 2
n , p δ n and q γ 1 -γ 0 δ n in case p + q ≤ 1, and p δ n , 1 -q δ n and q γ 1 -γ 0 δ n in case p + q ≥ 1, leading to Π

2 (A n ∩ B 2 n ) δ α+d n + δ α+β+d n . • For symmetry reasons, Π 2 (A n ∩ B 3 n ) = Π 2 (A n ∩ B 2 n ). • On A n ∩ B 4
n , p δ n and q δ n , so that Π 2 (A n ∩ B 4 n ) δ 2α n . Keeping only the leading terms, we see that (31) holds and this terminates the proof Theorem 3.

We now prove Lemma 3. We easily get Π 2 (U n ) n -3d/4 , and

D n ≥ Un×X e n (θ,x)-n(θ0,x) Π 2 (dθ)π X (dx) .
Let us now study n (θ, x)n (θ 0 , x). First, following the proof of Lemma 2 of [START_REF] Douc | Asymptotic properties of the maximum likelihood estimator in the autoregressive models with Markov regime[END_REF] we find that, for any θ ∈ U n , for any x,

| n (θ) -n (θ, x)| ≤ 1 + 2 1 -2 2 ,
where n (θ) = k x=1 µ θ (x) n (θ, x). Thus, for any θ ∈ U n and any x, and since n (θ 0 , x) does not depend on x,

n (θ, x) -n (θ 0 , x) ≥ n (θ) -n (θ 0 ) - 1 + 2 1 -2 2 . ( 32
)
Let us now study n (θ)n (θ 0 ).

n (θ) -n (θ 0 ) = n k=1 log P θ (X k = 1|Y 1:k-1 ) g γ1 g γ 0 (Y k ) + P θ (X k = 2|Y 1:k-1 ) g γ2 g γ 0 (Y k )
and we set for k = 1

P θ (X k = 1|Y 1:k-1 ) = P θ (X 1 = 1) = q p + q , P θ (X k = 2|Y 1:k-1 ) = P θ (X 1 = 2) = p p + q .
Denote p k (θ) the random variable P θ (X k = 1|Y 1:k-1 ), which is a function of Y 1:k-1 and thus independent of Y k . We have the recursion

p k+1 (θ) = (1 -p)p k (θ)g γ1 (Y k ) + q(1 -p k (θ))g γ2 (Y k ) p k (θ)g γ1 (Y k ) + (1 -p k (θ))g γ2 (Y k ) . ( 33
)
Note that, for any p, q in ]0, 1[, for any k ≥ 1, p k (p, q, γ 0 , γ 0 ) = q p + q .

We shall denote by D i (γ1) j ,(γ2) i-j the i-th partial derivative operator j times with respect to γ 1 and i -j times with respect to γ 2 (0 ≤ j ≤ i, the order in which derivatives are taken does not matter). Fix θ = (p, q, γ 1 , γ 2 ) ∈ U n . When derivatives are taken at point (p, q, γ 0 , γ 0 ), they are written with 0 as superscript. Using Taylor expansion till order 4, there exists t ∈ [0, 1] such that denoting θ t = tθ + (1 -t)(p, q, γ 0 , γ 0 ):

n (θ) -n (θ 0 ) = (γ 1 -γ 0 )D 1 γ1 0 n + (γ 2 -γ 0 )D 1 γ2 0 n + S n (θ) + T n (θ) + R n (θ, t) (34)
where S n (θ) denotes the term of order 2, T n (θ) denotes the term of order 3, and R n (θ, t) the remainder, that is

S n (θ) = (γ 1 -γ 0 ) 2 D 2 (γ1) 2 0 n + 2(γ 1 -γ 0 )(γ 2 -γ 0 )D 2 γ1,γ2 0 n + (γ 2 -γ 0 ) 2 D 2 (γ2) 2 0 n , T n (θ) = (γ 1 -γ 0 ) 3 D 3 (γ1) 3 0 n + 3(γ 1 -γ 0 ) 2 (γ 2 -γ 0 )D 3 (γ1) 2 ,γ2 0 n + 3(γ 1 -γ 0 )(γ 2 -γ 0 ) 2 D 3 γ1,(γ2) 2 0 n + (γ 2 -γ 0 ) 3 D 3 (γ2) 3 0 n and R n (θ, t) = 4 k=0 k 4 (γ 1 -γ 0 ) k (γ 2 -γ 0 ) 4-k D 4 (γ1) k ,(γ2) 4-k n (θ t ).
Easy but tedious computations lead to the following results.

(γ 1 -γ 0 )D 1 γ1 0 n + (γ 2 -γ 0 )D 1 γ2 0 n = n k=1 D 1 γ g γ0 g γ0 (Y k ) q(γ 1 -γ 0 ) + p(γ 2 -γ 0 ) p + q = 1 √ n n k=1 D 1 γ g γ0 g γ0 (Y k ) √ n q(γ 1 -γ 0 ) + p(γ 2 -γ 0 ) p + q so that sup θ∈Un (γ 1 -γ 0 )D 1 γ1 0 n + (γ 2 -γ 0 )D 1 γ2 0 n = O P θ 0 (1) . (35)
imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013 Also,

S n (θ) = -   1 n n k=1 D 1 γ g γ0 g γ0 (Y k ) 2   √ n q(γ 1 -γ 0 ) + p(γ 2 -γ 0 ) p + q 2 + 1 √ n n k=1 D 2 γ 2 g γ0 g γ0 (Y k ) q p + q n 1/4 (γ 1 -γ 0 ) 2 + p p + q n 1/4 (γ 2 -γ 0 ) 2 +2 n 1/4 (γ 1 -γ 0 ) 2 1 √ n n k=1 (D 1 γ1 p 0 k ) D 1 γ g γ0 g γ0 (Y k ) -2 n 1/4 (γ 2 -γ 0 ) 2 1 √ n n k=1 (D 1 γ2 p 0 k ) D 1 γ g γ0 g γ0 (Y k ) + 2 n 1/4 (γ 1 -γ 0 )(γ 2 -γ 0 ) 1 √ n n k=1 (D 1 γ2 p 0 k -D 1 γ1 p 0 k ) D 1 γ g γ0 g γ0 (Y k ) .
Using (33) one gets that for all integer k ≥ 2, (D 1 γ1 p 0 1 = 0 and D 1 γ2 p 0 1 = 0):

D 1 γ1 p 0 k = pq (p + q) 2 k-1 l=1 (1 -p -q) k-l D 1 γ g γ0 g γ0 (Y l ) and D 1 γ2 p 0 k = -D 1 γ1 p 0 k which leads to E θ0   1 √ n n k=1 (D 1 γ1 p 0 k ) D 1 γ g γ0 g γ0 (Y k ) 2   ≤   E θ0 D 1 γ g γ0 g γ0 (Y 1 ) 2   2 . and E θ0   1 √ n n k=1 (D 1 γ2 p 0 k ) D 1 γ g γ0 g γ0 (Y k ) 2   ≤   E θ0 D 1 γ g γ0 g γ0 (Y 1 ) 2   2 .
Thus, we obtain sup

θ∈Un |S n (θ)| = O P θ 0 (1) . (36)
For the order 3 term, as soon as θ ∈ U n :

T n (θ) = -   n k=1 D 1 γ g γ0 g γ0 (Y k ) 3   q(γ 1 -γ 0 ) + p(γ 2 -γ 0 ) p + q 3 + n k=1 D 3 γ 3 g γ0 g γ0 (Y k ) q p + q γ 1 -γ 0 3 + p p + q γ 2 -γ 0 3 -3 n k=1 D 1 γ g γ0 g γ0 (Y k ) D 2 γ 2 g γ0 g γ0 (Y k ) q(γ 1 -γ 0 ) + p(γ 2 -γ 0 ) p + q q (p + q) 2 γ 1 -γ 0 2 + p (p + q) 2 γ 2 -γ 0 2 + O n -3/4    n k=1 (D 1 γ1 p 0 k ) D 1 γ g γ0 g γ0 (Y k ) 2 + n k=1 (D 1 γ1 p 0 k ) D 2 γ 2 g γ0 g γ0 (Y k ) n k=1 (D 2 (γ1) 2 p 0 k ) D 1 γ g γ0 g γ0 (Y k ) + n k=1 (D 2 (γ2) 2 p 0 k ) D 1 γ g γ0 g γ0 (Y k ) + n k=1 (D 2 (γ1,γ2) p 0 k ) D 1 γ g γ0 g γ0 (Y k )
so that using assumptions ( 14)

sup θ∈Un |T n (θ)| = O P θ 0 n -1/4 + O P θ 0 (1) + O n -1/4 Z n with Z n = 1 √ n n k=1      D 1 γ g γ0 g γ0 (Y k ) 2 + D 2 γ 2 g γ0 g γ0 (Y k )   D 1 γ1 p 0 k + D 1 γ g γ0 g γ0 (Y k ) D 2 (γ1) 2 p 0 k + D 2 (γ2) 2 p 0 k + D 2 (γ1,γ2) p 0 k    . Now using (33) one gets that for all integer k ≥ 1, 1 1 -p -q D 2 (γ1) 2 p 0 k+1 = -2 pq 2 (p + q) 3 D 1 γ g γ0 g γ0 (Y k ) 2 +2(D 1 γ1 p 0 k ) D 1 γ g γ0 g γ0 (Y k )+ pq (p + q) 2 D 2 γ 2 g γ0 g γ0 (Y k )+D 2 (γ1) 2 p 0 k , 1 1 -p -q D 2 (γ2) 2 p 0 k+1 = 2 p 2 q (p + q) 3 D 1 γ g γ0 g γ0 (Y k ) 2 -2(D 1 γ1 p 0 k ) D 1 γ g γ0 g γ0 (Y k )- pq (p + q) 2 D 2 γ 2 g γ0 g γ0 (Y k )+D 2 (γ2) 2 p 0 k , 1 1 -p -q D 2 (γ1,γ2) p 0 k+1 = 2 pq(q -p) (p + q) 3 D 1 γ g γ0 g γ0 (Y k ) 2 + 2(D 1 γ1 p 0 k ) D 1 γ g γ0 g γ0 (Y k ) + D 2 (γ1,γ2) p 0 k ,
imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013 and using D 2 (γ1) 2 p 0 1 = 0, D 2 (γ2) 2 p 0 1 = 0, D 2 (γ1,γ2) p 0 1 = 0 and easy but tedious computations one gets that for some finite C > 0,

E θ0 Z 2 n ≤ CE θ0 D 1 γ g γ0 g γ0 (Y 1 ) 2   Eθ 0 D 1 γ g γ0 g γ0 (Y 1 ) 4 + E θ0 D 2 γ 2 g γ0 g γ0 (Y 1 ) 2 +   E θ0 D 1 γ g γ0 g γ0 (Y 1 ) 2   2    so that we finally obtain sup θ∈Un |T n (θ)| = O P θ 0 (1) . (37)
Let us finally study the fourth order remainder R n (θ, t). We have

sup θ∈Un |R n (θ, t)| ≤ 1 n n k=1 A k,n B k,n ,
where, for big enough n, A k,n is a polynomial of degree at most 4 in sup γ ∈B d (γ 0 , )

D i γ g γ g γ (Y k ) , and B k,n is a sum of terms of form sup θ∈Un 4 i=1 i j=0 D i (γ1) j ,(γ2) i-j p k (θ t ) ai,j (38)
where the a i,j are non negative integers such that for some finite C > 0. Now, using (33) one gets that for all integer k ≥ 1 and for any θ,

D 1 γ1 p k+1 (θ) = (1 -p -q) p k (θ)(1 -p k (θ))g γ2 (Y k )D 1 γ g γ1 (Y k ) + g γ1 (Y k )g γ2 (Y k )D 1 γ1 p k (θ) (p k (θ)g γ1 (Y k ) + (1 -p k (θ))g γ2 (Y k )) 2 , D 1 γ2 p k+1 (θ) = (1 -p -q) -p k (θ)(1 -p k (θ))g γ1 (Y k )D 1 γ g γ2 (Y k ) + g γ1 (Y k )g γ2 (Y k )D 1 γ2 p k (θ) (p k (θ)g γ1 (Y k ) + (1 -p k (θ))g γ2 (Y k )) 2 .
imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013

Notice that for any θ, any k ≥ 2, p k (θ) ∈ (1 -p, q) so that for any θ ∈ U n , any k ≥ 2, p k (θ) ∈ [ 1 2 -, 1 2 + ]. We obtain easily that for i = 1, 2, k ≥ 2, Using similar tricks, it is possible to get that there exists a finite constant C > 0 such that for any i = 1, 2, 3, 4, any j = 0, . . . , i, any k ≥ 2, which concludes the proof of (39). Now, using (32), ( 34), ( 35), ( 36), ( 37) and ( 39), we get D n ≥ e -O P θ 0

(1) Π 2 (U n ) so that (20) holds with S n satisfying (29).

Proof of Theorem 4

The proof follows the same lines as in [START_REF] Ghosal | Convergence rates of posterior distributions for non iid observations[END_REF]. We write

P Π f l,θ -f l,θ0 1 ρ θ -1 2R θ + ρ θ -1
≥ n |Y 1:n = An×X e n (θ,x)-n (θ0,x0) Π Θ (dθ)π X (dx)

Θ×X e n(θ,x)-n(θ0 ,x0) Π Θ (dθ)π X (dx)

:= N n D n ,
where A n = {θ : f l,θ -f l,θ0 1 ρ θ -1 2R θ +ρ θ -1 ≥ n }. A lower bound on D n is obtained in the following usual way. Set Ω n = {(θ, x); n (θ, x)n (θ 0 , x 0 ) ≥ -n˜ 2 n }, which is a random subset of Θ × X (depending on Y 1:n ), ≤ 2 Sn P θ0 n (θ, x)n (θ 0 , x 0 ) ≤ -n˜ 2 n Π Θ (dθ)π X (dx) Π(S n ) = o(1), and

P Π f l,θ -f l,θ0 1 ρ θ -1 2R θ + ρ θ -1 ≥ n |Y 1:n = o P θ 0 (1) + N n D n 1l 2Dn≥e -n˜ 2 n Π(Sn) .
But

N n = (An∩Fn)×X
e n (θ,x)-n(θ0,x0) Π Θ (dθ)π X (dx)+

(An∩F c n )×X
e n (θ,x)-n (θ0,x0) Π Θ (dθ)π X (dx)

and

E θ0 (An∩F c n )×X e n (θ,x)-n (θ0,x0) Π Θ (dθ)π X (dx) = O [Π Θ (A n ∩ F c n )] = o e -n˜ 2 n (Cn+1)
by Fubini's theorem and assumption C2 together with the fact that n (θ 0 )n (θ 0 , x 0 ) is uniformly upper bounded. This implies using assumption C1 that

P Π f l,θ -f l,θ0 1 ρ θ -1 2R θ + ρ θ -1 ≥ n |Y 1:n = o P θ 0 (1) + Ñn D n 1l 2Dn≥e -n˜ 2 n Π(Sn) (40)
where Ñn = (An∩Fn)×X e n (θ,x)-n (θ0,x0) Π Θ (dθ)π X (dx). Let now (θ j ) j=1,...,N , N = N (δ, F n , d l (., .)), be the sequence of θ j 's in F n such for all θ ∈ F n there exists a θ j with d l (θ j , θ) ≤ δ with δ = n /12. Assume for simplicity's sake and without loss of generality that n is a multiple of the integer l, and define

φ j = 1l n/l i=1
1l (Y li-l+1 ,...,Y li )∈A j -P θ 0 ((Y1,...,Y l )∈Aj ) >tj where A j = {(y 1 , . . . , y l ) ∈ Y l : f l,θ0 (y 1 , . . . , y l ) ≤ f l,θj (y 1 , . . . , y l )} for some positive real number t j to be fixed later also. Note that

P θj ((Y 1 , . . . , Y l ) ∈ A j ) -P θ0 ((Y 1 , . . . , Y l ) ∈ A j ) = 1 2 f l,θj -f l,θ0 1
Define also ψ n = max

E

  is enough to prove that E θ0 | n k=1 A k,n B k,n | = O(n). But for each k, p k (θ)and its derivatives depend on Y 1 , . . . , Y k-1 only, so that A k,n and B k,n are independent random variables, andE θ0 n k=1 A k,n B k,n ≤ n k=1 E θ0 |A k,n | E θ0 |B k,n | ≤ C max i=1,2,3,4 E θ0 sup γ ∈B d (γ 0 , ) θ0 |B k,n |

  j ,(γ2) i-j p k+1 (θ) ≤ C sup γ ∈B d (γ 0 , ) j ,(γ2) l-j p k (θ) i+1-lBy recursion, we obtain that there exists a finite C > 0 such that any term of form (38) has expectation uniformly bounded: j ,(γ2) i-j p k (θ t )

1l

  Ωn e n (θ,x)-n (θ0,x0) Π Θ (dθ)π X (dx) ≥ e -n˜ 2 n Π(S n ∩ Ω n ),imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013 thereforeP θ0 D n < e -n˜ 2 n Π(S n )/2 ≤ P θ0 [Π(S n ∩ Ω c n ) ≥ Π(S n )/2]

  n ≤ E θ0 ψ n ≤ N (δ, F n , d(., .)) max 1≤j≤N :θj ∈An E θ0 φ j(41) andE θ0 Ñn (1 -ψ n ) = X E θ0,x0 Ñn (1 -ψ n ) µ θ0 (dx 0 ) = (An∩Fn)×X E θ,x ((1 -ψ n )) Π Θ (dθ) π X (dx) (42) Now E θ0 [φ j ] = P θ0 li-l+1 ,...,Y li )∈Aj -P θ0 ((Y 1 , . . . , Y l ) ∈ A j ) > t j   and E θ,x (1 -φ j ) = P θ,x Y li-l+1 ,...,Y li )∈Aj + P θ,x ((Y li-l+1 , . . . , Y li ) ∈ A j ) > -t j + n/l i=1 (P θ,x ((Y li-l+1 , . . . , Y li ) ∈ A j ) -P θ0 ((Y 1 , . . . , Y l ) ∈ A j ))   . Consider the sequence (Z i ) i≥1 with for all i ≥ 1, Z i = (X li-l+1 , . . . , X li , Y li-l+1 , . . . , Y li ),which is, under P θ , a Markov chain with transition kernel Qθ given by Qθ (z, dz ) = g θ (y1 |x 1 ) • • • g θ (y l |x l )Q θ (x l , dx 1 )Q θ (x 1 , dx 2 ) • • • Q θ (x l-1 , dx l )µ(dy 1 ) • • • µ(dy l ).This kernel satisfies the same uniform ergodic property as Q θ , with the same coefficients, that is condition (17) holds with the coefficients R θ and ρ θ with the replacement of Q θ by Qθ , and we may use[START_REF] Rio | Inégalités de Hoeffding pour les fonctions lipschitziennes de suites dépendantes[END_REF]'s exponential inequality (corollary 1) with uniform mixing coeficients (as defined in[START_REF] Rio | Inégalités de Hoeffding pour les fonctions lipschitziennes de suites dépendantes[END_REF]) satisfying φ(m) ≤ R θ ρ -m θ . Indeed, by the Markov property, φ(m) = sup A∈σ(Z1),B∈σ(Zm+1)(P θ (B) -P θ (B|A)) ≤ sup z |P θ (Z m+1 ∈ B) -P θ (Z m+1 ∈ B|Z 1 = z)| ≤ R θ ρ -m θ .We thus obtain that, for any positive real number u, li-l+1 ,...,Y li )∈Aj -P θ0 ((Y 1 , . . . , Y l ) ∈ A j ) ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013

  bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013 and the theorem follows when A3 holds. If now A3bis holds instead of A3, one gets, taking u n

imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013

Acknowledgements

The authors would like to thank the anonymous referees for providing constructive comments that where very helpful to improve the readability of the paper.

* This work was partly supported by the 2010-2014 grant ANR Banhdits AAP Blanc SIMI 1.

This leads to

A simple recursive argument implies that b I = 0 for all I ∈ {1, . . . , t k0 } l which in turns implies that a I = 0 for all I ∈ {1, . . . , t k0 } l and condition A4bis is verified.

Proof of Theorem 3

First we obtain Lemma 2 Under the assumptions of Theorem 3, for any sequence M n tending to infinity,

We prove Lemma 2 by applying Theorem 4, using some of the computations of the proof of Theorem 1 but verifying assumption C3bis instead of C3. Set S n = U n × X with

for small but fixed . We shall prove later the following:

Lemma 3 Let M n tend to infinity. Then

Now we prove that assumption C3bis holds with n = M n / √ n, which will finish the proof of Lemma 2.By Proposition 1 we obtain that there exists c(θ 0 ) > 0 and η > 0 such that: and

(44) Set now

Since for any θ, ρ θ -1 2R θ +ρ θ -1 ≤ 1 and since consequently for θ j ∈ A n , f l,θj -f l,θ0 1 ≥ n , we first get, using ( 43),

Now, for any θ ∈ A n ,

for large enough n, using the triangular inequality and the fact that

imsart-bj ver. 2012/08/31 file: HMM-rev2.tex date: July 9, 2013

Combining (40), with ( 41), ( 45), ( 42), ( 46) and using assumptions C1 and C3 we finally obtain for large enough n

Assume now that Assumption C3bis holds. By writing A n ∩ F n = m≥1 A n,m ( n ) and using same reasoning, one gets, for some positive constant c:

and the second part of Theorem 4 is proved.