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).$$

$◻$

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

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

Now, note that if $p=q,$ $\frac{q_i}{p_i}=1$ and $D(p||q)=0.$ Conversely, suppose $D(p||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).$

$◻$

Note that $q_i=\sum _j{A}_{ij}{p}_j,$ by the definition of vector matrix multiplication. Now we'll define a couple of joint distributions:

$$r_{ij}=A_{ij}{p}_j,s_{ij}=A_{ij}{q}_i.$$

Now we find the relative-entropy from $s$ to $r$:

Now, addressing the first term on the RHS of the last line:

And the second term on the RHS of the last line:

So, we end up with $D(r||s)=H(q)-H(p).$ Since $D(r||s)\ge 0$ by Gibbs' Inequality, we have $H(q)-H(p)\ge 0,$ which implies that $H(q)\ge H(p),$ which is what we wanted to show.

Now, the equivalence case. If $q$ is just a rearrangement of $p,$ then obviously it has the same entropy as we can just re-index to recover $p.$ Now assume $H(p)=H(q).$ Then, $H(q)-H(p)=0⟹D(r||s)=0⟹r=s⟹A_{ij}{p}_j=A_{ij}{q}_i⟹p_j=q_i$ whenever Now, for each value $c$ appearing in $p$ or $q,$ let

$$J_c=\{j:p_j=c\},I_c=\{i:q_i=c\},$$

that is $J_c$ is the set of indices of $p$ where $p_j=c,$ and similarly with $I_c$ and $q.$ Now, consider row $i\in I_c.$ For any we have $p_j=q_i,$ so $j\in J_c,$ i.e. every nonzero entry of row $i$ lies in a column of $J_c,$ so the columns $j\in J_c$ have the entire mass of row $i.$ Similarly, for column $j\in J_c,$ for nonzero $A_{ij},$ $q_i=p_j=c,$ so $i\in I_c,$ and the rows $I_c$ contain all of column $j$'s mass. Taking ${\mathbf{1}}_S$ as the @indicator-vector of a set $S,$ we have that

$$A{\mathbf{1}}_{J_c}={\mathbf{1}}_{I_c},$$

that is, rows in $I_c$ sum to $1$ over the columns $J_c,$ while rows outside $I_c$ have no mass in the columns $J_c$ at all. Now we count the mass:

Therefore, $|I_c|=|J_c|$ for all $c,$ so each $c$ appears equally often in $p$ and in $q,$ and $q$ is therefore a rearrangement of $p.$

$◻$