Khinchin Uniqueness Theorem

Theorem.

There is a unique (up to scalar) function $H(\underline{p})$ over finite probability distributions $\underline{p}=\{p_1,\dots ,p_n\}$ such that it satisfies the following:

1. Continuity: For any fixed $n$, $H$ is continuous in the $p_i$
2. Increasing in the size of the uniform distribution: $H(\frac{1}{n},\dots ,\frac{1}{n})$ is increasing as a function of $n$
3. Decomposability: $H$ is such that $H(p_1,\dots ,p_n)=H(p_1,1-p_1)+(1-p_1)H\left(\frac{p_2}{1-p_1},\dots ,\frac{p_n}{1-p_1}\right)$. The unique function $H(\underline{p})$ satisfying the above conditions is equivalent to our definition of entropy.

---

The last condition seems arbitrary at first glance but is actually quite well-motivated. Suppose we sent the random variables $X_1$ and $X_2$ as part of one message to someone else. Intuitively, there should be no loss of information if instead we were to send $X_1$ first then $X_2$. We want our measure of information $I(\cdot )$ to be such that it obeys this intuition.

To be more specific, once we accept that the information $I(\cdot )$ should be a function of probability we want the following to be true:

$$I(P(X_1,X_2))=I(P(X_1))+I(P(X_2|X_1)).$$

The decomposability condition in the above theorem is essentially a generalization of this intuition, but for entropy instead of information. We want entropy to be such that if we decompose a random variable into a sequence of random variables, it adds.