Clustering in block Markov chains

DOI10.1214/19-AOS1939zbMATH Open1461.62108arXiv1712.09232OpenAlexW3006667237MaRDI QIDQ1996780FDOQ1996780

Authors: Jaron Sanders, Se-Young Yun, Alexandre Proutiere 

Publication date: 26 February 2021

Published in: The Annals of Statistics (Search for Journal in Brave)

Abstract: This paper considers cluster detection in Block Markov Chains (BMCs). These Markov chains are characterized by a block structure in their transition matrix. More precisely, the $n$ possible states are divided into a finite number of $K$ groups or clusters, such that states in the same cluster exhibit the same transition rates to other states. One observes a trajectory of the Markov chain, and the objective is to recover, from this observation only, the (initially unknown) clusters. In this paper we devise a clustering procedure that accurately, efficiently, and provably detects the clusters. We first derive a fundamental information-theoretical lower bound on the detection error rate satisfied under any clustering algorithm. This bound identifies the parameters of the BMC, and trajectory lengths, for which it is possible to accurately detect the clusters. We next develop two clustering algorithms that can together accurately recover the cluster structure from the shortest possible trajectories, whenever the parameters allow detection. These algorithms thus reach the fundamental detectability limit, and are optimal in that sense.

Full work available at URL: https://arxiv.org/abs/1712.09232

Recommendations

• On Clusters in Markov Chains
• Markov properties of cluster processes
• Clustering behaviour in Markov chains with eigenvalues close to one
• Clustering with hidden Markov model on variable blocks
• Clustering of Markov chain exceedances
• scientific article; zbMATH DE number 6263207
• scientific article; zbMATH DE number 7233060
• Clusters in Markov chains via singular vectors of Laplacian matrices
• Spectral clustering for non-reversible Markov chains

zbMATH Keywords

clusteringcommunity detectionMarkov chainsasymptotic analysischange of measureinformation theorymixing times

Mathematics Subject Classification ID

Applications of Markov chains and discrete-time Markov processes on general state spaces (social mobility, learning theory, industrial processes, etc.) (60J20) Statistical aspects of information-theoretic topics (62B10) Classification and discrimination; cluster analysis (statistical aspects) (62H30) Markov chains (discrete-time Markov processes on discrete state spaces) (60J10)

Cites Work

• Markov chains and mixing times. With a chapter on ``Coupling from the past by James G. Propp and David B. Wilson.
• Least squares quantization in PCM
• Reconstruction and estimation in the planted partition model
• Community detection thresholds and the weak Ramanujan property
• Achieving optimal misclassification proportion in stochastic block models
• Finding structure with randomness: probabilistic algorithms for constructing approximate matrix decompositions
• Exact Recovery in the Stochastic Block Model
• An introduction to matrix concentration inequalities
• Asymptotically efficient adaptive allocation rules
• Markov Chains
• Reinforcement learning. An introduction
• On the distribution of the roots of certain symmetric matrices
• Semicircle law for a matrix ensemble with dependent entries
• Spectrum of large random reversible Markov chains: heavy-tailed weights on the complete graph
• Concentration inequalities for Markov chains by Marton couplings and spectral methods
• Spectrum of large random reversible Markov chains: two examples
• Spectral techniques applied to sparse random graphs
• Adaptive aggregation for reinforcement learning in average reward Markov decision processes
• Achieving Exact Cluster Recovery Threshold via Semidefinite Programming
• Semicircle law for generalized Curie-Weiss matrix ensembles at subcritical temperature
• Sixty years of moments for random matrices

Cited In (12)

• A fast permuation-based algorithm for block clustering
• Guided cluster discovery with Markov model
• Markovian loop clusters on graphs
• Learning Theory
• A low-rank spectral method for learning Markov models
• Spectral norm bounds for block Markov chain random matrices
• Clusters in Markov chains via singular vectors of Laplacian matrices
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• On Clusters in Markov Chains
• Singular value distribution of dense random matrices with block Markovian dependence

This page was built for publication: Clustering in block Markov chains

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1996780)