 Theoretical Computer Science

# Gift bits when encoding a sequence of messages, how is that?

Recently a friend of mine asked a question I couldn't give immediate answer to.

Say we have $n$ messages of length $m$ bits each. Now we can pack them in a single message of length $n * m$ bits. So far so good, information quantity is additive.

But, from another side of view, besides coding the meaning of $n$ messages we also gave an order to them, this gives us additional $\log _2( n!)$ bits. How is that?

I told that unordered messages are meaningless, but he replied, "Take something like photos or novels for example, clearly the order doesn't matter and we can use it to pass additional information". ## Solution

The important thing is what "information quantity is additive" with respect to.

Information quantity is additive with respect to concatenating messages
each of which can only have one length, rather than forming a multiset
of messages each of which can only have one length.

Information quantity is subadditive with respect to forming a multiset of messages
each of which can only have one length, because for every concatenation,
there is a unique multiset that is consistent with that concatenation.

• +0 – (Sorry for taking so long to respond to your comment.) $\:$ No, we basically have a $\hspace{0.8 in}$ non-injective surjection. $\:$ This can be seen by considering the case of two binary messages. $\;\;$ — Aug 15, 2012 at 19:49