Compression of random binary data

[Gregory Ewing]

Chris Angelico wrote:
> One bit. It might send the message, or it might NOT send the message.

The entropy formula assumes that you are definitely
going to send one of the possible messages. If not
sending a message is a possibility, then you need
to include an empty message in the set of messages.

Another way to think about it: The receiver can be
in one of N possible states, and you want to ensure
that it's in a particular state. To do that, there
must be N possible messages that you can send.
If N = 1, the receiver is already in the right
state, so you don't need to send it a message at
all.

Example: If the message is "I love you", and your
SO already knows that, you don't need to tell
them. (Not according to information theory, at
least.)

-- 
Greg