Léa Longepierre
email: lea.longepierre@sorbonne-universite.fr

Catherine Matias
email: catherine.matias@sorbonne-universite.fr

Consistency of the maximum likelihood and variational estimators in a dynamic stochastic block model

Keywords: maximum likelihood estimation, dynamic network, dynamic stochastic block model, variational estimation, temporal network

We consider a dynamic version of the stochastic block model, in which the nodes are partitioned into latent classes and the connection between two nodes is drawn from a Bernoulli distribution depending on the classes of these two nodes. The temporal evolution is modeled through a hidden Markov chain on the nodes memberships. We prove the consistency (as the number of nodes and time steps increase) of the maximum likelihood and variational estimators of the model parameters, and obtain upper bounds on the rates of convergence of these estimators. We also explore the particular case where the number of time steps is fixed and connectivity parameters are allowed to vary.

Introduction

Random graphs are a suitable tool to model and describe interactions in many kinds of datasets such as biological, ecological, social or transport networks. Here we are interested in time-evolving networks, which is a powerful tool for modeling real-world phenomena, where the role or behaviour of the nodes in the network and the relationships between them are allowed to change over time. Indeed, it is important to take into account the evolutionary behaviour of the graphs, instead of just studying separate snapshots as static graphs. We focus on graphs evolving in discrete time and refer to [START_REF] Holme | Modern temporal network theory: a colloquium[END_REF] for an introduction to dynamic networks.

A myriad of dynamic graph models has been introduced in the past few years, see for instance [START_REF] Zhang | Random graph models for dynamic networks[END_REF]. We focus here on those which are based on the (static) stochastic block model [SBM, Holland et al., 1983] in which the nodes are partitioned into classes. In the SBM, class memberships of the nodes are represented by latent variables and the connection between two nodes is drawn from a distribution depending on the classes of these two nodes (a Bernoulli distribution in the case of binary graphs). A first dynamic version of the SBM with discrete time is proposed in [START_REF] Yang | Detecting communities and their evolutions in dynamic social networks-a Bayesian approach[END_REF]. There, the nodes are partitioned into Q classes and the graphs are binary or weighted. The nodes are allowed to change membership over time, and these changes are governed by independent Markov chains with values in the Q classes, while the connection probabilities are constant over time. [START_REF] Xu | Dynamic stochastic blockmodels for time-evolving social networks[END_REF] introduce a state-space model on the logit of the connection probabilities for dynamic (binary) networks with connection probabilities and group memberships varying over time. Unfortunately, their model presents parameter identifiability issues [START_REF] Matias | Statistical clustering of temporal networks through a dynamic stochastic block model[END_REF]. [START_REF] Xu | Stochastic block transition models for dynamic networks[END_REF] proposes a stochastic block transition model in which the presence or absence of an edge between two nodes at a particular time affects the presence or absence of such an edge at a future time. There, the nodes can change classes over time, new nodes can enter the network, and the connection probabilities are allowed to vary over time. The model in [START_REF] Matias | Statistical clustering of temporal networks through a dynamic stochastic block model[END_REF] and in [START_REF] Becker | Nonparametric identification in the dynamic stochastic block model[END_REF] is quite similar to that of [START_REF] Yang | Detecting communities and their evolutions in dynamic social networks-a Bayesian approach[END_REF] except that it allows the connection probabilities to vary and the latter is moreover nonparametric. [START_REF] Bartolucci | Dealing with reciprocity in dynamic stochastic block models[END_REF] extend the model of [START_REF] Yang | Detecting communities and their evolutions in dynamic social networks-a Bayesian approach[END_REF] to deal with different forms of reciprocity in directed graphs, by directly modeling dyadic relations and with the assumption that the dyads are conditionally independent given the latent variables. [START_REF] Paul | Consistent community detection in multi-relational data through restricted multi-layer stochastic blockmodel[END_REF] and [START_REF] Han | Consistent estimation of dynamic and multi-layer block models[END_REF] study multi-graph SBM, arising in settings including dynamic networks and multi-layer networks where each layer corresponds to a type of edge. In these two models, the nodes memberships stay constant over the layers. [START_REF] Pensky | Dynamic network models and graphon estimation[END_REF], [START_REF] Pensky | Spectral clustering in the dynamic stochastic block model[END_REF] study a dynamic SBM for undirected and binary edges where both connection probabilities and group memberships vary over time, assuming that the connection probabilities between groups are a smooth function of time. [START_REF] Xing | A state-space mixed membership blockmodel for dynamic network tomography[END_REF] and [START_REF] Ho | Evolving cluster mixed-membership blockmodel for time-varying networks[END_REF] introduce dynamic versions of the mixed-membership stochastic block model, allowing each actor to carry out different roles when interacting with different peers. [START_REF] Zreik | The dynamic random subgraph model for the clustering of evolving networks[END_REF] introduce the dynamic random subgraph model, given a known decomposition of the graph into subgraphs, in which the latent class membership depends on the subgraph membership and the edges are categorical variables, their types being sampled from a distribution depending on the latent classes of the two nodes. There, a state-space model is used to characterize the temporal evolution of the latent classes proportions.

As far as estimation is concerned, different methods of inference are proposed to estimate groups and model parameters. The maximum likelihood estimator (MLE) is not tractable in the SBM, thus neither in its dynamic versions. Variational methods are rather popular to approximate that MLE [START_REF] Xing | A state-space mixed membership blockmodel for dynamic network tomography[END_REF][START_REF] Ho | Evolving cluster mixed-membership blockmodel for time-varying networks[END_REF][START_REF] Han | Consistent estimation of dynamic and multi-layer block models[END_REF][START_REF] Paul | Consistent community detection in multi-relational data through restricted multi-layer stochastic blockmodel[END_REF][START_REF] Zreik | The dynamic random subgraph model for the clustering of evolving networks[END_REF][START_REF] Matias | Statistical clustering of temporal networks through a dynamic stochastic block model[END_REF][START_REF] Bartolucci | Dealing with reciprocity in dynamic stochastic block models[END_REF]. [START_REF] Yang | Detecting communities and their evolutions in dynamic social networks-a Bayesian approach[END_REF] rely on Gibbs sampling and simulated annealing. [START_REF] Pensky | Spectral clustering in the dynamic stochastic block model[END_REF] propose an estimator of the connection probabilities matrix at each time step by a discrete kernel-type method and obtain a clustering of the nodes thanks to spectral clustering on this estimated matrix. They also give an estimator for the number of clusters. Spectral clustering algorithms are also used by [START_REF] Han | Consistent estimation of dynamic and multi-layer block models[END_REF] on the mean graph over time and by [START_REF] Liu | Global spectral clustering in dynamic networks[END_REF] who use eigenvector smoothing to get some similarity across time periods (and allow the number of classes to be unknown and possibly varying over time).

Some theoretical results on the convergence of the procedures have been proven, mainly for static graphs. In the static SBM, [START_REF] Celisse | Consistency of maximum-likelihood and variational estimators in the stochastic block model[END_REF] prove the consistency of the MLE and variational estimates as the number of nodes increases, and [START_REF] Bickel | Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels[END_REF] establish their asymptotic normality. [START_REF] Mariadassou | Convergence of the groups posterior distribution in latent or stochastic block models[END_REF] have a different approach and give sufficient conditions for the groups posterior distribution to converge to a Dirac mass located at the actual groups configuration, for every parameter in a neighborhood of the true one. [START_REF] Rohe | Spectral clustering and the high-dimensional stochastic blockmodel[END_REF] give asymptotic results on the normalized graph Laplacian and its eigenvectors for the spectral clustering algorithm, allowing the number of clusters to grow with the number of nodes. They also provide bounds on the number of misclustered nodes, requiring an assumption on the degree distribution. [START_REF] Lei | Consistency of spectral clustering in stochastic block models[END_REF] prove consistency for the recovery of communities in the spectral clustering on the adjacency matrix, with milder conditions on the degrees, and also extend this result to degree corrected stochastic block models. [START_REF] Klopp | Oracle inequalities for network models and sparse graphon estimation[END_REF] derive oracle inequalities for the connection probabilities estimator and obtain minimax estimation rates, including the sparse case where the density of edges converges to zero as the number of nodes increase thus extending previous results of [START_REF] Gao | Rate-optimal graphon estimation[END_REF]. [START_REF] Gaucher | Maximum likelihood estimation of sparse networks with missing observations[END_REF] propose a bound on the risk of the maximum likelihood estimator of network connection probabilities, and show that it is minimax optimal in the sparse graphon model.

In the dynamic setting, fewer theoretical results have been established. [START_REF] Pensky | Dynamic network models and graphon estimation[END_REF] derives a penalized least squares estimator of the connection probabilities adaptive to the number of blocks and which does not require knowledge of the number of classes Q. She shows that it satisfies an oracle inequality. Under the additional assumption that at most n 0 nodes change groups between two time steps, this estimator attains minimax lower bounds for the risk. She also introduces a dynamic graphon model and shows that the estimators (that do not require knowledge of a degree of smoothness of the graphon function) are minimax optimal within a logarithmic factor of the number of time steps. Based on the same dynamic SBM with at most n 0 nodes changing groups between two time steps, [START_REF] Pensky | Spectral clustering in the dynamic stochastic block model[END_REF] give an upper bound for the (non asymptotic) error of their estimators of the connection probabilities matrix and group memberships (and also an estimator for the number of clusters). [START_REF] Han | Consistent estimation of dynamic and multi-layer block models[END_REF] show consistency (as the number of time steps increases but the number of nodes is fixed) of two estimators of the class memberships for dynamic SBM (and more generally multi-graph SBM) in which the nodes memberships are constant over time but the connection probabilities are allowed to vary and the considered graphs are binary and symmetric. They show that the spectral clustering (on the mean graph over time) estimator of the class memberships is consistent under some stationarity and ergodicity conditions on the connection probabilities. They also prove that the MLE of the class memberships is consistent (i.e. that the fraction of misclustered nodes converges to 0) in the general case (without any structure on the connection probabilities), provided certain sufficient conditions are satisfied. In their multi-layer model, [START_REF] Paul | Consistent community detection in multi-relational data through restricted multi-layer stochastic blockmodel[END_REF] give minimax rates of misclassification under certain conditions on the growth of the types of relations, number of nodes and number of classes, extending the result of [START_REF] Han | Consistent estimation of dynamic and multi-layer block models[END_REF].

