I have a little understanding problem with Appendix A ("Universal Codes") in the paper "Shannon Information and Kolmogorov complexity" by Gründwald and Vitanyi (Link).

At the end of page 50, they say something corresponding to:

For each Prefix-code, the fraction of sequences of length $n$ that can be compressed by more than $m$ bits is less than $2^{-m}$.

Either this is a writing mistake or I should make a break from reading.

It is easy to see, that the number of strings with length $n$ and compression length smaller than $m$ is smaller $2^{m-n}$ for a prefix-code because there are simple not enough "shorter" words.. Did they mean this information?

It is also easy to understand, that the Kraft-Inequality $\sum_{x\in X}2^{-l(x)}\leq1$ holds for a prefix code with source word set $X$ and the compression length $l(x)$ for strings $x\in X$.

Is that only a writing mistake? Respectively can you tell me an explanation?


1 Answer 1


There is no problem with the statement. An encoding $f$ of the set of strings of length $n$ is a map from $\{0,1\}^n$ to $\{0,1\}^*$ which is injective (one-to-one). Such a mapping compresses a string $x$ by more than $m$ if $|f(x)| < |x| - m$. In our case, all the strings have length $n$, so a string $x \in \{0,1\}^n$ is compressed by more than $m$ if $|f(x)| < n-m$. There are $\sum_{i=0}^{n-m-1} 2^i = 2^{n-m}-1 < 2^{n-m}$ such strings, and since $f$ is injective, the fraction of strings compressed by more than $m$ is less than $2^{n-m}/2^n = 2^{-m}$.

  • $\begingroup$ Thank you very much. I misunderstand the the statement "compresses a string by more than m" to $|f(x)|<m$ instead of $|f(x)|<n-m$. Thanks again. $\endgroup$
    – Danny
    Jan 31, 2014 at 8:14

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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