On Mixtures of Markov Chains
We study the problem of reconstructing a mixture of Markov chains from the trajectories generated by random walks through the state space. Under mild nondegeneracy conditions, we show that we can uniquely reconstruct the underlying chains by only considering trajectories of length three, which represent triples of states. Our algorithm is spectral in nature, and is easy to implement.
The paper proposes a novel approach to estimate the parameters of a mixture of Markov chains. It is based on samples of trajectories with length 3 (the 3-trails) of the finite mixture and uses SVD decompositions and simple linear algebra techniques to recover the parameters from the empirical distribution of these 3-trails. Some synthetic experiments and a real data application are provided.   
The paper is globally sound and makes a new contribution to an important topic. However some technicalities need to be addressed and a revised version should be encouraged.   Major remarks: - There is a confusion on whether the Markov chains under consideration are supposed to be stationary or not.  Indeed, the concept of t-trail either requires that the Markov chains under study are stationary or one should specify that all the trails start with same initial distribution, i.e. these trails are observations of (X_1,X_2,X_3) and not (X_s, X_{s+1},X_{s+2}) for some s. I first understood that you adopt the second approach (as you count the parameters of initial distributions as free parameters) but in the real data experiments, you take many (3001)-trails and break them into 3000 overlapping 3-trails (by the way, you need a 3002-trail to obtain these). This causes two different problems: the first is related to stationarity and the second will be developed below. So, by breaking a t-trail into several 3-trails you implicitly assume that the chains follow a stationary regime. This should be stated more clearly. And this should be taken into account when discussing the number of parameters (the stationary distribution for the \ell-th Markov chain will be entirely determined by its transition M^\ell - as soon as some ergodicity conditions are satisfied on M^\ell). To summarize, breaking a trail into several t-trails only makes sense in a stationary regime.  - The second problem induced by breaking a t-trail into several 3-trails lies in the overlap. One could safely consider non-overlapping 3-trails (resulting in a smaller amount of data). Here, the authors choose to rely on overlapping t-trails (at least this is done in the real data experiments). Then, the law of large numbers is satisfied for each Markov chain provided some ergodicity conditions are  assumed on their transition. In particular, the statement that ‘It is easy to see that using O(1/\epsilon^2 log n) sample trails, every entry in O_j for every j is approximated to within an additive +/- \epsilon’ (lines 97-99) is not valid in general when using non independent samples.   - In the synthetic experiments, computation of the error requires to explore all the permutations for matching \mathcal{M} with \mathcal{N}. This is not a trivial task. How do you proceed? (same question applies in the real data experiments, especially when you have L=10 groups). - In the real data experiments with L=10 groups, you assume that the group structure is known and given by the 10 different users. How did you compute the prediction error for L less than 10? What is the truth here? In the case of 10 groups, why not simply computing an adjusted rand index (ARI) to evaluate the classifications (yours and EM) with respect to ‘truth’?  - Synthetic experiments rely on only 11 different runs which is really small. You should go to at least 100 replicates of your experiments for each sample size.  - Synthetic experiments: the authors draw initial distributions s^\ell from the Dirichlet distribution on the simplex (indeed, uniform distribution on the simplex is the Dirichlet distribution with parameters (1,…,1)) and then divide by L to obtain a distribution on the pair (group, initial state). This boils down to assuming that all the groups have equal probability, which could be noticed. More importantly, what happens when the groups are not equally distributed?  - Those results are reminiscent of results obtained by Allman et al. ‘Identifiability of parameters in latent structure models with many observed variables’, Annals of Statistics, 2009. In this paper, the authors rely on a result by Kruskal on 3-ways arrays to prove identifiability of different classes of model. Dimension 3 plays an important role and they also obtain ‘generic identifiability’ results meaning that the set of non-identifiable parameters has Lebesgue measure 0. I believe this reference could be included.      Minor remarks: - Line 82, M^1, …, M^L are more precisely transition matrices of Markov chains (and not Markov chains by themselves).  - Line 110, ‘To appreciate such a need, consider the obviously necessary, though not sufficient, condition that the matrices in M be distinct.’  I don’t see how this is related to the previous sentence.  - Number of parameters (lines 113-114): it seems to me that the set \mathcal{S} corresponds to distributions on the pair (group, initial state), in which case, there are additional constraints on those parameters and they should reduce to L(n-1) free parameters (each one of the L Markov chains has an initial distribution determined by n-1 parameters). In any case, I mentioned above that the general setting of the paper should be the stationary regime in which case initial distribution is not a free parameter anymore.  - Line 228: ‘we consider the first 3001 state transitions that change their state’: what do you mean exactly by ‘that change their state’? Do you mean that you discard data where X_s=X_{s+1}? If yes, why do you do that and why would this be valid?     - line 236:’The prediction error ranges from 1/L to 1’/ I don’t understand that statement. I would say that it ranges from 0 to 1.   - Baseline EM: how do you initialize the algorithm? How many starting points do you use?    Typos:  - Line 83, initial probability is denoted s^\ell(i) while later it becomes s^\ell_i.  - Equation (2): I believe the last factor 2 should be removed.  - Line 176, ‘(P,Q) is a shuffle pair’ should be (\mathcal{P},\mathcal{Q}). - Line 157: matrix R^’ should be R (both instances).  - Line 223-224: E_l is not defined. It is related to ‘error’ above.