  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.
