Information theory for Dummies

If a secret agent has to send a hundred messages with the least amount of bits, what is the strategy? How can both sides have a translator for my code?

Without any restrictions, let us build a coding machine its simplest form, a binary tree with root atop and terminating leaves going doing. A message is fed to the machine and based on limit values in each node, the message will travelleft or right in each binary node. Cal this the plain vanilla partition machine.

If the partition machine works properly, then the same machine will work properly in simulating any other trinary or quatenary tree to any sufficient accuracy.  What I am saying is that no matter how finely granular your message, I can stack a sufficiently high binary encoder. Meaning, it is K to do this trick in fixed arithmetic binary.

So far I have not mentioned how to set the parameters at each node. What are the rules for making maximum use of the available, finite number of bits?  Let us add a further restriction on our general model, the number of bits used to send  message is equal to the number of nodes traveled in the machine to encode the message, going from root to leave.

So far, no proofs, no nothing, just a restriction on my counting method.  But notice, the bit allocated will be log base two of the message. That is a restriction I imposed.

So, right away, with no restrictions we get that if i was the proportion of one type of message,. then i *  coded_msg length will be the total amount of bandwidth used in our machine. That is, each output message requires some fixed travel down the binary encoder, and that will happen in proportion to the input message frequency. We show the encoder mus be optimum as it must be unique.

In a perfectly balanced binary tree the input and output messages were equally random, already perfectly encoded because the appearance of each message was equally surprising.  In that case the individual messages are equal likely and they can be sent is digital words on fixed boundaries.

Sp far so good.  Next we show that within the round off error any other distribution of messages can be so encoded by allowing skew on our binary tree.  We show a node by node set of exchanges must exist.  This is the new trick, I think, with random graph proofs.