Computing Entropy Rate Of Symbol Sources & A Distributionfree Limit Theorem
Abstract
Entropy rate of sequential datastreams naturally quantifies the complexity of the generative process. Thus entropy rate fluctuations could be used as a tool to recognize dynamical perturbations in signal sources, and could potentially be carried out without explicit background noise characterization. However, state of the art algorithms to estimate the entropy rate have markedly slow convergence; making such entropic approaches nonviable in practice. We present here a fundamentally new approach to estimate entropy rates, which is demonstrated to converge significantly faster in terms of input data lengths, and is shown to be effective in diverse applications ranging from the estimation of the entropy rate of English texts to the estimation of complexity of chaotic dynamical systems. Additionally, the convergence rate of entropy estimates do not follow from any standard limit theorem, and reported algorithms fail to provide any confidence bounds on the computed values. Exploiting a connection to the theory of probabilistic automata, we establish a convergence rate of $O(\log \vert s \vert/\sqrt[3]{\vert s \vert})$ as a function of the input length $\vert s \vert$, which then yields explicit uncertainty estimates, as well as required data lengths to satisfy prespecified confidence bounds.
 Publication:

arXiv eprints
 Pub Date:
 January 2014
 arXiv:
 arXiv:1401.0711
 Bibcode:
 2014arXiv1401.0711C
 Keywords:

 Computer Science  Information Theory;
 Computer Science  Machine Learning;
 Mathematics  Probability;
 Statistics  Computation;
 Statistics  Machine Learning