Estimation of the entropy rate of a stochastic process with unknown statistics, from a single sample path is a classical problem in information theory. While universal estimators for general families of processes exist, the estimates have not been accompanied by guarantees for fixed-length sample paths. We provide finite sample bounds on the convergence of a plug-in type estimator for the entropy rate of a Markov chain in terms of its alphabet size and its mixing properties. We also discuss Renyi entropy rate estimation for reversible Markov chains.
['Sudeep Kamath', 'Sergio Verdu']
Estimation of entropy rate and Rényi entropy rate for Markov chains