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) = m A(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

$$ s^m \leq t^n < s^{m+1}. $$

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

$$ m \log{s} \leq n \log{t} < (m+1)\log{s}, $$

and dividing by $n \log{s}$ gives

$$ \frac{m}{n} \leq \frac{\log{t}}{\log{s}} < \frac{m}{n} + \frac{1}{n}, $$

and because $n$ is arbitrarily large,

$$ \left | \frac{m}{n} - \frac{\log{t}}{\log{s}} \right | < \epsilon, $$

where $\epsilon$ is arbitrarily small.

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

$$ \begin{aligned} A(s^m) & \leq A(t^n) \leq A(s^{m+1}) \\ mA(s) & \leq nA(t) \leq (m+1)A(s). \end{aligned} $$

Then, dividing by $nA(s)$ gives

$$ \frac{m}{n} \leq \frac{A(t)}{A(s)} \leq \frac{m}{n} + \frac{1}{n} \text{ or } \left | \frac{m}{n} - \frac{A(t)}{A(s)} \right | < \epsilon, $$

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

$$ \begin{aligned} \left | \frac{A(t)}{A(s)} - \frac{\log{t}}{\log{s}} \right | & \leq 2 \epsilon \\ \left | A(t) - \frac{A(s)}{\log{s}} \log{t} \right | & \leq 2 \epsilon. \end{aligned} $$

Since $\epsilon$ can be arbitrarily small, we have that $A(t) = K \log(t),$ with $K > 0$ 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

$$ \begin{aligned} K \log{\sum n_i} & = H(p_1, \dots, p_n) + \sum p_i A(n_i) \\ & = H(p_1, \dots, p_n) + \sum p_i K \log{n_i} \\ & = H(p_1, \dots, p_n) + K \sum p_i \log{n_i}. \\ \end{aligned} $$

Then, $$ \begin{aligned} H(p_1, \dots, p_n) & = K \log{\sum n_i} - K \sum p_i \log{n_i} \\ & = K \left [ \log{\sum n_i} - \sum p_i \log{n_i} \right ] \\ & = K \left [ \sum p_i \left ( \log{\sum n_i} \right ) - \sum p_i \left ( \log{n_i} \right ) \right ] \quad \text{ because } \sum p_i = 1 \\ & = K \left [ \sum p_i \left ( \log{\sum n_i} - \log{n_i} \right ) \right ] \\ & = K \left [ \sum p_i \left ( - \log{\frac{n_i}{\sum n_i}} \right ) \right ] \\ & = - K \sum p_i \log{p_i }. \\ \end{aligned} $$

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.

$\square$

Suppose $H(p_1, \dots, p_n) = 0.$ Then, $0 = - \sum_{i=1}^n p_i \log{p_i}.$ Note that because $0 \leq p_i \leq 1,$ we have $\log{p_i} \leq 0,$ and $-p_i \log{p_i} \geq 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 $- p_i \log{p_i} > 0,$ 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.$

$\square$

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

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

Then, for any $p_i$ we want

$$ \begin{aligned} \frac{\partial \mathcal{L}}{\partial p_i} & = -\ln{p_i} - 1 - \lambda = 0 \\ & \implies p_i = e^{-1 - \lambda}. \end{aligned} $$

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.

$\square$

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'} p(x,y')$ and $p(y) = \sum_{x'} p(x',y)$ for the marginals (the argument names the distribution), we have

$$ H(X) = - \sum_{x,y} p(x,y) \log{\sum_{y'}{p(x,y')}}, \quad H(Y) = - \sum_{x,y} p(x,y) \log{\sum_{x'}{p(x',y)}}. $$

So,

$$ \begin{aligned} H(X) + H(Y) - H(X,Y) & = - \sum_{x,y} p(x,y) \log{\sum_{y'}{p(x,y')}} - \sum_{x,y} p(x,y) \log{\sum_{x'}{p(x',y)}} + \sum_{x,y} p(x,y) \log{p(x,y)} \\ & = \sum_{x,y} p(x, y) \left ( \log{p(x,y)} - \log{\sum_{y'}{p(x,y')}} - \log{\sum_{x'}{p(x',y)}} \right ) \\ & = \sum_{x,y} p(x, y) \left ( \log{p(x,y)} - \log{p(x)} - \log{p(y)} \right ) \\ & = \sum_{x,y} p(x, y) \left ( \log{\frac{p(x,y)}{p(x)p(y)}} \right ) \\ & = - \sum_{x,y} p(x, y) \left ( \log{\frac{p(x)p(y)}{p(x,y)}} \right ) \end{aligned} $$

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

