CLUSTERING IN BLOCK MARKOV CHAINS

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 th...

Full description

Saved in:
Bibliographic Details
Published in:The Annals of statistics 2020-12, Vol.48 (6), p.3488-3512
Main Authors: Sanders, Jaron, Proutière, Alexandre, Yun, Se-Young
Format: Article
Language:English
Subjects:
Algorithms
asymptotic analysis
change of measure
Cluster analysis
Clustering
community detection
Error detection
information theory
Lower bounds
Markov analysis
Markov chains
mixing times
Parameter identification
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0090-5364
2168-8966
2168-8966
DOI:10.1214/19-AOS1939