Compressibility is defined as


The book is made up of a simple alphabet of only {a,b,c,d} which occur with probabilities $$P(a)=0.2, P(b)=0.4, P(c)=0.1, P(d)=0.3$$

In class we were given the example of calculating the entropy of a simple string of coin tosses, where $N$ is the number of coin tosses.

So, for example, we could say that $P(heads)=0.1$ and $P(tails)=0.9$. The entropy of each coin toss is therefore $H(p=0.9)=0.469$ If we toss the coin 4 times then we end up with a compressibility of: $$C=\frac{2^{HN}}{2^{H_{max}N}}=\frac{2^{0.469\cdot4}}{2^{1\cdot 4}}=22.3\%$$ How do we extend this to the book case?

The entropy of the letter occurance is $$H(p=0.2,p=0.4,p=0.1,p=0.3)=1.85$$

and the maximum entropy is just 2 bits (i.e. we require 2 bits to descibe four characters)

Since this is all the information given in the question, I presume that we just set $N=4$ and plug in the values for $H$ and $H_{max}$ to get the entropy. However, I am struggeling to see why. Why is $N$ not the number of letters that make up this book?

  • $\begingroup$ Can you add in the question an accessible reference where your compressibility is introduced? $\endgroup$ – John L. Jan 14 '19 at 5:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.