Designing optimal tests for slow converging Markov chains

We design a Neyman-Pearson test for differentiating between two Markov Chains using a relatively small number of samples compared to the state space size or the mixing time. We assume the transition matrices corresponding to the null and alternative hypothesis are known but the initial distribution is not known. We bound the error using ideas from large deviation theory but in a non-asymptotic setting. As an application, using scRNA-seq data, we design a Neyman-Pearson test for inferring whether a given distribution of RNA expressions from a murine pancreatic tissue sample corresponds to a given transition matrix or not, using only a small number of cell samples.