Uncertainty: $f(n) = K \log n$? I've been searching for the derivation of Shannon's info theory derivation and I landed upon this page from Stanford:
http://micro.stanford.edu/~caiwei/me334/Chap7_Entropy_v04.pdf
They've repeated referenced formulas (page 9) like $f(n) = K \log n$, $f(mn) = f(m)+f(n)$ where $f$ seems to represent uncertainty. 
I'd really like some idea as to how this formula came about?
Thank you!
 A: These aren't referenced equations. These are equations which are logically derived from the above text.
(The rest of the answer references the text -- I will put another link here for convenience: http://micro.stanford.edu/~caiwei/me334/Chap7_Entropy_v04.pdf.)
Let's try to go through the logic. Equation (9) simply defines the function $f(N)$ as being the uncertainty $S(1/N,\ldots,1/N)$ of picking one object out of $N$ objects with uniform probability. This function is assumed to be monotonically increasing (the more objects, the higher the uncertainty). Simple enough.
Next, let's break the group of $N$ objects into $m$ groups of $n_k$ objects with $k=1,\ldots, m$. We then break the experiment of picking one of the $N$ objects into two steps: picking the group then picking the element of the group. Picking group $k$ comes with probability $p_k\equiv n_k/N$. Thus, if $A$ is the process of picking the group, $S(A)=S(p_1,\ldots,p_m)$. If $B$ is the process of picking the element of the group, $S(B|A)=f(n_k)$ after we picked the group. All in all, using hypothesis 3) from page 8, we have that the uncertainty of the whole experiment is
$$f(N)=S(AB)=S(A)+\sum_{k=1}^{m}p_kS(B|A)=S(p_1,\ldots,p_m)+\sum_{k=1}^{m}p_kf(n_k)$$
This equation determines the form of $f$ almost uniquely. In particular, take the case when $n_k=n=N/m$ for all $k$ (uniform groups), so that $p_k=1/m$. Then this relation becomes
$$f(N)=S(1/m,\ldots,1/m)+\sum_{k=1}^{m}\frac{1}{m}f(n)=f(m)+f(n)$$
Which must now hold for all $m$ and $n$. The only continuous increasing functions which satisfiy $f(mn)=f(m)+f(n)$ for all $m$ and $n$ are precisely
$$f(x)=K\log{x}$$
For some constant $K$. This was not pulled out of thin air -- it was logically deduced.
The rest of the proof is straightforward. Go back to the general case with arbitrary $n_k$. Then
$$K\log{N}=S(p_1,\ldots,p_m)+K\sum_{k=1}^{m}p_k\log{n_k}$$
Since $\sum_{k}p_k=1$, we can rewrite this as
$$S(p_1,\ldots,p_k)=K\sum_{k=1}^{m}p_k\left(\log{N}-\log{n_k}\right)=-K\sum_{k=1}^{m}p_k\log{p_k}$$
And Eurika! We have derived Shannon entropy from first principles!
I hope this helped clear up some confusion!
