Aryeh Kontorovich

In this chapter, we provide an overview of the two inference problems of learning and identity testing of a Markov chain based on a single trajectory of observations started from an arbitrary state. The learning problem is concerned with the estimation of the state transition probabilities of the process, while the testing problem deals with determining whether the unknown Markov chain is identical to or far from a given reference chain. We analyze both tasks from within the minimax framework and with respect to several competing notions of distance. We observe that the sample complexities depend on the number of states and often also on the stationary and mixing properties of the Markov chains. We further proceed to compare advantages and drawbacks of the different contrast functions we consider.