Minimax Estimation and Identity Testing of Markov Chains

A fundamental problem in statistics is to estimate a probability distribution from independent samples. In order to make the question precise, we choose a notion of distance \(\rho\) between distributions, pick two small numbers \(\delta, \varepsilon 0\) and can for instance say that an estimator is good, when with high probability \(1 - \delta\) over the random choice of the sample, the estimator is \(\varepsilon\) close to the true distribution. The problem of determining \(n_0\) is then typically addressed by providing two distinct answers. On one hand, we construct an estimator that would be good for any distribution given that \(n n_0 {UB}\). Conversely, we set up a hard problem such that no estimator can be good when \(n n_0 {LB}\).