Minimax Testing of Identity to a Reference Ergodic Markov Chain
  We exhibit an efficient procedure for testing, based on a single long state
sequence, whether an unknown Markov chain is identical to or $\varepsilon$-far
from a given reference chain. We obtain nearly matching (up to logarithmic
factors) upper and lower sample complexity bounds for our notion of distance,
which is based on total variation. Perhaps surprisingly, we discover that the
sample complexity depends solely on the properties of the known reference chain
and does not involve the unknown chain at all, which is not even assumed to be
ergodic.
