# 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".

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.

• Do I correctly understand you? There is no bijection between a set of concatenated messages and a set of multisets of messages? We basically have an injection here and it's the reason of subadditive behavior. – Dmitry Vyal Aug 14 '12 at 9:24
• (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. $\;\;$ – user6973 Aug 15 '12 at 19:49

Another answer is to consider how you apply concatenation process.

When you concatenate two messages (apply the concatenation operator) you choose a priori an order for the two messages, before concatenation takes place. This order is extra information besides the message bits. Concatenation essentially preserves the order you have presented the messages to the concatenation operator, it does not add any.

If you use a commutative operator, such as "building a multiset", then there is no extra ordering information in the input and thus no extra information in the output.