Abstract
Estimating the entropy based on data is one of the prototypical problems indistribution property testing and estimation. For estimating the Shannonentropy of a distribution on $S$ elements with independent samples,[Paninski2004] showed that the sample complexity is sublinear in $S$, and[Valiant--Valiant2011] showed that consistent estimation of Shannon entropy ispossible if and only if the sample size $n$ far exceeds $\frac{S}{\log S}$. Inthis paper we consider the problem of estimating the entropy rate of astationary reversible Markov chain with $S$ states from a sample path of $n$observations. We show that: (1) As long as the Markov chain mixes not too slowly, i.e., the relaxationtime is at most $O(\frac{S}{\ln^3 S})$, consistent estimation is achievablewhen $n \gg \frac{S^2}{\log S}$. (2) As long as the Markov chain has some slight dependency, i.e., therelaxation time is at least $1+\Omega(\frac{\ln^2 S}{\sqrt{S}})$, consistentestimation is impossible when $n \lesssim \frac{S^2}{\log S}$. Under both assumptions, the optimal estimation accuracy is shown to be$\Theta(\frac{S^2}{n \log S})$. In comparison, the empirical entropy raterequires at least $\Omega(S^2)$ samples to be consistent, even when the Markovchain is memoryless. In addition to synthetic experiments, we also apply theestimators that achieve the optimal sample complexity to estimate the entropyrate of the English language in the Penn Treebank and the Google One BillionWords corpora, which provides a natural benchmark for language modeling andrelates it directly to the widely used perplexity measure.