Learning Markov distributions: Does estimation trump compression?
Moein Falahatgar, Alon Orlitsky, Venkatadheeraj Pichapati, Ananda Theertha Suresh · 2016
A significant amount of multidisciplinary research has recently focused on the rate at which i.i.d. distributions can be estimated. In particular, it was shown that for these distributions, optimal estimation implies optimal compression, hence in a sense for i.i.d. distributions, estimation “trumps” compression. Progressing from idealized i.i.d. to more practical distributions, we define and study the rate at which Markov distributions can be estimated. We determine this rate up to a constant factor and show two perhaps surprising implications. First, while the compression redundancy of i.i.d. and Markov distributions have the same growth rate, their estimation losses have different growth rates. Second, while for i.i.d. distributions optimal estimation implies optimal compression, for Markov distributions this implication does not hold, yet we show that any optimal compression algorithm has a smaller cumulative estimation loss than that guaranteed for optimal estimators, hence in a sense, for Markov distributions, compression "trumps" estimation. We also construct an algorithm that is optimal for both estimation and compression. Finally, we consider the important subclass of Markov distributions where all transition probabilities are bounded away from zero. For this subclass we determine the best estimation rate to the right constant factor and show that unlike i.i.d. distributions, for Markov distributions, the estimation rate of the full simplex and its interior differ.