methods do not work well, however, when the low-rank tensor is perturbed; e.g., due to insufficient mixing / sample averaging of the triple occurrence probabilities.

It is also possible to handle cases where $K>N$. The key observation is that, given $X_t$, $Y_t$ is conditionally independent of $Y_{t-1},...,Y_{t-\tau}$ and $Y_{t+1},...,Y_{t+\tau}$. Then, grouping $Y_{t-1},...,Y_{t-\tau}$ into a single categorical variable taking $N^\tau$ possible outcomes, and $Y_{t+1},...,Y_{t+\tau}$ into another one, we can construct a much bigger tensor of size $N^\tau\times N^\tau\times N$, and then uniquely identify the underlying HMM structure with $K\gg N$ as long as certain linear independence requirements are satisfied for the conditional distribution of the *grouped* variables [@Allman2009; @bhaskara14a; @Huang2016; @Sharan2017]. It is intuitively clear that for fixed $N$, we need a much larger realization length $T$ in order to accurately estimate $(2\tau+1)$-occurrence probabilities as $\tau$ grows, which is the price we need to pay for learning a HMM with a larger number of hidden states.

This paper
----------

The focus of this paper is on cases where $K \leq N$, and $T$ is large enough to obtain accurate estimate of $\Pr[Y_t,Y_{t+1}]$, but not large enough to accurately estimate triple or higher-order occurrence probabilities. We [*prove*]{} that it is actually possible 