$$ \begin{aligned} H(X) + H(Y) - H(X,Y) & = - \sum_{x,y} p(x, y) \left ( \log{\frac{p(x)p(y)}{p(x,y)}} \right ) \\ & = - \sum_{x,y} p(x, y) \left ( \log{Z} \right ) \\ & = -\mathbb{E}[\log{Z}]. \\ \end{aligned}$$

Now, by Jensen's Inequality, because The $\log$ @function is @concave, i.e. $-\log$..., we have that $\mathbb{E}[\log{Z}] \leq \log{\mathbb{E}[Z]}.$ Now,

$$ \begin{aligned} \mathbb{E}[Z] & = \sum_{x,y} p(x,y) \cdot \frac{p(x)p(y)}{p(x,y)} \\ & = \sum_{x,y}p(x)p(y) \\ & = \big ( \sum_{x}p(x) \big ) \big ( \sum_{y}p(y) \big ) \\ & = 1 \cdot 1 \\ & = 1. \\ \end{aligned} $$ Therefore $\log{\mathbb{E}[Z]} = \log{1} = 0,$ and we have that $\mathbb{E}[\log{Z}] \leq 0 \implies -\mathbb{E}[\log{Z}] \geq 0,$ and

$$ \begin{aligned} H(X) + H(Y) - H(X,Y) & \geq 0 \\ - H(X,Y) & \geq -H(X) -H(Y) \\ H(X,Y) & \leq H(X) + H(Y). \\ \end{aligned} $$

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 \implies 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) \left ( \log{1} \right ) = 0, $$

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

note that Jensen's Inequality gives us equality iff $Z$ is (almost surely) constant. Since $Z = \frac{p(x)p(y)}{p(x,y)},$ it's constant iff $p(x,y) = p(x)p(y).$

$\square$

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, \quad s_{ij} = A_{ij} q_i. $$

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

$$ \begin{aligned} D(r || s) & = \sum_{i,j} r_{ij} \log{\frac{r_{ij}}{s_{ij}}} \\ & = \sum_{i,j} A_{ij} p_j \log{\frac{A_{ij} p_j}{A_{ij} q_i }} \\ & = \sum_{i,j} A_{ij} p_j \log{\frac{p_j}{q_i}} \\ & = \sum_{i,j} A_{ij} p_j \left ( \log{p_j} - \log{q_i} \right ) \\ & = \sum_{i,j} A_{ij} p_j \log{p_j} - \sum_{i,j} A_{ij} p_j \log{q_i} \\ \end{aligned} $$

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

$$ \begin{aligned} \sum_{i,j} A_{ij} p_j \log{p_j} & = \sum_j \left [ p_j \log{p_j} \sum_{i} A_{ij} \right ] \\ & = \sum_j \left [ p_j \log{p_j} \cdot 1 \right ] \\ & = \sum_j p_j \log{p_j} \\ & = -H(p). \\ \end{aligned} $$

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

$$ \begin{aligned} \sum_{i,j} A_{ij} p_j \log{q_i} & = \sum_{i} \left [ \log{q_i} \sum_{j} A_{ij} p_j \right ] \\ & = \sum_{i} \left [ \log{q_i} q_i \right ] \\ & = -H(q). \end{aligned} $$

So, we end up with $D(r || s) = H(q) - H(p).$ Since $D(r || s) \geq 0,$ we have $H(q) - H(p) \geq 0,$ which implies that $H(q) \geq 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 \implies D(r || s) = 0 \implies r = s \implies A_{ij} p_j = A_{ij} q_i \implies p_j = q_i,$ so $q$ is a rearrangement of $p.$

$\square$

Note that

$$ \begin{aligned} H(Y | X) & = - \sum_{x, y} p(x,y) \log{\frac{p(x,y)}{p(x)}} \\ & = - \sum_{x, y} p(x,y) \log{p(x,y)} + \sum_{x, y} p(x,y) \log{p(x)}.\\ \end{aligned} $$

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

$$ \begin{aligned} \sum_{x, y} p(x,y) \log{p(x)} & = \sum_{x} \left [ \sum_{y} p(x,y) \right ] \log{p(x)} \\ & = \sum_{x} p(x) \log{p(x)} \\ & = -H(X). \end{aligned} $$

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

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

$\square$

From Let $X$ and $Y$ be discrete @random-variables... and The @entropy of the joint event $X,Y$..., we have

$$ \begin{aligned} H(X) + H(Y) & \geq H(X,Y) \\ & = H(X) + H(Y|X), \\ \end{aligned} $$

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

$\square$