On Learning Markov Chains
This addresses a fundamental gap in statistical learning for sequential data, with potential applications in fields like bioinformatics and finance, though it is incremental relative to prior work on distribution estimation.
The paper tackles the problem of estimating an unknown Markov chain from sequential samples, determining the min-max prediction risk for KL-divergence to within a linear factor in alphabet size, with bounds of Ω(k log log n / n) and O(k² log log n / n), and resolves the problem for estimating the transition matrix with various f-divergences under bounded-away-from-zero probabilities.
The problem of estimating an unknown discrete distribution from its samples is a fundamental tenet of statistical learning. Over the past decade, it attracted significant research effort and has been solved for a variety of divergence measures. Surprisingly, an equally important problem, estimating an unknown Markov chain from its samples, is still far from understood. We consider two problems related to the min-max risk (expected loss) of estimating an unknown $k$-state Markov chain from its $n$ sequential samples: predicting the conditional distribution of the next sample with respect to the KL-divergence, and estimating the transition matrix with respect to a natural loss induced by KL or a more general $f$-divergence measure. For the first measure, we determine the min-max prediction risk to within a linear factor in the alphabet size, showing it is $Ω(k\log\log n\ / n)$ and $\mathcal{O}(k^2\log\log n\ / n)$. For the second, if the transition probabilities can be arbitrarily small, then only trivial uniform risk upper bounds can be derived. We therefore consider transition probabilities that are bounded away from zero, and resolve the problem for essentially all sufficiently smooth $f$-divergences, including KL-, $L_2$-, Chi-squared, Hellinger, and Alpha-divergences.