  Labelled Markov chains (LMCs) are widely used in probabilistic verification,
speech recognition, computational biology, and many other fields. Checking two
LMCs for equivalence is a classical problem subject to extensive studies, while
the total variation distance provides a natural measure for the "inequivalence"
of two LMCs: it is the maximum difference between probabilities that the LMCs
assign to the same event.
  In this paper we develop a theory of the total variation distance between two
LMCs, with emphasis on the algorithmic aspects: (1) we provide a
polynomial-time algorithm for determining whether two LMCs have distance 1,
i.e., whether they can almost always be distinguished; (2) we provide an
algorithm for approximating the distance with arbitrary precision; and (3) we
show that the threshold problem, i.e., whether the distance exceeds a given
threshold, is NP-hard and hard for the square-root-sum problem. We also make a
connection between the total variation distance and Bernoulli convolutions.

Logic in Computer Science