On Learning Markov Chains
  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 $\Omega(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.
