Consistency of Optimal Matching-based Clustering for Mixtures of Markov Chains
Abstract
We study clustering of categorical sequences using the Optimal Matching (OM) distance under finite mixtures of finite-state Markov chains. We show that the normalized OM distance between two independent chains converges almost surely to a deterministic population quantity, concentrates exponentially around its finite-horizon mean, and admits an O(√(log n/n)) convergence rate when the two chains have the same transition kernel. These population quantities yield a natural separation condition: the largest within-component limit must be smaller than the smallest between-component limit. Under this condition, hierarchical clustering with any bracketed linkage and Partitioning Around Medoids consistently recover the latent mixture partition. We also propose a consistent estimator of the number of components based on empirical OM distance profiles. The results extend to finite-state hidden Markov models and multichannel categorical observations. Overall, they provide a statistical justification for standard OM-based clustering methods for categorical time series.
Related
- A flexible approach to high-dimensional clustering and classification using mixtures of finite mutually repulsive mixtures
- On the Consistency of Spectral Clustering under Generalized Gaussian Mixture Models
- Robust model-based clustering via mixtures of multivariate pseudo-Voigt distributions
- Bayesian heterogeneous copula mixtures with nonparametric margins: consistency, identifiability and tail asymmetry in physical fitness data
- Variational Inference for Functional Data Clustering via Dirichlet Process Mixtures with Correlated Errors
BibTeX
@misc{khalifa2026consistency,
title = {{Consistency of Optimal Matching-based Clustering for Mixtures of Markov Chains}},
author = {Ottavio Khalifa},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.21985},
eprint = {2609.21985},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.21985},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Consistency of Optimal Matching-based Clustering for Mixtures of Markov Chains
AU - Ottavio Khalifa
PY - 2026
DA - 2026/09/18
PB - arXiv
DO - 10.48550/arxiv.2609.21985
UR - https://arxiv.org/abs/2609.21985
AB - We study clustering of categorical sequences using the Optimal Matching (OM) distance under finite mixtures of finite-state Markov chains. We show that the normalized OM distance between two independent chains converges almost surely to a deterministic population quantity, concentrates exponentially around its finite-horizon mean, and admits an O(√(log n/n)) convergence rate when the two chains have the same transition kernel. These population quantities yield a natural separation condition: the largest within-component limit must be smaller than the smallest between-component limit. Under this condition, hierarchical clustering with any bracketed linkage and Partitioning Around Medoids consistently recover the latent mixture partition. We also propose a consistent estimator of the number of components based on empirical OM distance profiles. The results extend to finite-state hidden Markov models and multichannel categorical observations. Overall, they provide a statistical justification for standard OM-based clustering methods for categorical time series.
ER -