Optimal message length and cross entropy When it comes to cross entropy, the assumption is that an optimal encoding would use $\log(\frac{1}{p_i})$ bits for a symbol with probability $p_i$.  While I understand this from a theoretical standpoint, and this definition is of course useful for optimization & learning, I am hoping to:


*

*See a formal derivation of this intuitive result. That is, we should be able to conclude that $\sum_ip_i\log(1/p_i)$ (i.e. the expected message length) is optimal across all possible encodings for any messages drawn from the underlying distribution.

*See a practical example of this type of encoding (perhaps Huffman coding?)


For #2, for example, consider the following symbols and probabilities:


*

*p(A) = 0.8. requires 0.32 bits

*p(B) = 0.1. requires 2.32 bits

*p(C) = 0.1, requires 2.32 bits


What would the optimal encoding of a message here actually look like in practice?
Related threads for reference:


*

*Qualitively what is Cross Entropy

*What is the role of the logarithm in Shannon's entropy?
 A: 
See a formal derivation of this intuitive result

This is shown very nicely in the first few chapters of Thomas & Cover's Elements of Information Theory. 
The proof is too long for an answer, but it generally goes as follows. First, by definition, a code must be uniquely decodable, meaning that there is only one way to decode it. Then, they show that prefix-free codes, a strict subset of uniquely-decodable codes, are just as efficient. Prefix-tree codes can be represented by trees, and the Kraft Inequality can be used to complete the average $\log\left(\frac{1}{p_i}\right)$ bits proof.
If you are willing to settle for a less rigorous proof, it can be shown through the Asymptotic Equipartition Property. Assume symbol $i$ is generated with probability $p_i$. Then taking the negative log of the probabilities, and noting that the log of a product is the product of a log, the law of large numbers says that there is a set of size $e^{n H}$ containing nearly all the probabilities of sets generated by this process. 
Thus a code of average per-bit length $H$ is about as efficient as you can get. This is what you'd get if you'd assign length $-\log\left( \frac{1}{p_i} \right)$ to symbol $i$. You cannot assign a better length based on $-\log\left( \frac{1}{p_i} \right)$. The $q_i$ would have to be a distribution as well (if not, either the code could be made more efficient, or it would violate Kraft). Using Gibb's Inequality, since
$$
\ln x \leq x-1 
$$
(formally, by derivation and checking $x = 1$), then
$$
- \sum_i \left[ p_i \ln\left(\frac{q_i}{p_i}\right) \right] \leq 
- \sum_i \left[ p_i \left(\frac{q_i}{p_i} - 1\right) \right] = 
- \sum_i \left[ q_i - p_i \right].
$$
The right hand side, however, is 0, as $p$ and $q$ are probability distributions.

See a practical example

Given a set of probabilities, you can construct a concrete code using Arithmetic Coding.

Looking back at the answer, it seems to me a bit long and rambling. Again, I suggest you go over the first chapters of Cover & Thomas.
