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

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

2009-12-27

arxiv.org/abs/0912.5079v1

Computer Science

Information Theory

Scientific paper

Suppose that, for any (k \geq 1), (\epsilon > 0) and sufficiently large $\sigma$, we are given a black box that allows us to sample characters from a $k$th-order Markov source over the alphabet (\{0, ..., \sigma - 1\}). Even if we know the source has entropy either 0 or at least (\log (\sigma - k)), there is still no algorithm that, with probability bounded away from (1 / 2), guesses the entropy correctly after sampling at most ((\sigma - k)^{k / 2 - \epsilon}) characters.

Affiliated with

Also associated with

No associations

Rating

A Lower Bound on the Complexity of Approximating the Entropy of a Markov Source does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with A Lower Bound on the Complexity of Approximating the Entropy of a Markov Source, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Lower Bound on the Complexity of Approximating the Entropy of a Markov Source will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-568411