Assume we have a function $A(n)$ that satisfies the three properties listed above, such that

$$A(n)=H(\frac{1}{n},\frac{1}{n},\dots ,\frac{1}{n}).$$

Then, by property (3) above, we can decompose a choice from $s^m$ equally likely possibilities into a sequence of $m$ choices each from $s$ equally likely possibilities. For example, if we have $2^4$ equally likely possibilities, the probability of any given event is $1/16$. If we instead we have a series of $4$ choices each with $1/2$ probability, we end up with $1/16$ as the probability of any specific sequence of events. So, we have that $A(s^m)=mA(s).$

Now, with arbitrarily large $n,$ we can also have $t^n$ such that $A(t^n)=nA(t),$ by the same logic, and we can pick $m$ such that

Now, we can take the logarithm of each term to get

and dividing by $n\log s$ gives

and because $n$ is arbitrarily large,

where $ϵ$ is arbitrarily small.

By property (2) of $A(n)$ (it is a @monotonically-increasing function of $n$,)

Then, dividing by $nA(s)$ gives

Now, by the @triangle-inequality, we have that

Since $ϵ$ can be arbitrarily small, we have that $A(t)=K\log (t),$ with so that property (2) holds. Now we know what $A(n)$ is, and thus what $H$ is when we have equal probabilities for all events.

Now let's say that we have a choice from $n$ possible events with commensurable probabilities $p_i=\frac{n_i}{\sum n_i}.$ We can break down a choice from $\sum n_i$ possibilities into a choice from $n$ possibilities with probabilities $p_1,\dots ,p_n$ and then, if the $i$th possibility was chosen, $n_i$ choices of equal probability $p_i.$ We do this because above, we found how to find $H$ when all events are equally likely, and property (3) of our desired function lets us break down our overall choice from $\sum n_i$ possibilities. This gives us

Then,

If the $p_i$ are incommensurable, we can approximate them as closely as we'd like with rationals, since The rationals are dense in the reals.. By the first property we assumed for $H,$ it is continuous in the $p_i,$ and so its value at the incommensurable $p_i$ equals its limit as we approach via the rationals, and so our expression holds in general. $K$ is left to us to pick, picking it is equivalent to picking a base for the logarithm.

$◻$

Suppose $H(p_1,\dots ,p_n)=0.$ Then, $0=-\sum _{i=1}^n{p}_i\log p_i.$ Note that because $0\le p_i\le 1,$ we have $\log p_i\le 0,$ and $-p_i\log p_i\ge 0$ (with the convention $0\log 0=0,$ since $\underset{p\to 0^{+}}{lim}p\log p=0$). Assume for contradiction that more than one $p_i$ is non-zero. Then, because $\sum p_i=1,$ each non-zero $p_i$ is in $(0,1)$ and therefore its and the sum of these terms is therefore non-zero, a contradiction. Now, since all probabilities are required to sum to 1, it can't be the case that all probabilities are zero, which means that exactly one probability must be non-zero and that probability must be $1.$

$◻$

Note that

The first term on the RHS is just $-\sum _{x,y}p(x,y)\log p(x,y)=H(X,Y).$ The second is

Altogether, we have that $H(Y|X)=H(X,Y)-H(X),$ or

$$H(X,Y)=H(X)+H(Y|X).$$

$◻$

We'll prove (c) first:

Now, from Chain rule for joint entropy we prove (a) and (b) with

and

(d) is trivial from symmetry of $p(a,b)=p(b,a)$ and $a\ast b=b\ast a.$

To prove (e) we use our result from (a):

$◻$

From Chain rule for joint entropy, we have

$◻$

From Mutual Information and Entropy we have

$$I(X_1,X_2,\dots ,X_n;Y)=H(X_1,X_2,\dots ,X_n)-H(X_1,X_2,\dots ,X_n|Y)$$

Then, from Chain Rule for Entropy and Chain Rule for Conditional Joint Entropy we have, simplifying,

Now, from our definition of conditional mutual information we get