Here, we consider a dynamic version of the binary SBM as in [START_REF] Yang | Detecting communities and their evolutions in dynamic social networks-a Bayesian approach[END_REF], where each node is allowed to change group membership at each time step according to a Markov chain, independently of other nodes. We prove the consistency of the connectivity parameter MLE and, under some additional conditions, of the transition matrix MLE, when the number of nodes and of time steps are increasing. We also give upper bounds on the rates of convergence of these estimators. While these upper bounds are known to be non optimal in the static case where asymptotic normality is obtained with classical parametric rates of convergence [START_REF] Bickel | Asymptotic normality of maximum likelihood and its variational approximation for stochastic blockmodels[END_REF], these are the first to be established in a dynamic setting for the MLE. As already mentioned, the log-likelihood is intractable (except for very small values of the number of nodes n and the number of time steps T ), as it requires to sum over Q nT terms. Thus, while its consistency remains an important result, the estimator cannot be computed. A possible alternative is to rely on a variational estimator to approximate the MLE [see for instance [START_REF] Matias | Statistical clustering of temporal networks through a dynamic stochastic block model[END_REF]. We also establish the consistency of the variational estimator of the connectivity parameter and under some additional assumptions, that of the variational estimator of the transition matrix and obtain the same upper bounds on the rates of convergence as for the MLE. In the particular case where the number of time steps T is fixed, we also consider the model of [START_REF] Matias | Statistical clustering of temporal networks through a dynamic stochastic block model[END_REF], in which the connection probabilities are allowed to vary over time and generalise these results with only the number of nodes increasing. When T = 1, we not only recover the results of [START_REF] Celisse | Consistency of maximum-likelihood and variational estimators in the stochastic block model[END_REF] but extend these by giving rates of convergence. Unlike the model studied in [START_REF] Han | Consistent estimation of dynamic and multi-layer block models[END_REF] and [START_REF] Paul | Consistent community detection in multi-relational data through restricted multi-layer stochastic blockmodel[END_REF], the node memberships in our model evolve over time. Our context is different from [START_REF] Pensky | Dynamic network models and graphon estimation[END_REF] that focuses on least squares estimate.

This article is organized as follows. Section 2 introduces our model and notation. More precisely, Section 2.1 describes the dynamic stochastic block model as introduced in [START_REF] Yang | Detecting communities and their evolutions in dynamic social networks-a Bayesian approach[END_REF], Section 2.2 gives the assumptions we make on the model parameters, Section 2.3 describes the dynamic stochastic block model as in [START_REF] Matias | Statistical clustering of temporal networks through a dynamic stochastic block model[END_REF] for the finite time case and Section 2.4 states the expression of the likelihood of this model to define the MLE. Section 3 establishes the consistency and upper bounds of the rates of convergence for the MLE of the connection probabilities in Section 3.1 and of the transition matrix in Section 3.2. Section 4 is dedicated to variational estimators: Section 4.1 and 4.2 establish the consistency of the variational estimators of the connection probabilities and transition matrix, respectively, along with upper bounds of the associated rates of convergence. All the proofs of the main results are postponed to Section 5, except those for the fixed T case that are in Appendix A, while the more technical proofs are deferred to Appendix B.

Model and notation

Dynamic stochastic block model

We consider a set of n vertices, forming a sequence of binary undirected graphs with no self-loops at each time t = 1, . . . , T . The case of a set of directed graphs, with or without self-loops, may be handled similarly. These vertices are assumed to be split into Q latent classes, and we denote by Z t i the label of the i-th vertex at time t.

Letting Z i = (Z 1 i , . . . , Z T i )
, we assume that the {Z i } 1≤i≤n are independent and identically distributed (iid) and each Z i is a homogeneous and stationary Markov chain with transition probabilities

P(Z t+1 i = l | Z t i = q) = γ ql , ∀1 ≤ q, l ≤ Q
where Γ = (γ ql ) 1≤q,l≤Q is a stochastic matrix, i.e. with nonnegative coefficients and with each row summing to 1. We let α = (α 1 , . . . , α Q ) the stationary distribution of the Markov chain. For any i ∈ 1, n , the probability distribution of Z i is then

P θ (Z i ) = α Z 1 i T -1 t=1 γ Z t i Z t+1 i .
We will also denote

Z t = (Z t 1 , . . . , Z t n ) and Z 1:T = (Z 1 , . . . , Z T ) = (Z t i ) 1≤t≤T,1≤i≤n . Consider X t = {X t i j } 1≤i
, j≤n the symmetric binary adjacency matrix of the graph at time t such that for every nodes 1 ≤ i, j ≤ n, we have X t ii = 0 and X t i j = X t ji . Each X t follows a stochastic block model so that, conditional on the latent groups {Z t i } 1≤i≤n , the {X t i j } 1≤i, j≤n are independent Bernoulli random variables

X t i j | Z t i = q, Z t j = l ∼ B(π ql )
where (π ql ) 1≤q,l≤Q ∈ [0, 1] Q 2 are the connectivity parameters. More precisely, conditional on the whole sequence of latent groups {Z t i } 1≤t≤T,1≤i≤n , the graphs X 1:T = X 1 , . . . , X T are assumed to be independent, each X t having a distribution depending only on {Z t i } 1≤i≤n . The model is thus parameterized by θ = (Γ, π), with Γ = (γ ql ) 1≤q,l≤Q and π = (π ql ) 1≤q,l≤Q . Note that π is a symmetric matrix in the undirected setup. We denote by P θ (resp. E θ ) the probability distribution (resp. expectation) of all the random variables {Z t i , X t i j } t≥1;i, j≥1 , under the parameter value θ. In the following, we assume that we observe {X t i j } 1≤i, j,≤n, 1≤t≤T and we denote by θ * = (Γ * , π * ) = ((γ * ql ) 1≤q,l≤Q , (π * ql ) 1≤q,l≤Q ) the true parameter value, with corresponding probability distribution P θ * and expectation E θ * , and by α * = (α * q ) 1≤q≤Q the (true) stationary distribution corresponding to the transition matrix Γ * . We also let 1 A denote the indicator function of the set A and A c the complementary set of A in the ambient set. For any integer M ≥ 1, the set 1, M is the set of integers between 1 and M. For any finite set A, let |A| denote its cardinality. For any configuration z 1:T , we denote N q (z t ) (resp. N ql (z 1:T )) the number of nodes assigned to class q by the configuration z t (resp. the number of transitions from class q to class l in configuration z 1:T ), that is

N q (z t ) = |{i ∈ 1, n ; z t i = q}| and N ql (z 1:T ) = T -1 t=1 n i=1 1 z t i =q,z t+1 i =l . (1)
We also define for any two parameters θ = (Γ, π) and θ ′ = (Γ ′ , π ′ ) the following distances

π -π ′ ∞ = max 1≤q,l≤Q |π ql -π ′ ql | and Γ -Γ ′ ∞ = max 1≤q,l≤Q |γ ql -γ ′ ql |.

Assumptions

The assumptions we make on the model parameters are the following.

1. For every 1 ≤ q q ′ ≤ Q, there exists some l ∈ 1, Q such that π ql π q ′ l .

2. There exists some 0 < δ < 1/Q such that for any (q, l) ∈ 1, Q 2 , we have

γ ql ∈ [δ, 1 -δ].
3. There exists some ζ > 0 such that for any (q, l) ∈ 1, Q 2 , we have

π ql ∈ [ζ, 1 -ζ].
Assumption 1 is necessary for identifiability of the model. Indeed, if it does not hold, we cannot distinguish between classes q and q ′ . Assumption 2 ensures that each Markov chain Z i is irreducible, aperiodic and recurrent. This assumption could be weakened at the cost of technicalities. In particular, it implies that the stationary distribution α exists. Moreover, Assumption 2 also implies that for any q ∈ 1, Q , we have α q ∈ [δ, 1δ]. Note that this can be seen as an equivalent of Assumption 2 in [START_REF] Celisse | Consistency of maximum-likelihood and variational estimators in the stochastic block model[END_REF] (on the probability distribution of the class memberships) in the dynamic case. [START_REF] Celisse | Consistency of maximum-likelihood and variational estimators in the stochastic block model[END_REF] however also have an additional assumption that is an empirical version of this assumption (which states that the observed class proportions are bounded away from 0) that is true with high probability. We do not make such an assumption and use the fact that the probability of this event converges to 1. Assumption 3 is technical and could also be weakened with additional technicalities. For example, [START_REF] Celisse | Consistency of maximum-likelihood and variational estimators in the stochastic block model[END_REF] also consider the case

π ql ∈ {0, 1} (i.e. π ql ∈ {0, 1} ∪ [ζ, 1 -ζ]) whereas we do not.
The whole parameter set defined by these constraints is denoted by Θ. In the following, we assume that θ * ∈ Θ.

In what follows, we work up to label permutation on the groups. Indeed, as in any latent group model, the parameters can only be recovered up to label switching on the latent groups. We then define the following notation for any permutation σ ∈ S Q with S Q the set of permutations on 1, Q θ σ = (Γ σ , π σ ) = (γ σ(q)σ(l) ) 1≤q,l≤Q , (π σ(q)σ(l) ) 1≤q,l≤Q .

Finite time case

If the number of time steps T is fixed, it is possible to let the connection probabilities vary over time. We then consider this case, the connection parameter now being π 1:T = (π 1 , . . . , π T ) with π t = (π t ql ) 1≤q,l≤Q for every t ∈ 1, T and π t ql = P θ (X t i j = 1 | Z t i = q, Z t j = l) for any (t, q, l) ∈ 1, T × 1, Q 2 . Note that this is the more general model of [START_REF] Matias | Statistical clustering of temporal networks through a dynamic stochastic block model[END_REF], in which the model parameter is θ = (Γ, π 1:T ). Moreover, we introduce the following Assumptions 1' and 3' that are alternate versions of Assumptions 1 and 3 respectively for the finite time case.

1'. For every t ∈ 1, T , for every 1 ≤ q q ′ ≤ Q, there exists some l ∈ 1, Q such that π t ql π t q ′ l .

3'. There exists some ζ > 0 such that for every t ∈ 1, T , for any (q, l) ∈ 1, Q 2 , we have

π t ql ∈ [ζ, 1 -ζ].
Assumption 1' (resp. Assumption 3') expresses that for every t ∈ 1, T , π t satisfies Assumption 1 (resp. Assumption 3). We also introduce the following additional assumption, which ensures (together with Assumption 1') that the model is identifiable (up to a label permutation). See [START_REF] Matias | Statistical clustering of temporal networks through a dynamic stochastic block model[END_REF].

For every

q ∈ 1, Q , for every t 1 , t 2 ∈ 1, T , π t 1 qq = π t 2 qq ≔ π qq and {π qq ; q ∈ 1, Q } are Q distinct values.
Assumption 4 states that the diagonal of π does not change over time, and that its values are distinct. We denote by Θ T the set of parameters satisfying Assumptions 1', 2, 3' and 4. As before, we assume in the following that θ * ∈ Θ T in the fixed T case. We also define as before for any π 1:T and π ′1:T the distance

π 1:T -π ′1:T ∞ = max (q,l,t)∈ 1,Q 2 × 1,T |π t ql -π ′t ql |.

Likelihood

The conditional log-likelihood and the log-likelihood write

ℓ c (θ; Z 1:T ) = log P θ (X 1:T | Z 1:T ) = T t=1 log P θ (X t | Z t ) = T t=1 1≤i< j≤n X t i j log π Z t i Z t j + (1 -X t i j ) log(1 -π Z t i Z t j ) and ℓ(θ) = log P θ (X 1:T ) = log          z 1:T ∈ 1,Q nT e ℓ c (θ;z 1:T ) P θ (Z 1:T = z 1:T )          , (2)
respectively. We then denote the maximum likelihood estimator (MLE) by

θ = ( Γ, π) = argmax θ∈Θ ℓ(θ).
In the next section, we study separately the consistency of the connectivity parameter estimator π and that of the transition matrix estimator Γ.

3 Consistency of the maximum likelihood estimate

Connectivity parameter

We first prove the consistency of the maximum likelihood estimator of the connectivity parameter π = (π ql ) 1≤q,l≤Q when the number of nodes and time steps increase. We denote the normalized log-likelihood by

M n,T (Γ, π) = 2 n(n -1)T ℓ(θ) = 2 n(n -1)T log P θ (X 1:T )
and introduce the quantities, for any

A = (a ql ) 1≤q,l≤Q ∈ A the set of Q × Q stochastic matrices, M(π, A) = 1≤q,l≤Q α * q α * l 1≤q ′ ,l ′ ≤Q a qq ′ a ll ′ [π * ql log π q ′ l ′ + (1 -π * ql ) log(1 -π q ′ l ′ )]
and

M(π) = sup A∈A M(π, A) = M(π, Āπ ), (3)
where Āπ = argmax A∈A M(π, A). It is worth noticing that M(π), which will be the limiting value for M n,T (Γ, π) when n and T increase (see below), does not depend on Γ.

Theorem 1. For any sequence {r n,T } n,T ≥1 increasing to infinity, if log(T ) = o(n), we have for all ǫ > 0

P θ * sup (Γ,π)∈Θ M n,T (Γ, π) -M(π) > ǫr n,T √ n ------→ n,T →+∞ 0.
We then conclude on the consistency of the maximum likelihood estimator of the connection probabilities with the following corollary. Note that we also obtain an upper bound of the rate of convergence of this estimator.

Corollary 1. For any sequence {r n,T } n,T ≥1 increasing to infinity such that r n,T = o(n 1/4 ) and if log(T ) = o(n), we have for every ǫ > 0

P θ * min σ∈S Q π * -πσ ∞ > ǫr n,T n 1/4 -----→ n,T →∞ 0.
We want to get equivalent consistency results if the number of time steps T is fixed and only the number of nodes n increases. In that case, denoting by θ = ( Γ, π1:T ) the MLE of θ, we have the following Corollary that is the equivalent of Corollary 1.

Corollary 2. If the number of time steps T is fixed, we have for every ǫ > 0 and for any sequence {r n } n≥1 increasing to infinity such that r n = o(n 1/4 )

P θ * min σ∈S Q π * 1:T -π1:T σ ∞ > ǫr n n 1/4 ----→ n→∞ 0, denoting π1:T σ = ( πt σ ) t∈ 1,T .
This result states that min σ∈S Q π * 1:T -π1:T σ ∞ converges to 0 in P θ * -probability as n increases, i.e. the MLE of the connection probabilities is consistent up to label switching, and gives an upper bound of the rate of convergence of the MLE of the connection probabilities. The particular case when T = 1 is then a stronger result than that of [START_REF] Celisse | Consistency of maximum-likelihood and variational estimators in the stochastic block model[END_REF] where no rate of convergence is given.

Remark 1. Note that in Corollaries 1 and 2, the results still hold for any sequences r n,T and r n increasing to infinity, respectively. However, we are interested in sequences increasing slowly to infinity, giving the strongest results, namely the smallest lower bounds. Indeed, whenever these assumptions are not satisfied, the lower bounds appearing in the inequalities are larger, and the results may even become trivial.

Latent transition matrix

We now prove that the MLE for the transition matrix Γ is consistent when the number of nodes and time steps increase.

Lemma 1. Any critical point θ = ( Γ, π) of the likelihood function ℓ(•) is such that Γ satisfies the fixed point equation

∀(q, l) ∈ 1, Q 2 , γql = T -1 t=1 n i=1 P θ Z t i = q, Z t+1 i = l | X 1:T T -1 t=1 n i=1 P θ Z t i = q | X 1:T . ( 4
)
There are two different possible cases for the MLE θ

• Either θ is a critical point of the likelihood function. Then Γ satisfies equation (4).

• Or θ is not a critical point (this can happen if it belongs to the boundary of Θ) and we assume that there exists Γ such that ( Γ, π) ∈ Θ and ( Γ, π) satisfies equation (4) (at least for n and T large enough). We then choose as our estimator ( Γ, π). By an abuse of notation, we will denote this estimator θ = ( Γ, π) and call it MLE in the following.

In what follows, for any fixed configuration z 1:T , any θ ∈ Θ and any ǫ > 0, we consider the event

E(z 1:T , θ, ǫ) ≔ P θ (Z 1:T z 1:T | X 1:T ) P θ (Z 1:T = z 1:T | X 1:T ) > ǫ .
The following result establishes that asymptotically, any estimator that correctly estimates the transition probability matrix π also recovers the group memberships. This result is similar to Theorem 1 in [START_REF] Mariadassou | Convergence of the groups posterior distribution in latent or stochastic block models[END_REF].

Theorem 2. For any estimator θ ∈ Θ (at least for n and T large enough), if log(T ) = o(n), there exist some positive constants C, C 1 , C 2 , C 3 , C 4 such that for any ǫ > 0, for any positive sequence {y n,T } n,T ≥1 such that log(1/y n,T ) = o(n), any η ∈ (0, δ) and for n and T large enough, we have

P θ * E(Z 1:T , θ, ǫy n,T ) ≤ QT exp(-2η 2 n) + P θ * π -π * ∞ > v n,T + CnT        exp -(δ -η) 2 C 1 n + C 2 log(nT ) -C 4 log(ǫy n,T ) + exp -C 3 (log(nT )) 2 nv 2 n,T + 3n log(nT )        , whenever {v n,T } n,T ≥1 is a sequence decreasing to 0 such that v n,T = o( log(nT )/n).
Theorem 3. If log(T ) = o(n), for any ǫ > 0 and {r n,T } n,T ≥1 any sequence increasing to infinity such that r n,T = o nT/ log n , we have for any σ ∈ S Q

P θ *        Γσ -Γ * ∞ > ǫr n,T log n √ nT        ≤ Q 2 (3Q + 1)P θ * πσ -π * ∞ > v n,T + o(1)
with {v n,T } n,T ≥1 a sequence decreasing to 0 such that v n,T = o( log(nT )/n).

Corollary 3. Assume that log(T ) = o(n) and min σ∈S Q πσ -π * ∞ = o P θ * (v n,T
) with {v n,T } n,T ≥1 a sequence decreasing to 0 such that v n,T = o( log(nT )/n). Then for any ǫ > 0 and {r n,T } n,T ≥1 any sequence increasing to infinity such that r n,T = o nT/ log n , we have the convergence

P θ *        min σ∈S Q Γσ -Γ * ∞ > ǫr n,T log n √ nT        -----→ n,T →∞ 0.
Remark 2. Note that the upper bound obtained in Corollary 1 on the rate of convergence in probability of π does not ensure that min σ∈S Q πσπ * ∞ = o P θ * (v n,T ) holds. While the latter has never been established (to our knowledge), it is a reasonable assumption.

We want an equivalent result than that of Corollary 3 when the number of time steps T is fixed, and the connection probabilities are varying over time (the connection parameter being π = π 1:T = (π 1 , . . . , π T ) with π t = (π t ql ) q,l ). For that, we are going to need an equivalent of Theorem 2 in that case. Theorem 4. For any fixed T ≥ 2, for any estimator θ ∈ Θ T (at least for n large enough), there exist some positive constants C, C 1 , C 2 , C 3 , C 4 such that for any ǫ > 0, for any positive sequence {y n } n≥1 such that log(1/y n ) = o(n), any η ∈ (0, δ) and for n large enough, we have

P θ * E(Z 1:T , θ, ǫy n ) ≤ QT exp(-2η 2 n) + P θ * π1:T -π * 1:T ∞ > v n + CnT exp -(δ -η) 2 C 1 n + C 2 log(nT ) -C 4 log(ǫy n ) + exp -C 3 (log(nT )) 2 nv 2 n + 5n log(nT ) , whenever {v n } n≥1 is a sequence decreasing to 0 such that v n = o( log(n)/n).
The following corollary gives the expected result.

Corollary 4. Let the number of time steps T ≥ 2 be fixed. Assume that

min σ∈S Q π1:T σ -π * 1:T ∞ = o P θ * (v n ) with {v n } n≥1 a sequence decreasing to 0 such that v n = o( log(n)/n).
Then for any ǫ > 0 and {r n } n≥1 any sequence increasing to infinity such that r n = o n/ log n , we have the convergence

P θ *        min σ∈S Q Γσ -Γ * ∞ > ǫr n log n √ n        ----→ n→∞ 0.
The proof of Corollary 4 is the same as that of Corollary 3, but relying on Theorem 4 instead of Theorem 2 and is therefore omitted.

Remark 3. As in Remark 1 for Corollaries 1 and 2, the results of Corollaries 3 and 4 still hold for sequences r n,T and r n increasing to infinity at any rate.

Variational estimators

In practice, we cannot compute the MLE except for very small values of n and T , because it involves a summation over all the Q nT possible latent configurations. We cannot either use the Expectation-Maximization (EM) algorithm to approximate it because it involves the computation of the conditional distribution of the latent variables given the observations which is not tractable. A common solution is to use the Variational Expectation-Maximization (VEM) algorithm that optimizes a lower bound of the log-likelihood (see for example Daudin et al. [2008]). Let us denote Z t iq = 1 Z t i =q for every t, i and q. Using the same approach as in [START_REF] Matias | Statistical clustering of temporal networks through a dynamic stochastic block model[END_REF] for the VEM algorithm in the dynamic SBM, we consider a variational approximation of the conditional distribution of the latent variable Z 1:T given the observed variable X 1:T in the class of probability distributions parameterized by χ = (τ, η) = {τ t iq } t,i,q , {η t iql } t,i,q,l of the form

Q χ (Z 1:T ) = n i=1 Q χ (Z 1 i ) T t=2 Q χ (Z t i | Z t-1 i ) = n i=1                  Q q=1 (τ 1 iq ) Z 1 iq         T -1 t=1 1≤q,l≤Q        η t iql τ t iq        Z t iq Z t+1 il          , i.e. with Q χ such that E Q χ Z t iq Z t+1 il = η t iql and E Q χ Z t iq = τ t iq . Notice that Q χ (Z t+1 i = l | Z t i = q) = η t iql /τ t iq = η t iql / Q q ′ =1 η t iqq ′ .
The quantity to optimize in the VEM algorithm is then

J(χ, θ) = ℓ(θ) -KL(Q χ , P θ (•|X 1:T )) = E Q χ log P θ (X 1:T , Z 1:T ) + H(Q χ )
with KL(•, •) denoting the Kullback-Leibler divergence and H(•) denoting the entropy. Define

χ(θ) = (τ(θ), η(θ)) = argmax χ∈[0,1] T 2 n 2 Q 3 J(χ, θ),
and the variational estimator of θ θ = ( Γ, π) = argmax θ∈Θ J( χ(θ), θ).

Moreover, we denote χ = (τ, η) = χ( θ) = (τ( θ), η( θ)). In practice, the VEM algorithm is an iterative algorithm that maximizes the function J alternatively with respect to χ and θ in order to find θ.

Connectivity parameter

Theorem 5. For any sequence {r n,T } n,T ≥1 increasing to infinity, if log(T ) = o(n), we have for all ǫ > 0

P θ * sup θ∈Θ 2 n(n -1)T J( χ(θ), θ) -M(π) > ǫr n,T √ n -→ n,T →+∞ 0.
We conclude on the consistency of the connection probabilities variational estimators as n and T increase thanks to the following corollary.

Corollary 5. For any sequence {r n,T } n,T ≥1 increasing to infinity such that r n,T = o(n 1/4 ), we have for any ǫ > 0

1 2 P θ * min σ∈S Q πσ -π * ∞ > ǫr n,T n 1/4 -----→ n,T →∞ 0.
We have the equivalent following corollary for a fixed number of time steps.

Corollary 6. If the number of time steps T is fixed, we have for every ǫ > 0 and for any sequence {r n } n≥1 increasing to infinity such that r n = o(n 1/4 )

1 2 P θ * min σ∈S Q π1:T σ -π * 1:T ∞ > ǫr n n 1/4 ----→ n→∞ 0.
Remark 4. As for Corollaries 1 to 4, the results of Corollaries 5 and 6 still hold for any sequences r n,T and r n increasing to infinity.

Latent transition matrix

We now prove that Γ is consistent when the number of nodes and time steps increase.

Lemma 2. Any critical point ( χ, θ) of the function J(•, •) is such that Γ satisfies the fixed-point equation

∀(q, l) ∈ 1, Q 2 , γql = n i=1 T -1 t=1 ηt iql n i=1 T -1 t=1 τt iq . (5)
We assume that ( χ, θ) is a critical point of J(•, •). Then we have the fixed-point equation

∀(q, l) ∈ 1, Q 2 , γql = n i=1 T -1 t=1 ηt iql ( θ) n i=1 T -1 t=1 τt iq ( θ) . ( 6
)
The following proposition gives the consistency and a rate of convergence of this estimator, under an assumption on the rate of convergence of π.

Theorem 6. If log(T ) = o(n), for any ǫ > 0 and {r n,T } n,T ≥1 any sequence increasing to infinity such that r n,T = o nT/ log n and for any σ ∈ S Q

P θ *        Γσ -Γ * ∞ > ǫr n,T log n √ nT        ≤ 2Q 2 (3Q + 1)P θ * πσ -π * ∞ > v n,T + o(1)
with {v n,T } n,T ≥1 a sequence decreasing to 0 such that v n,T = o( log(nT )/n).

Corollary 7. Assume that log(T ) = o(n) and

min σ∈S Q πσ -π * ∞ = o P θ * (v n,T
) with {v n,T } n,T ≥1 a sequence decreasing to 0 such that v n,T = o( log(nT )/n). Then for any ǫ > 0 and {r n,T } n,T ≥1 any sequence increasing to infinity such that r n,T = o nT/ log n , we have the convergence

P θ *        min σ∈S Q Γσ -Γ * ∞ > ǫr n,T log n √ nT        -----→ n,T →∞ 0.
The proof of Corollary 7 is the same as that of Corollary 3, using Theorem 6 instead of Theorem 3 and is therefore omitted.

When the number of time steps T is fixed and the connection probabilities can vary over time, we have the following Corollary that is the equivalent of Corollary 7.

Corollary 8. Let the number of time steps T ≥ 2 be fixed. Assume that min σ∈S Q π1:T σπ * 1:T ∞ = o P θ * (v n ) with {v n } n≥1 a sequence decreasing to 0 such that v n = o( log(n)/n). Then for any ǫ > 0 and {r n } n≥1 any sequence increasing to infinity such that r n = o n/ log n , we have the convergence

P θ *        min σ∈S Q Γσ -Γ * ∞ > ǫr n log n √ n        ----→ n→∞ 0.
The proof of Corollary 8 is the same as that of Corollary 7, but relying on Theorem 4 instead of Theorem 2 and is therefore omitted.

Remark 5. As for Corollaries 1 to 6, the results of Corollaries 7 and 8 still hold for any sequences r n,T and r n increasing to infinity.

5 Proofs of main results

Proof of Theorem 1

The proof follows the lines of the proof of Theorem 3.6 in [START_REF] Celisse | Consistency of maximum-likelihood and variational estimators in the stochastic block model[END_REF]. Nonetheless, our result is sharper as we establish an upper bound of the rate of convergence (in probability) of the normalised likelihood. We fix some θ ∈ Θ and introduce the quantities ẑ1:T = argmax

z 1:T ∈ 1,Q nT log P θ (X 1:T | Z 1:T = z 1:T ), (7)
Z1:T = argmax

z 1:T ∈ 1,Q nT E θ * log P θ (X 1:T | Z 1:T = z 1:T ) Z 1:T . ( 8
)
Note that Z1:T is a random variable that depends on Z 1:T and that ẑ1:T = argmax

z 1:T ∈ 1,Q nT T t=1 log P θ (X t | Z t = z t ) = argmax z∈ 1,Q n log P θ (X 1 | Z 1 = z), . . . , argmax z∈ 1,Q n log P θ (X T | Z T = z) . (9)
Similarly, for any t ∈ 1, T , we have Zt

= argmax z∈ 1,Q n E θ * log P θ (X t | Z t = z) | Z t .
We bound the difference between M n,T (Γ, π) and M(π) by introducing three intermediate terms so that we can write, for any sequence {r n,T } n,T ≥1 and any ǫ > 0

P θ * sup θ∈Θ M n,T (Γ, π) -M(π) > ǫr n,T √ n ≤P θ * sup θ∈Θ 2 n(n -1)T log P θ (X 1:T ) - 2 n(n -1)T log P θ (X 1:T | Z 1:T = ẑ1:T ) > ǫr n,T 3 √ n + P θ * sup θ∈Θ 2 n(n -1)T log P θ (X 1:T | Z 1:T = ẑ1:T ) - 2 n(n -1)T E θ * log P θ (X 1:T | Z 1:T = Z1:T ) Z 1:T > ǫr n,T 3 √ n + P θ * sup θ∈Θ 2 n(n -1)T E θ * log P θ (X 1:T | Z 1:T = Z1:T ) Z 1:T -M(π) > ǫr n,T 3 √ n . ( 10
)
In the following, we prove separately the convergence (in P θ * -probability) to zero of the three terms of this sum (while controlling for the rate of these convergences). Before starting, let us remark that we have

log P θ (X 1:T | Z 1:T = z 1:T ) = T t=1 1≤i< j≤n X t i j log π z t i z t j + (1 -X t i j ) log(1 -π z t i z t j ) (11)
and

E θ * log P θ (X 1:T | Z 1:T = z 1:T ) Z 1:T = T t=1 1≤i< j≤n π * Z t i Z t j log π z t i z t j + (1 -π * Z t i Z t j ) log(1 -π z t i z t j ). ( 12
)
In particular, for every t ∈ 1, T , we have

ẑt = argmax z=(z 1 ,...,z n )∈ 1,Q n 1≤i< j≤n X t i j log π z i z j + (1 -X t i j ) log(1 -π z i z j ), Zt = argmax z=(z 1 ,...,z n )∈ 1,Q n 1≤i< j≤n π * Z t i Z t j log π z i z j + (1 -π * Z t i Z t j ) log(1 -π z i z j ).
First term of the right-hand side of (10). We let

T 1 ≔ 2 n(n -1)T log P θ (X 1:T ) - 2 n(n -1)T log P θ (X 1:T | Z 1:T = ẑ1:T ) ≤ 2 n(n -1)T T t=1 log P θ (X t | X 1:t-1 ) -log P θ (X t | Z t = ẑt ) . ( 13
)
Lemma 3. For every t ∈ 1, T , we have

log P θ (X t |X 1:t-1 ) -log P θ (X t |Z t = ẑt ) ≤ log P θ (Z t = ẑt |X 1:t-1 ) .
Going back to (13) and applying Lemma 3, we get

T 1 ≤ 2 n(n -1)T T t=1 log P θ (Z t = ẑt | X 1:t-1 ) = - 2 n(n -1)T T t=1 log P θ (Z t = ẑt | X 1:t-1 ).
Now, using classical dependency rules in directed acyclic graphs [see for e.g. [START_REF] Lauritzen | of Oxford Statistical Science Series[END_REF] combined with Assumption 2, we get

T 1 ≤ - 2 n(n -1)T T t=1 log z t-1 ∈ 1,Q n P θ (Z t = ẑt | Z t-1 = z t-1 )P θ (Z t-1 = z t-1 | X 1:t-1 ) ≤ - 2 n(n -1)T T t=1 log z t-1 ∈ 1,Q n δ n P θ (Z t-1 = z t-1 | X 1:t-1 ) ≤ - 2 n(n -1)T T t=1 n log δ = 2 n -1 log(1/δ).
This implies that

P θ * (sup θ∈Θ T 1 > ǫr n,T /(3 √ n)) = 0 as soon as ǫr n,T / √ n ≥ 6 log(1/δ)/(n -1)
. Then for any sequence {r n,T } n,T ≥1 increasing to infinity, for any ǫ > 0, we have that

P θ * (sup θ∈Θ T 1 > ǫr n,T /(3 √ n)) → 0 as n and T increase.
Second term of the right-hand side of (10). Let us denote

T 2 (Z 1:T ) ≔ 2 n(n -1)T log P θ (X 1:T | Z 1:T = ẑ1:T ) - 2 n(n -1)T E θ * log P θ (X 1:T |Z 1:T = Z1:T ) Z 1:T .
For the sake of clarity, we study this term on the event {Z 1:T = z * 1:T } where z * 1:T ∈ 1, Q nT is a fixed configuration. This event induces the definition of Z1:T following Equation (8) as

Z1:T = argmax z 1:T ∈ 1,Q nT E θ * log P θ (X 1:T | Z 1:T = z 1:T ) Z 1:T = z * 1:T , or equivalently for every t ∈ 1, T , Zt = argmax z=(z 1 ,...,z n )∈ 1,Q n 1≤i< j≤n π * z * t i z * t j log π z i z j + (1 -π * z * t i z * t j ) log(1 -π z i z j ).
By definition of ẑ1:T and Z1:T respectively, we have the two inequalities

log P θ (X 1:T | Z 1:T = ẑ1:T ) ≥ log P θ (X 1:T | Z 1:T = Z1:T ) and E θ * log P θ (X 1:T | Z 1:T = Z1:T ) Z 1:T = z * 1:T ≥ E θ * log P θ (X 1:T | Z 1:T = ẑ1:T ) Z 1:T = z * 1:T ,
implying the lower and upper bounds

log P θ (X 1:T | Z 1:T = Z1:T ) -E θ * log P θ (X 1:T | Z 1:T = Z1:T ) Z 1:T = z * 1:T ≤ log P θ (X 1:T | Z 1:T = ẑ1:T ) -E θ * log P θ (X 1:T | Z 1:T = Z1:T ) Z 1:T = z * 1:T ≤ log P θ (X 1:T | Z 1:T = ẑ1:T ) -E θ * log P θ (X 1:T | Z 1:T = ẑ1:T ) Z 1:T = z * 1:T .
Taking the absolute value gives us an upper bound for T 2 (z * 1:T )

T 2 (z * 1:T ) ≤ max z 1:T ∈{ẑ 1:T , Z1:T } 2 n(n -1)T log P θ (X 1:T | Z 1:T = z 1:T ) -E θ * log P θ (X 1:T | Z 1:T = z 1:T ) Z 1:T = z * 1:T .
Using Equations ( 11) and ( 12), we then obtain the following upper bound for T 2 (z * 1:T )

T 2 (z * 1:T ) ≤ max z 1:T ∈{ẑ 1:T , Z1:T } 2 n(n -1)T T t=1 1≤i< j≤n (X t i j -π * z * t i z * t j ) log        π z t i z t j 1 -π z t i z t j        .
We use the following concentration result to conclude.

Lemma 4. Let ǫ, β > 0 and {x n,T } n,T ≥1 a sequence of positive real numbers. We let

P * θ * (•) denote the probability conditional on {Z 1:T = z * 1:T } under parameter θ * , i.e. P * θ * (•) = P θ * (•|Z 1:T = z * 1:T ). Denoting Λ = 2 log[(1-ζ)/ζ] > 0 we have for any θ ∈ Θ P * θ *          sup z 1:T ∈ 1,Q nT sup π∈[ζ,1-ζ] Q 2 2 n(n -1)T T t=1 1≤i< j≤n (X t i j -π * z * t i z * t j ) log        π z t i z t j 1 -π z t i z t j        > ǫ          ≤P * θ *        (1 + β)Λ √ n(n -1)T/2 + Λ x n,T /2 √ n(n -1)T/2 + (1/β + 1/3) (Λ/2)x n,T n(n -1)T/2 > ǫ        + 2e -x n,T ≤1 2Ω/(n(n-1)T )>ǫ + 2e -x n,T ( 14
)
with

Ω = (1 + β)Λ √ n(n -1)T/2 + Λ n(n -1)T x n,T /4 + (1/β + 1/3)(Λ/2)x n,T .
Let us choose x n,T = log(n) in the above lemma. For any ǫ > 0, for any sequence {r n,T } n,T ≥1 increasing to infinity, we have for n and T large enough

ǫr n,T 3 √ n ≥ 2Ω n(n -1)T .
Then for n and T large enough, the first term in the right-hand side of inequality ( 14) is equal to 0 and we have

P * θ * sup θ∈Θ T 2 (z * 1:T ) > ǫr n,T 3 √ n ≤ 2 n and P θ * sup θ∈Θ T 2 (Z 1:T ) > ǫr n,T 3 √ n ≤ z * 1:T P * θ * sup θ∈Θ T 2 (z * 1:T ) > ǫr n,T 3 √ n P θ * (Z 1:T = z * 1:T ) ≤ 2 n .
Third term of the right-hand side of (10). Let us denote

T 3 (Z 1:T ) ≔ 2 n(n -1)T E θ * log P θ (X 1:T | Z 1:T = Z1:T ) Z 1:T -M(π) = 2 n(n -1)T T t=1 E θ * log P θ (X t | Z t = Zt ) Z t -M(π, Āπ ) .
For any fixed configuration z t ∈ 1, Q n , analogous to Equation ( 12), we write

E θ * log P θ (X t | Z t = z t ) Z t = 1≤i< j≤n π * Z t i Z t j log π z t i z t j + (1 -π * Z t i Z t j ) log(1 -π z t i z t j ) = 1 2 1≤i j≤n π * Z t i Z t j log π z t i z t j + (1 -π * Z t i Z t j ) log(1 -π z t i z t j ) = 1 2 1≤q,l,q ′ ,l ′ ≤Q 1≤i j≤n π * ql log π q ′ l ′ + (1 -π * ql ) log(1 -π q ′ l ′ ) 1 {Z t i =q,Z t j =l,z t i =q ′ ,z t j =l ′ } = 1 2 1≤q,l,q ′ ,l ′ ≤Q C qq ′ (Z t , z t )C ll ′ (Z t , z t ) π * ql log π q ′ l ′ + (1 -π * ql ) log(1 -π q ′ l ′ ) ,
where

C qq ′ (Z t , z t ) = |{i ∈ 1, n ; Z t i = q, z t i = q ′ }|
is the (random variable) number of nodes classified in group q in the current (random) configuration Z t , while they belong to group q ′ in (deterministic) configuration z t . Recall that N q (z t ) is the number of nodes assigned to class q by the configuration z t and let us denote a t qq ′ = a qq ′ (Z t , z t ) = C qq ′ (Z t , z t )/N q (Z t ) the (random) proportion of vertices from class q in Z t attributed to class q ′ by z t . We write

2 n(n -1) E θ * log P θ (X t | Z t = z t ) Z t = 1≤q,l,q ′ ,l ′ ≤Q N q (Z t )N l (Z t ) n(n -1) a t qq ′ a t ll ′ π * ql log π q ′ l ′ + (1 -π * ql ) log(1 -π q ′ l ′ ) ≔ Φ t (A t , π),
with A t = (a t qq ′ ) 1≤q,q ′ ≤Q . Now extending these notations to the case where z t = Zt , we let Ãt = (ã t qq ′ ) 1≤q,q ′ ≤Q where ãt qq ′ = a qq ′ (Z t , Zt ). We remark that the definition of Zt implies that Ãt = argmax A t ∈A t (Z 1:T ) Φ t (A t , π) with A t (Z 1:T ) the (random) subset of stochastic matrices defined for every t ∈ 1, T by

A t (Z 1:T ) = A = (n ql /N q (Z t )) 1≤q,l≤Q ; n ql ∈ 0, N q (Z t ) , Q l=1 n ql = N q (Z t ) .

Let us also denote Āt

π = argmax A∈A t (Z 1:T ) M(π, A). Then sup θ∈Θ T 3 (Z 1:T ) ≤ sup π∈[ζ,1-ζ] Q 2 1 T T t=1 Φ t ( Ãt , π) -M(π, Āπ ) ≤ sup π∈[ζ,1-ζ] Q 2 1 T T t=1 Φ t ( Ãt , π) -M(π, Āt π ) + 1 T T t=1 sup π∈[ζ,1-ζ] Q 2 M(π, Āt π ) -M(π, Āπ ) . ( 15
)
We start by stating a concentration lemma on the random variable N q (Z t ) for any q ∈ 1, Q and any t ∈ 1, T .

Lemma 5. For any θ ∈ Θ and any η ∈ (0, δ), let

Ω η (θ) ≔ z 1:T ∈ 1, Q nT ; ∀t ∈ 1, T , ∀q ∈ 1, Q , N q (z t ) n ≥ α q -η . Then P θ Z 1:T ∈ Ω η (θ) ≥ 1 -QT exp(-2η 2 n).
Building on the previous concentration lemma, the following one gives the convergence in P θ * -probability of the second term in the right-hand side of (15). Lemma 6. For any ǫ > 0, any η ∈ (0, δ) and {r n,T } n,T ≥1 any positive sequence,

P θ *         1 T T t=1 sup π∈[ζ,1-ζ] Q 2 M(π, Āt π ) -M(π, Āπ ) > ǫr n,T 6 √ n         ≤ QT exp -2η 2 n + 1 n≤6c √ n/[ǫr n,T (δ-η)]
( 16)

with c = 6(1 -δ) 2 (1 -ζ) log(1/ζ)Q 4 .
Then taking any η ∈ (0, δ), for any ǫ > 0, for any sequence {r n,T } n,T ≥1 increasing to infinity, we have the following inequality for n and T large enough

r n,T > 6c √ n ǫ(δ -η)n , (17)
implying that the probability in Lemma 6 converges to 0 as n and T increase for any ǫ > 0, as long as log T = o(n). Now, for the first term in the right-hand side of (15), note that we have for every π and every t

Φ t ( Ãt , π) ≥ Φ t ( Āt π , π) because Ãt = argmax A∈A t Φ t (A, π) M(π, Āt π ) ≥ M(π, Ãt ) because Āt π = argmax A∈A t M(π, A). Then, either M(π, Āt π ) ≤ Φ t ( Ãt , π) and 0 ≤ Φ t ( Ãt , π) -M(π, Āt π ) ≤ Φ t ( Ãt , π) -M(π, Ãt ) or M(π, Āt π ) ≥ Φ t ( Ãt , π) and 0 ≤ M(π, Āt π ) -Φ t ( Ãt , π) ≤ M(π, Āt π ) -Φ t ( Āt π , π).
In both cases, we get that Φ t ( Ãt , π) -M(π, Āt π ) ≤ sup A∈A Φ t (A, π) -M(π, A) for every t and π, thus obtaining the upper bound

sup π∈[ζ,1-ζ] Q 2 1 T T t=1 Φ t ( Ãt , π) -M(π, Āt π ) ≤ 1 T T t=1 sup π∈[ζ,1-ζ] Q 2 sup A t ∈A Φ t (A t , π) -M(π, A t ) .
Letting

∆(ζ) = sup π∈[ζ,1-ζ] sup π * ∈[ζ,1-ζ] |π * log π + (1 -π * ) log(1 -π)| ∈ (0, +∞)
and recalling that 0 ≤ a ql ≤ 1 (for every q, l ∈ 1, Q ) for every A = (a ql ) 1≤q,l≤Q ∈ A, we have sup

π∈[ζ,1-ζ] Q 2 sup A t ∈A Φ t (A t , π) -M(π, A t ) ≤ sup π∈[ζ,1-ζ] Q 2 sup A t ∈A 1≤q,l,q ′ ,l ′ ≤Q N q (Z t )N l (Z t ) n(n -1) -α * q α * l a t qq ′ a t ll ′ π * ql log π q ′ l ′ + (1 -π * ql ) log(1 -π q ′ l ′ ) ≤ ∆(ζ)Q 2 1≤q,l≤Q N q (Z t )N l (Z t ) n(n -1) -α * q α * l .
Finally, we bound the first term of the right-hand-side of (15) as follows

sup π∈[ζ,1-ζ] Q 2 1 T T t=1 Φ t ( Ãt , π) -M(π, Āt π ) ≤ ∆(ζ)Q 2 1≤q,l≤Q 1 T T t=1 N q (Z t )N l (Z t ) n(n -1) -α * q α * l . (18)
Applying Markov's Inequality, we obtain

P θ *         sup π∈[ζ,1-ζ] Q 2 1 T T t=1 Φ t ( Ãt , π) -M(π, Āt π ) > ǫr n,T 6 √ n         ≤ q,l P θ *        1 T T t=1 N q (Z t )N l (Z t ) n(n -1) -α * q α * l > ǫr n,T 6∆(ζ)Q 4 √ n        ≤ 6∆(ζ)Q 4 √ n ǫr n,T q,l 1 T T t=1 E θ * N q (Z t )N l (Z t ) n(n -1) -α * q α * l ≤ 6∆(ζ)Q 4 √ n ǫr n,T q,l E θ * N q (Z 1 )N l (Z 1 ) n(n -1) -α * q α * l .
The following lemma gives an upper bound of the expectation appearing in the previous inequality, for any q, l ∈ 1, Q .

Lemma 7. For any q, l ∈ 1, Q and any t ∈ 1, T , we have the following inequality

E θ * N q (Z t )N l (Z t ) n(n -1) -α * q α * l ≤ 2 √ n n -1 .
This leads to

P θ *         sup π∈[ζ,1-ζ] Q 2 1 T T t=1 Φ t ( Ãt , π) -M(π, Āt π ) > ǫr n,T 6 √ n         ≤ 12∆(ζ)Q 6 n ǫr n,T (n -1) .
Then for any ǫ > 0, for any sequence {r n,T } n,T ≥1 increasing to infinity, we have the convergence

P θ *         sup π∈[ζ,1-ζ] Q 2 1 T T t=1 Φ t ( Ãt , π) -M(π, Āt π ) > ǫr n,T /(6 √ n)         -----→ n,T →∞ 0.
We proved the convergence to 0 of the three terms in the right-hand side of (10) for any sequence {r n,T } n,T ≥1 increasing to infinity and as long as log T = o(n). This gives the expected result and concludes the proof.

Proof of Corollary 1

To prove this corollary, we establish the following lemma that allows us to obtain a rate of convergence of π to π * from a rate of convergence of M n,T to M. Note that this lemma is a bit more general than what we need and gives an equivalent result when the number of time steps T is fixed, which will be useful for Corollary 2.

Lemma 8. Let {F n,T } n,T ≥1 be any random functions on the set Θ (resp. Θ T ) and M (resp. M T ) defined as before.

Assume that there exists a sequence {v n,T } n,T ≥1 (resp. {v n } n≥1 ) a sequence decreasing to 0 such that for every ǫ > 0, we have the following convergence as n, T → ∞ (resp. n → ∞)

P θ * sup (Γ,π)∈Θ F n,T (Γ, π) -M(π) > ǫv n,T -----→ n,T →∞ 0       resp. P θ *       sup (Γ,π)∈Θ T F n,T (Γ, π 1:T ) -M T (π 1:T ) > ǫv n       ----→ n→∞ 0       .
If for any n and T , θ = ( Γ, π) (resp. θ = ( Γ, π1:T )) is defined as the maximizer of F n,T on the set Θ, (resp. Θ T ) we have the following convergence

P θ * min σ∈S Q πσ -π * ∞ > ǫ √ v n,T -----→ n,T →∞ 0 resp. P θ * min σ 1 ,...,σ T ∈S Q π1:T σ 1:T -π * 1:T ∞ > ǫ √ v n ----→ n→∞ 0 with π1:T σ 1:T = ( πt σ t ) t∈ 1,T .
The result of Corollary 1 is then a direct consequence of Theorem 1 (choosing the sequence {r 2 n,T } n,t≥1 ) and Lemma 8 applied with F n,T = M n,T .

Proof of Theorem 2

The proof follows the lines of the proof of Theorem 3.8 in [START_REF] Celisse | Consistency of maximum-likelihood and variational estimators in the stochastic block model[END_REF]. Nonetheless, our result is sharper as we will establish an upper bound of the rate of convergence (in probability) of the quantity at stake. For any ǫ > 0, any sequence {y n,T } n,T ≥1 and η ∈ (0, δ), we write

P θ * (E(Z 1:T , θ, ǫy n,T )) = z * 1:T ∈ 1,Q nT P θ * (E(z * 1:T , θ, ǫy n,T ); Z 1:T = z * 1:T ) ≤ P θ * (Z 1:T ∈ Ω c η (θ * )) + z * 1:T ∈Ω η (θ * ) P θ *         P θ Z 1:T z * 1:T | X 1:T P θ Z 1:T = z * 1:T | X 1:T > ǫy n,T Z 1:T = z * 1:T         P θ * Z 1:T = z * 1:T (19)
with Ω η (θ * ) as defined in Lemma 5. We will establish that there exist some positive constants C, C 1 , C 2 , C 3 , C 4 such that for any fixed configuration z * 1:T ∈ Ω η (θ * ), any ǫ > 0, any positive sequence {y n,T } n,T ≥1 such that log(1/y n,T ) = o(n) and n and T large enough, we have

P θ * P θ(Z 1:T z * 1:T | X 1:T ) P θ(Z 1:T = z * 1:T | X 1:T ) > ǫy n,T Z 1:T = z * 1:T ≤ P θ * π -π * ∞ > v n,T | Z 1:T = z * 1:T + CnT        exp -(δ -η) 2 C 1 n + C 2 log(nT ) + C 4 log(1/(ǫy n,T )) + exp -C 3 (log(nT )) 2 nv 2 n,T + 3n log(nT )        . ( 20
)
Combined with (19) and applying Lemma 5, this gives the desired result. So now we focus on establishing (20).

In what follows, we consider a fixed configuration z * 1:T ∈ Ω η (θ * ) and introduce the Hamming distance between z * 1:T and any other configuration z 1:T defined as

z 1:T -z * 1:T 0 = T t=1 n i=1 1 z t i z * t i .
We let P * θ * (•) denote the probability conditional on {Z 1:T = z * 1:T } under parameter θ = θ * , i.e. P * θ * (•) = P θ * (• | Z 1:T = z * 1:T ). In the following, we will often use the fact that the variables {X t i j } are independent under P * θ * (with mean

value π * z * t i z * t j
) so that we can rely on Hoeffding's Inequality. We introduce a sequence {v n,T } n,T ≥1 decreasing to 0 and Ω n,T the event defined as

Ω n,T = { π -π * ∞ ≤ v n,T }.
We bound the probability of interest in (20) by splitting it on the two complementary events Ω n,T and Ω c n,T . For any ǫ > 0 and any positive sequence {y n,T } n,T ≥1

P * θ * P θ(Z 1:T z * 1:T | X 1:T ) P θ(Z 1:T = z * 1:T | X 1:T ) > ǫy n,T ≤ P * θ * Ω c n,T + P * θ * P θ(Z 1:T z * 1:T | X 1:T ) P θ(Z 1:T = z * 1:T | X 1:T ) > ǫy n,T ∩ Ω n,T . (21)
Thus, the proof of (20) boils down to establishing the desired upper bound on the second term appearing in the right-hand side of (21). We have

P * θ * P θ(Z 1:T z * 1:T | X 1:T ) P θ(Z 1:T = z * 1:T | X 1:T ) > ǫy n,T ∩ Ω n,T ≤ nT r=1 z 1:T ; z 1:T -z * 1:T 0 =r P * θ * P θ(Z 1:T = z 1:T | X 1:T ) P θ(Z 1:T = z * 1:T | X 1:T ) > ǫy n,T /(Q r (nT ) r+1 ) ∩ Ω n,T ,
by using the bound (Q -1) r nT r ≤ Q r (nT ) r on the number of terms in the sum over {z 1:T ; z 1:Tz * 1:T 0 = r} (for each value of r). Then,

P * θ * P θ(Z 1:T z * 1:T | X 1:T ) P θ(Z 1:T = z * 1:T | X 1:T ) > ǫy n,T ∩ Ω n,T ≤ nT r=1 z 1:T ; z 1:T -z * 1:T 0 =r P * θ * log P θ(Z 1:T = z 1:T | X 1:T ) P θ(Z 1:T = z * 1:T | X 1:T ) > log(ǫy n,T ) -r log Q -(r + 1) log(nT ) ∩ Ω n,T ≤ nT r=1 z 1:T ; z 1:T -z * 1:T 0 =r P * θ * log P θ(Z 1:T = z 1:T | X 1:T ) P θ(Z 1:T = z * 1:T | X 1:T ) > -log(1/(ǫy n,T )) -3r log(nT ) ∩ Ω n,T , (22)
as long as nT ≥ Q. For any configuration z 1:T such that z 1:Tz * 1:T 0 = r, we denote by r(1), . . . , r(T ) the number of differences between the two configurations at each time step t ∈ 1, T , i.e. r(t) = z t -z * t 0 such that r = t r(t). Moreover, for any parameter π, we define D n,T (z 1:T , π) the subset of indexes (i, j, t) ∈ 1, n 2 × 1, T such that i < j for which the parameter π differs between the configuration z * 1:T and z 1:T , namely

D n,T (z 1:T , π) ≔ (i, j, t) ∈ I n,T ; π z t i z t j π z * t i z * t j , with I n,T = {(i, j, t) ∈ 1, n 2 × 1, T ; i < j}
the set of indexes over which we sum to compute the conditional log-likelihood. In what follows, we abbreviate to D * (resp. D), the set D n,T (z 1:T , π * ) (resp. D n,T (z 1:T , π)). Next lemma gives a decomposition of the main term at stake in (22).

Lemma 9. We have the decomposition

log P θ(Z 1:T = z 1:T | X 1:T ) P θ(Z 1:T = z * 1:T | X 1:T ) = U 1 + U 2 -U 3 , where U 1 ≔ (i, j,t)∈D *          X t i j log π * z t i z t j π * z * t i z * t j + (1 -X t i j ) log 1 -π * z t i z t j 1 -π * z * t i z * t j          + n i=1 log αz 1 i αz * 1 i + T -1 t=1 n i=1 log γz t i z t+1 i γz * t i z * t+1 i (23) U 2 ≔ (i, j,t)∈D * ∪ D log          1 + ( πz t i z t j -π * z t i z t j )(X t i j -π * z t i z t j ) π * z t i z t j (1 -π * z t i z t j )          (24) U 3 ≔ (i, j,t)∈D * ∪ D log          1 + ( πz * t i z * t j -π * z * t i z * t j )(X t i j -π * z * t i z * t j ) π * z * t i z * t j (1 -π * z * t i z * t j )          . (25)
Combining ( 22) and Lemma 9, we obtain

P * θ *                   z 1:T z * 1:T P θ(Z 1:T = z 1:T | X 1:T ) P θ(Z 1:T = z * 1:T | X 1:T ) > ǫy n,T          ∩ Ω n,T          ≤ nT r=1 z 1:T ; z 1:T -z * 1:T 0 =r P * θ * U 1 + U 2 -U 3 > -log(1/(ǫy n,T )) -3r log(nT ) ∩ Ω n,T . (26)
We then decompose

P * θ * U 1 + U 2 -U 3 > -log(1/(ǫy n,T )) -3r log(nT ) ∩ Ω n,T ≤P * θ * U 1 + U 2 -U 3 > -log(1/(ǫy n,T )) -3r log(nT ) ∩ Ω n,T ∩ |U 3 | ≤ r log(nT ) + P * θ * Ω n,T ∩ |U 3 | > r log(nT ) ≤P * θ * U 1 + U 2 > -log(1/(ǫy n,T )) -4r log(nT ) ∩ Ω n,T + P * θ * Ω n,T ∩ |U 3 | > r log(nT ) ≤P * θ * U 1 > -log(1/(ǫy n,T )) -5r log(nT ) + P * θ * Ω n,T ∩ |U 2 | > r log(nT ) + P * θ * Ω n,T ∩ |U 3 | > r log(nT ) . ( 27
)
We handle these three terms separately in the following. From now on, we consider a configuration z 1:T such that

z 1:T -z * 1:T 0 = r = t r(t).
First term in the right-hand side of (27). Recall that U 1 is given by ( 23). We can further decompose this term

U 1 = (i, j,t)∈D *          (X t i j -π * z * t i z * t j ) log π * z t i z t j π * z * t i z * t j 1 -π * z * t i z * t j 1 -π * z t i z t j          + (i, j,t)∈D *          π * z * t i z * t j log π * z t i z t j π * z * t i z * t j + (1 -π * z * t i z * t j ) log 1 -π * z t i z t j 1 -π * z * t i z * t j          + n i=1 log αz 1 i αz * 1 i + T -1 t=1 n i=1 log γz t i z t+1 i γz * t i z * t+1 i .
For n and

T large enough such that Γ ∈ [δ, 1 -δ] Q 2 (implying for the corresponding stationary distribution α ∈ [δ, 1 -δ] Q ), we have n i=1 log αz 1 i αz * 1 i + T -1 t=1 n i=1 log γz t i z t+1 i γz * t i z * t+1 i = n i=1 1 {z 1 i z * 1 i } log αz 1 i αz * 1 i + T -1 t=1 n i=1 1 {(z t i ,z t+1 i ) (z * t i ,z * t+1 i )} log γz t i z t+1 i γz * t i z * t+1 i ≤ r(1) log 1 -δ δ + T -1 t=1 [r(t) + r(t + 1)] log 1 -δ δ ≤ 2r log 1 -δ δ .
To handle the term U 1 , we need to lower bound the cardinality of the set D * . This is the purpose of Lemma 10 which is a generalization of Proposition B.4 in [START_REF] Celisse | Consistency of maximum-likelihood and variational estimators in the stochastic block model[END_REF]. This can be done for all the configurations z 1:T and all the configurations z * 1:T that belong to some Ω η (θ).

Lemma 10. For any η ∈ (0, δ), any parameter θ ∈ Θ, any configuration z 1:T and any z

* 1:T ∈ Ω η (θ) such that z 1:T -z * 1:T 0 = r, we have D n,T (z 1:T , π) ≥ (δ -η) 2 4 nr.
Combining Lemma 10 with the previous bound, we get that

(|D * |) -1         n i=1 log αz 1 i αz * 1 i + T -1 t=1 n i=1 log γz t i z t+1 i γz * t i z * t+1 i         ≤ 2r |D * | log 1 -δ δ ≤ 8 n(δ -η) 2 log 1 -δ δ -----→ n→+∞ 0. ( 28
)
We also have

(|D * |) -1 (i, j,t)∈D *          π * z * t i z * t j log π * z t i z t j π * z * t i z * t j + (1 -π * z * t i z * t j ) log 1 -π * z t i z t j 1 -π * z * t i z * t j          ≤ max q,l,q ′ ,l ′ ;π * ql π * q ′ l ′ -k(π * ql , π * q ′ l ′ ) with k(x, y) = x log(x/y) + (1 -x) log[(1 -x)/(1 -y)]
for (x, y) ∈ (0, 1) 2 . The function k is positive for every (x, y) such that x y, hence, introducing the notation

K * = min q,l,q ′ ,l ′ ;π * ql π * q ′ l ′ k(π * ql , π * q ′ l ′ )/2, max q,l,q ′ ,l ′ ;π * ql π * q ′ l ′ -k(π * ql , π * q ′ l ′ ) ≔ -2K * < 0.
So, by (28), we have for n large enough

(|D * |) -1          (i, j,t)∈D *          π * z * t i z * t j log π * z t i z t j π * z * t i z * t j + (1 -π * z * t i z * t j ) log 1 -π * z t i z t j 1 -π * z * t i z * t j          + n i=1 log αz 1 i αz * 1 i + T -1 t=1 n i=1 log γz t i z t+1 i γz * t i z * t+1 i          ≤ -K * .
This leads to

P * θ * (U 1 > u) ≤ P * θ *          (i, j,t)∈D *          (X t i j -π * z * t i z * t j ) log π * z t i z t j π * z * t i z * t j 1 -π * z * t i z * t j 1 -π * z t i z t j          -|D * |K * > u         
for any u > 0 and large enough n. Moreover, thanks to Hoeffding's Inequality and Assumption 3,

P * θ * (U 1 > u) ≤P * θ *          (i, j,t)∈D *          (X t i j -π * z * t i z * t j ) log π * z t i z t j π * z * t i z * t j 1 -π * z * t i z * t j 1 -π * z t i z t j          > u + |D * |K *          ≤ exp - u 2 + |D * | 2 K * 2 + 2u|D * |K * |D * |C ζ ≤ exp - |D * | 2 K * 2 + 2u|D * |K * |D * |C ζ = exp - 2uK * C ζ exp - |D * |K * 2 C ζ ,
where C ζ is a constant depending on ζ. Finally using Lemma 10, we have

P * θ * U 1 > -log(1/(ǫy n,T )) -5r log(nT ) ≤ exp log(1/(ǫy n,T )) + 5r log(nT ) 2K * C ζ exp - |D * |K * 2 C ζ ≤ exp log(1/(ǫy n,T )) + 5r log(nT ) 2K * C ζ exp -nr (δ -η) 2 K * 2 4C ζ .
Second term in the right-hand side of (27). We have

U 2 ≔ (i, j,t)∈D * ∪ D log          1 + ( πz t i z t j -π * z t i z t j )(X t i j -π * z t i z t j ) π * z t i z t j (1 -π * z t i z t j )          ≤ (i, j,t)∈D * ∪ D ( πz t i z t j -π * z t i z t j )(X t i j -π * z t i z t j ) π * z t i z t j (1 -π * z t i z t j
) .

For any q, l, q ′ , l ′ ∈ 1, Q , we introduce the sets

F qlq ′ l ′ = F qlq ′ l ′ (z 1:T , z * 1:T ) ≔ {(i, j, t) ∈ I n,T ; z t i = q, z t j = l, z * t i = q ′ , z * t j = l ′ } F ql = F ql (z 1:T ) ≔ ∪ 1≤q ′ ,l ′ ≤Q F qlq ′ l ′ = {(i, j, t) ∈ I n,T ; z t i = q, z t j = l} G qlq ′ l ′ = G qlq ′ l ′ (z 1:T , z * 1:T , π * , π) ≔ (D * ∪ D) ∩ F qlq ′ l ′ = {(i, j, t) ∈ I n,T ; z t i = q, z t j = l, z * t i = q ′ , z * t j = l ′ and (π * z t i z t j π * z * t i z * t j or πz t i z t j πz * t i z * t j )} G ql = G ql (z 1:T , z * 1:T , π * , π) ≔ (D * ∪ D) ∩ F ql = {(i, j, t) ∈ I n,T ; z t i = q, z t j = l and (π * z t i z t j π * z * t i z * t j or πz t i z t j πz * t i z * t j )}. Then we bound |U 2 | ≤ 1≤q,l≤Q πql -π * ql π * ql (1 -π * ql ) (i, j,t)∈D * ∪ D(X t i j -π * ql )1 z t i =q,z t j =l ≤ 1≤q,l≤Q πql -π * ql π * ql (1 -π * ql ) (i, j,t)∈G ql (X t i j -π * ql ) ≤ 1≤q,l≤Q πql -π * ql π * ql (1 -π * ql ) (i, j,t)∈G ql (X t i j -π * z * t i z * t j ) + 1≤q,l≤Q πql -π * ql π * ql (1 -π * ql ) (i, j,t)∈G ql (π * z * t i z * t j -π * ql ) ≤ 1≤q,l≤Q πql -π * ql π * ql (1 -π * ql ) (i, j,t)∈G ql (X t i j -π * z * t i z * t j ) + 1≤q,l≤Q πql -π * ql π * ql (1 -π * ql ) q ′ ,l ′ (π * q ′ l ′ -π * ql )|G qlq ′ l ′ | . ( 29
)
For every u > 0, we thus have

P * θ * (Ω n,T ∩ {|U 2 | > u}) ≤P * θ *                    1≤q,l≤Q πql -π * ql π * ql (1 -π * ql ) (i, j,t)∈G ql (X t i j -π * z * t i z * t j ) > u/2          ∩ Ω n,T           + P * θ *                    1≤q,l≤Q πql -π * ql π * ql (1 -π * ql ) 1≤q ′ ,l ′ ≤Q (π * q ′ l ′ -π * ql )|G qlq ′ l ′ | > u/2          ∩ Ω n,T           . ( 30
)
We start by dealing with the first term of the right-hand side of (30). Notice that on the event Ω n,T , we have ( πqlπ * ql )/(π * ql (1π * ql )) ≤ v n,T /ζ 2 for every q, l ∈ 1, Q . The next lemma establishes that any set D n,T (z 1:T , π) is included in a larger set, whose cardinality is bounded. In particular, the random set D is included in a larger deterministic subset.

Lemma 11. Let z 1:T and z * 1:T denote two configurations such that z 1:Tz * 1:T 0 = r. Then for any parameter π = (π ql ) 1≤q,l≤Q , we have

D n,T (z 1:T , π) ⊂ D n,T (z 1:T ) ≔ (i, j, t) ∈ 1, n 2 × 1, T ; (z t i , z t j ) (z * t i , z * t j ) and D n,T (z 1:T ) ≤ 2nr.
As the set G ql is random (because D is random), we write

P * θ *                    1≤q,l≤Q πql -π * ql π * ql (1 -π * ql ) (i, j,t)∈G ql (X t i j -π * z * t i z * t j ) > u/2          ∩ Ω n,T           ≤P * θ *          1≤q,l≤Q (i, j,t)∈G ql (X t i j -π * z * t i z * t j ) > uζ 2 2v n,T          ≤ D⊂D n,T (z 1:T ) P * θ *          1≤q,l≤Q (i, j,t)∈F ql ∩D (X t i j -π * z * t i z * t j ) > uζ 2 2v n,T          ,
where now D is a deterministic set. By a union bound and Hoeffding's inequality, we have for any D ⊂ D n,T (z 1:T )

P * θ *          1≤q,l≤Q (i, j,t)∈F ql ∩D (X t i j -π * z * t i z * t j ) > uζ 2 2v n,T          ≤Q 2 max 1≤q,l≤Q P * θ *          (i, j,t)∈F ql ∩D (X t i j -π * z * t i z * t j ) > uζ 2 2v n,T          ≤2Q 2 exp        - 2u 2 ζ 4 4v 2 n,T Q 4 1 |D|        .
This leads to

P * θ *                    1≤q,l≤Q πql -π * ql π * ql (1 -π * ql ) (i, j,t)∈G ql (X t i j -π * z * t i z * t j ) > u/2          ∩ Ω n,T           ≤ D⊂D n,T (z 1:T ) 2Q 2 exp        - 2u 2 ζ 4 4v 2 n,T Q 4 1 |D|        ≤ 2nr k=1 D⊂D n,T (z 1:T );|D|=k 2Q 2 exp        - 2u 2 ζ 4 4v 2 n,T Q 4 1 k        ≤ 2Q 2 2nr k=1 (2nr) k exp        - 2u 2 ζ 4 4v 2 n,T Q 4 1 2nr        ≤ 2Q 2 exp        - u 2 ζ 4 4v 2 n,T Q 4 nr        (2nr) 2nr+1 .
For the second term of (30), we get from a union bound and from Lemma 11 (that gives an upper bound for |D * ∪ D|) that

P * θ *                   1≤q,l≤Q ( πql -π * ql ) π * ql (1 -π * ql ) 1≤q ′ ,l ′ ≤Q (π * q ′ l ′ -π * ql )|G qlq ′ l ′ | > u/2          ∩ Ω n,T          ≤P * θ *          1≤q,l≤Q 1≤q ′ ,l ′ ≤Q (π * q ′ l ′ -π * ql )|G qlq ′ l ′ | > uζ 2 2v n,T          ≤Q 2 max 1≤q,l≤Q P * θ *          1≤q ′ ,l ′ ≤Q (π * q ′ l ′ -π * ql )|G qlq ′ l ′ | > uζ 2 2v n,T Q 2          ≤ Q 2 P * θ * 2nr > uζ 2 2v n,T Q 2 , because |π * q ′ l ′ -π * ql | ≤ 1, implying that q ′ ,l ′ (π * q ′ l ′ -π * ql )|G qlq ′ l ′ | ≤ q ′ ,l ′ |G qlq ′ l ′ | = |G ql | = |F ql ∩ (D * ∪ D)| ≤ |D n,T (z 1:T )| ≤ 2nr.
Finally, we have the following upper bound for the second term of ( 27)

P * θ * Ω n,T ∩ |U 2 | > r log(nT ) ≤ 2Q 2 exp        - rζ 4 (log(nT )) 2 4Q 4 v 2 n,T n        (2nr) 2nr+1 + Q 2 P * θ * v n,T > ζ 2 log(nT ) 4Q 2 n .
Third term in the right-hand side of (27). We want to bound (in probability) the last term U 3 . Distinguishing between the cases where X t i j = 0 and X t i j = 1, we have

U 3 ≔ (i, j,t)∈D * ∪ D log          1 + ( πz * t i z * t j -π * z * t i z * t j )(X t i j -π * z * t i z * t j ) π * z * t i z * t j (1 -π * z * t i z * t j )          = (i, j,t)∈D * ∪ D          (1 -X t i j ) log          1 - ( πz * t i z * t j -π * z * t i z * t j ) (1 -π * z * t i z * t j )          + X t i j log          1 + ( πz * t i z * t j -π * z * t i z * t j ) π * z * t i z * t j                   = 1≤q,l≤Q (i, j,t)∈D * ∪ D        (1 -X t i j ) log        1 - ( πql -π * ql ) (1 -π * ql )        + X t i j log        1 + ( πql -π * ql ) π * ql               1 z * t i =q,z * t j =l .
For any (q, l) ∈ 1, Q 2 , we further introduce the sets

F * ql = ∪ 1≤q ′ ,l ′ ≤Q F q ′ l ′ ql = {(i, j, t) ∈ I n,T ; z * t i = q, z * t j = l} G * ql = ∪ 1≤q ′ ,l ′ ≤Q G q ′ l ′ ql = (D * ∪ D) ∩ F * ql = {(i, j, t) ∈ D * ∪ D; z * t i = q, z * t j = l}.
Centering the X t i j (under the distribution P * θ * ), we get

U 3 = 1≤q,l≤Q (i, j,t)∈D * ∪ D        (π * ql -X t i j ) log        1 - ( πql -π * ql ) (1 -π * ql )        + (X t i j -π * ql ) log        1 + ( πql -π * ql ) π * ql               1 z * t i =q,z * t j =l + 1≤q,l≤Q (i, j,t)∈D * ∪ D        (1 -π * ql ) log        1 - ( πql -π * ql ) (1 -π * ql )        + π * ql log        1 + ( πql -π * ql ) π * ql               1 z * t i =q,z * t j =l = 1≤q,l≤Q        log        1 + ( πql -π * ql ) π * ql        -log        1 - ( πql -π * ql ) (1 -π * ql )               (i, j,t)∈G * ql (X t i j -π * ql ) + 1≤q,l≤Q |G * ql |        (1 -π * ql ) log        1 - ( πql -π * ql ) (1 -π * ql )        + π * ql log        1 + ( πql -π * ql ) π * ql               .
Then, on the event Ω n,T and for n and T large enough such that |( πql -π * ql )/(1 -π * ql )| ≤ 1/2 and |( πql -π * ql )/π * ql | ≤ 1/2 for every q and l, using the fact that | log(1 + x)| ≤ 2|x| for x ∈ [-1/2, 1/2], we have

|U 3 | ≤4 v n,T ζ 1≤q,l≤Q (i, j,t)∈G * ql (X t i j -π * ql ) + 4 v n,T ζ 1≤q,l≤Q |G * ql |.
Then, for every u > 0,

P * θ * Ω n,T ∩ {|U 3 | > u} ≤P * θ *           1≤q,l≤Q (i, j,t)∈G * ql (X t i j -π * ql ) > uζ 8v n,T           + P * θ *         v n,T 1≤q,l≤Q |G * ql | > uζ 8         . (31)
For the first term of (31), using Hoeffding's inequality as before,

P * θ *           1≤q,l≤Q (i, j,t)∈G * ql (X t i j -π * ql ) > uζ 8v n,T           ≤ 2nr k=1 D⊂D n,T (z 1:T );|D|=k P * θ *           1≤q,l≤Q (i, j,t)∈D∩F * ql (X t i j -π * ql ) > uζ 8v n,T           ≤2Q 2 (2nr) 2nr+1 exp        - u 2 ζ 2 8 2 Q 4 v 2 n,T nr        .
For the second term of (31), we use

P * θ *         v n,T 1≤q,l≤Q |G * ql | > uζ 8         ≤ P * θ * v n,T > uζ 16nr .
Finally, we have the following upper bound for the third term of ( 27)

P * θ * Ω n,T ∩ |U 3 | > r log(nT ) ≤ 2Q 2 (2nr) 2nr+1 exp        - r(log(nT )) 2 ζ 2 8 2 Q 4 v 2 n,T n        + P * θ * v n,T > log(nT )ζ 16n .
Combining the 3 bounds on the right-hand-side of (27).

P * θ * U 1 + U 2 -U 3 > -log(1/(ǫy n,T )) -3r log(nT ) ∩ Ω n,T ≤ exp log(1/(ǫy n,T )) + 5r log(nT ) 2K * C ζ exp -nr (δ -η) 2 K * 2 4C ζ + 2Q 2 (2nr) 2nr+1 exp        - rζ 4 (log(nT )) 2 4Q 4 v 2 n,T n        + Q 2 P * θ * v n,T > ζ 2 log(nT ) 4Q 2 n + 2Q 2 (2nr) 2nr+1 exp        - r(log(nT )) 2 ζ 2 8 2 Q 4 v 2 n,T n        + P * θ * v n,T > log(nT )ζ 16n .
Now we choose the sequence v n,T such that v n,T = o( log(nT )/n) which is sufficient to imply that the quantities P * θ * v n,T > ζ 2 log(nT )/(4Q 2 n) and P * θ * v n,T > log(nT )ζ/(16n) vanish as n and T increase. For large enough values of n and T and with C 1 , C 2 , C 3 , C 4 and κ positive constants only depending on Q, ζ and K * , we then have

P * θ * U 1 + U 2 -U 3 > -log(1/(ǫy n,T )) -3r log(nT ) ∩ Ω n,T ≤ exp log(1/(ǫy n,T )) + 5r log(nT ) 2K * C ζ exp -nr (δ -η) 2 K * 2 4C ζ + 2Q 2 (2nr) 2nr+1 exp        - rζ 4 (log(nT )) 2 4Q 4 v 2 n,T n        + 2Q 2 (2nr) 2nr+1 exp        - r(log(nT )) 2 ζ 2 8 2 Q 4 v 2 n,T n        ≤ exp -(δ -η) 2 C 1 nr + C 2 log(nT )r + C 4 log(1/(ǫy n,T )) + κ exp 3nr log(nT ) -C 3 (log(nT )) 2 r nv 2 n,T . (32)
Let us introduce

u nT = exp -(δ -η) 2 C 1 n + C 2 log(nT ) + C 4 log(1/(ǫy n,T )) w nT = exp        -C 3 (log(nT )) 2 nv 2 n,T + 3n log(nT )        .
Now we go back to (26). Noticing that the number of configurations z 1:T such that z 1:Tz * 1:T 0 = r is equal to nT r (Q -1) r , we have

P * θ * P θ(Z 1:T z * 1:T | X 1:T ) P θ(Z 1:T = z * 1:T | X 1:T ) > ǫy n,T ∩ Ω n,T ≤ nT r=1 nT r (Q -1) r u r nT + nT r=1 nT r (Q -1) r κw r nT ≤[1 + Qu nT ] nT -1 + κ [1 + Qw nT ] nT -1 .
Finally, notice that as long as log T = o(n) and log(1/y n,T ) = o(n) (resp. as long as v n,T = o( log(nT )/n)), we have nT u nT (resp. nT w nT ) converges to 0. Then we obtain for some universal positive constant C and large enough n and T

P * θ * P θ(Z 1:T z * 1:T | X 1:T ) P θ(Z 1:T = z * 1:T | X 1:T ) > ǫy n,T ∩ Ω n,T ≤ CnT (u nT + w nT ).
This leads directly to inequality (20).

Proof of Theorem 3

We fix some σ ∈ S Q and study the convergence in P θ * -probability of γσ(q)σ(l) to γ * ql with Γ as defined by the fixed point equation (4), i.e.

γσ(q)σ(l) = T -1 t=1 n i=1 P θσ Z t i = q, Z t+1 i = l | X 1:T T -1 t=1 n i=1 P θσ Z t i = q | X 1:T .
First, let us denote

A q,l = 1 n(T -1) T -1 t=1 n i=1 P θσ Z t i = q, Z t+1 i = l | X 1:T , B q = 1 n(T -1) T -1 t=1 n i=1 P θσ Z t i = q | X 1:T .
Then we can write the quantity at stake as

γσ(q)σ(l) -γ * ql = A q,l B q -γ * ql = A q,l -α * q γ * ql B q + α * q γ * ql 1 B q - 1 α * q
to obtain the following upper bound on the probability of interest

P θ *        γσ(q)σ(l) -γ * ql > ǫr n,T log n √ nT        ≤ P θ *        A q,l -α * q γ * ql B q > ǫ 2 r n,T log n √ nT        + P θ *        α * q γ * ql 1 B q - 1 α * q > ǫ 2 r n,T log n √ nT        . ( 33
)
First term of the right-hand side of (33). For the first term in (33), for any 0 < λ < δ (implying λ < α * q for any q ∈ 1, Q ),

P θ *        A q,l -α * q γ * ql B q > ǫ 2 r n,T log n √ nT        =P θ *        A q,l -α * q γ * ql B q > ǫ 2 r n,T log n √ nT B q ≥ α * q -λ        P θ * B q ≥ α * q -λ + P θ *        A q,l -α * q γ * ql B q > ǫ 2 r n,T log n √ nT B q < α * q -λ        P θ * B q < α * q -λ ≤P θ *        A q,l -α * q γ * ql > ǫ 2 r n,T log n √ nT (α * q -λ)        + P θ * B q < α * q -λ . (34)
First, we upper bound the probability

P θ * A q,l -α * q γ * ql > ǫr n,T √ log n √ nT
for any ǫ > 0, using the following lemma.

Lemma 12. If log(T ) = o(n), for any ǫ > 0, for any sequence {r n,T } n,T ≥1 increasing to infinity such that r n,T = o nT/ log n and any η ∈ (0, δ), we have for any σ ∈ S Q

P θ *         1 n(T -1) T -1 t=1 n i=1 P θσ Z t i = q, Z t+1 i = l | X 1:T -α * q γ * ql > ǫr n,T log n √ nT         ≤ P θ * πσ -π * ∞ > v n,T + o(1)
with v n,T a sequence decreasing to 0 such that v n,T = o log(nT )/n .

Then, for the second term of (34), notice that B q = Q l=1 A q,l and Q l=1 γ * ql = 1. We then have, if log(T ) = o(n) and v n,T = o log(nT )/n , using Lemma 12 again,

P θ * B q < α * q -λ =P θ * B q -α * q < -λ = P θ *         Q l=1 (A q,l -α * q γ * ql ) < -λ         ≤ Q l=1 P θ * A q,l -α * q γ * ql < -λ/Q ≤ Q l=1 P θ * A q,l -α * q γ * ql > λ/Q ≤ QP θ * πσ -π * ∞ > v n,T + o(1).
Finally, for the first term of (33), if y n,T is such that 1/y n,T = o nT/ log(n) , if v n,T = o log(nT )/n and as long as log(T ) = o(n), we obtain

P θ *        A q,l -α * q γ * ql B q > ǫ 2 r n,T log n √ nT        ≤ (Q + 1)P θ * πσ -π * ∞ > v n,T + o(1). ( 35
)
Second term of the right-hand side of (33). For the second term of (33), we split it on two complementary events as before. For any 0 < λ < δ, we have

P θ *        α * q γ * ql 1 B q - 1 α * q > ǫ 2 r n,T log n √ nT        =P θ *        α * q γ * ql 1 B q - 1 α * q > ǫ 2 r n,T log n √ nT B q ≥ α * q -λ        P θ * B q ≥ α * q -λ + P θ *        α * q γ * ql 1 B q - 1 α * q > ǫ 2 r n,T log n √ nT B q < α * q -λ        P θ * B q < α * q -λ ≤P θ *        α * q γ * ql 1 B q - 1 α * q > ǫ 2 r n,T log n √ nT B q ≥ α * q -λ        P θ * B q ≥ α * q -λ + P θ * B q < α * q -λ . (36)
We already gave an upper bound on the second term in the right-hand side of (36). Let us give one for the first term. Notice that as α * q ≥ δ and if B q ≥ α * qλ ≥ δλ > 0, we have by the mean value theorem

1 B q - 1 α * q ≤ 1 (δ -λ) 2 B q -α * q .
We can then write for the first term in the right-hand side of (36), as long as log(T ) = o(n), for {y n,T } n,T ≥1 such that 1/y n,T = o nT/ log n and with v n,T such that v n,T = o log(nT )/n , still using Lemma 12

P θ *        α * q γ * ql 1 B q - 1 α * q > ǫ 2 r n,T log n √ nT B q ≥ α * q -λ        P θ * B q ≥ α * q -λ ≤P θ *        B q -α * q > (δ -λ) 2 ǫ 2α * q γ * ql r n,T log n √ nT        = P θ *         Q l=1 (A q,l -α * q γ * ql ) > (δ -λ) 2 ǫ 2α * q γ * ql r n,T log n √ nT         ≤ Q l=1 P θ *        A q,l -α * q γ * ql > (δ -λ) 2 ǫ 2α * q γ * ql Q r n,T log n √ nT        ≤ QP θ * πσ -π * ∞ > v n,T + o(1).
We finally obtain for the second term of the right-hand side of ( 33)

P θ *        α * q γ * ql 1 B q - 1 α * q > ǫ 2 r n,T log n √ nT        ≤ 2QP θ * πσ -π * ∞ > v n,T + o(1). ( 37
)
We conclude the proof by summing the upper bounds obtained in ( 35) and ( 37)

P θ *        γσ(q)σ (l) -γ * ql > ǫr n,T log n √ nT        ≤(3Q + 1)P θ * πσ -π * ∞ > v n,T + o(1)
and by noticing that

P θ * ( Γσ -Γ * ∞ > ǫr n,T log n/ √ nT ) ≤ 1≤q,l≤Q P θ * (| γσ(q)σ(l) -γ * ql | > ǫr n,T log n/ √ nT ).

Proof of Corollary 3

Denoting by σ n,T the permutation minimizing the distance between π (permuted) and π * for every (n, T ) ∈ 1, n × 1, T , i.e. σ n,T = argmin σ∈S Q πσπ * ∞ , we apply Theorem 3 to θσ n,T in order to get

P θ *        min σ∈S Q Γσ -Γ * ∞ > ǫr n,T log n √ nT        ≤P θ *        Γσ n,T -Γ * ∞ > ǫr n,T log n √ nT        ≤Q 2 (3Q + 1)P θ * min σ∈S Q πσ -π * ∞ > v n,T + o(1) -----→ n,T →∞ 0,

Proof of Theorem 5

We use the following lemma, that states that the quantity we optimize in the VEM algorithm and the log-likelihood are asymptotically equivalent.

Lemma 13. We have the following inequality P θ * -a.s.

sup θ∈Θ 2 n(n -1)T J( χ(θ), θ) - 2 n(n -1)T ℓ(θ) ≤ 2 log(1/δ) n -1 .
We have that for any ǫ > 0, for n and T large enough,

P θ * sup θ∈Θ 2 n(n -1)T J( χ(θ), θ) - 2 n(n -1)T ℓ(θ) > ǫr n,T √ n ≤ P θ * 2 log(1/δ) n -1 > ǫr n,T √ n = 0
We then conclude by combining this result with Theorem 1.

Proof of Corollary 5

This is a direct consequence of Theorem 5 and Lemma 8 applied with the functions F n,T = 2 n(n-1)T J( χ(•), •).

Proof of Theorem 6

This proof is quite similar to that of Theorem 3. We fix some σ ∈ S Q and study the convergence in P θ * -probability of γσ(q)σ(l) to γ * ql with Γ as defined by the fixed point equation ( 5), i.e. γσ(q)σ(l)

= n i=1 T -1 t=1 ηt iql ( θσ ) n i=1 T -1 t=1 τt iq ( θσ )
.

First, let us denote

A q,l = 1 n(T -1) n i=1 T -1 t=1 ηt iql ( θσ ) = 1 n(T -1) n i=1 T -1 t=1 Q χ( θσ ) (Z t i = q, Z t+1 i = l), B q = 1 n(T -1) n i=1 T -1 t=1 τt iq ( θσ ) = 1 n(T -1) n i=1 T -1 t=1 Q χ( θσ ) (Z t i = q).
Then we can write the quantity at stake as

γσ(q)σ(l) -γ * ql = A q,l B q -γ * ql = A q,l -α * q γ * ql B q + α * q γ * ql 1 B q - 1 α * q .
We follow the line of the proof of Theorem 3, using Lemma 14 below instead of Lemma 12 in order to obtain the result.

Lemma 14. For any ǫ > 0, for any sequence {r n,T } n,T ≥1 increasing to infinity such that r n,T = o nT/ log n and any η ∈ (0, δ), we have for any σ ∈ S Q

P θ *         1 n(T -1) n i=1 T -1 t=1 Q χ( θσ ) (Z t i = q, Z t+1 i = l) -α * q γ * ql > ǫr n,T log n √ nT         ≤ 2P θ * πσ -π * ∞ > v n,T + o(1)
with v n,T a sequence decreasing to 0 such that v n,T = o( log(nT )/n).

A Proofs of main results for the finite time case

A.1 Proof of Corollary 2

When the number of time steps is fixed and the connection probabilities vary over time, the conditional loglikelihood is

ℓ T c (θ; Z 1:T ) = T t=1 1≤i< j≤n X t i j log π t Z t i Z t j + (1 -X t i j ) log(1 -π t Z t i Z t j )
and the likelihood ℓ T (θ) is defined as in ( 2) with ℓ T c (•) instead of ℓ c (•). The maximum likelihood estimator is then

θ = ( Γ, π1:T ) = argmax θ∈Θ T ℓ T (θ).
As before, we denote the normalized log-likelihood M n,T (Γ, π 1:T ) = 2/(n(n-1)T )ℓ T (θ). We introduce the following limiting quantity

M T (π 1:T ) = 1 T T t=1 M(π t ) = 1 T T t=1 sup A∈A M(π t , A).
We follow the lines of the proof of Theorem 1 in order to prove that we have for any sequence y n → +∞, for all ǫ > 0

P θ *       sup (Γ,π 1:T )∈Θ T M n,T (Γ, π 1:T ) -M T (π 1:T ) > ǫy n √ n       -→ n→+∞ 0. ( 38
)
Choosing y n = r 2 n , we then use Lemma 8 to conclude that, as r 2 n / √ n = o(1) by assumption, for any ǫ > 0,

P θ * min σ 1 ,...,σ T ∈S Q π1:T σ 1:T -π * 1:T ∞ > ǫr n /n 1/4 ----→ n→∞ 0.
In particular, for every t ∈ 1, T , πt converges in P θ * -probability to π * t up to label switching. Then, let us prove that on the event {min σ 1 ,...,σ T ∈S Q π1:Tπ * 1:T σ 1:T ∞ ≤ ǫr n n -1/4 } (whose probability converges to 1), for n large enough, the permutation σ t minimizing the distance between π * t and πt σ t is the same for every t ∈ 1, T . We consider n large enough such that ǫr n n -1/4 < min 1≤q l≤Q |π * qqπ * ll |/4. Denoting by σ 1 m , . . . , σ T m the permutations (depending on n) minimizing π1:Tπ * 1:T σ 1:T ∞ , we have that, for any 1 ≤ t t ′ ≤ T , if some q, l ∈ 1, Q are such that σ t m (q) = σ t ′ m (l), then πt

σ t m (q)σ t m (q) = πt σ t ′ m (l)σ t ′ m (l) = πt ′ σ t ′ m (l)σ t ′ m (l)
and on the event we consider

|π * t qq -π * t ll | = |π * t qq -π * t ′ ll | = |π * t qq -πt σ t m (q)σ t m (q) + πt ′ σ t ′ m (l)σ t ′ m (l) -π * t ′ ll | ≤ |π * t qq -πt σ t m (q)σ t m (q) | + | πt ′ σ t ′ m (l)σ t ′ m (l) -π * t ′ ll | ≤ 2ǫr n n -1/4 < min 1≤q l≤Q |π * qq -π * ll |/2,
implying that q = l. This means that on this event, the permutation σ t m minimizing the distance between π * t and πt σ t is the same for every t ∈ 1, T . We can conclude that

P θ * min σ∈S Q π1:T σ -π * 1:T ∞ > ǫr n /n 1/4 = 1 -P θ * min σ∈S Q π1:T σ -π * 1:T ∞ ≤ ǫr n /n 1/4 ----→ n→∞ 0.

A.2 Proof of Theorem 4

First, let us introduce some notations, as in the proof of Theorem 2. For any fixed configuration z * 1:T ∈ Ω η , we define for any configuration z 1:T and any parameter θ

D n,T (z 1:T , π 1:T ) ≔ (i, j, t) ∈ I n,T ; π t z t i z t j π t z * t i z * t j and for any 1 ≤ t ≤ T D t n,T (z t , π t ) ≔ (i, j) ∈ 1, n 2 ; i < j and π t z t i z t j π t z * t i z * t j ,
and as before, we abbreviate to D * (resp. D), the set D n,T (z 1:T , π * 1:T ) (resp. D n,T (z 1:T , π1:T )). We also introduce for any q, l, q ′ , l ′ ∈ 1, Q the quantities F qlq ′ l ′ , F ql , G qlq ′ l ′ and G ql as before, accordingly to this definition of D n,T (z 1:T , π 1:T ). Finally, we introduce for any t ∈ 1, T and q, l, q ′ , l ′ ∈ 1, Q the quantities

F t qlq ′ l ′ = F t qlq ′ l ′ (z t , z * t ) ≔ {(i, j) ∈ 1, n 2 ; i < j and z t i = q, z t j = l, z * t i = q ′ , z * t j = l ′ } F t ql = F t ql (z t ) ≔ ∪ 1≤q ′ ,l ′ ≤Q F t qlq ′ l ′ = {(i, j) ∈ 1, n 2 ; i < j and z t i = q, z t j = l} G t qlq ′ l ′ = G t qlq ′ l ′ (z t , z * t , π * t , πt ) ≔ (D * t ∪ Dt ) ∩ F t qlq ′ l ′ = {(i, j) ∈ 1, n 2 ; i < j and z t i = q, z t j = l, z * t i = q ′ , z * t j = l ′ and (π * t z t i z t j π * t z * t i z * t j or πt z t i z t j πt z * t i z * t j )} G t ql = G t ql (z t , z * t , π * t , πt ) ≔ (D * t ∪ Dt ) ∩ F t ql = {(i, j) ∈ 1
, n 2 ; i < j and z t i = q, z t j = l and (π * t

z t i z t j π * t z * t i z * t j or πt z t i z t j πt z * t i z * t j )}.
Note that we can get an equivalent of Lemma 10 with a similar proof that gives that for any configuration z * 1:T in Ω η , for any configuration z 1:T and any θ ∈ Θ T , D n,T (z 1:T , π 1:T ) ≥ γ 2 4 nr.

In the same way, we have an equivalent of Lemma 11 (with a similar proof) that gives that for any z t and z * t two configurations at time t such that z tz * t 0 = r(t) and any parameter π t = (π t ql ) 1≤q,l≤Q , we have

D t n,T (z t , π t ) ⊂ D t n,T (z t ) ≔ (i, j) ∈ 1, n 2 × 1, T ; (z t i , z t j ) (z * t i , z * t j ) and D t n,T (z t ) ≤ 2nr(t). ( 39
)
Going back to the proof of Theorem 4, we follow the line of that of Theorem 2, with a few changes. We get the same decomposition as in equation ( 26), replacing π by π 1 , . . . , π T in the definitions of U 1 , U 2 and U 3 , and replacing the event Ω n,T by

Ω n = { π1:T -π * 1:T ∞ ≤ v n }.
For U 1 , the proof does not change. For U 2 , we write (instead of ( 29))

|U 2 | ≤ (i, j,t)∈D * ∪ D 1≤q,l≤Q πt ql -π * t ql π * t ql (1 -π * t ql ) (X t i j -π * t ql )1 z t i =q,z t j =l ≤ T t=1 1≤q,l≤Q πt ql -π * t ql π * t ql (1 -π * t ql ) (i, j)∈G t ql (X t i j -π * t ql ) ≤ T t=1 1≤q,l≤Q πt ql -π * t ql π * t ql (1 -π * t ql ) q ′ ,l ′ (i, j)∈G t qlq ′ l ′ (X t i j -π * t ql ) ≤ T t=1 1≤q,l≤Q πt ql -π * t ql π * t ql (1 -π * t ql ) q ′ ,l ′ (i, j)∈G t qlq ′ l ′ (X t i j -π * t q ′ l ′ ) + T t=1 1≤q,l≤Q πt ql -π * t ql π * t ql (1 -π * t ql ) q ′ ,l ′ (π * t q ′ l ′ -π * t ql )|G t qlq ′ l ′ | .
For every u > 0, we thus have

P * θ * ({|U 2 | > u} ∩ Ω n ) ≤ T t=1 P * θ *                       1≤q,l≤Q πt ql -π * t ql π * t ql (1 -π * t ql ) 1≤q ′ ,l ′ ≤Q (i, j)∈G t qlq ′ l ′ (X t i j -π * t q ′ l ′ ) > u 2T            ∩ Ω n            + T t=1 P * θ *                    1≤q,l≤Q πt ql -π * t ql π * t ql (1 -π * t ql ) 1≤q ′ ,l ′ ≤Q (π * t q ′ l ′ -π * t ql )|G t qlq ′ l ′ | > u 2T          ∩ Ω n           . ( 40
)
We start by dealing with the first term of (40). Notice that on the event Ω n , we have πt qlπ * t ql /(π * t ql (1-π * t ql )) ≤ v n /ζ 2 for every q, l ∈ 1, Q . As the set G t ql is random (because Dt is random), we write for every t ∈ 1, T , using (39),

P * θ *                       1≤q,l≤Q πt ql -π * t ql π * t ql (1 -π * t ql ) 1≤q ′ ,l ′ ≤Q (i, j)∈G t ql (X t i j -π * t q ′ l ′ ) > u 2T            ∩ Ω n            ≤P * θ *           1≤q,l≤Q 1≤q ′ ,l ′ ≤Q (i, j)∈G t ql (X t i j -π * t q ′ l ′ ) > uζ 2 2T v n           ≤ D⊂D t n,T (z t ) P * θ *           1≤q,l≤Q 1≤q ′ ,l ′ ≤Q (i, j)∈F t ql ∩D (X t i j -π * t q ′ l ′ ) > uζ 2 2T v n          
where now D is a deterministic set. By a union bound and Hoeffding's inequality, we have for any D ⊂ D t n,T (z t )

P * θ *           1≤q,l≤Q 1≤q ′ ,l ′ ≤Q (i, j)∈F t ql ∩D (X t i j -π * t q ′ l ′ ) > uζ 2 2T v n           ≤Q 2 max 1≤q,l≤Q P * θ *           1≤q ′ ,l ′ ≤Q (i, j)∈F t ql ∩D (X t i j -π * t q ′ l ′ ) > uζ 2 2T v n Q 2           ≤2Q 2 exp - 2u 2 ζ 4 4T 2 v 2 n Q 4 1 |D| .
This leads to, for the first term of (40),

T t=1 P * θ *                       1≤q,l≤Q ( πt ql -π * t ql ) π * t ql (1 -π * t ql ) 1≤q ′ ,l ′ ≤Q (i, j)∈G t ql (X t i j -π * t q ′ l ′ ) > u 2T            ∩ Ω n            ≤ T t=1 D⊂D t n,T (z t ) 2Q 2 exp - 2u 2 ζ 4 4T 2 v 2 n Q 4 1 |D| ≤ T t=1 2nr(t) k=1 D⊂D t n,T (z t );|D|=k 2Q 2 exp - 2u 2 ζ 4 4T 2 v 2 n Q 4 1 k ≤2Q 2 T t=1 exp - u 2 ζ 4 4T 2 v 2 n Q 4 nr(t) (2nr(t)) 2nr(t)+1 ≤ 2Q 2 T exp - u 2 ζ 4 4T 2 v 2 n Q 4 nr (2nr) 2nr+1 .
For the second term of (40), we get from a union bound and from (39) that

T t=1 P * θ *                   1≤q,l≤Q ( πt ql -π * t ql ) π * t ql (1 -π * t ql ) 1≤q ′ ,l ′ ≤Q (π * t q ′ l ′ -π * t ql )|G t qlq ′ l ′ | > u 2T          ∩ Ω n          ≤Q 2 T t=1 max 1≤q,l≤Q P * θ *          1≤q ′ ,l ′ ≤Q (π * t q ′ l ′ -π * t ql )|G t qlq ′ l ′ | > uζ 2 2T v n Q 2          ≤ Q 2 T P * θ * 2nr > uζ 2 2v n T Q 2 .
Finally, we have the following upper bound for U 2

P * θ * Ω n ∩ |U 2 | > r log(nT ) ≤2Q 2 T exp - rζ 4 (log(nT )) 2 4Q 4 T 2 v 2 n n (2nr) 2nr+1 + Q 2 T P * θ * v n > ζ 2 log(nT ) 4Q 2 T n .
For the third term U 3 , denoting G * t ql = ∪ 1≤q ′ ,l ′ ≤Q G t ql = {(i, j) ∈ D * t ∪ Dt ; z * t i = q, z * t j = l}, we have

U 3 = 1≤q,l≤Q (i, j,t)∈D * ∪ D        (π * t ql -X t i j ) log        1 - ( πt ql -π * t ql ) (1 -π * t ql )        + (X t i j -π * t ql ) log        1 + ( πt ql -π * t ql ) π * t ql               1 z * t i =q,z * t j =l + 1≤q,l≤Q (i, j,t)∈D * ∪ D        (1 -π * ql ) log        1 - ( πt ql -π * t ql ) (1 -π * t ql )        + π * t ql log        1 + ( πt ql -π * t ql ) π * t ql               1 z * t i =q,z * t j =l = T t=1 1≤q,l≤Q        log        1 + ( πt ql -π * t ql ) π * t ql        -log        1 - ( πt ql -π * t ql ) (1 -π * t ql )               (i, j)∈G * t ql (X t i j -π * t ql ) + T t=1 1≤q,l≤Q |G * t ql |        (1 -π * t ql ) log        1 + ( πt ql -π * t ql ) π * t ql        + π * t ql log        1 - ( πt ql -π * t ql ) (1 -π * t ql )               .
Then, we have on the event Ω n and for n large enough such that |( πt ql -π * t ql )/π * t ql | ≤ 1/2 and |( πt ql -π * t ql )/(1-π * t ql )| ≤ 1/2 for every q and l, using the fact that | log(1

+ x)| ≤ 2|x| for x ∈ [-1/2, 1/2], |U 3 | ≤ T t=1 4 v n ζ 1≤q,l≤Q (i, j)∈G * t ql (X t i j -π * t ql ) + T t=1 4 v n ζ 1≤q,l≤Q |G * t ql |.
Then, for every u > 0,

P * θ * (Ω n ∩ {|U 3 | > u}) ≤ T t=1 P * θ *           1≤q,l≤Q (i, j)∈Q * t ql (X t i j -π * t ql ) > uζ 8v n T           + T t=1 P * θ *         v n 1≤q,l≤Q |G * t ql | > uζ 8T         . (41)
For the first term of (41), using Hoeffding's inequality as before,

T t=1 P * θ *           q,l (i, j)∈G * t ql (X t i j -π * t ql ) > uζ/(8v n T )           ≤ T t=1 2nr(t) k=1 D⊂D t n,T (z t );|D|=k P * θ *           q,l (i, j)∈F * t ql ∩D (X t i j -π * t ql ) > uζ/(8v n T )           ≤2Q 2 T exp - u 2 ζ 2 8 2 T 2 Q 4 v 2 n nr (2nr) 2nr+1 ,
and for the second term of (41),

T t=1 P * θ *         v n q,l |G * t ql | > uζ 8T         ≤ T P * θ * v n > uζ 16T nr .
Finally, we have the following upper bound for U 3

P * θ * Ω n ∩ |U 3 | > r log(nT ) ≤2Q 2 T exp - rζ 2 (log(nT )) 2 8 2 T 2 Q 4 v 2 n n (2nr) 2nr+1 + T P * θ * v n > ζ log(nT ) 16T n .
Now we choose the sequence v n such that v n = o( log n/n) which is sufficient to imply that the quantities

P * θ * v n > ζ 2 log(nT )/(4Q 2 T n) and P * θ * v n > ζ log(nT )/(16T n) vanish
as n increases and we gather the three upper bounds. For large enough values of n and with C 1 , C 2 , C 3 , C 4 and κ positive constants only depending on Q, ζ, K * and T , we then have

P * θ * U 1 + U 2 -U 3 > -log(1/(ǫy n )) -3r log(nT ) ∩ Ω n ≤ exp (log(1/(ǫy n )) + 5r log(nT )) 2K * C ζ exp -nr (δ -η) 2 K * 2 4C ζ + 2Q 2 T exp - rζ 4 (log(nT )) 2 4Q 4 T 2 v 2 n n (2nr) 2nr+1 + 2Q 2 T exp - rζ 2 (log(nT )) 2 8 2 T 2 Q 4 v 2 n n (2nr) 2nr+1 ≤ exp -(δ -η) 2 C 1 nr + C 2 log(nT )r + C 4 log(1/(ǫy n )) + κ exp 5nr log(nT ) -C 3 (log(nT )) 2 r nv 2 n
Then, introducing

u nT = exp -(δ -η) 2 C 1 n + C 2 log(nT ) + C 4 log(1/(ǫy n )) w nT = exp -C 3 (log(nT )) 2 nv 2 n + 5n log(nT ) ,
we conclude as in the proof of Theorem 2, noticing that nT u nT (resp. nT w nT ) converges to 0 as n increases as long as log(1/y

n ) = o(n) (resp. as long as v n = o( log(n)/n)).

A.3 Proof of Corollary 6

As in the proof of Theorem 5, using the convergence in Equation ( 38) and Lemma 13, we obtain for any ǫ > 0

P θ * sup θ∈Θ 2 n(n -1)T J( χ(θ), θ) -M T (π 1:T ) > ǫr 2 n √ n -→ n→+∞ 0.
We then conclude by using Lemma 8 applied with

F n,T = 2 n(n-1)T J( χ(•), •).

B Proofs of technical lemmas B.1 Proof of Lemma 1

As in the proof of Lemma E.2 from [START_REF] Celisse | Consistency of maximum-likelihood and variational estimators in the stochastic block model[END_REF], we use the method of Lagrange multipliers to find the fixed-point equation of the critical point. Recall that θ = (Γ, π) and let us denote the likelihood L(Γ, π) ≔ exp ℓ(θ) = P θ (X 1:T ) and the conditional likelihood L c (z 1:T , π) = P θ (X 1:T | Z 1:T = z 1:T ). Recall the definition of N ql (z 1:T ) in (1) and that

P θ (Z 1:T = z 1:T ) = 1≤q,l≤Q γ N ql (z 1:T ) ql n i=1 α 1 z 1 i .
We compute the derivative of the Lagrangian with respect to each parameter γ ql .

∂ ∂γ ql         L(Γ, π) + Q m=1 λ m         Q k=1 γ mk -1                 = ∂ ∂γ ql         z 1:T L c (z 1:T , π)P θ (Z 1:T = z 1:T )         + λ q = z 1:T L c (z 1:T , π) N ql (z 1:T ) γ ql P θ (Z 1:T = z 1:T ) + λ q = 1 γ ql         T -1 t=1 n i=1 z 1:T L c (z 1:T , π)P θ (Z 1:T = z 1:T )1 z t i =q,z t+1 i =l + λ q γ ql         = 1 γ ql         T -1 t=1 n i=1 P θ (X 1:T , Z t i = q, Z t+1 i = l) + λ q γ ql         .
At the critical point θ = ( γ, π), we obtain that for each (q, l) ∈ 1,

Q 2 we have γql ∝ T -1 t=1 n i=1 P θ(X 1:T , Z t i = q, Z t+1 i = l)
where ∝ means 'proportional to'. The constraint l γ ql = 1 gives the normalizing term and we obtain

γql = T -1 t=1 n i=1 P θ(X 1:T , Z t i = q, Z t+1 i = l) T -1 t=1 n i=1 P θ(X 1:T , Z t i = q) = T -1 t=1 n i=1 P θ(Z t i = q, Z t+1 i = l | X 1:T ) T -1 t=1 n i=1 P θ(Z t i = q | X 1:T ) .

B.2 Proof of Lemma 2

We can write the quantity to optimize

J(χ, θ) =E Q χ log P θ (X 1:T , Z 1:T ) + H(Q χ ) =E Q χ log P θ (X 1:T | Z 1:T ) + E Q χ log P θ (Z 1:T ) -E Q χ log Q χ (Z 1:T ) =E Q χ         T t=1 i< j X t i j log π Z t i Z t j + (1 -X t i j ) log(1 -π Z t i Z t j )         + E Q χ         n i=1 log α Z 1 i + n i=1 T -1 t=1 log γ Z t i Z t+1 i         -E Q χ         n i=1 log Q χ (Z 1 i ) + n i=1 T -1 t=1 log Q χ (Z t+1 i | Z t i )         = T t=1 i< j q,l τ t iq τ t jl X t i j log π ql + (1 -X t i j ) log(1 -π ql ) + n i=1 Q q=1 τ 1 iq log α q + n i=1 q,l T -1 t=1 η t iql log γ ql - n i=1 Q q=1 τ 1 iq log τ 1 iq - n i=1 T -1 t=1 q,l η t iql log η t iql τ t iq . (42)
Using this expression, we can obtain directly the expected fixed-point equation for the variational estimator of the transition probability from q to l.

B.3 Proof of Lemma 3

We rely on the notation introduced in the proof of Theorem 1. For any t ∈ 1, T , using classical dependency rules in directed acyclic graphs and the expression (9) of ẑt , we write

log P θ (X t | X 1:t-1 ) = log z t P θ (X t | Z t = z t )P θ (Z t = z t | X 1:t-1 ) ≤ log         P θ (X t | Z t = ẑt ) z t P θ (Z t = z t | X 1:t-1 )         = log P θ (X t | Z t = ẑt ) and thus log P θ (X t | X 1:t-1 ) -log P θ (X t | Z t = ẑt ) ≤ 0. (43)
Using Bayes' rule, we have

log P θ (X t | X 1:t-1 ) = log P θ (X t , Z t | X 1:t-1 ) -log P θ (Z t | X 1:t ).
Taking the expectation of this quantity with respect to any distribution Q on Z t , we obtain

log P θ (X t | X 1:t-1 ) = E Q log P θ (X t , Z t | X 1:t-1 ) + KL Q; P θ (Z t | X 1:t ) + H(Q) ≥ E Q log P θ (X t , Z t | X 1:t-1 ) + H(Q) ≥ E Q log P θ (X t | Z t ) + E Q log P θ (Z t | X 1:t-1 ) + H(Q),
where KL Q

; P θ (Z t | X 1:t ) = E Q log Q(Z t ) -log P θ (Z t | X 1:t ) is a Kullback-Leibler divergence (thus non negative) and H(Q) = -E Q log Q(Z t ) is the entropy of Q.
Taking now Q as the Dirac distribution located on ẑt , we have

H(Q) = 0 and log P θ (X t | X 1:t-1 ) ≥ log P θ (X t | Z t = ẑt ) + log P θ (Z t = ẑt | X 1:t-1 ). (44)
Now, combining Inequalities ( 43) and ( 44), we obtain

log P θ (Z t = ẑt | X 1:t-1 ) ≤ log P θ (X t | X 1:t-1 ) -log P θ (X t | Z t = ẑt ) ≤ 0,
giving the expected result.

B.4 Proof of Lemma 4

To prove this lemma, we first establish a control of the expectation of the random variable appearing in the statement.

Lemma 15. We have the following inequality for z * 1:T and z 1:T any configurations and any θ ∈ Θ

E θ *          sup (z 1:T ,π)∈ 1,Q nT ×[ζ,1-ζ] Q 2 2 n(n -1)T T t=1 i< j (X t i j -π * z * t i z * t j ) log        π z t i z t j 1 -π z t i z t j        Z 1:T = z * 1:T          ≤ 2 n(n -1)T Λ with Λ = 2 log[(1 -ζ)/ζ].
We now turn to the proof of Lemma 4. Let us first recall Talagrand's inequality [see for e.g. Massart, 2007, page 170, Equation (5.50)].

Theorem (Talagrand's inequality). Let {Y t i j } 1≤i< j≤n,1≤t≤T denote independent and centered random variables. Define

∀g ≔ {g t i j } 1≤i< j≤n,1≤t≤T ∈ G, S n,T (g) = 1≤i< j≤n T t=1 Y t i j g t i j ,
where G ⊂ R n(n-1)T/2 . Let us further assume that there exist b > 0 and σ 2 > 0 such that |Y t i j g t i j | ≤ b for every (i, j, t) ∈ 1, n 2 × 1, T and any g ∈ G and sup g∈G i< j t Var(Y t i j g t i j ) ≤ σ 2 . Then, for every β > 0 and x > 0, for any finite set {g 1 , . . . , g 2 n(n-1)T/2 } of elements of G, we have

P max g∈{g 1 ,...,g 2 n(n-1)T/2 } S n,T (g) ≥ E max g∈{g 1 ,...,g 2 n(n-1)T/2 } S n,T (g) (1 + β) + √ 2σ 2 x + b(β -1 + 3 -1 )x ≤ e -x . (45)
First, notice that argmin

̟∈[ζ,1-ζ] log(̟/(1 -̟)) = ζ and argmax ̟∈[ζ,1-ζ] log(̟/(1 -̟)) = 1 -ζ so that we have P * θ *          sup (z 1:T ,π)∈ 1,Q nT ×[ζ,1-ζ] Q 2 2 n(n -1)T T t=1 i< j (X t i j -π * with ̟ ≔ {̟ t i, j } 1≤i< j≤n,1≤t≤T
. The set {ζ, 1 -ζ} n(n-1)T/2 is finite, of size 2 n(n-1)T/2 . Let us now apply Talagrand's inequality to our setup. Note that for every (i, j, t) ∈ 1, n 2 × 1, T , for any π ∈

[ζ, 1 -ζ] Q 2 , we have (X t i j -π *          max ̟∈{ζ,1-ζ} n(n-1)T/2 2 n(n -1)T T t=1 i< j (X t i j -π * z * t i z * t j ) log        ̟ t i, j 1 -̟ t i, j        > 2 n(n -1)T Ω          ≤P * θ * 2 n(n -1)T Ω > ǫ + 2e -x n,T ≤ 1 ǫ<2Ω/(n(n-1)T ) + 2e -x n,T .

B.5 Proof of Lemma 5

For any η ∈ (0, δ), Hoeffding's inequality [see for example Theorem 2.8 from [START_REF] Boucheron | Concentration Inequalities: A Nonasymptotic Theory of Independence[END_REF] gives that

P θ ∀t ∈ 1, T , ∀q ∈ 1, Q , N q (Z t ) n ≥ α q -η = 1 -P θ        ∃t ∈ 1, T , ∃q ∈ 1, Q ; 1 n n i=1 1 Z t i =q < α q -η        ≥ 1 - Q q=1 T t=1 exp -2η 2 n ≥ 1 -QT exp -2η 2 n ,
which concludes the proof.

B.6 Proof of Lemma 6

First notice that argmax A∈A M(π, A) may not be unique, it is in fact a closed subset of A. However, we choose a fixed element Āπ in this subset in the following. Letting ǫ > 0 and η ∈ (0, δ) and using Lemma 5, we can split the probability as

P θ *         1 T T t=1 sup π∈[ζ,1-ζ] Q 2 M(π, Āt π ) -M(π, Āπ ) > ǫr n 6 √ n         ≤P θ *                1 T T t=1 sup π∈[ζ,1-ζ] Q 2 M(π, Āt π ) -M(π, Āπ ) > ǫr n 6 √ n        ∩ Ω η (θ * )         + QT exp -2η 2 n , recalling that Ω η (θ) ≔ z 1:T ∈ 1, Q nT ; ∀t ∈ 1, T , ∀q ∈ 1, Q , N q (z t ) n ≥ α q -η .
We thus want to bound the quantity

P θ * T -1 T t=1 sup π∈[ζ,1-ζ] Q 2 M(π, Āt π ) -M(π, Āπ ) > ǫr n /(6 √ n) on the event Z 1:T ∈ Ω η (θ * )
, which means bounding

P θ *         1 T T t=1 sup π∈[ζ,1-ζ] Q 2 M(π, Āt π ) -M(π, Āπ ) > ǫr n 6 √ n Z 1:T ∈ Ω η (θ * )         .
Let us denote for any matrix P of size m × n the norm P ∞ = max (i, j)∈ 1,m × 1,n |P i j |. Then note that, for any matrix Ȃ with coefficients in [0, 1], for any π ∈ [ζ, 1ζ] Q 2 , using Assumption 2 and 3,

M(π, Āπ ) -M(π, Ȃ) ≤ q,l α * q α * l q ′ ,l ′ |ā qq ′ āll ′ -ȃqq ′ ȃll ′ | sup π∈[ζ,1-ζ] Q 2 |π * ql log π q ′ l ′ + (1 -π * ql ) log(1 -π q ′ l ′ )| ≤ 2(1 -δ) 2 (1 -ζ) log(1/ζ) q,l q ′ ,l ′ |ā qq ′ āll ′ -ȃqq ′ ȃll ′ | ≤ 2(1 -δ) 2 (1 -ζ) log(1/ζ)Q 4 2 Ȃ -Āπ ∞ ≔ c Ȃ -Āπ ∞ with c = 4(1 -δ) 2 (1 -ζ) log(1/ζ)Q 4 .
On the event Ω η (θ * ) we then have

P θ *         1 T T t=1 sup π∈[ζ,1-ζ] Q 2 M(π, Āt π ) -M(π, Āπ ) > ǫr n 6 √ n         =1 -P θ *         1 T T t=1 sup π∈[ζ,1-ζ] Q 2 M(π, Āt π ) -M(π, Āπ ) ≤ ǫr n 6 √ n         ≤1 -P θ *         ∀t ∈ 1, T , sup π∈[ζ,1-ζ] Q 2 M(π, Āπ ) -M(π, Āt π ) ≤ ǫr n 6 √ n         ≤1 -P θ * ∀t ∈ 1, T , ∀π ∈ [ζ, 1 -ζ] Q 2 , M(π, Āπ ) -M(π, Āt π ) ≤ ǫr n 6 √ n ≤1 -P θ * ∀t ∈ 1, T , ∀π ∈ [ζ, 1 -ζ] Q 2 , ∃ Ȃ ∈ A t (Z 1:T ); M(π, Āπ ) -M(π, Ȃ) ≤ ǫr n 6 √ n ≤1 -P θ * ∀t ∈ 1, T , ∀π ∈ [ζ, 1 -ζ] Q 2 , ∃ Ȃ ∈ A t (Z 1:T ); Ȃ -Āπ ∞ < ǫr n 6c √ n .
We then show that for any ǫ > 0, for every t ∈ 1, T and every π

∈ [ζ, 1 -ζ] Q 2 , for any n such that n > 6c √ n/[ǫr n (δ -η)]
, there exists some Ȃ ∈ A t (Z 1:T ) such that Ȃ -Āπ ∞ < ǫr n /(6c √ n), i.e. such that for every q, l, |ȃ qlāql | < ǫr n /(6c √ n). For every 1 ≤ q ≤ Q, we can construct Ȃq• = (ȃ q1 , . . . , ȃqQ ) as follows. On the event Ω η (θ * ), for every q ∈ 1, Q , for any n such that n > 6c √ n/[ǫr n (δη)], we have N q (Z t )ǫr n /(6c √ n) > 1 for every t ∈ 1, T . We then construct (n ql ) 1≤l≤Q as follows and take ȃql = nql /N q (Z 1:T ) for every l ∈ 1, Q .

• for l = 1 choose nq1 as the closest integer to N q (Z t )ā q1 . It is in the interval (N q (Z t )ā q1 -1, N q (Z t )ā q1 + 1) so we have |ā q1 -nq1 /N q (Z t )| < 1/N q (Z t ) < ǫr n /(6c √ n). Moreover, note that 0 ≤ nq1 ≤ N q (Z t ) because 0 ≤ N q (Z t )ā q1 ≤ N q (Z t ).

• Repeat for l = 2, . . . , Q if l-1 l ′ =1 (N q (Z t )ā ql ′nql ′ ) ≥ 0 choose nql as the closest bigger (or equal) integer to N q (Z t )ā ql . if l-1 l ′ =1 (N q (Z t )ā ql ′nql ′ ) < 0 choose nql as the closest smaller (or equal) integer to N q (Z t )ā ql .

As before, nql is in the interval (N q (Z t )ā ql -1, N q (Z t )ā ql + 1) so we have

|ā ql -nql /N q (Z t )| < 1/N q (Z 1:T ) < ǫr n /(6c √ n). Moreover 0 ≤ nql ≤ N q (Z t ) because 0 ≤ N q (Z t )ā ql ≤ N q (Z t
). We also have (by induction)

l l ′ =1 (N q (Z t )ā ql ′ -nql ′ ) =         l-1 l ′ =1 N q (Z t )ā ql ′ -nql ′         + N q (Z t )ā ql -nql < 1.
In the end, we have n). This leads to

| Q l=1 (N q (Z t )ā ql -nql )| < 1 i.e. |N q (Z t ) -Q l=1 nql | < 1, meaning that Q l=1 nql = N q (Z t ), both N q (Z t ) and Q l=1 nql being integers. Then, if n > 6c √ n/[ǫr n (δ -η)], there exists Ȃ ∈ A t (Z 1:T ) such that Ȃ -Āπ ∞ < ǫr n /(6c √
P θ *        1 T T t=1 M(π, Āt π ) -M(π, Āπ ) > ǫr n 6 √ n        ≤ QT exp(-2η 2 n) + 1 -1 n>6c √ n/[ǫr n (δ-η)]
which concludes the proof.

B.7 Proof of Lemma 7

We can upper bound the expectation as follows

E θ * N q (Z 1 )N l (Z 1 ) n(n -1) -α * q α * l =E θ * N q (Z 1 ) n -α * q N l (Z 1 ) n -1 + α * q N l (Z 1 ) n -1 -α * l ≤E θ * N q (Z 1 ) n -α * q N l (Z 1 ) n -1 + α * q E θ * N l (Z 1 ) n -1 -α * l ≤ E θ *        N q (Z 1 ) n -α * q 2        E θ * N l (Z 1 ) 2 (n -1) 2 + α * q E θ *        N l (Z 1 ) n -1 -α * l 2        .
We have for any q ∈ 1, Q

E θ * N q (Z 1 ) 2 = i, j E θ * 1 Z 1 i =q 1 Z 1 j =q = i α * q + i j α * 2 q = nα * q + n(n -1)α * 2 q .
This implies that

E θ *        N q (Z 1 ) n -α * q 2        = E θ * N q (Z 1 ) 2 n 2 -α * 2 q = 1 n α * q + n -1 n α * 2 q -α * 2 q = 1 n α * q (1 -α * q ),
and identically

E θ *        N l (Z 1 ) n -1 -α * l 2        = E θ * N l (Z 1 ) 2 (n -1) 2 + α * 2 l -2 n n -1 α * 2 l = n (n -1) 2 α * l - 1 n -1 α * 2 l = 1 n -1 α * l n n -1 -α * l .
This leads to

E θ * N q (Z 1 )N l (Z 1 ) n(n -1) -α * q α * l ≤ 1 n α * q (1 -α * q ) n (n -1) 2 α * q + n n -1 α * 2 q + α * q 1 n -1 α * l n n -1 -α * l ≤ 1 (n -1) 2 + 1 n -1 + n (n -1) 2 ≤ 2 √ n n -1 , (46)
using the fact that 0 ≤ α * q ≤ 1 for every q ∈ 1, Q .

B.8 Proof of Lemma 8

We first consider the case when T → ∞, and π is constant over time. We use the following lemma.

Lemma 16. For any θ ∈ Θ, we have for ǫ small enough (0 < ǫ < min 1≤q q ′ ≤Q max 1≤l≤Q |π * qlπ * q ′ l |/2)

min σ∈S Q π σ -π * ∞ > ǫ =⇒ M(π * ) -M(π) > 2δ 2 Q 2 ǫ 2 .
This gives an upper bound on the probability of interest

P θ * min σ∈S Q πσ -π * ∞ > ǫ √ v n,T ≤ P θ * M(π * ) -M( π) > 2δ 2 Q 2 ǫ 2 v n,T .
By definition of θ = ( Γ, π), we write

M(π * ) = F n,T ( Γ, π * ) + M(π * ) -F n,T ( Γ, π * ) ≤ F n,T ( Γ, π) + M(π * ) -F n,T ( Γ, π * ), implying that M(π * ) -M( π) ≤ F n,T ( Γ, π) -M( π) + M(π * ) -F n,T ( Γ, π * ) .
We then obtain the following upper bound, that converges to 0 as n and T increase by assumption,

P θ * min σ∈S Q πσ -π * ∞ > ǫ √ v n,T ≤P θ * F n,T ( Γ, π) -M( π) > δ 2 Q 2 ǫ 2 v n,T + P θ * M(π * ) -F n,T ( Γ, π * ) > δ 2 Q 2 ǫ 2 v n,T .
When the number of time steps T is fixed and π is allowed to vary over time, the proof is almost the same. Indeed, min σ 1 ,...,σ T ∈S Q π1:T

σ 1:T -π * 1:T ∞ > ǫ √ v n means that there exists t ∈ 1, T such that min σ t ∈S Q πt σ t -π * t ∞ > ǫ √
v n and we can apply Lemma 16 to this πt to obtain that M(π * t ) -M( πt ) > 2ǫ 2 δ 2 v n /Q 2 . This implies that M T (π * 1:T ) -M T ( π1:T ) > 2ǫ 2 δ 2 v n /(T Q 2 ), which allows to conclude in the same way as before.

B.9 Proof of Lemma 9

We have log P θ(Z 1:T = z 1:T | X 1:T ) P θ(Z 1:T = z * 1:T | X 1:T ) = log P θ(X 1:T | Z 1:T = z 1:T ) P θ(X 1:T | Z 1:T = z * 1:T ) + log P θ(Z 1:T = z 1:T ) P θ(Z 1:T = z * 1:T )

= T t=1 1≤i< j≤n        X t i j log πz t i z t j πz * t i z * t j + (1 -X t i j ) log 1 -πz t i z t j 1 -πz * t i z * t j        + n i=1 log αz 1 i αz * 1 i + T -1 t=1 n i=1 log γz t i z t+1 i γz * t i z * t+1 i .
We decompose this sum as

log P θ(Z 1:T = z 1:T | X 1:T ) P θ(Z 1:T = z * 1:T | X 1:T ) = T t=1 1≤i< j≤n          X t i j log π * z t i z t j π * z * t i z * t j + (1 -X t i j ) log 1 -π * z t i z t j 1 -π * z * t i z * t j          + n i=1 log αz 1 i αz * 1 i + T -1 t=1 n i=1 log γz t i z t+1 i γz * t i z * t+1 i + T t=1 1≤i< j≤n          X t i j log πz t i z t j π * z t i z t j π * z * t i z * t j πz * t i z * t j + (1 -X t i j ) log 1 -πz t i z t j 1 -π * z t i z t j 1 -π * z * t i z * t j 1 -πz * t i z * t j          . (47)
In the first sum of the right-hand side of ( 47), the terms are different from zero only for triplets (i, j, t) in D * . Similarly in the last sum, the terms are different from zero for triplets (i, j, t) in D * ∪ D. As a consequence, we obtain

log P θ(Z 1:T = z 1:T | X 1:T ) P θ(Z 1:T = z * 1:T | X 1:T ) = (i, j,t)∈D *          X t i j log π * z t i z t j π * z * t i z * t j + (1 -X t i j ) log 1 -π * z t i z t j 1 -π * z * t i z * t j          + n i=1 log αz 1 i αz * 1 i + T -1 t=1 n i=1 log γz t i z t+1 i γz * t i z * t+1 i + (i, j,t)∈D * ∪ D          X t i j log πz t i z t j π * z t i z t j π * z * t i z * t j πz * t i z * t j + (1 -X t i j ) log 1 -πz t i z t j 1 -π * z t i z t j 1 -π * z * t i z * t j 1 -πz * t i z * j          .
We now write the last sum in the right-hand side as

(i, j,t)∈D * ∪ D          X t i j log πz t i z t j π * z t i z t j π * z * t i z * t j πz * t i z * t j + (1 -X t i j ) log 1 -πz t i z t j 1 -π * z t i z t j 1 -π * z * t i z * t j 1 -πz * t i z * t j          = (i, j,t)∈D * ∪ D          X t i j          log          1 + πz t i z t j -π * z t i z t j π * z t i z t j          + log π * z * t i z * t j πz * t i z * t j          + (1 -X t i j )          log          1 - πz t i z t j -π * z t i z t j 1 -π * z t i z t j          + log 1 -π * z * t i z * t j 1 -πz * t i z * t j                   .
Distinguishing between the cases where X t i j = 1 and X t i j = 0, we obtain

(i, j,t)∈D * ∪ D          X t i j log πz t i z t j π * z t i z t j π * z * t i z * t j πz * t i z * t j + (1 -X t i j ) log 1 -πz t i z t j 1 -π * z t i z t j 1 -π * z * t i z * t j 1 -πz * t i z * t j          = (i, j,t)∈D * ∪ D log          1 + ( πz t i z t j -π * z t i z t j )(X t i j -π * z t i z t j ) π * z t i z t j (1 -π * z t i z t j )          - (i, j,t)∈D * ∪ D log          1 + ( πz * t i z * t j -π * z * t i z * t j )(X t i j -π * z * t i z * t j ) π * z * t i z * t j (1 -π * z * t i z * t j )          .
In the end, we decompose

log P θ(Z 1:T = z 1:T | X 1:T ) P θ(Z 1:T = z * 1:T | X 1:T ) = (i, j,t)∈D *          X t i j log π * z t i z t j π * z * t i z * t j + (1 -X t i j ) log 1 -π * z t i z t j 1 -π * z * t i z * t j          + n i=1 log αz 1 i αz * 1 i + T -1 t=1 n i=1 log γz t i z t+1 i γz * t i z * t+1 i + (i, j,t)∈D * ∪ D log          1 + ( πz t i z t j -π * z t i z t j )(X t i j -π * z t i z t j ) π * z t i z t j (1 -π * z t i z t j )          - (i, j,t)∈D * ∪ D log          1 + ( πz * t i z * t j -π * z * t i z * t j )(X t i j -π * z * t i z * t j ) π * z * t i z * t j (1 -π * z * t i z * t j )          ,
which gives the result.

B.10 Proof of Lemma 10

We first notice that

D n,T (z 1:T , π) = 1 2 (i, j, t) ∈ 1, n 2 × 1, T ; π z t i z t j π z * t i z * t j = 1 2 T t=1 (i, j) ∈ 1, n 2 ; π z t i z t j π z * t i z * t j .
For every t ∈ 1, T , we can apply Proposition B.4. from [START_REF] Celisse | Consistency of maximum-likelihood and variational estimators in the stochastic block model[END_REF], as their Assumption (A4) is required to hold only for z * t (see proof) and is valid on Ω η (θ) with the constant δη. We obtain

(i, j) ∈ 1, n 2 ; π z t i z t j π z * t i z * t j ≥ (δ -η) 2 2 nr(t).
We conclude by noticing that T t=1 r(t) = r.

B.11 Proof of Lemma 11

The inclusion of the sets is straightforward. Now we have

(i, j, t) ∈ 1, n 2 × 1, T ; π z t i z t j π z * t i z * t j ≤ (i, j, t) ∈ 1, n 2 × 1, T ; (z t i , z t j ) (z * t i , z * t j ) ≤ (i, j, t) ∈ 1, n 2 × 1, T ; z t i z * t i + (i, j, t) ∈ 1, n 2 × 1, T ; z t j z * t j ≤2 T t=1 nr(t) ≤ 2nr.

B.12 Proof of Lemma 12

First, let us decompose the quantity at stake as follows

P θ *         1 n(T -1) T -1 t=1 n i=1 P θσ Z t i = q, Z t+1 i = l | X 1:T -α * q γ * ql > ǫr n,T log n √ nT         ≤P θ *         1 n(T -1) T -1 t=1 n i=1 P θσ Z t i = q, Z t+1 i = l | X 1:T - N ql (Z 1:T ) n(T -1) > ǫ 2 r n,T log n √ nT         + P θ *        N ql (Z 1:T ) n(T -1) -α * q γ * ql > ǫ 2 r n,T log n √ nT        , (48)
and upper bound the two terms in the right-hand side of (48). For the first one we will follow the proof of Theorem 3.9 from [START_REF] Celisse | Consistency of maximum-likelihood and variational estimators in the stochastic block model[END_REF]. Let z 1:T denote a fixed configuration. We work on the set {Z 1:T = z 1:T } and write

V 1 (z 1:T ) ≔ 1 n(T -1) T -1 t=1 n i=1 P θσ Z t i = q, Z t+1 i = l | X 1:T - N ql (z 1:T ) n(T -1) ≤ 1 n(T -1) T -1 t=1 n i=1 P θσ Z t i = q, Z t+1 i = l | X 1:T 1 (z t i ,z t+1 i )=(q,l) - N ql (z 1:T ) n(T -1) + 1 n(T -1) T -1 t=1 n i=1 P θσ Z t i = q, Z t+1 i = l | X 1:T 1 (z t i ,z t+1 i ) (q,l) ≤ 1 n(T -1) T -1 t=1 n i=1 1 -P θσ (Z t i , Z t+1 i ) = (z t i , z t+1 i ) | X 1:T 1 (z t i ,z t+1 i )=(q,l) + 1 n(T -1) T -1 t=1 n i=1 P θσ (Z t i , Z t+1 i ) (z t i , z t+1 i ) | X 1:T 1 (z t i ,z t+1 i ) (q,l) ≤ 2P θσ Z 1:T z 1:T | X 1:T . Then P θ *        V 1 (Z 1:T ) > ǫ 2 r n,T log n √ nT        =E θ *        P θ *        V 1 (Z 1:T ) > ǫ 2 r n,T log n √ nT Z 1:T               ≤ z 1:T P θ *        P θσ Z 1:T z 1:T | X 1:T > ǫ 4 r n,T log n √ nT Z 1:T = z 1:T        P θ * Z 1:T = z 1:T ≤ z 1:T P θ *         P θσ Z 1:T z 1:T | X 1:T P θσ Z 1:T = z 1:T | X 1:T > ǫ 4 r n,T log n √ nT Z 1:T = z 1:T         P θ * Z 1:T = z 1:T ≤QT exp(-2η 2 n) + P θ * πσ -π * ∞ > v n,T + CnT exp        -(δ -η) 2 C 1 n + C 2 log(nT ) + C 4 log        4 √ nT ǫr n,T log n               + CnT exp        -C 3 (log(nT )) 2 nv 2 n,T + 3n log(nT )        , (49)
where the last inequality comes from Theorem 2 where the bound is uniform with respect to z 1:T . Now, for the second term of (48), we use the following lemma.

Lemma 17. There exist c 1 , c 2 > 0 such that for any ǫ > 0, for any sequence {r n,T } n,T ≥1 , we have, as long as

ǫr n,T log n/(2α * q γ * ql √ nT ) < 1, P θ *        N ql (Z 1:T ) n(T -1) -α * q γ * ql > ǫ 2 r n,T log n √ nT        ≤ c 1 exp -c 2 ǫ 2 r 2 n,T . (50)
We then combine the two upper bounds obtained in ( 49) and ( 50) in order to conclude, the assumption ǫr n,T log n/(2α * q γ * ql √ nT ) < 1 being satisfied for n and T large enough because r n,T = o( nT/ log n). We obtain the expected result, using the fact that log(T ) = o(n), that r n,T increases to infinity and that v n,T = o log(nT )/n ,

P θ *         1 n(T -1) T -1 t=1 n i=1 P θσ Z t i = q, Z t+1 i = l | X 1:T -α * q γ * ql > ǫy n,T         ≤ P θ * πσ -π * ∞ > v n,T + o(1).

B.13 Proof of Lemma 13

We have the following inequalities by definition of ẑ1:T , J(χ, θ) and χ(θ) and because the Kullback-Leibler divergence is non-negative

J(ẑ 1:T , θ) ≤ J( χ(θ), θ) ≤ ℓ(θ) ≤ ℓ c (θ, ẑ1:T ), (51)
with J(ẑ 1:T , θ) = ℓ(θ) -KL(δ ẑ1:T , P θ (•|X 1:T )). We write this Kullback-Leibler divergence (from

P θ (•|X 1:T ) to Q χ = δ ẑ1:T , with χ = (τ, η) such that τ t iq = ẑt iq and η t iql = ẑt iq ẑt+1 il ) as follows KL(δ ẑ1:T , P θ (•|X 1:T )) = -log P θ (ẑ 1:T |X 1:T ).
We then obtain

J(ẑ 1:T , θ) = log P θ (X 1:T ) + log P θ (ẑ 1:T |X 1:T ) = P θ (X 1:T |ẑ 1:T ) + log P θ (ẑ 1:T ) =ℓ c (θ; ẑ1:T ) + n i=1 log α ẑ1 i + n i=1 T t=2 log γ ẑt-1 i ẑt i .
Combined with (51), this leads to the following inequality for any parameter θ ∈ Θ

|J( χ(θ), θ) -ℓ(θ)| ≤ J(ẑ 1:T , θ) -ℓ c (θ, ẑ1:T ) ≤ - n i=1 log α ẑ1 i - n i=1 T t=2 log γ ẑt-1 i ẑt i ≤ nT log(1/δ).
We can conclude that sup

θ∈Θ 2 n(n -1)T J( χ(θ), θ) - 2 n(n -1)T ℓ(θ) ≤ 2 log(1/δ) n -1 .

B.14 Proof of Lemma 14

This proof is quite similar to that of Lemma 12. For any ǫ > 0, let us write

P θ *         1 n(T -1) n i=1 T -1 t=1 Q χ( θσ ) (Z t i = q, Z t+1 i = l) -α * q γ * ql > ǫr n,T log n √ nT         ≤P θ *         1 n(T -1) n i=1 T -1 t=1 Q χ( θσ ) (Z t i = q, Z t+1 i = l) - N ql (Z 1:T ) n(T -1) > ǫ 2 r n,T log n √ nT         + P θ *        N ql (Z 1:T ) n(T -1) -α * q γ * ql > ǫ 2 r n,T log n √ nT       
and upper bound the two probabilities in the right-hand side of this inequality. We already proved in Lemma 12 that the second term converges to 0 thanks to the assumptions on the sequence {r n,T } n,T ≥1 . For the first term, let z 1:T denote a fixed configuration. Let us work on the set {Z 1:T = z 1:T } and use the same method as in the proof of Lemma 12,

1 n(T -1) n i=1 T -1 t=1 Q χ( θσ ) (Z t i = q, Z t+1 i = l) = 1 n(T -1) n i=1 T -1 t=1 Q χ( θσ ) (Z t i = q, Z t+1 i = l)1 z t i =q,z t+1 i =l + 1 n(T -1) n i=1 T -1 t=1 Q χ( θσ ) (Z t i = q, Z t+1 i = l)1 (z t i ,z t+1 i ) (q,l) , leading to 1 n(T -1) n i=1 T -1 t=1 Q χ( θσ ) (Z t i = q, Z t+1 i = l) - N ql (z 1:T ) n(T -1) ≤2Q χ( θσ ) (Z 1:T z 1:T ).
Then we obtain

P θ *         1 n(T -1) n i=1 T -1 t=1 Q χ( θσ ) (Z t i = q, Z t+1 i = l) - N ql (Z 1:T ) n(T -1) > ǫ 2 r n,T log n √ nT         ≤ z 1:T P θ *        Q χ( θσ ) (Z 1:T z 1:T ) > ǫ 4 r n,T log n √ nT Z 1:T = z 1:T        P θ * Z 1:T = z 1:T .
For each z 1:T , we use the following lemma.

Lemma 18. Denoting Pσ (•) = P˜θ σ (Z 1:T = • | X 1:T ), we have the following inequality for any configuration z 1:T Q χ( θσ ) (z 1:T ) -Pσ (z 1:T ) ≤ -1 2 log Pσ (z 1:T ) .

This gives us

P θ *        Q χ( θσ ) (Z 1:T z 1:T ) > ǫ 4 r n,T log n √ nT
Noticing that the assumptions on {r n,T } n,T ≥1 imply that

-log        1 -exp        - ǫ 2 r 2 n,T log n 32nT               = o(n) and -log        r n,T log n √ nT        = o(n),
we can conclude by applying the result of Theorem 2 with the estimator θσ = ( Γσ , πσ ) for both terms of the right-hand side of (52).

B.15 Proof of Lemma 15

The proof follows the lines of the proof of Lemma C.3. from [START_REF] Celisse | Consistency of maximum-likelihood and variational estimators in the stochastic block model[END_REF]. Let E * θ * [•] denote the expectation given Z 1:T = z * 1:T , i.e.

E * θ * [•] = E θ * [• | Z 1:T = z * 1:T ].
Introducing a ghost sample { Xt i j } i, j,t that is independent of {X t i j } i, j,t and has the same distribution, we write

E ≔E * θ *          sup (z 1:T ,π)∈ 1,Q nT ×[ζ,1-ζ] Q 2 2 n(n -1)T T t=1 i< j (X t i j -π * z * t i z * t j ) log        π z t i z t j 1 -π z t i z t j                 =E * θ *          sup (z 1:T ,π)∈ 1,Q nT ×[ζ,1-ζ] Q 2 2 n(n -1)T E * θ *         T t=1 i< j (X t i j -Xt i j ) log        π z t i z t j 1 -π z t i z t j        {X t i j } i, j,t                  ≤E * θ *          E * θ *          sup (z 1:T ,π)∈ 1,Q nT ×[ζ,1-ζ] Q 2 2 n(n -1)T T t=1 i< j (X t i j -Xt i j ) log        π z t i z t j 1 -π z t i z t j        {X t i j } i, j,t                   ≤E * θ * ,X, X          sup (z 1:T ,π)∈ 1,Q nT ×[ζ,1-ζ] Q 2 2 n(n -1)T T t=1 i< j (X t i j -Xt i j ) log        π z t i z t j 1 -π z t i z t j                 ,
where E * θ * ,X, X [•] denotes the expectation with respect to {X, X} = {X t i j , Xt i j } i, j,t under the true parameter θ * and given Z 1:T = z * 1:T . At this point, we notice that, if {ǫ t i j } i, j,t ≔ ǫ are n 2 T independent Rademacher variables, then the random variables E ǫ T t=1 i< j ǫ t i j (X

E * θ * ,X, X          sup (z 1:T ,π)∈ 1,Q nT ×[ζ,1-ζ] Q 2 2 n(n -1)T E ǫ T t=1 i< j ǫ t i j (X t i j -Xt i j ) log        π z t i z t j 1 -π z t i z t j                 = E * θ * ,X, X          sup (z 1:T ,π)∈ 1,Q nT ×[ζ,1-ζ] Q 2 2 n(n -1)T T t=1 i< j (X t i j -Xt i j ) log        π z t i z t j 1 -π z t i z t j                 .
As a consequence, we have

E ≤E * θ * ,X, X          sup (z 1:T ,π)∈ 1,Q nT ×[ζ,1-ζ] Q 2 2 n(n -1)T E ǫ T t=1 i< j ǫ t i j (X t i j -Xt i j ) log        π z t i z t j 1 -π z t i z t j                 ≤E * θ *          sup (z 1:T ,π)∈ 1,Q nT ×[ζ,1-ζ] Q 2 2 n(n -1)T E ǫ T t=1 i< j ǫ t i j X t i j log        π z t i z t j 1 -π z t i z t j                 + E * θ *          sup (z 1:T ,π)∈ 1,Q nT ×[ζ,1-ζ] Q 2 2 n(n -1)T E ǫ T t=1 i< j ǫ t i j Xt i j log        π z t i z t j 1 -π z t i z t j                 ≤2E * θ *          sup (z 1:T ,π)∈ 1,Q nT ×[ζ,1-ζ] Q 2 2 n(n -1)T E ǫ T t=1 i< j ǫ t i j X t i j log        π z t i z t j 1 -π z t i z t j                 .
Then using Jensen's inequality, Assumption 3 and the bound Var ǫ (ǫ t i j X t i j ) ≤ 1, we get

E ≤2E * θ *             sup (z 1:T ,π)∈ 1,Q nT ×[ζ,1-ζ] Q 2 2 n(n -1)T E ǫ                  T t=1 i< j ǫ t i j X t i j log        π z t i z t j 1 -π z t i z t j                2                      ≤2E * θ *           sup (z 1:T ,π)∈ 1,Q nT ×[ζ,1-ζ] Q 2 2 n(n -1)T Var ǫ         T t=1 i< j ǫ t i j X t i j log        π z t i z t j 1 -π z t i z t j                          ≤2E * θ *        2 n(n -1)T sup π∈[ζ,1-ζ] log π 1 -π n(n -1)T 2        ≤ 2 n(n -1)T Λ,
where Λ = 2 log[(1ζ)/ζ], concluding the proof.

B.16 Proof of Lemma 16

We assume that min σ∈S Q π σπ * ∞ > ǫ. Without loss of generality, assume that the permutation (or one of the permutations) minimizing this distance is the identity. Let us write, using the fact that I Q the identity matrix of size Q maximizes in A (over the set of Q × Q stochastic matrices) the quantity M(π * , A) (see the proof of Theorem 3.6 in [START_REF] Celisse | Consistency of maximum-likelihood and variational estimators in the stochastic block model[END_REF]) and denoting (ā qq ′ ) q,q ′ ∈ 1,Q the coefficients of Āπ (thus depending on π),

M(π * ) -M(π) = q,l α * q α * l q ′ ,l ′ āqq ′ āll ′       π * ql log π * ql π q ′ l ′ + (1 -π * ql ) log 1 -π * ql 1 -π q ′ l ′       = q,l α * q α * l q ′ ,l ′ āqq ′ āll ′ K(π * ql , π q ′ l ′ )
denoting K(p 1 , p 2 ) = p 1 log(p 1 /p 2 ) + (1p 1 ) log[(1p 1 )/(1p 2 )] > 0 the Kullback-Leibler divergence from a Bernoulli distribution with parameter p 2 to a Bernoulli distribution with parameter p 1 . For every q, there exists q ′ ≔ f (q) such that āqq ′ ≥ 1/Q because Āπ is a stochastic matrix. Using Assumption 2, we obtain

M(π * ) -M(π) ≥ δ 2 Q 2 q,l K(π * ql , π f (q) f (l) ) ≥ δ 2 Q 2 q,l 2(π * ql -π f (q) f (l) ) 2
thanks to a result on Kullback-Leibler divergence for Bernoulli distributions (see for instance [START_REF] Bubeck | Jeux de bandits et fondations du clustering[END_REF], Chapter 10, Section 2, Lemma 10.3). We then want to show that there exist q, l such that |π * qlπ f (q) f (l) | > ǫ. • If f is a permutation, the assumption min σ∈S Q π σπ * ∞ > ǫ gives the expected result.

• If f is not a permutation, it is not injective and there exist q 1 q 2 such that f (q 1 ) = f (q 2 ). Thanks to Assumption 1, take l 0 ∈ 1, Q such that |π q 1 l 0π q 2 l 0 | = max l∈ 1,Q |π q 1 lπ q 2 l | > 0. Then |π * q 1 l 0π f (q 1 ) f (l 0 ) | + |π f (q 2 ) f (l 0 )π * q 2 l 0 | ≥ |π * q 1 l 0π f (q 1 ) f (l 0 ) + π f (q 2 ) f (l 0 )π * q 2 l 0 | = |π * q 1 l 0π * q 2 l 0 | > 0 leading to either |π * q 1 l 0π f (q 1 ) f (l 0 ) | ≥ |π * q 1 l 0π * q 2 l 0 |/2 > ǫ or |π * q 2 l 0π f (q 2 ) f (l 0 ) | ≥ |π * q 1 l 0π * q 2 l 0 |/2 > ǫ, using the fact that ǫ < min 1≤q q ′ ≤Q max 1≤l≤Q |π * qlπ * q ′ l |/2. So, as there exist q, l such that |π * qlπ f (q) f (l) | > ǫ, we have

M(π * ) -M(π) > 2δ 2 Q 2 ǫ 2 .
B.17 Proof of Lemma 17

For any node i ∈ 1, n , the Markov chain {Z t i } t≥1 is geometrically ergodic because its transition matrix Γ satisfies Doeblin's condition thanks to Assumption 2. For any z ∈ 1, Q , let us denote δ z the Dirac mass at z. There exists a positive constant A and some r ∈ (0, 1) such that ∀q ∈ 1, Q and ∀t ≥ 1, we have

δ q Γ t -α T V ≤ Ar t ,
where • T V is the total variation norm. This leads to

δ q Γ t -α T V = 1 2 δ q Γ t -α 1 = 1 2 l∈ 1,Q |Γ t (q, l) -α l | ≤ Ar t .
We now consider the Markov chain {Z t = (Z t 1 , . . . , Z t n )} t≥1 of the n nodes evolving through time. Note that it is irreducible and aperiodic. Moreover, its transition matrix is given by P n = Γ ⊗n , the n-th Kronecker power of Γ and its stationary distribution is α ⊗n . For any z = (z 1 , . . . , z n ) ∈ 1, Q n , let us denote µ n,z = ⊗ n i=1 δ z i . For every t ≥ 1, we can decompose

µ n,z P t n -α ⊗n T V = n ⊗ i=1 δ z i (Γ ⊗n ) t -α ⊗n T V = n ⊗ i=1 δ z i (Γ t ) ⊗n -α ⊗n T V = n ⊗ i=1 δ z i Γ t -α ⊗n T V = 1 2 n ⊗ i=1 δ z i Γ t -α ⊗n 1 = 1 2 (z ′ 1 ,...,z ′ n )∈ 1,Q n n i=1 Γ t (z i , z ′ i ) - n i=1 α z ′ i .
We use

n i=1 Γ t (z i , z ′ i ) - n i=1 α z ′ i = n i=1                  i-1 j=1 α z ′ j         Γ t (z i , z ′ i ) -α z ′ i n k=i+1 (µ z k Γ t ) z ′ k         
.

So, reorganizing the terms, we write

µ n,z P t n -α ⊗n T V ≤ 1 2 (z ′ 1 ,...,z ′ n )∈ 1,Q n n i=1                  i-1 j=1 α z ′ j         Γ t (z i , z ′ i ) -α z ′ i n k=i+1 (µ z k Γ t ) z ′ k          ≤ 1 2 n i=1 z ′ 1 α z ′ 1 . . . z ′ i-1 α z ′ i-1 z ′ i Γ t (z i , z ′ i ) -α z ′ i z ′ i+1 Γ t (z i+1 , z ′ i+1 ) . . . z ′ n Γ t (z n , z ′ n ) ≤ 1 2 n i=1 z ′ i Γ t (z i , z ′ i ) -α z ′ i ≤ nAr t .
Let us recall the definition of an ǫ-mixing time. For any Markov transition matrix M over the set X with stationary distribution α, for any ǫ > 0, the ǫ-mixing time of the Markov chain is defined as

τ(ǫ) = min{t ≥ 1; max x∈X δ x M t -α T V ≤ ǫ}.
Denoting by τ n (ǫ) the ǫ-mixing time of the Markov chain {Z t } t≥1 , we thus obtain τ n (ǫ) ≤ log(nA/ǫ) log(1/r) .

Now, we introduce a new Markov chain Y = {Y t } t≥1 , that is defined by

Y t = (Z t , Z t+1 ) ∀t ≥ 1.
Notice that it is irreducible and aperiodic, with stationary distribution ρ defined for every state (q t 1 , . . . , q t n , q t+1 1 , . . . , q t+1 n ) by ρ (q t 1 ,...,q t n ,q t+1 1 ,...,q t+1 n ) = α q t 1 . . . α q t n γ q t 1 q t+1 1 . . . γ q t n q t+1 n .

It is easily seen that for any ǫ > 0, its ǫ-mixing time τ Y,n (ǫ) equals τ n (ǫ) + 1. We apply Theorem 3 from Chung et al.

[2012], for any η ≤ 1/8, considering the weight function f (Y t ) = n i=1 for every t ≥ 1 (of expectation nα * q γ * ql under the stationary distribution). Then N ql (Z 1:T ) = T -1 t=1 f (Y t ), and denoting ǫ n,T = ǫr n,T log n/(2α * q γ * ql √ nT ), we obtain that there exist c 1 , c 2 > 0 such that for any ǫ > 0, as long as ǫ n,T ≤ 1

P θ *        N ql (Z 1:T ) n(T -1) -α * q γ * ql > ǫ 2 r n,T log n √ nT        =P θ * N ql (Z 1:T ) > (1 + ǫ n,T )nα * q γ * ql (T -1)
+ P θ * N ql (Z 1:T ) < (1ǫ n,T )nα * q γ * ql (T -1)

≤c 1 exp        - ǫ 2 n,T nα * q γ * ql (T -1) 72τ Y,n (η)        ≤ c 1 exp -c 2 ǫ 2 r 2 n,T .

Acknowledgement

Work partly supported by the grant ANR-18-CE02-0010 of the French National Research Agency ANR (project EcoNet).

B.18 Proof of Lemma 18

For any configuration z 1:T ,

the third inequality being true because by definition Q χ( θσ ) minimizes KL(•, Pσ ) over the set of variational distributions.