Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

If I have a sequence which is comprised of one of 10 prefixes, one of 5 suffixes and a variable length middle, how do I compute the entropy of the sequence?

Using Shannon-Entropy $Hs= -\Sigma_{i=1}^{m} p_i ln(p_i)$

I can compute the entropy contributions from the 10 starting and 5 ending sequences using this sum, but I am unsure how to computer the variable length section. If the distribution of length is:

  • 0=0.5
  • 1=0.25
  • 2=0.2
  • 3=0.05

And each character can be A-F say, for 16 possibility with equal probability how do I calculate the number of bits of entropy? If I simply use the sum above, I am underestimating the contribution from the longer sequences, which have more possibilities. Do I also need to ignore the $p0$ term, as $0.5ln(0.5)$ isn't actually adding any additional characters to the sequence.

share|cite|improve this question

If all $16$ possibilities has an equal probability, that entropy must $\ln 16\approx 2.77$ its; $H\sim \max= \sum[ \frac1n \ln(\frac1n) ]$. Adding new information with "equal" probability is not add extra information into entropy.

share|cite|improve this answer
While I agree adding 1 character with 16 equal possibilities adds log(16) entropy, the problem here is how to cope with variable length sequence. – Nick May 23 '13 at 15:05

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.