Testing Symmetric Markov Chains from a Single Trajectory

Constantinos Daskalakis, Nishanth Dikkala, Nick Gravin

Classical distribution testing assumes access to i.i.d. samples from the distribution that is being tested. We initiate the study of Markov chain testing, assuming access to a sing…