Identity testing of reversible Markov chains
  We consider the problem of identity testing of Markov chain transition
matrices based on a single trajectory of observations under the distance notion
introduced by Daskalakis et al. [2018a] and further analyzed by Cherapanamjeri
and Bartlett [2019]. Both works made the restrictive assumption that the Markov
chains under consideration are symmetric. In this work we relax the symmetry
assumption and show that it is possible to perform identity testing under the
much weaker assumption of reversibility, provided that the stationary
distributions of the reference and of the unknown Markov chains are close under
a distance notion related to the separation distance. Additionally, we provide
intuition on the distance notion of Daskalakis et al. [2018a] by showing how it
behaves under several natural operations. In particular, we address some of
their open questions.
