Complexity Explorer Santa Fe Institute

Question 1:

Shannon’s Noisy Channel Coding Theorem states that the maximal rate of information that can be send across a channel is determined by the mutual information between the sender and receiver.
In particular, it is determined by the maximum mutual information between the sender and receiver for any sender distribution.

 

Question 2: 

We first determine the maximum amount of information that Alice needs to send.
We know that there are 100 possible messages, but we don’t know which distribution of messages Alice will use. At the same time, we know that the entropy of a distribution over 100 messages is maximized by the uniform distribution, which has entropy
   H_max = log₂100 ≈ 6.64 bits
Thus, in the worst case, Alice needs a channel with capacity 6.64 bits.

Supplemental Information