Elizabeth S Allman
email: e.allman@uaf.edu

Catherine Matias
email: catherine.matias@genopole.cnrs.fr

John A Rhodes
email: j.rhodes@uaf.edu

Identifiability of parameters in latent structure models with many observed variables *

Keywords: AMS 2000 subject classifications: Primary 62E10; secondary 62F99, 62G99 Identifiability, finite mixture, latent structure, conditional independence, multivariate Bernoulli mixture, non-parametric mixture, contingency table, algebraic statistics

Identifiability of parameters in latent structure models with many observed variables

Abstract: While hidden class models of various types arise in many statistical applications, it is often difficult to establish the identifiability of their parameters. Focusing on models in which there is some structure of independence of some of the observed variables conditioned on hidden ones, we demonstrate a general approach for establishing identifiability, utilizing algebraic arguments. A theorem of J. Kruskal for a simple latent-class model with finite state space lies at the core of our results, though we apply it to a diverse set of models. These include mixtures of both finite and non-parametric product distributions, hidden Markov models, and random graph mixture models, and lead to a number of new results and improvements to old ones.

In the parametric setting, this approach indicates that for such models the classical definition of identifiability is typically too strong. Instead generic identifiability holds, which implies that the set of non-identifiable parameters has measure zero, so that parameter inference is still meaningful. In particular, this sheds light on the properties of finite mixtures of Bernoulli products, which have been used for decades despite being known to have non-identifiable parameters. In the non-parametric setting, we again

Introduction

Statistical models incorporating latent variables are widely used to model heterogeneity within datasets, via a hidden structure. However, the fundamental theoretical question of the identifiability of parameters of such models can be difficult to address. For specific models it is even known that certain parameter values lead to non-identifiability, while empirically the model appears to be well-behaved for most values. Thus, parameter inference procedures may still be performed, even though theoretical justification of their consistency is still lacking. In some cases (e.g., hidden Markov models [START_REF] Petrie | Probabilistic functions of finite state Markov chains[END_REF]), it has been formally established that generic choices of parameters are identifiable, which means that only a subset of parameters of measure zero may not be identifiable.

In this work, we consider a number of such variable models, all of which exhibit a conditional independence structure, in which (some of) the observed variables are independent when conditioned on the unobserved ones. In particular, we investigate 1. finite mixtures of products of finite measures, where the mixing parameters are unknown (including finite mixtures of multivariate Bernoulli distributions), also called latent-class models in the literature, 2. finite mixtures of products of non-parametric measures, again with unknown mixing parameters, 3. discrete hidden Markov models, 4. a random graph mixture model, in which the probability of the presence of an edge is determined by the hidden states of the vertices it joins.

We show how a fundamental algebraic result of J. Kruskal [START_REF] Kruskal | More factors than subjects, tests and treatments: an indeterminacy theorem for canonical decomposition and individual differences scaling[END_REF][START_REF] Kruskal | Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics[END_REF] on 3-way tables can be used to derive identifiability results for all of these models. While Kruskal's work is focused on only 3 variates, each with finite state spaces, we use it to obtain new identifiability results for mixtures with more variates (point 1, above), whether discrete or continuous (point 2). For hidden Markov models (point 3), with their more elaborate dependency structure, Kruskal's work allows us to easily recover some known results on identifiability that were originally approached with other tools, and to strengthen them in certain aspects. For the random graph mixture model (point 4), in which the presence/absence of each edge is independent conditioned on the states of all vertices, we obtain new identifiability results via this method, again by focusing on the model's essential conditional independence structure. While we establish the validity of many identifiability statements not previously known, the major contribution of this paper lies as much in the method of analysis it introduces. By relating a diverse collection of models to Kruskal's work, we indicate the applicability of this method of establishing identifiability to a variety of models with appropriate conditional independence structure. Although our example of applying Kruskal's work to a complicated model such as the random graph one requires substantial additional algebraic arguments tied to the details of the model, it illustrates well that the essential insight can be a valuable one.

Finally, we note that in establishing identifiability of the parameters of a model this method clearly indicates one must allow for the possibility of certain 'exceptional' choices of parameter values which are not identifiable. However, as these exceptional values can be characterized through algebraic conditions, one may deduce that they are of measure zero within the parameter space (in the finite-dimensional case). Since 'generic' parameters are identifiable, one is unlikely to face identifiability problems in performing inference. Thus generic identifiability of the parameters of a model is generally sufficient for data analysis purposes. Although the notion of identifiability of parameters off a set of measure zero is not a new one, neither the usefulness of this notion nor its algebraic origins seem to have been widely recognized.

Background

Latent structure models form a very large class of models including, for instance, finite univariate or multivariate mixtures [START_REF] Mclachlan | Finite mixture models[END_REF], hidden Markov models [START_REF] Cappé | Inference in hidden Markov models[END_REF][START_REF] Ephraim | Hidden Markov processes[END_REF] and non-parametric mixtures [START_REF] Lindsay | Mixture models: theory, geometry and applications[END_REF].

General formulations of the identification problem were made by several authors and pioneering works may be found in [START_REF] Koopmans | The identification of structural characteristics[END_REF][START_REF] Tjalling | Statistical Inference in Dynamic Economic Models[END_REF]. The study of identifiability proceeds from a hypothetical exact knowledge of the distribution of observed variables and asks whether one may, in principle, recover the parameters. Thus, identification problems are not problems of statistical inference in a strict sense. However, since non-identifiable parameters cannot be consistently estimated, identifiability is a prerequisite of statistical parameter inference.

In the following, we are interested in models defined by a family M(Θ) = {P θ , θ ∈ Θ} of probability distributions on some space Ω, with parameter space Θ (not necessarily finite-dimensional). The classical definition of identifiability, which we will refer to as strict identifiability, requires that for any two different values θ = θ ′ in Θ, the corresponding probability distributions P θ and P θ ′ are different. This is exactly to require injectivity of the model's parameterization map Ψ, which takes values in M 1 (Ω), the set of probability measures on Ω, and is defined by Ψ(θ) = P θ .

In many cases, the above map will not be strictly injective. For instance, it is well known that in models with discrete hidden variables (such as finite mixtures or discrete hidden Markov models), the latent classes can be freely relabeled without changing the distribution of the observations, a phenomenon known as 'label swapping.' In this sense, the above map is always at least r!-to-one, where r is the number of classes in the model. However, this does not prevent the statistician from inferring the parameters of these models. Indeed, parameter identifiability up to a permutation on the class labels (which we henceforth consider as a type of strict identifiability), is largely enough for practical use, at least in a maximum likelihood setting. Note that the label swapping issue may cause major problems in a Bayesian framework, see for instance [START_REF] Mclachlan | Finite mixture models[END_REF]Section 4.9].

A related concept of local identifiability only requires the parameter to be unique in small neighborhoods in the parameter space. For parametric models (i.e., when the parameter space is finite-dimensional), with some regularity conditions, there is an equivalence between local identifiability of the parameters and nonsingularity of the information matrix [START_REF] Thomas | Identification in parametric models[END_REF]. When an iterative procedure is used to approximate an estimator of the parameter, different initializations can help to detect multiple solutions of the estimation problem. This often corresponds to the existence of multiple parameter values giving rise to the same distribution. However, the validity of such procedures relies on knowing that the parameterization map is at most finite-to-one and a precise characterization of the value of k such that it is a k-to-one map would be most useful.

Thus, knowledge that the parameterization map is finite-to-one might be too weak a result from a statistical perspective on identifiability. Moreover, we argue in the following that infinite-to-one maps might not be problematic, as long as they are generic k-to-one maps for known finite k.

While all our results are proved relying on the same underlying tool, they must be expressed differently in the parametric framework (including the finite case) and in the non-parametric one.

The parametric framework

While the focus on one-to-one or k-to-one parameterization maps is well-suited for most of the classical models encountered in the literature, it is inadequate in some important cases. For instance, it is well-known that finite mixtures of Bernoulli products are not identifiable [START_REF] Gyllenberg | Nonuniqueness in probabilistic numerical identification of bacteria[END_REF], even up to a relabelling of latent classes. However, these distributions are widely used to model data when many binary variables are observed from individuals belonging to different unknown populations, and parameter estimation procedures are performed in this context. For instance, these models may be used in numerical identification of bacteria (see [START_REF] Gyllenberg | Nonuniqueness in probabilistic numerical identification of bacteria[END_REF] and the references therein). Statisticians are aware of this apparent contradiction; the title of the article [START_REF] Miguel | Practical identifiability of finite mixtures of multivariate Bernoulli distributions[END_REF], Practical identifiability of finite mixtures of multivariate Bernoulli distributions, indicates the need to reconcile non-identifiability and validity of inference procedures, and clearly indicates that the strict notion of identifiability is not useful in this specific context. We establish that parameters of finite mixtures of multivariate Bernoulli distributions (with a fixed number of components) are in fact generically identifiable (see Section 5).

Here 'generic' is used in the sense of algebraic geometry, as will be defined in the subsection on algebraic terminology below. Most importantly, it implies that the set of points for which identifiability does not hold has measure zero. In this sense, any observed data set has probability one of being drawn from a distribution with identifiable parameters.

Understanding when generic identifiability holds, even in the case of finite measures, can be mathematically difficult. There are well-known examples of latent-class models in which the parameterization map is in fact infinite-to-one, for reasons that are not immediately obvious. For instance, Goodman [START_REF] Goodman | Exploratory latent structure analysis using both identifiable and unidentifiable models[END_REF] describes a 3-class model with four manifest binary variables, and thus a parameter space of dimension 3(4) + 2 = 14. Though the distributions resulting from this model lie in a space of dimension 2 4 -1 = 15, the image of the parameterization map has dimension only 13. From a statistical point of view, this results in non-identifiability.

An important observation that underlies our investigations is that many finite space models (e.g., latent-class models, hidden Markov models) involve parameterization maps which are polynomial in the scalar parameters. Thus, statistical models have recently been studied by algebraic geometers [START_REF] David | Algebraic geometry of Bayesian networks[END_REF][START_REF]Algebraic Statistics for Computational Biology[END_REF]. Even in the more general case of distributions belonging to an exponential family, which lead to analytic but non-polynomial maps, it is possible to use perspectives from algebraic geometry. See, for instance, [START_REF] Allman | The identifiability of tree topology for phylogenetic models, including covarion and mixture models[END_REF][START_REF] Allman | The identifiability of covarion models in phylogenetics[END_REF][START_REF] Drton | Algebraic techniques for Gaussian models[END_REF]. Algebraic geometers use terminology rather different from the statistical language, for instance, describing the image of the parameterization map of a simple latent-class model as a higher secant variety of a Segre variety. When the dimension of this variety is less than expected, as in the example of Goodman above, the variety is termed defective, and one may conclude the parameterization map is generically infinite-to-one. Recent works such as [START_REF] Abo | Induction for secant varieties of Segre varieties[END_REF][START_REF] Catalisano | Ranks of tensors, secant varieties of Segre varieties and fat points[END_REF][START_REF] Catalisano | Higher secant varieties of the Segre varieties P 1 × • • • × P 1[END_REF] have made much progress on determining when defects occur.

