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

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

摘要： 我们研究了聚类问题，其中包含长度为$H$的$T$条轨迹，每条轨迹由有限状态空间大小为$S$的$K$个未知的遍历马尔可夫链之一生成。目标是根据它们各自的生成模型准确地对轨迹进行分组。首先，我们推导了一个依赖于实例的、高概率的聚类误差率下界，该下界由链的转移核之间的加权KL散度控制。然后，我们提出了一种新颖的两阶段聚类算法。在第一阶段，我们使用一种新的遍历马尔可夫链的可嵌入欧几里得空间方法进行谱聚类——这是一个独立有趣的贡献，它能够实现尖锐的集中结果。第二阶段通过基于似然性的重新分配来细化初始聚类。 我们的方法在条件$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.