concentration result for HMMs [@kontorovich2006measure] states that for any 1-Lipschitz function $f$ $$\Pr[|f(\{Y_t\})-\operatorname{E}f(\{Y_t\})|>\epsilon]
\leq 2\exp\left(-T\epsilon^2/c\right),$$ where $c$ is a constant that only depends on the specific HMM structure but not on the function $f$ (cf. [@kontorovich2006measure] for details). Taking $f$ as any entry in $\widehat{{\boldsymbol{\varOmega}}}$ or $\widehat{\underline{{\boldsymbol{\varOmega}}_3}}$, we can check that indeed it is 1-Lipschitz, meaning as $T$ goes to infinity, both estimators converge to their expectation with negligible fluctuations.

We now prove that for a given set of observations $\{Y_t\}_{t=0}^T$, $\widehat{{\boldsymbol{\varOmega}}}$ is always going to be more accurate than $\widehat{\underline{{\boldsymbol{\varOmega}}_3}}$. Since both of them represent probabilities, we use two common metrics to measure the differences between the estimators and their expectations, the Kullback-Leibler divergence $D_\text{KL}(\cdot)$ and the total-variation difference $D_\text{TV}(\cdot)$.

\[ppst:2&gt;3\] Let $\widehat{{\boldsymbol{\varOmega}}}$ and $\widehat{\underline{{\boldsymbol{\varOmega}}_3}}$ be obtained from the same set of observations $\{Y_t\}_{t=0}^T$, we have that $$\begin{aligned}
D_\textup{KL}(\widehat{{\boldsymbol{\varOmega}}}\|{\boldsymbol{\varOmega}}) &\leq 
D_\textup{KL}(\widehat{\underline{{\boldsymbol{\varOmega}}_3}}\|\underline{{\boldsymbol{\varOmega}}_3})
\qquad\text{and}\\
D_\textup{TV}(\widehat{{\boldsymbol{\varOmega}}}\|{\boldsymbol{\varOmega}}) &\leq 
D_\textup{TV}(\widehat{\underline{{\boldsymbol{\varOmega}}_3}}\|\underline{{\boldsymbol{\varOmega}}_3}).\end{aligned}$$

The proof of Proposition \[ppst:2&gt;3\] is relegated to the supplementary material.

Identifiability of HMMs from Pairwise Co-occurrence Probabilities
=================================================================

The arguments made in the previous section motivate going back to matrix factorization methods for learning a HMM when the realization length $T$ is not large enough to obtain accurate estimates of triple co-occurrence probabilities. 