$$\sum _{i=1}^{n}H(X_i|X_{i-1},\dots ,X_1)-H(X_i|Y,X_{i-1},\dots ,X_1)=\sum _{i=1}^{n}I(X_i;Y|X_1,X_2,\dots ,X_{i-1}).$$

$◻$

Using relative-entropy, Multiplication Rule for Distributions, Product Rule for Logarithms, and conditional relative entropy:

$◻$

Because Log is Concave, by Jensen's Inequality we have that

Then, since ${\mathbb{E}}_p[\log \frac{q_i}{p_i}]=-D(p\Vert q),$ we have that $D(p\Vert q)\ge 0.$

Now, note that if $p=q,$ $\frac{q_i}{p_i}=1$ and $D(p\Vert q)=0.$ Conversely, suppose $D(p\Vert q)=0.$ Since $\log$ is strictly concave, it is not @affine, and Jensen's Inequality condition for equality gives us that $\frac{q_i}{p_i}=c.$ Now, $\sum _i{q}_i=\sum _{i}c{p}_i=1,$ and since $p$ is a probability distribution, $c=1,$ and therefore $p_i=q_i$ and $p=q.$

$◻$

We will use a @Lagrangian function of entropy to show this. Let

$$\mathcal{L}(\mathbf{p},\lambda )=-\sum _i[p_i\ln p_i]-\lambda [\left(\sum _i{p}_i\right)-1].$$

Then, for any $p_i$ we want

But, this means $p_i$ doesn't depend on $i,$ and so is the same for each $i$ and therefore $p_i=\frac{1}{n}.$

It remains to show that this extreme of $H$ is a maximum. This follows from the facts that the domain is a convex, compact set and that the entropy function is strictly concave. TODO: more details on these.

$◻$

From Let $X$ and $Y$ be discrete random... and Chain rule for joint entropy, we have

hence $H(Y)\ge H(Y|X).$

$◻$

The entropy of the joint event is

$$H(X,Y)=-\sum _{x,y}p(x,y)\log p(x,y).$$

This is just treating each possible pair of individual outcomes as its own outcome, i.e. we have $|\mathcal{X}|\times |\mathcal{Y}|$ possible outcomes. Writing $p(x)=\sum _{y^{\prime }}p(x,y^{\prime })$ and $p(y)=\sum _{x^{\prime }}p(x^{\prime },y)$ for the marginals (the argument names the distribution), we have

$$H(X)=-\sum _{x,y}p(x,y)\log \sum _{y^{\prime }}p(x,y^{\prime }),H(Y)=-\sum _{x,y}p(x,y)\log \sum _{x^{\prime }}p(x^{\prime },y).$$

So,

Now, let's define a new random variable for convenience, $Z=\frac{p(X)p(Y)}{p(X,Y)}.$ We now have that

Now, by Jensen's Inequality, because Log is Concave, we have that $\mathbb{E}[\log Z]\le \log \mathbb{E}[Z].$ Now,

Therefore $\log \mathbb{E}[Z]=\log 1=0,$ and we have that $\mathbb{E}[\log Z]\le 0⟹-\mathbb{E}[\log Z]\ge 0,$ and

Now, for the equality part. Suppose $H(X)+H(Y)=H(X,Y).$ Then, $\mathbb{E}[\log Z]=0,$ and recalling that $\mathbb{E}[Z]=1,$ $\mathbb{E}[\log Z]=\log \mathbb{E}[Z]=0.$ In Jensen's Inequality, equality holds only if our function is @affine or if $Z$ is constant; since $\log$ is @affine on no interval, $Z$ must be constant, and since $\mathbb{E}[Z]=1,$ $Z=\frac{p(x)p(y)}{p(x,y)}=1⟹p(x)p(y)=p(x,y).$

Now, suppose $p(x)p(y)=p(x,y).$ Then $Z=1$ and

$$H(X)+H(Y)-H(X,Y)=-\sum _{x,y}p(x,y)(\log 1)=0,$$

so $H(X)+H(Y)=H(X,Y).$

$◻$