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

الأصل · EN

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 ((σ- k)), there is still no algorithm that, with probability bounded away from (1 / 2), guesses the entropy correctly after sampling at most ((σ- k)ᵏ / ² ⁻ ε) characters.