A Lower Bound on the Complexity of Approximating the Entropy of a Markov Source

2009/12/27 by Gagie, Travis
#FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.0912.5079

Abstract

Suppose that, for any (k ≥ 1), (ε> 0) and sufficiently large σ, we are given a black box that allows us to sample characters from a kth-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.

Related

• Entropy Rate Estimation for Markov Chains with Large State Space
• An efficient algorithm for the entropy rate of a hidden Markov model with unambiguous symbols
• Estimation of Entropy in Constant Space with Improved Sample Complexity
• Tight Sample Bounds for Renyi and Min-Entropy Estimation
• Minimum MS. E. Gerber's Lemma