标题： 马尔可夫链混合中的近似最优聚类 显示英文标题

标题： Near-Optimal Clustering in Mixture of Markov Chains

摘要： 我们研究了如下问题：给定长度为$H$的$T$条轨迹，每条轨迹由大小为$S$的有限状态空间上的$K$个未知的遍历马尔可夫链之一生成，准确地根据其潜在生成模型对这些轨迹进行聚类。 首先，我们推导出一个依赖于实例的高概率下界，该下界由链的转移核之间的加权KL散度控制。 然后，我们提出了一种新颖的两阶段聚类算法。 在阶段 I 中，我们使用一种新的遍历马尔可夫链的可嵌入欧几里得空间方法进行谱聚类——这是一个独立有趣的贡献，它能够得到尖锐的集中结果。 阶段 II 通过基于似然性的重新分配步骤来细化初始聚类。 我们的方法以高概率实现了接近最优的聚类误差，在条件 $H = \tilde{\Omega}(\gamma_{\mathrm{ps}}^{-1} (S^2 \vee \pi_{\min}^{-1}))$ 和 $TH = \tilde{\Omega}(\gamma_{\mathrm{ps}}^{-1} S^2 )$ 下，其中 $\pi_{\min}$ 是跨越 $K$ 条链的任意状态的最小平稳概率，而 $\gamma_{\mathrm{ps}}$ 是最小伪谱间隙。 如果不能达到最先进的保证（Kausik 等人，2023年），这些要求至少可以提供相当的改进，并且更重要的是，我们的算法提供了关键的实际优势：与现有方法不同，它不需要事先了解特定模型的量（例如，核之间的分离或访问概率）。 最后，我们讨论了上下界之间的固有差距，提供了对该聚类问题独特结构的见解。 显示英文摘要

摘要： We study the problem of clustering $T$ trajectories of length $H$, each generated by one of $K$ unknown ergodic Markov chains over a finite state space of size $S$. The goal is to accurately group trajectories according to their underlying generative model. We begin by deriving an instance-dependent, high-probability lower bound on the clustering error rate, governed by the weighted KL divergence between the transition kernels of the chains. We then present a novel two-stage clustering algorithm. In Stage~I, we apply spectral clustering using a new injective Euclidean embedding for ergodic Markov chains -- a contribution of independent interest that enables sharp concentration results. Stage~II refines the initial clusters via a single step of likelihood-based reassignment. Our method achieves a near-optimal clustering error with high probability, under the conditions $H = \tilde{\Omega}(\gamma_{\mathrm{ps}}^{-1} (S^2 \vee \pi_{\min}^{-1}))$ and $TH = \tilde{\Omega}(\gamma_{\mathrm{ps}}^{-1} S^2 )$, where $\pi_{\min}$ is the minimum stationary probability of a state across the $K$ chains and $\gamma_{\mathrm{ps}}$ is the minimum pseudo-spectral gap. These requirements provide significant improvements, if not at least comparable, to the state-of-the-art guarantee (Kausik et al., 2023), and moreover, our algorithm offers a key practical advantage: unlike existing approach, it requires no prior knowledge of model-specific quantities (e.g., separation between kernels or visitation probabilities). We conclude by discussing the inherent gap between our upper and lower bounds, providing insights into the unique structure of this clustering problem.