A Lower Bound on the Complexity of Approximating the Entropy of a Markov Source
Travis Gagie · arXiv (Cornell University) · 2009
Suppose that, for any (k \geq 1), (ε> 0) and sufficiently large $σ$, we are given a black box that allows us to sample characters from a $k$th-order Markov source over the alphabet (\{0, ..., σ- 1\}). Even if we know the source has entropy either 0 or at least (\log (σ- k)), there is still no algorithm that, with probability bounded away from (1 / 2), guesses the entropy correctly after sampling at most ((σ- k)^{k / 2 - ε}) characters.