Lossless data compression must make some messages longer? [duplicate]

This question already has an answer here:

I read on Wikipedia and in lecture notes that if a lossless data compression algorithm makes a message shorter, it must make another message longer.

E.g. In this set of notes, it says:

Consider, for example, the 8 possible 3 bit messages. If one is compressed to two bits, it is not hard to convince yourself that two messages will have to expand to 4 bits, giving an average of 3 1/8 bits.

There must be a gap in my understand because I thought I could compress all 3 bit messages this way:

• Encode: If it starts with a zero, delete the leading zero.
• Decode: If message is 3 bit, do nothing. If message is 2 bit, add a leading zero.
• Compressed set: 00,01,10,11,100,101,110,111

What am I getting wrong? I am new to CS, so maybe there are some rules/conventions that I missed?

migrated from cstheory.stackexchange.comFeb 19 '13 at 18:41

This question came from our site for theoretical computer scientists and researchers in related fields.

I think you should consider the (binary) messages of length up to a certain value, say $n$. Then you have $2^{n+2}-1$ messages, which you have to map onto the same $2^{n+2}-1$ messages, if you don't permit "compressed" messages with more than $n$ bits. In other words, your compression is a permutation $f$. Any word $w$ with $|f(w)| < |w|$ is in a cycle of $f$, which contains another word $w': |f(w')| > |w'|$.