However, as pointed out by Elmore, Hall, and Neeman [START_REF] Elmore | An application of classical invariant theory to identifiability in nonparametric mixtures[END_REF], focusing on dimension is not sufficient for a complete understanding of the identifiability question. Indeed, even if the dimensions of the parameter space and the image match, the parameterization might be a generically k-to-one map, and the finite number k cannot be characterized by using dimension approaches. For example, consider latent-class models, assuming the number r of classes is known. In this context, even though the dimensions agree, we might have a generically k-to-one map with k > r!. (Recall that r! corresponds to the number of points which are equivalent by permutating label classes.)

This possibility was already raised in the context of psychological studies by J. Kruskal [START_REF] Kruskal | More factors than subjects, tests and treatments: an indeterminacy theorem for canonical decomposition and individual differences scaling[END_REF] whose work in [START_REF] Kruskal | Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics[END_REF] provides a strong result ensuring generic r!to-oneness of the parameterization map for latent r-class models, under certain conditions. Kruskal's work, however, is focused on models with only 3 observed variables or, in other terms, on secant varieties of Segre products with 3 factors, or on 3-way arrays. While the connection of Kruskal's work to the algebraic geometry literature seems to have been overlooked, the nature of his result is highly algebraic.

Although [START_REF] Elmore | An application of classical invariant theory to identifiability in nonparametric mixtures[END_REF] is ultimately directed at understanding non-parametric mixtures, Elmore, Hall, and Neeman address the question of identifiability of the parameterization for latent-class models with many binary observed variables (i.e., for secant varieties of Segre products of projective lines with many factors, or on 2 × 2 × • • • × 2 tables). These are just the mixtures of Bernoulli products referred to above, though the authors never introduce that terminology. Using algebraic methods, they show that with sufficiently many observed variables, the image of the parameterization map is birationally equivalent to a symmetrization of the parameter space under the symmetric group Σ r . Thus, for sufficiently many observed variables, the parameterization map is generically r!-to-one. (Although the generic nature of the result is not made explicit, that is, however, all that one can deduce from a birational equivalence.) Their proof is constructive enough to give a numerical understanding of how many observed variables are sufficient, though this number's growth in r is much larger than is necessary (see Corollary 5 and Theorem 8 for more details).

The non-parametric framework

Non-parametric mixture models have received much attention recently [START_REF] Benaglia | An EM-like algorithm for semi and non parametric estimation in multivariate mixtures[END_REF][START_REF] Hall | Nonparametric estimation of component distributions in a multivariate mixture[END_REF][START_REF] Hettmansperger | Almost nonparametric inference for repeated measures in mixture models[END_REF]. They provide an interesting framework for modelling very general heterogeneous data. However, identifiability is a difficult and crucial issue in such a high-dimensional setting.

Using algebraic methods to study statistical models is most straightforward when state spaces are finite. One way of handling continuous random variables via an algebraic approach is to discretize the problem by binning the random variable into a finite number of sets. For instance, [START_REF] Cruz-Medina | Semiparametric mixture models and repeated measures: the multinomial cut point model[END_REF][START_REF] Elmore | Estimating component cumulative distribution functions in finite mixture models[END_REF][START_REF] Hettmansperger | Almost nonparametric inference for repeated measures in mixture models[END_REF] developed cut points methods, to transform multivariate continuous observations into Binomial or Multinomial random variables.

As already mentioned, Elmore, Hall, and Neeman [START_REF] Elmore | An application of classical invariant theory to identifiability in nonparametric mixtures[END_REF] consider a finite mixture of products of continuous distributions. By binning each continuous random variable X to create a binary one, defined by the indicator function 1{X ≤ t}, for some choice of t, they pass to a related finite model. But identification of a distribution is equivalent to identification of its cumulative distribution function (cdf) F (t) = P(X ≤ t). Having addressed the question of identifiability of the parameters of a mixture of products of binary variables, they can thus argue for the identifiability of the parameters of the original continuous model, as they continue to do so in [START_REF] Hall | Nonparametric inference in multivariate mixtures[END_REF]. However, because the authors are not explicit about the generic aspect of their results in [START_REF] Elmore | An application of classical invariant theory to identifiability in nonparametric mixtures[END_REF], there are significant gaps in the formal justification of their claims. Moreover, the bounds they claim on the number of observed variable which ensure generic identifiability leave much room for improvement, as they point out.

The general approach

Our theme in this work is the applicability of the fundamental result of Kruskal on 3-way arrays to a spectrum of models with latent structure. Though our ap-proach is highly algebraic, it has little in common with that of [START_REF] Elmore | An application of classical invariant theory to identifiability in nonparametric mixtures[END_REF][START_REF] Hall | Nonparametric inference in multivariate mixtures[END_REF] for establishing that with sufficiently many observed variables the parameterization map of r-latent-class models is either generically r!-to-one in the parametric case, or that it is exactly r!-to-one (under some conditions) in the non-parametric case. Our results apply not only to binary variables, but as easily to ones with more states, or even to continuous ones. In the case of binary variables (multivariate Bernoulli mixtures), we obtain a much lower upper bound for a sufficient number of variables to ensure generic identifiability (up to label swapping) than the one that can be deduced from [START_REF] Elmore | An application of classical invariant theory to identifiability in nonparametric mixtures[END_REF], and in fact our bound gives the correct order of growth, log 2 r. (The constant factor we obtain is however still unlikely to be optimal.)

While our first results are on the identifiability of finite mixtures (with a fixed number of components) of finite measure products, our method has further consequences for more sophisticated models with a latent structure. Our approach for such models with finite state spaces can be summarized very simply: we group the observed variables into 3 collections, and view the composite states of each collection as the states of a single clumped variable. We choose our collections so that they will be conditionally independent given the states of some of the hidden variables. Viewing these hidden variables as a single composite one, the model reduces to a special instance of the model Kruskal studied. Thus Kruskal's result on 3-way tables can be applied, after a little work, to show that Kruskal's condition is satisfied. This might be done either by showing that the clumping process results in a sufficiently generic model (ensuring Kruskal's condition is automatically satisfied for generic parameters), or that explicit restrictions on the parameters ensure this clumping process satisfies Kruskal's condition. In more geometric terms, we embed a complicated finite model into a simple latent-class model with 3 observed variables, taking care to verify that the embedding does not end up in the small set for which Kruskal's result tells us nothing.

To take up the continuous random variables case, we simply bin the realvalued random variables into a partition of R into κ intervals and apply the previous method to the new discretized random variables. As a consequence, we are able to prove that finite mixtures of non-parametric independent variates, with at least 3 variates, have identifiable parameters under a mild and explicit regularity condition. This is in sharp contrast not only with [START_REF] Elmore | An application of classical invariant theory to identifiability in nonparametric mixtures[END_REF][START_REF] Hall | Nonparametric inference in multivariate mixtures[END_REF], but also with works such as [START_REF] Hettmansperger | Almost nonparametric inference for repeated measures in mixture models[END_REF], where the components of the mixture are assumed to be independent but also identically distributed and [START_REF] Hall | Nonparametric estimation of component distributions in a multivariate mixture[END_REF], which dealt only with r = 2 groups (see Section 7 for more details).

We note that Kruskal's result has already been successfully used in phylogeny, to prove identifiability of certain models of evolution of biological sequences along a tree [START_REF] Allman | The identifiability of covarion models in phylogenetics[END_REF]. However, application of Kruskal's result is limited to hidden class models, or to other models with some conditional independence structure, which have at least 3 observed variates. Kruskal's theorem can sometimes be used for models with many hidden variables, by considering a clumped latent variable Z = (Z 1 , . . . , Z n ). We give two examples of such a use for models presenting a dependency structure on the observations, namely hidden Markov models (Section 6.1) and mixture models for random graphs (Section 6.2). For hidden Markov models, we recover many known results, and improve on some of them. For the random graph mixture model, we establish identifiability for the first time. Note that in all these applications we always assume the number of latent classes is known, which is crucial in using Kruskal's approach. Identification of the number of classes is an important issue that we do not consider here.

Algebraic terminology

Polynomials play an important role throughout our arguments, so we introduce some basic terminology and facts from algebraic geometry that we need. For a more thorough but accessible introduction to the field, we recommend [START_REF] Cox | Ideals, varieties, and algorithms[END_REF].

An algebraic variety V is defined as the simultaneous zero-set of a finite collection of multivariate polynomials

{f i } n i=1 ⊂ C[x 1 , x 2 , . . . , x k ], V = V (f 1 , . . . , f n ) = {a ∈ C k | f i (a) = 0, 1 ≤ i ≤ n}.
A variety is all of C k only when all f i are 0; otherwise, a variety is called a proper subvariety and must be of dimension less than k, and hence of Lebesgue measure 0 in C k . Analogous statements hold if we replace C k by R k , or even by any subset Θ ⊆ R k containing an open k-dimensional ball. This last possibility is of course most relevant for the statistical models of interest to us, since the parameter space is naturally identified with a full-dimensional subset of [0, 1] L for some L (see Section 3 for more details). Intersections of algebraic varieties are algebraic varieties as they are the simultaneous zero-set of the unions of the original sets of polynomials. Finite unions of varieties are also varieties, since if sets S 1 and S 2 define varieties, then {f g | f ∈ S 1 , g ∈ S 2 } defines their union. Given a set Θ ⊆ R k of full dimension, we will often need to say some property holds for all points in Θ except possibly for those on some proper subvariety Θ∩ V (f 1 , . . . f n ). We express this succinctly by saying the property holds generically on Θ. We emphasize that the set of exceptional points of Θ, where the property need not hold, is thus necessarily of Lebesgue measure zero.

In studying parametric models, Θ is typically taken to be the parameter space for the model, so that a claim of generic identifiability of model parameters means that all non-identifiable parameter choices lie within a proper subvariety, and thus form a set of Lebesgue measure zero. While we do not always explicitly characterize the subvariety in statements of theorems, one could do so by careful consideration of our proofs.

In a non-parametric context, where algebraic terminology appropriate to the finite dimensional setting is inappropriate, we avoid the use of the term 'generic'. Instead we always give explicit characterizations of those parameter choices which may not be identifiable.

Roadmap

We first present finite mixtures of finite measure products with a conditional independence structure (or latent-class models) in Section 3. Then, Kruskal's result and consequences are presented in Section 4. Direct consequences on the identifiability of the parameters of finite mixtures of finite measure products appear in Section 5. More complicated dependent variables models, including hidden Markov models and a random graph mixture model, are studied in Section 6. In Section 7, we consider mixtures of non-parametric distributions, analogous to the finite ones considered earlier. All proofs are postponed to Section 8.

Finite mixtures of finite measure products

Consider a vector of observed random variables {X j } 1≤j≤p where X j has finite state space with cardinality κ j . Note that these variables are not assumed to be i.i.d. nor to have the same state space. To model the distribution of these variables, we use a latent (unobserved) random variable Z with values in {1, . . . , r} where r is assumed to be known. We interpret Z as denoting an unobservable class, and assume that conditional on Z, the X j 's are independent random variables. The probability distribution of Z is given by the vector π = (π i ) ∈ (0, 1) r with π i = 1. Moreover, the probability distribution of X j conditional on Z = i is specified by a vector p ij ∈ [0, 1] κj . We use the notation p ij (l) for the l-th coordinate of this vector (1 ≤ l ≤ κ j ). Thus, we have l p ij (l) = 1.

For each class i, the joint distribution of the variables X 1 , . . . , X p conditional on Z = i is then given by a p-dimensional κ 1 × • • • × κ p table

P i = p j=1 p ij , whose (l 1 , l 2 , . . . , l p )-entry is p j=1 p ij (l j ). Let P = r i=1 π i P i . ( 1
)
Then P is the distribution of a finite mixture of finite measure products, with a known number r of components. The π i are interpreted as probabilities that a draw from the population is in the ith of r classes. Conditioned on the class, the p observable variables are independent. However, since the class is not discernible, the p feature variables X j described by one-dimensional marginalizations of P are generally not independent.

We refer to the model described above as the r-class, p-feature model with state space {1, . . . , κ 1 }ו • •×{1, . . . , κ p }, and denote it by M(r; κ 1 , κ 2 , . . . , κ p ). Identifying the parameter space of this model with a subset Θ of [0, 1] L where L = (r -1) + r p i=1 (κ i -1) and letting K = p i=1 κ i , the parameterization map for this model is Ψ r,p,(κi) : Θ → [0, 1] K .

In the following, we specify parameters by vectors such as π and p ij , always implicitly assuming their entries add to 1.

As previously noted, this model's parameters are not strictly identifiable if r > 1, since the sum in equation ( 1) can always be reordered without changing P. Even modulo this label swapping, there are certainly special instances when identifiability will not hold. For instance, if P i = P j , then the parameters π i and π j can be varied, as long as their sum π i + π j is held fixed, without effect on the distribution P. Slightly more elaborate 'special' instances of nonidentifiability can be constructed, but in full generality this issue remains poorly understood. Ideally, one would know for which choices of r, p, (κ i ) generic values of the model's parameters are identifiable up to permutation of the terms in (1), and additionally have a characterization of the exceptional set of parameters on which identifiability fails.

Kruskal's theorem and its consequences

The basic identifiability result on which we build our later arguments is a result of J. Kruskal [START_REF] Kruskal | More factors than subjects, tests and treatments: an indeterminacy theorem for canonical decomposition and individual differences scaling[END_REF][START_REF] Kruskal | Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics[END_REF] in the context of factor analyses for p = 3 features. Kruskal's result deals with a 3-way contingency table (or array) which crossclassifies a sample of n individuals with respect to 3 polytomous variables (the ith of which takes values in {1, . . . , κ i }). If there is some latent variable Z with values in {1, . . . , r} so that each of the n individuals belongs to one of the r latent classes and within the lth latent class, the 3 observed variables are mutually independent, then this r-class latent structure would serve as a simple explanation of the observed relationships among the variables in the 3-way contingency table. This latent structure analysis corresponds exactly to the model M(r; κ 1 , κ 2 , κ 3 ) described in the previous section.

To emphasize the focus on 3-variate models, note that in [START_REF] Kruskal | Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics[END_REF] Kruskal points out that 2-way tables arising from the model M(r; κ 1 , κ 2 ) do not have a unique decomposition when r ≥ 2. This non-identifiability is intimately related to the non-uniqueness of certain matrix factorizations. While Goodman [START_REF] Goodman | Exploratory latent structure analysis using both identifiable and unidentifiable models[END_REF] studied the model M(r; κ 1 , κ 2 , κ 3 , κ 4 ) for fitting to 4-way contingency tables, no formal result about uniqueness of the decomposition was established. In fact, nonidentifiability of the model under certain circumstances is highlighted in that work.

To present Kruskal's result, we introduce some algebraic notation. For j = 1, 2, 3, let M j be a matrix of size r × κ j , with

m j i = (m j i (1), . . . , m j i (κ j )) the ith row of M j . Let [M 1 , M 2 , M 3 ] denote the κ 1 × κ 2 × κ 3 tensor defined by [M 1 , M 2 , M 3 ] = r i=1 m 1 i ⊗ m 2 i ⊗ m 3 i . In other words, [M 1 , M 2 , M 3 ] is a three-dimensional array whose (u, v, w) ele- ment is [M 1 , M 2 , M 3 ] u,v,w = r i=1 m 1 i (u) m 2 i (v) m 3 i (w), for any 1 ≤ u ≤ κ 1 , 1 ≤ v ≤ κ 2 , 1 ≤ w ≤ κ 3 . Note that [M 1 , M 2 , M 3 ] is left
unchanged by simultaneously permuting the rows of all the M j and/or rescaling the rows so that the product of the scaling factors used for the m j i , j = 1, 2, 3 is equal to 1.

A key point is that the probability distribution in a finite latent-class model with three observed variables is exactly described by such a tensor: Let M j , j = 1, 2, 3 be the matrix whose ith row is

p ij = P(X j = • | Z = i). Let M1 = diag(π)M 1 be the matrix whose ith row is π i p i1 . Then the (u, v, w) el- ement of the tensor [ M1 , M 2 , M 3 ] equals P(X 1 = u, X 2 = v, X 3 = w). Thus, knowledge of the distribution of (X 1 , X 2 , X 3 ) is equivalent to the knowledge of the tensor [ M1 , M 2 , M 3 ].
Note that the M i s are stochastic matrices and thus the vector of π i s can be thought of as scaling factors.

For a matrix M , the Kruskal rank of M will mean the largest number I such that every set of I rows of M are independent. Note that this concept would change if we replaced 'row' by 'column,' but we will only use the row version in this paper. With the Kruskal rank of M denoted by rank K M , we have rank K M ≤ rank M, and equality of rank and Kruskal rank does not hold in general. However, in the particular case where a matrix M of size p × q has rank p, it also has Kruskal rank p.

The fundamental algebraic result of Kruskal is the following.

Theorem 1. (Kruskal [START_REF] Kruskal | More factors than subjects, tests and treatments: an indeterminacy theorem for canonical decomposition and individual differences scaling[END_REF][START_REF] Kruskal | Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics[END_REF]) Let I j = rank K M j . If

I 1 + I 2 + I 3 ≥ 2r + 2, then [M 1 , M 2 , M 3 ]
uniquely determines the M j , up to simultaneous permutation and rescaling of the rows.

The equivalence between the distributions of 3-variate latent-class models and 3-tensors, combined with the fact that rows of stochastic matrices sum to 1, gives the following reformulation.

Corollary 2. Consider the model M(r; κ 1 , κ 2 , κ 3 ), with the parameterization of Section 3. Suppose all entries of π are positive. For each j = 1, 2, 3, let M j denote the matrix whose rows are p ij , i = 1, . . . , r, and let I j denote its Kruskal rank. Then if

I 1 + I 2 + I 3 ≥ 2r + 2,
the parameters of the model are uniquely identifiable, up to label swapping.

By observing that Kruskal's condition on the sum of Kruskal ranks can be expressed through polynomial inequalities in the parameters, and thus holds generically, we obtain the following corollary.

Corollary 3. The parameters of the model M(r; κ 1 , κ 2 , κ 3 ) are generically identifiable, up to label swapping, provided min(r, κ 1 ) + min(r, κ 2 ) + min(r, κ 3 ) ≥ 2r + 2.

The assertion remains valid if in addition the class proportions {π i } 1≤i≤r are held fixed and positive in the model.

For the last statement of this corollary, we note that if the mixing proportions are positive then one can translate Kruskal's condition into a polynomial requirement so that only the parameters p ij (l) = P(X j = l | Z = i) appear. Thus, the generic aspect only concerns this part of the parameter space, and not the part with the proportions π i . As a consequence, the statement is valid when the proportions are held fixed in (0, 1). This is of great importance, as often statisticians assume that these proportions are fixed and known (for instance using π i = 1/r for every 1 ≤ i ≤ r). Without observing this fact, we would not have a useful identifiability result in the case of known π i , since fixing values of the π i results in considering a subvariety of the full parameter space, which a priori might be included in the subvariety of non-identifiable parameters allowed by Corollary 3.

Parameter identifiability of finite mixtures of finite measure products

Finite mixtures of products of finite measure are widely used to model data, for instance in biological taxonomy, medical diagnosis, or classification of text documents [START_REF] Glick | Sample-based multinomial classification[END_REF][START_REF] Nigam | Text classification from labeled and unlabeled documents using EM[END_REF]. The identifiability issue for these models was first addressed forty years ago by Teicher [START_REF] Teicher | Identifiability of mixtures of product measures[END_REF]. Teicher's result states the equivalence between identifiability of mixtures of product measure distributions and identifiability of the corresponding one-dimensional mixture models. As a consequence, finite mixtures of Bernoulli products are not identifiable in a strict sense [START_REF] Gyllenberg | Nonuniqueness in probabilistic numerical identification of bacteria[END_REF]. Teicher's result is valid for finite mixtures with an unknown number of components, but it can easily be seen that non-identifiability occurs even with a known number of components [6, Section 1]. The very simplicity of the equivalence condition stated by Teicher [START_REF] Teicher | Identifiability of mixtures of product measures[END_REF] likely impeded statisticians from looking further at this issue.

Here we prove that finite mixtures of Bernoulli products (with a known number of components) are in fact generically identifiable, indicating why these models are well-behaved in practice with respect to statistical parameter inference, despite their lack of strict identifiability [START_REF] Miguel | Practical identifiability of finite mixtures of multivariate Bernoulli distributions[END_REF].

To obtain our results, we must first pass from Kruskal's theorem on 3-variate models to a similar one for p-variate models. To do this, we observe that p observed variables can be combined into 3 agglomerate variables, so that Kruskal's result can be applied.

Theorem 4. Consider the model M(r; k 1 , . . . , k p ) where p ≥ 3. Suppose there exists a tripartition of the set S = {1, . . . , p} into three disjoint non-empty subsets S 1 , S 2 , S 3 , such that if κ i = j∈Si k j then min(r, κ 1 ) + min(r, κ 2 ) + min(r, κ 3 ) ≥ 2r + 2.

(

) 2
Then model parameters are generically identifiable, up to label swapping. Moreover, the statement remains valid when the mixing proportions {π i } 1≤i≤r are held fixed and positive.

Considering the special case of finite mixtures of r Bernoulli products with p components (i.e, the r-class, p-binary feature model M(r; 2, 2, . . . , 2)), to obtain the strongest identifiability result we choose a tripartition that maximizes the left hand side of inequality [START_REF] Allman | The identifiability of tree topology for phylogenetic models, including covarion and mixture models[END_REF]. Doing so yields the following.

Corollary 5. Parameters of the finite mixture of r different Bernoulli products with p components are generically identifiable, up to label swapping, provided

p ≥ 2 ⌈log 2 r⌉ + 1,
where ⌈x⌉ is the smallest integer at least as large as x.

Note that generic identifiability of this model for sufficiently large values of p is a consequence of the results of Elmore, et al., in [START_REF] Elmore | An application of classical invariant theory to identifiability in nonparametric mixtures[END_REF], although neither the generic nature of the result, nor the fact that the model is simply a mixture of Bernoulli products, is noted by the authors. Moreover, our lower bound on p to ensure generic identifiability is superior to the one obtained in [START_REF] Elmore | An application of classical invariant theory to identifiability in nonparametric mixtures[END_REF]. Indeed, letting C(r) be the minimal integer such that if p ≥ C(r) then the r-class, p-binary feature model is generically identifiable, then [START_REF] Elmore | An application of classical invariant theory to identifiability in nonparametric mixtures[END_REF] established that

log 2 r ≤ C(r) ≤ c 2 r log 2 r
for some effectively computable constant c 2 . While the lower bound for C(r) is easy to obtain from the necessity that the dimension of the parameter space, rp + (r -1), be no larger than that of the distribution space 2 p -1, the upper bound required substantial work. Corollary 5 above establishes the stronger result that C(r) ≤ 2 ⌈log 2 r⌉ + 1.

Note that this new upper bound, along with the simple lower bound, shows that the order of growth of C(r) is precisely log 2 r.

For the more general M(r; κ, . . . , κ) model, our lower bound on the number of variates needed to generically identify the parameters, up to label swapping, is p ≥ 2 ⌈log κ r⌉ + 1.

The proof of this bound follows the same lines as that of Corollary 5, and is therefore omitted.

Hidden classes models with dependent observations

In this section, we give several additional illustrations of the applicability of Kruskal's result in the context of dependent observations. The hidden Markov models and random graph mixture models we consider may at first appear to be far from the focus of Kruskal's theorem. This is not the case, however, as in both the observable variables are independent when appropriately conditioned on hidden ones. We succeed in embedding these models into an appropriate M(3; κ 1 , κ 2 , κ 3 ) and then use extensive algebraic arguments to obtain the (generic) identifiability results we desire.

Hidden Markov models

Almost 40 years ago Petrie [39, Theorem 1.3] proved generic identifiability, up to label swapping, for discrete hidden Markov models (HMMs). We offer a new proof, based on Kruskal's theorem, of this well-known result. This provides an interesting alternative to Petrie's more direct approach, and one that might extend to more complex frameworks, such as Markov chains with Markov regime, where no identifiability results are known (see for instance [START_REF] Chambaz | Number of hidden states and memory: a joint order estimation problem for Markov chains with Markov regime[END_REF]). Moreover, as a by-product, our approach establishes a new bound on the number of consecutive variables needed such that the marginal distribution for a generic HMM uniquely determines the full probability distribution.

We first briefly describe HMMs. Consider a stationary Markov chain {Z n } n≥0 on state space {1, . . . , r} with transition matrix A and initial distribution π (assumed to be the stationary distribution). Conditional on {Z n } n≥0 , the observations {X n } n≥0 on state space {1, . . . , κ} are assumed to be i.i.d., and the distribution of each X n only depends on Z n . Denote by B the matrix of size r × κ containing the conditional probabilities P(X n = k | Z n = i). The process {X n } n≥0 is then a hidden Markov chain. Note that this is not a Markov process. The matrices A and B constitute the parameters for the r-hidden state, κ-observable state HMM, and the parameter space can be identified with a fulldimensional subset of R r(r+κ-2) . We refer to [START_REF] Cappé | Inference in hidden Markov models[END_REF][START_REF] Ephraim | Hidden Markov processes[END_REF] for more details on HMMs.

Petrie [START_REF] Petrie | Probabilistic functions of finite state Markov chains[END_REF] describes quite explicitly, for fixed r and κ, a subvariety of the parameter space for an HMM on which identifiability might fail. Indeed, Petrie proved that the set of parameters on which identifiability holds is the intersection of the following: the set of regular HMMs; the set where the components of the matrix B, namely P(X n = k | Z n = i) are non-zero; the set where some row of B has distinct entries (namely there exists some i ∈ {1, . . . , r} such that all the {P(X n = k | Z n = i)} k are distinct); the set where the matrix A is nonsingular and 1 is an eigenvalue with multiplicity one for A (namely, P ′ (1, A) = 0 where P (λ, A) = det(λI -A)). Regular HMMs were first described by Gilbert in [START_REF] Gilbert | On the identifiability problem for functions of finite Markov chains[END_REF]. The definition relies on a notion of rank and an HMM is regular if its rank is equal to its number of hidden states r. More details may be found in [START_REF] Finesso | Consistent estimation of the order for Markov and hidden Markov chains[END_REF][START_REF] Gilbert | On the identifiability problem for functions of finite Markov chains[END_REF].

The result of Petrie assumes knowledge of the whole probability distribution of the HMM. But it is known [17, Lemma 1.2.4] that the distribution of an HMM with r hidden states and κ observed states, is completely determined by the marginal distribution of 2r consecutive variables. An even stronger result appears in [38, Chapter 1, Corollary 3.4]: the marginal distribution of 2r -1 consecutive variables suffices to reconstruct the whole HMM distribution. Combining these results shows that generic identifiability holds for HMMs from the distribution of 2r -1 consecutive observations. Note there is no dependence of this number on κ, even though one might suspect a larger observable state space would aid identifiability.

Using Kruskal's theorem we prove the following.

Theorem 6. The parameters of an HMM with r hidden states and κ observable states are generically identifiable from the marginal distribution of 2k + 1 consecutive variables provided k satisfies

k + κ -1 κ -1 ≥ r. (3)
While we do not explicitly characterize a set of possibly non-identifiable parameters as Petrie did, in principle we could do so.

Note, however, that we require only the marginal of 2k + 1 consecutive variables, where k satisfies an explicit condition involving κ. The worst case (i.e. the largest value for k) arises when κ = 2, since κ → k + κ -1 κ -1 is an increasing function for positive κ. In this worst case, we easily compute that 2k +1 = 2r -1 consecutive variables suffice to generically identify the parameters. Thus our approach yields generic versions of the claims of [START_REF] Finesso | Consistent estimation of the order for Markov and hidden Markov chains[END_REF] and [START_REF] Paz | Introduction to probabilistic automata[END_REF] described above. Moreover, when the number κ of observed states is increased, the minimal value of 2k + 1 which ensures identifiability by Theorem 6 becomes smaller. Thus the fact that generic HMMs are characterized by the marginal of 2k + 1 consecutive variables, where k satisfies (3), results in a much better bound than 2r -1 as soon as the observed state space has more than 2 points. In this sense, our result is stronger than the one of Paz [START_REF] Paz | Introduction to probabilistic automata[END_REF].

In proving Theorem 6, we embed the hidden Markov model in a simpler latent-class model, as illustrated in Figure 1. The hidden variable Z k is the only one we preserve, while we cluster the observed variables into groups so they may be treated as 3 observed variables. According to properties of graphical models (see for instance [START_REF] Steffen | of Oxford Statistical Science Series[END_REF]), the agglomerated variables are independent when conditioned on Z k . So Kruskal's theorem applies. However, additional algebraic arguments are needed to see that the embedding gives sufficiently generic points so that we may identify parameters.

To conclude this section, note that Leroux [START_REF] Leroux | Maximum-likelihood estimation for hidden Markov models[END_REF] used Teicher's result [START_REF] Teicher | Identifiability of mixtures of product measures[END_REF] to establish a sufficient condition for exact identifiability of parametric hidden Markov models, with possibly continuous observations.

Z 0 Z k Z 2k X 0 X k X 2k X k Z k X 0 X k-1 X 2k X k+1

A random graph mixture model

We next illustrate the application of our method to studying a random graph mixture model. This heterogeneous model is used in a wide range of applications, such as molecular biology (gene interactions or metabolic networks [START_REF] Daudin | A mixture model for random graphs[END_REF]), social sciences (relationships or co-authorship networks [START_REF] Nowicki | Estimation and prediction for stochastic blockstructures[END_REF]) or the study of the world wide web (hyperlinks graphs [START_REF] Zanghi | Fast online graph clustering via Erdös Rényi mixture[END_REF]).

We consider a random graph mixture model in which each node belongs to some unobserved class, or group, and, conditional on the classes of all nodes, the edges are independent random variables whose distributions depend only on the classes of the nodes they connect. More precisely, consider an undirected graph with n nodes labelled 1, . . . , n and where presence/absence of an edge between two different nodes i and j is given by the indicator variable X ij . Let {Z i } 1≤i≤n be i.i.d. random variables with values in {1, . . . , r} and probability distribution π ∈ (0, 1) r representing node classes. Conditional on the classes of nodes {Z i }, the edge indicators X ij are independent random variables whose distribution is Bernoulli with some parameter p ZiZj . The between-groups connection parameters p ij ∈ [0, 1] satisfy p ij = p ji , for all 1 ≤ i, j ≤ r. We emphasize that the observed random variables X ij for this model are not independent, just as the observed variables were not independent in the mixture models considered earlier in this paper.

The interest in the random graph model lies in the fact that different nodes may have different connectivity properties. For instance one class may describe hubs which are nodes with a very high connectivity, and a second class may contain the others nodes with a lower overall connectivity. Thus one can model different node behaviours with a reasonable number of parameters. Examples of networks easily modelled with this approach, and more details on the properties of this model, can be found in [START_REF] Daudin | A mixture model for random graphs[END_REF]. This model has been rediscovered many times in the literature and in various fields of applications. A non-exhaustive bibliography includes [START_REF] Daudin | A mixture model for random graphs[END_REF][START_REF] Frank | Cluster inference by using transitivity indices in empirical graphs[END_REF][START_REF] Nowicki | Estimation and prediction for stochastic blockstructures[END_REF][START_REF] Tallberg | A Bayesian approach to modeling stochastic blockstructures with covariates[END_REF]. However, identifiability of the parameters for this random graph model has never been addressed in the literature.

In [START_REF] Frank | Cluster inference by using transitivity indices in empirical graphs[END_REF], Frank and Harary study the statistical inference of the parameters in the restricted α-β or affiliation model. In this setup, only two parameters are used to model the intra-group and inter-group probabilities of an edge occurrence p ii = α, 1 ≤ i ≤ r and p ij = β, 1 ≤ i < j ≤ r. Using the total number of edges, the proportion of transitive triads and the proportion of 3-cycles among triads (see definitions ( 3) and ( 4) in [START_REF] Frank | Cluster inference by using transitivity indices in empirical graphs[END_REF]), they obtain estimates of the parameters α, β and sometimes r, in various cases (α, β unknown and π i = 1/r with unknown r, for instance). However, they do not discuss the uniqueness of the solutions of the non-linear equations defining those estimates (see equations ( 16), ( 29) and ( 33) in [START_REF] Frank | Cluster inference by using transitivity indices in empirical graphs[END_REF]).

We prove the following result.

Theorem 7. The parameters of the random graph model with r = 2 node states are strictly identifiable, up to label swapping, provided there are at least 16 nodes and the connection parameters {p 11 , p 12 , p 22 } are distinct.

Our basic approach is to embed the random graph model into a model to which Kruskal's theorem applies. Since we have many hidden variables, one for each node, we combine them into a single composite variable describing the states of all nodes at once. Since the observed edge variables are binary, we also combine them into collections, to create 3 composite edge variables with more states. We do this in such a way that the composite edge variables are still independent conditioned on the composite node state. The main technical difficulty is that the matrices whose entries give probabilities of observing a composite edge variable conditioned on a composite node state must have wellunderstood Kruskal rank. This requires some involved algebraic work.

The random graph model will be studied more thoroughly in a forthcoming work. The special case of the affiliation model, which is not adressed by Theorem 7, will be dealt with there as well.

Finite mixtures of non-parametric measure products

In this section, we consider a non-parametric model of finite mixtures of r different probability distributions µ 1 , . . . , µ r on R p , with p ≥ 3. For every 1 ≤ i ≤ r, we denote by µ j i the jth marginal of µ i and F j i the corresponding cdf (defined by

F j i (t) = µ j i ((-∞, t]
) for any t ∈ R). Without loss of generality, we may assume that the functions F j i are absolutely continuous. For our first result, we assume further that the mixture model has the form

P = r i=1 π i µ i = r i=1 π i p j=1 µ j i , (4)
in which, conditional on a latent structure (specified by the proportions π i ), the p variates are independent. The µ j i are viewed in a non-parametric setting. In the next theorem, we prove identifiability of the model's parameters -that is, that P uniquely determines the factors appearing in equation ( 4) -under a mild and explicit regularity condition on P, as soon as there are at least 3 variates and r is known. Making a judicious use of cut points to discretize the distribution, and then using Kruskal's work, we prove the following.

Theorem 8. Let P be a mixture of the form (4), such that for every j ∈ {1, . . . , p}, the measures {µ j i } 1≤i≤r are linearly independent. Then, if p ≥ 3, the parameters {π i , µ j i } 1≤i≤r,1≤j≤p are strictly identifiable from P, up to label swapping.

This result also generalizes to non-parametric mixture models where at least three blocks of variates are independent conditioned on the latent structure. Let b 1 , . . . , b p be integers with p ≥ 3 the number of blocks, and the µ j i be absolutely continuous probability measures on R bj . With m = j b j , consider the mixture distribution on R m given by

P = r i=1 π i p j=1 µ j i . ( 5
)
Theorem 9. Let P be a mixture of the form (5), such that for every j ∈ {1, . . . , p}, the measures {µ j i } 1≤i≤r on R bj are linearly independent. Then, if p ≥ 3, the parameters {π i , µ j i } 1≤i≤r,1≤j≤p are strictly identifiable from P, up to label swapping.

Both Theorem 8 and Theorem 9 could be strengthened somewhat, as their proofs do not depend on the full power of Kruskal's theorem. As an analog of Kruskal rank for a matrix, say a finite set of measures has Kruskal rank k if k is the maximal integer such that every k-element subset is linearly independent. Then, for instance, when p = 3 straightforward modifications of the proofs establish identifiability provided the sum of the Kruskal ranks of the sets {µ j i } 1≤i≤r for j = 1, 2, 3 is at least 2r + 2.

Note that an earlier result linking identifiability with linear independence of the densities to be mixed appears in [START_REF] Yakowitz | On the identifiability of finite mixtures[END_REF] in a parametric context. Combining this statement with the one obtained by Teicher [START_REF] Teicher | Identifiability of mixtures of product measures[END_REF], we get that in the parametric framework, a sufficient and necessary condition for strict identifiability of finite mixtures of product distributions is the linear independence of the univariate components (this statement does not require the knowledge of r). In this sense, our result may be seen as a generalization of these statements in the non-parametric context.

Our results should be compared to two previous ones. First, Hettmansperger and Thomas [START_REF] Hettmansperger | Almost nonparametric inference for repeated measures in mixture models[END_REF] studied the identical marginals case, where for each 1 ≤ i ≤ r, we have µ j i = µ k i for all 1 ≤ j, k ≤ p (with corresponding cdf F i ). They proved that, as soon as p ≥ 2r-1 and there exists some c ∈ R such that the {F i (c)} 1≤i≤r are all different, the mixing proportions π i are identifiable. Although they do not state it (because they are primarily interested in estimation procedures and not identifiability), they also identify the cdfs

F i (c), 1 ≤ i ≤ r at any point c ∈ R such that the {F i (c)} 1≤i≤r are all different.
Second, Hall and Zhou [START_REF] Hall | Nonparametric estimation of component distributions in a multivariate mixture[END_REF] proved that for r = 2, if p ≥ 3 and the mixture P is such that its two-dimensional marginals are not the product of the corresponding one dimensional ones, i.e., that for any 1 ≤ j, k ≤ p we have P(X j , X k ) = P(X j )P(X k ), [START_REF] Miguel | Practical identifiability of finite mixtures of multivariate Bernoulli distributions[END_REF] then the parameters π and F j i are uniquely identified by P. They also provide consistent estimation procedures for the mixing proportions as well as for the univariate cdfs {F j i } 1≤j≤p,i=1,2 . Hall and Zhou state that their results 'apparently do not have straightforward generalizations to mixtures of three or more products of independent components'. In fact, Theorem 8 can already be viewed as such a generalization, since in the r = 2 case we will show inequality ( 6) is in fact equivalent to the independence for each j of the set {µ j i } 1≤i≤2 . To develop a more direct generalization of the condition of Hall and Zhou, we say a bivariate continuous probability distribution is of rank r if it can be written as a sum of r products of signed univariate distributions (not necessarily probability distributions), but no fewer. We emphasize that we allow the univariate distributions to have negative values, even though the bivariate does not. The related notion of non-negative rank, which additionally requires that the univariate distributions be non-negative, will not play a role here.

This definition of rank of a bivariate distribution is a direct generalization of the notion of the rank for a matrix, with the bivariate distribution replacing the matrix, the univariate ones replacing vectors, and the product of distributions replacing the vector outer product. Moreover, in the case r = 2, inequality ( 6) is equivalent to saying P(X j , X k ) has rank 2, since its rank is at most 2 from the expression (4), and if it had rank 1 then marginalizing would show P(X j , X k ) = P(X j )P(X k ).

Next we connect this concept to the hypotheses of Theorem 8.

Lemma 10. Consider a bivariate distribution of the form

P(X 1 , X 2 ) = r i=1 π i µ 1 i (X 1 )µ 2 i (X 2 ).
Then P(X 1 , X 2 ) has rank r if, and only if, for each of j = 1, 2 the measures {µ j i } 1≤i≤r are linearly independent.

¿From Theorem 8, this immediately yields the following.

Corollary 11. Let P be a mixture of the form (4), and suppose that for every j ∈ {1, . . . , p}, there is some k ∈ {1, . . . , p} such that the marginal P(X j , X k ) is of rank r. Then, if p ≥ 3, the parameters {π i , µ j i } 1≤i≤r,1≤j≤p are strictly identifiable from P, up to label swapping.

Note that if the distribution P arising from (4) could be written with strictly fewer than r different product distributions, then the assumption of Corollary 11 (and of Theorem 8) would not be met. Here, we state that a slightly stronger condition, namely that any two-variate marginal of P cannot be written as the sum of strictly fewer than r product components, suffices to ensure identifiability of the parameters. Note also that the condition appearing in Theorem 8 is stated in terms of the parameters of the distribution P, which are unknown to the statistician. However, the rephrased assumption appearing in Corollary 11 is stated in terms of the observation distribution. Thus, one could imagine testing this assumption on the data (even if this might be a tough issue) prior to statistical inference.

The restriction to p ≥ 3, which arises in our method from using Kruskal's theorem, is necessary in this context. Indeed, in the case of r = 2 groups and p = 2 variates, [START_REF] Hall | Nonparametric estimation of component distributions in a multivariate mixture[END_REF] proved that there exists a two-parameter continuum of points (π, {µ j i } 1≤i≤2,1≤j≤2 ) solving equation ( 4). This simply echos the nonidentifiability in the case of 2 variates with finite state spaces commented on in [START_REF] Kruskal | Three-way arrays: rank and uniqueness of trilinear decompositions, with application to arithmetic complexity and statistics[END_REF].

For models with more than 2 components in the mixture, Benaglia et al. [START_REF] Benaglia | An EM-like algorithm for semi and non parametric estimation in multivariate mixtures[END_REF] recently proposed an algorithmic estimation procedure, without insurance that the model would be identifiable. Our results states that under mild regularity conditions, it is possible to identify the parameters from the mixture P, at least when the number of components r is fixed. Thus our approach gives some theoretical support to the procedure developed in [START_REF] Benaglia | An EM-like algorithm for semi and non parametric estimation in multivariate mixtures[END_REF].

Finally, recall that in [START_REF] Elmore | An application of classical invariant theory to identifiability in nonparametric mixtures[END_REF][START_REF] Hall | Nonparametric inference in multivariate mixtures[END_REF], an upper bound on the number of variates needed to ensure 'generic' identifiability of the model is claimed which is of the order r log 2 (r). Our Theorem 8 lowers this bound considerably, as it shows 3 variates suffice to identify the model, regardless of the value of r (under a mild regularity assumption).

Proofs

Proof of Corollary 2. For each j = 1, 2, 3, let M j be the matrix of size r × κ j describing the probability distribution of X j conditional on Z. More precisely, the ith row of M j is p ij = P(X j = • | Z = i), for any i ∈ {1, . . . , r}. Let M1 be the matrix of size r × κ 1 such that its ith row is

π i p i1 = π i P(X 1 = • | Z = i).
Kruskal ranks of M j and M1 are denoted I j and Ĩ1 , respectively. We have already seen that the tensor [ M1 , M 2 , M 3 ] describes the probability distribution of the observations (X 1 , X 2 , X 3 ). Kruskal's result states that, as soon as Kruskal ranks satisfy the condition Ĩ1 + I 2 + I 3 ≥ 2r + 2, this probability distribution uniquely determines the matrices M1 , M 2 and M 3 up to rescaling of the rows and label swapping. Note that as π has positive entries, Kruskal rank Ĩ1 is equal to I 1 . Moreover, using that the matrices M 1 , M 2 and M 3 are stochastic and that the entries of π are positive, the corollary follows.

Proof of Corollary 3. We first show that for any fixed choice of a positive integer I j ≤ min(r, κ j ), those r × κ j matrices M j whose Kruskal rank is strictly less than I j form a proper algebraic variety. But the matrices for which a specific set of I j rows are dependent is the zero set of all I j × I j minors obtained from those rows. By taking appropriate products of these minors for all such sets of I j rows we may construct a set of polynomials whose zero set is precisely those matrices of Kruskal rank less than I j . This variety is proper, since matrices of full rank do not lie in it.

Thus the set of triples of matrices (M 1 , M 2 , M 3 ) for which the Kruskal rank of M i is strictly less than min(r, κ i ) forms a proper subvariety. For triples not in this subvariety, our assumptions ensure that the rank inequality of Corollary 3 holds, so the inequality holds generically. If the π i 's are fixed and positive, the proof is finished. Otherwise, note that the set of parameters with vectors π admitting zero entries is also a proper subvariety of the parameter set.

Proof of Theorem 4. Our goal is to apply Kruskal's result to models with more than 3 observed variables by means of a 'grouping' argument. We require a series of lemmas to accomplish this.

First, given an n × a 1 matrix A 1 and an n × a 2 matrix A 2 , define the n × a 1 a 2 matrix A = A 1 ⊗ row A 2 , as the row-wise tensor product, so that

A(i, a 2 (j -1) + k) = A 1 (i, j)A 2 (i, k).
The proof of the following lemma is straightforward and therefore omitted.

Lemma 12. If conditional on a finite random variable Z, the random variables X 1 , X 2 are independent, with the distribution of X i conditional on Z given by the matrix A i of size r × a i , then the row tensor product A = A 1 ⊗ row A 2 of size r × (a 1 a 2 ) contains the probability distribution of (X 1 , X 2 ) conditional on Z.

For each j ∈ {1, . . . , p}, denote by M j the r × k j matrix whose ith row is

P(X j = • | Z = i). Introduce three matrices N i , i = 1, 2, 3, of size r × κ i , defined as N i = row j∈Si M j ,
and the tensor N = [ Ñ1 , N 2 , N 3 ], where the ith row of Ñ1 is π i times the ith row of N 1 . According to Lemma 12, the tensor N contains the probabilities of the three clumped variables ({X j } j∈S1 , {X j } j∈S2 , {X j } j∈S3 ). Thus, knowledge of the distribution of the observations is equivalent to knowledge of N . Moreover, for parameters π having positive entries (which is a generic condition), the Kruskal ranks of Ñ1 and N 1 are equal.

In the next lemma we characterize the Kruskal rank of the row-tensor product obtained from generic matrices A i . Lemma 13. Let A i , i = 1, . . . , q denote r × a i matrices, a = q i=1 a i and A = row i=1,...,q A i the r × a matrix obtained by taking tensor products of the corresponding rows of the A i . Then for generic A i s,

rank K A = rank A = min(r, a).
Proof. The condition that a matrix A not have full rank (resp. full Kruskal rank) is equivalent to the simultaneous vanishing of its maximal minors (resp. idem when r ≤ a, and equivalent to the existence of one vanishing maximal minor when r > a). Composing the map sending {A i } → A with these minors gives polynomials in the entries of the A i . To see that the polynomials in the entries of the A i are non-zero, it is enough to exhibit a single choice of the A i for which A has full rank (resp. full Kruskal rank).

Let x ij , i = 1, . . . , q, j = 1, . . . , a i be distinct prime numbers. Consider A i defined by

A i =        1 1 . . . 1 x i1 x i2 . . . x iai x 2 i1 x 2 i2 . . . x 2 iai . . . . . . . . . . . . x r-1 i1 x r-1 i2 . . . x r-1 iai        .
For any vector y ∈ C t , let W (y) = W (y 1 , y 2 , . . . , y t ) denote the t × t Vandermonde matrix, with entries y i-1 j . Suppose first that a ≥ r. Then the rows of A are the first r rows of the Vandermonde matrix W (ỹ), where ỹ is a vector whose entries are i x iji for choices of 1 ≤ j i ≤ a i . As the products i x iji are distinct by choice of the x ij , W (ỹ) is non-singular, so A has rank and Kruskal rank equal to r.

If instead r > a, then the first a rows of A form an invertible Vandermonde matrix. Thus A is of rank a. To argue that A has full Kruskal rank, compose the map {A i } → A with the a × a minor from the first a rows of A. This gives us a polynomial in the entries of the A i , the non-vanishing of which ensures the first a rows of A are independent. This polynomial is not identically zero, since a specific choice of the A i s such that the first a rows of A are independent has been given. By composing this polynomial with maps that permute rows of all the A i simultaneously, we may construct non-zero polynomials whose nonvanishing ensures all other sets of a rows of A are independent. The proper subvariety defined by the product of these polynomials then is precisely those choices of {A i } for which A is not of full Kruskal rank. This concludes the proof of the lemma.

Returning to the proof of Theorem 4, note that to apply the preceding lemma to stochastic matrices M j , we must address the fact that each row of each M j sums to 1. However, as both rank and Kruskal rank are unaffected by multiplying rows by non-zero scalars, and rows sums being non-zero is a generic condition (defined by the non-vanishing of linear polynomials), we see immediately the conclusion of Lemma 13 holds when all the M j are additionally assumed to have row sums equal to 1.

We thus see that for generic M j the matrices N i defined above have Kruskal rank I i = min(r, κ i ). Now, by assumption, the matrices N i satisfy the condition of Corollary 2. This implies that the tensor N = [ Ñ1 , N 2 , N 3 ] uniquely determines the matrices N i and the vector π, up to permutation of the rows. We need a last lemma before completing the proof of Theorem 4. Lemma 14. Suppose A = row i=1,...,q A i where the A i are stochastic matrices. Then the A i are uniquely determined by A.

Proof of the lemma. Since each row of each A i sums to 1, one easily sees that each entry in A i can be recovered as a sum of certain entries in the same row of A.

Using this lemma, we have that each N i uniquely determines the matrices M j for j ∈ S i , and Theorem 4 follows.

Proof of Corollary 5. It is enough to consider the case where p = 2 ⌈log 2 r⌉ + 1. With k = ⌈log 2 r⌉, we have that 2 k-1 < r ≤ 2 k . Choosing

κ 1 = κ 2 = 2 k , κ 3 = 2,
inequality [START_REF] Allman | The identifiability of tree topology for phylogenetic models, including covarion and mixture models[END_REF] in Theorem 4 holds.

Proof of Theorem 6. The 2k + 1 consecutive observed variables can be taken to be X 0 , X 1 ,. . . ,X 2k . Note that the transition matrix from Z i to Z i-1 is given by

A ′ = diag(π) -1 A T diag(π).
Let B 1 be the r×κ k matrix giving probabilities of joint states of X 0 , X 1 , . . . , X k-1 conditioned on the states of Z k . Similarly, let B 2 be the r × κ k matrix giving probabilities of joint states of X k+1 , . . . , X 2k conditioned on the states of Z k . Now the joint distribution for the model M(r; κ k , κ k , κ) with parameters π, B 1 , B 2 , B is the same as that of the HMM with parameters π, A, B. Thus we apply Kruskal's theorem, after we first show π, B 1 , B 2 are sufficiently generic to do so for generic choices of A, B. The entries of π have been assumed to be positive. With I M denoting the Kruskal rank of a matrix M , in order to apply Corollary 2 we want to ensure

I B1 + I B2 + I B ≥ 2r + 2.
Making the generic assumption that B has Kruskal rank at least 2, it is sufficient to make

I B1 , I B2 ≥ r,
that is, to require that B 1 , B 2 have full row rank. Now B 1 , B 2 can be explicitly given as

B 1 = A ′ (B ⊗ row (. . . A ′ (B ⊗ row (A ′ (B ⊗ row (A ′ B)))) . . . )), B 2 = A(B ⊗ row (. . . A(B ⊗ row (A(B ⊗ row (AB)))) . . . )), (7)
with k copies of A ′ and of B appearing in the expression for B 1 , and k copies of A and B appearing in that for B 2 . To show these have full row rank for generic choices of stochastic A and B, it is enough to show they have full row rank for some specific choice of stochastic A, B, π , since that will establish that some r r minors of B 1 , B 2 are non-zero polynomials in the entries of A ′ , B and A, B, respectively. For this argument, we may even allow our choice of A to lie outside of those usually allowed in the statistical model, as long as it lies in their (Zariski) closure. We therefore choose A to be the identity, and π arbitrarily, so that A ′ is also the identity, thus simplifying to considering

B 1 = B 2 = B ⊗ row B ⊗ row • • • ⊗ row B (k factors). (8)
It is now enough to show that B 1 , as given in equation ( 8), has full row rank for some choice of stochastic B. We proceed very similarly to the proof of Lemma 13, but since a row tensor power occurs here rather than an arbitrary product, we must make some small changes to the argument. Since non-zero rescalings of the rows of B have no effect on the rank of B 1 in equation ( 8), we do not need to require that the row sums of B are 1. So let x = (x 1 , x 2 , . . . , x κ ) be a vector of distinct primes, and define B by

B =        1 1 . . . 1 x 1 x 2 . . . x κ x 2 1 x 2 2 . . . x 2 κ . . . . . . . . . . . . x r-1 1 x r-1 2 . . . x r-1 κ        . Let y = x ⊗ x ⊗ • • • ⊗
x with k factors. Then using notation from Lemma 13, B 1 will be the first r rows of the Vandermonde matrix W (y). To ensure B 1 has rank r, it is sufficient to ensure that r of the entries of y are distinct, since then B 1 has a non-singular Vandermonde submatrix of size r. The number of distinct entries of y is the number of distinct monomials of degree k in the x i , 1 ≤ i ≤ κ. This number is k+κ-1 κ-1 , so to ensure that generic A, B lead to B 1 having full row rank, we ask that k satisfy

k + κ -1 κ -1 ≥ r.
For fixed κ, the expression on the left of this inequality is an increasing and unbounded function of k, so this condition can be met for any r, κ.

Thus by Kruskal's theorem, from the joint distribution of 2k + 1 consecutive variables of the HMM for generic A, B we may determine P B 1 , P B 2 , P B, where P is an unknown permutation. Now to identify A, B up to label swapping means to determine A = P AP t and B = P B for some permutation P . As B has been found, we focus on A. From equation ( 7) one finds

P B 2 = A( B row (. . . A( B ⊗ row ( A( B ⊗ row ( A B)))) . . . )).
In this expression A and B appear k times. Since each row of B sums to 1, by appropriate summing of the columns of this matrix (marginalizing over the variable X 2k ), we may determine a matrix M given by a similar formula, but with only k -1 occurrences of A and B. Then

P B 2 = A( B ⊗ row M ).
As P B 2 and B ⊗ row M are known and generically of rank r, from this equation one can identify the matrix A.

Thus, the HMM parameters A and B are identifiable up to permutation of the states of the hidden variables.

Proof of Theorem 7. For the n node model, with node set V n = {v k } 1≤k≤n , denote (undirected) edges in the complete graph K n on V n by (v k , v l ) = (v l , v k ) for k = l. We assume 0 < π 1 ≤ π 2 < 1, p ij ∈ [0, 1] and p 11 , p 12 , p 22 are distinct.

Let Z = (Z 1 , Z 2 , . . . , Z n ) be the random variable, with state space {1, 2} n , which describes the state of all nodes collectively. Ordering the elements of the state space in some way, we find the probabilities of the various states of Z are given by the entries of a vector v ∈ R 2 n all of which have the form π k 1 π n-k 2 . Observe for later use that no entries of v are zero, and the smallest and largest entries are π n 1 and π n 2 , respectively (if π 1 = π 2 = 1/2, then all the entries of v are equal to 2 -n ).

Elements of the state space of Z are specified by I = (i 1 , i 2 , . . . , i n ) ∈ {1, 2} n , meaning i k is the state of v k . An assignment of states to all edges in a graph G ⊆ K n will be represented by a subgraph G ⊆ G containing only those edges in state 1, in accord with the interpretation of edge states 0 and 1 as 'absent' and 'present'. We refer to the probability of a particular state assignment to the edges of G as the probability of observing the corresponding G. We may think of any such G as specifying a composite edge variable, whose states are represented by the subgraphs G ⊆ G.

To relate the random graph model to the model of Kruskal's theorem, we must choose three observed variables and one hidden variable that reflect a conditional independence structure. The hidden variable will be Z described above, indicating the state of some number of nodes n, to be chosen below. The observed variables will correspond to three pairwise edge-disjoint subgraphs G 1 , G 2 , G 3 of K n , By choosing the G i to have no edges in common, we ensure that for i = j observing any subgraph G i of G i is independent of observing any subgraph G j of G j , conditioned on the state of Z. To meet the technical assumptions of Kruskal's Theorem, we will also choose the G i so that the three matrices B i whose entries give probabilities of observing each subgraph G i of G i , conditioned on the state of Z, have full row rank. These matrices thus give conditional probabilities of observations marginalized over all edges not in G i .

The construction of the G i proceeds in several steps. We begin by considering a small complete graph, and an associated matrix: For a set of 4 nodes, define a 2 4 × 2 ( 42 ) = 16 × 64 matrix A, with rows indexed by assignments I ∈ {1, 2} 4 of states to the nodes, columns indexed by all subgraphs G of K 4 , and entries giving the probability of observing the subgraph conditioned on the state assignment of the nodes. Each entry of A is thus a monomial in the p ij and q ij = 1p ij . Explicitly, if I = (i 1 , i 2 , i 3 , i 4 ), and e kl ∈ {0, 1} is the state of edge (v k , v l ) in G, the (I, G)-entry of A is 1≤k<l≤4 p e kl i k i l q 1-e kl i k i l .

Lemma 15. For distinct p 11 , p 12 , p 22 , the 16 × 64 matrix A described above has full row rank.

This lemma can be established by a rank computation with symbolic algebra software, so we omit a proof. One can also see, either through computation or reasoning, that the complete graph on fewer than 4 nodes fails to produce a matrix of full rank.

The next lemma shows we can find the 3 edge-disjoint subgraphs needed for the application of Kruskal's theorem. As the rest of the proof does not depend on the nodes having 2 states, we state the following lemma for an arbitrary number of node states. The more general formulation we prove here will be needed in a subsequent paper.

Let r denote the number of node states and suppose we have found a number m such that the r m ×2 ( m 2 ) matrix A of probabilities of observations of subgraphs of the complete graph on m nodes conditioned on node states has rank r m . Lemma 15 establishes that for r = 2, we may take m = 4. Lemma 16. Suppose for the r-node-state model, the number of nodes m is such that the r m × 2 ( m 2 ) matrix A of probabilities of observing subgraphs of K m conditioned on node state assignments has rank r m . Then with n = m 2 there exist pairwise edge-disjoint subgraphs G 1 , G 2 , G 3 of K n such that for each G i the matrix B i of probabilities of observing subgraphs of G i conditioned on node state assignments has rank r n .

Proof. We first describe the construction of the subgraphs G 1 , G 2 , G 3 of K n . For each G i , we partition the m 2 nodes into m groups of size m in a way to be to the full random graph model, but rather its marginalization over all edges not in G

1 ∪ G 2 ∪ G 3 . Suppose now that π 1 = π 2 . Since π m 2 1 , π m 2 2
are the smallest and largest entries of v, respectively, we may determine π 1 , π 2 , as well as which of the rows of B i correspond to the having all nodes in state 1 or all in state 2. Summing appropriate entries of these rows, we obtain the probabilities p 11 and p 22 of observing a single edge conditioned on these node states. (This is simply a marginalization; sum the row entries corresponding to all subgraphs of G i that contain a fixed edge.) To find p 12 , by consulting v we may choose one of the n rows of B 1 which corresponds to node states with all nodes but one in state 1. By considering sums of row entries to obtain the conditional probability of observing a single edge, we can produce the numbers p 11 , p 12 . As p 11 is known, and p 12 is distinct from it, we thus determine p 12 .

If π 1 = π 2 , then we cannot immediately determine which rows of B i correspond to all nodes being in state 1 or in state 2. However, by marginalizing all rows to obtain the conditional probability of observing a single edge, we may determine the set of numbers {p 11 , p 12 , p 22 }. With these in hand, we may then determine which two rows correspond to having all nodes in state 1 and all in state 2. This then uniquely determines which of the numbers is p 12 , so everything is known up to label swapping.

Remark. While the above argument shows generic identifiability of the parameters of the 2-node state random graph model provided there are at least 16 nodes, a slightly more complicated argument, which we do not include here, can replace Lemma 16 to establish generic identifiability provided there are at least 10 nodes. Thus we make no claim to having determined the minimum number of nodes to ensure identifiability.

Proof of Theorem 8. We assume as usual that Z is a latent random variable with distribution on {1, . . . , r} given by the vector π, and X = (X 1 , . . . , X p ) is the vector of observations such that conditional on Z = i, the variates {X j } 1≤j≤p are independent, each X j having probability distribution µ j i . We focus on 3 random variables at a time only, beginning first with X 1 , X 2 , X 3 . The idea is to construct a binning of the random variables X 1 , X 2 and X 3 using κ j -1 ∈ N cut points for X j . For each j = 1, 2, 3, consider a partition of R into κ j consecutive intervals {I k j } 1≤k≤κj and consider the random variable Y j = (1{X j ∈ I 1 j }, . . . , 1{X j ∈ I κj j }), where 1{A} denotes the indicator function of set A. This is a finite random variable taking values in {0, 1} κj with at most one non-zero entry. We will show here that we can identify the proportions π i and the probability measures µ j i , 1 ≤ i ≤ r, 1 ≤ j ≤ 3 relying only on the binned observed variables {Y 1 , Y 2 , Y 3 } for some well-chosen partitions of R.

Consider for each j = 1, 2, 3, the matrices M j of size r × κ j whose ith row is the distribution of Y j conditional on Z = i, namely the vector (P(X j ∈ I 1 j |Z = i), . . . , P(X j ∈ I κj j |Z = i)). Introduce the matrix M1 whose ith row is the ith row of M 1 multiplied by the value π i . Note that the M j 's are stochastic matrices. Moreover, the tensor product

[ M1 , M 2 , M 3 ] is the κ 1 × κ 2 × κ 3 table whose (k 1 , k 2 , k 3 ) entry is the probability P((X 1 , X 2 , X 3 ) ∈ I k1 1 × I k2 2 × I k3 3
). This tensor is completely known as soon as the probability distribution (4) is given. Now, we use Kruskal's result to prove that with knowledge of the tensor [ M1 , M 2 , M 3 ], we can recover the parameters π and the stochastic matrices M j , j = 1, 2, 3. If we can do so for general enough and well-chosen partitions {I k j } 1≤k≤κj , then we will be able to recover the measures µ j i , for j = 1, 2, 3 and 1 ≤ i ≤ r.

We look for partitions {I k } 1≤k≤κ , with κ ≥ r, such that the corresponding matrix M has full row rank. Here, we deliberately dropped the index j = 1, 2, 3. If we can construct these matrices with full row rank, then we get I 1 + I 2 + I 3 = 3r ≥ 2r + 2 and Kruskal's result applies. As the partition {I k } 1≤k≤κ is composed of consecutive intervals, the rows of the matrix M are of the form (F i (u 1 ), F i (u 2 ) -F i (u 1 ), . . . , F i (u κ-1 ) -F i (u κ-2 ), 1 -F i (u κ-1 )) for some real number cut points u 1 < u 2 < . . . < u κ-1 . Replacing the jth column C j of M by C j + C j-1 for consecutive j from 2 to κ, we construct M ′ with same rank as M and whose ith row is (F i (u 1 ), F i (u 2 ), . . . , F i (u κ-1 ), 1). Now, linear independence of the probability distributions {µ i } 1≤i≤r is equivalent to linear independence of the cdfs {F i } 1≤i≤r . We need the following lemma. Lemma 17. Let {F i } 1≤i≤r be linearly independent functions on R. Then there exists some κ ∈ N and real numbers u 1 < u 2 < . . . < u κ-1 such that the vectors {(F i (u 1 ), . . . , F i (u κ-1 ), 1)} 1≤i≤r are linearly independent.

Proof. Let us consider a set of points u 1 < u 2 < . . . < u m in R with m ≥ r and the matrix A m of size r × m whose ith row is (F i (u 1 ), . . . , F i (u m ), 1). Denote by N m = {α ∈ R r | αA m = 0}, the left nullspace of the matrix A m , and let d m be its dimension. If d m = 0, then the matrix A m has full row rank and the proof is finished. Now, if d m ≥ 1, choose a non-zero vector α ∈ N m . By linear independence of the F i 's, we know that r i=1 α i F i is not the zero function, which means that there exists some u m+1 ∈ R such that r i=1 α i F i (u m+1 ) = 0. Up to a reordering of the u's, we may assume u m < u m+1 and consider the matrix A m+1 whose ith row is (F i (u 1 ), . . . , F i (u m+1 ), 1) and whose left nullspace N m+1 has dimension d m+1 < d m . Indeed, we have N m+1 ⊂ N m and by construction, the one dimensional space spanned by the vector α is not in N m+1 . Repeating this construction a finite number of times, we find a matrix A κ with the desired properties.

With this lemma, we have proved that the desired partition exists. Moreover, for any value t ∈ R, we may, by increasing κ, include t among the points u k without lowering the rank of the matrix. Thus, we can construct partitions that involve any chosen cut point in such a fashion that Kruskal's result in the form of Corollary 2 will apply. That is, the vector π and the matrices M j may be recovered from the mixture P, up to permutation of the rows. Moreover, summing up the first columns of the matrix M j , up to the one corresponding to the chosen cut point t, we obtain the value of F j i (t), 1 ≤ i ≤ r, j = 1, 2, 3. To see that this enables to recover the whole probability distribution µ j i , up to label swapping on the i's indexes, note that once we fix an ordering on the states of the hidden variable, the rows (F i (u 1 ), . . . , F i (u κ )) 1≤i≤r are fixed and for each value of t ∈ R, we associate to the ith row the value F i (t).

To conclude the proof, in the case of more than 3 variates we repeat the same procedure with the random variables X 1 , X 2 , X 4 . This enables us to recover the values of {µ 1 i , µ 2 i , µ 4 i } 1≤i≤r up to a relabelling of the groups. As soon as the µ 1 i are linearly independent, they must be different, and using the two sets {µ 1 i , µ 2 i , µ 3 i } 1≤i≤r and {µ 1 i , µ 2 i , µ 4 i } 1≤i≤r which are each known only up to (different) label swappings, we can thus recover the set {µ 1 i , µ 2 i , µ 3 i , µ 4 i } 1≤i≤r up to a relabelling of the groups. Adding a new random variable at a time finally gives the result.

Proof of Theorem 9. In case of non-unidimensional blocks of independent components, we proceed much as in the proof of Theorem 8, but construct a binning into product intervals. For instance, if X is two-dimensional, we use κ 2 different bins, constructing Y = (1{X ∈ I 1 × J 1 }, 1{X ∈ I 1 × J 2 }, . . . , 1{X ∈ I κ × J κ }) where {J k } 1≤k≤κ is a second partition of R into κ ∈ N consecutive intervals. This yields a matrix M whose rows are of the form

(F i (u 1 , v 1 ), F i (u 1 , v 2 ) -F i (u 1 , v 1 ), . . . , F i (u 1 , +∞) -F i (u 1 , v κ-1 ), F i (u 2 , v 1 ) -F i (u 1 , v 1 ), F i (u 2 , v 2 ) -F i (u 1 , v 2 ) -F i (u 2 , v 1 ) + F i (u 1 , v 1 ),
. . . , F i (u 2 , +∞) -F i (u 1 , +∞) -F i (u 2 , v κ-1 ) + F i (u 1 , v κ-1 ), . . . F i (+∞, v 1 )-F i (u κ-1 , v 1 ), F i (+∞, v 2 )-F i (u κ-1 , v 2 )-F i (+∞, v 1 )+F i (u κ-1 , v 1 ), . . . , 1 -F i (u κ-1 , +∞) -F i (+∞, v κ-1 ) + F i (u κ-1 , v κ-1 )) for some real numbers u 1 < u 2 < . . . < u κ-1 and v 1 < v 2 < . . . < v κ-1 . (To avoid cumbersome formulas, we only write the form of the matrix rows in the case b = 2.) This matrix has the same rank as M ′ whose ith row is composed of the values F i (u k , v l ) for 1 ≤ k, l ≤ κ, using the convention u κ = v κ = +∞. The equivalence between linear independence of the probability distributions and corresponding multidimensional cdfs remains valid.

Lemma 17 generalizes to the following. Lemma 18. Let {F i } 1≤i≤r be linearly independent functions on R b . There exists some κ, and b collections of real numbers u i 1 < u i 2 < . . . < u i κ-1 , for 1 ≤ i ≤ b, such that the r row vectors composed of the values {F i (u 1 i1 , . . . , u b i b ) | i 1 , . . . , i b ∈ {1, . . . , κ}}, for 1 ≤ i ≤ r are linearly independent.

The proof of this lemma is essentially the same as the proof of Lemma 17. The only difference with the previous setup is that now the construction of the desired set relies on addition of b coordinates at a time, namely t 1 , . . . , t b ∈ R, which results in adding b-1 j=0 b j κ j columns in the matrix.

To complete the argument establishing Theorem 9, we may again include any point (t 1 , . . . , t b ) ∈ R b among the u k 's without changing the row ranks of the matrices to which we apply Kruskal's theorem. Thus, we may recover the values F 1 (t 1 , . . . , t b ), . . . , F r (t 1 , . . . , t b ), and conclude the proof in the same way as the last theorem.

Proof of Lemma 10. Suppose the probability distribution

P(X 1 , X 2 ) = r i=1 π i µ 1 i (X 1 )µ 2 i (X 2 )
has rank r. Then for k = 1, 2, the sets {µ k i } 1≤i≤r must be independent, since any dependency relation would allow P to be expressed as a sum of fewer products.

Conversely, suppose for k = 1, 2, the measures {µ k i } 1≤i≤r are independent. The corresponding sets of cdfs {F k i } 1≤i≤r are also independent, and thus we may choose collections of points {t k j } 1≤j≤r such that the r × r matrices M k whose i, j-entries are F k i (t k j ) have full rank. Then with F denoting the cdf for P, the matrix N with entries F (t 1 i , t 2 j ) can be expressed as

N = M T 1 diag(π)M 2 ,
and therefore has full rank. But if the rank of P were less than r, a similar factorization arising from the expression of P using fewer than r summands shows that N has rank smaller than r. Thus the rank of P is at least r, and since the given form of P shows the rank is at most r, it has rank exactly r.

Fig 1 .

 1 Fig 1. Embedding the Hidden Markov model into a simpler latent-class model.

The authors thank the Isaac Newton Institute for the Mathematical Sciences and the Statistical and Applied Mathematical Sciences Institute for their support during residencies in which some of this work was undertaken. ESA and JAR also thank the National Science Foundation, for support from NSF grant DMS 0714830. 1

described shortly. Then G i will be the union of the m complete graphs on each partition set. Thus G i has m m 2 edges. For conditional independence of observations of edges in G i from those in G j with i = j, we must ensure G i and G j have no edges in common. This requires only that a partition set of nodes leading to G i has at most one element in common with a partition set leading to G j , if i = j. Labeling the nodes by (i, j) ∈ {1, • • • , m} × {1, • • • , m}, we picture the nodes as lattice points in a square grid. We take as the partition leading to G 1 the rows of the grid, as the partition leading to G 2 the columns of the grid, and as the partition leading to G 3 the diagonals. Explicitly, if

and each G i is the union over j ∈ {1, • • • , m} of the complete graphs on node set V i j . Now B i , the matrix of conditional probabilities of observing all possible subgraphs of G i , conditioned on node states, has r n rows indexed by composite states of all n = m 2 nodes, and 2 m( m 2 ) columns indexed by subgraphs of G i . Observe that with an appropriate ordering of the rows and columns (which is dependent on i), B i has a block structure given by

(Note that since A is r m × 2 ( m 2 ) , the tensor product on the right is (r

) , the size of B i .) That B i is this tensor product is most easily seen by noting the partitioning of the m 2 nodes into m disjoint sets V i j gives rise to m copies of the matrix A, one for each complete graph on a V i j . The row indices of B i are obtained by choosing an assignment of states to the nodes in V i j for each j independently, and the column indices by the union of independently-chosen subgraphs of the complete graphs on V i j for each j. This independence in both rows and columns leads to the tensor decomposition of B i . Now since A has full row rank, equation [START_REF] Chambaz | Number of hidden states and memory: a joint order estimation problem for Markov chains with Markov regime[END_REF] implies that B i does as well.

Remark. For future work, we note that this lemma easily generalizes to graph models in which edges may be in any of s states, with s > 2. In that case, the matrix A is r m ×s ( m 2 ) , and the columns of A are no longer indexed by subgraphs of K m , but rather by s-colorings of the edges of K m .

To complete the proof of Theorem 7, we apply Corollary 2 for M 2 m 2 ; 2 m( m 2 ) , 2 m( m 2 ) , 2 m( m 2 ) to the parameter choice π = v, M i = B i , to find v and each B i is identifiable, up to row permutation. Thus, here we do not apply the corollary