LBIT Proofs 8: Propositions 53-58

post by Diffractor · 2020-12-16T03:29:34.423Z · LW · GW · 0 comments

Contents

No comments

 

 

Theorem 4: ${lim}_{\alpha \to 1}{H}_{\alpha }\left(h\right)$ exists for all infradistributions over a finite set $X$, and equals $-{sup}_{q}dh(1;\ln (q\left)\right)$

So, as a recap, here's how it works. $\alpha >1$. The Renyi entropy for $\alpha >1$ is:

$\frac{\alpha }{1-\alpha }\ln \left({sup}_q\left(h\left(q^{\frac{\alpha -1}{\alpha }}\right)\right)\right)$

Where $q$ is taken over functions with ${\sum }_i{q}_i=1$ (we have finitely many points, we're summing it up over all of those). And our task is to take the limit as $\alpha$ tends to 1.

Our first step is to let $\alpha =1+ϵ$, and with this reindexing, we can instead take the limit as $ϵ$ tends to 0, and get the same answer. So, we're trying to find:

${lim}_{ϵ\to 0}\frac{1+ϵ}{-ϵ}\ln \left({sup}_q\left(h\left(q^{\frac{ϵ}{1+ϵ}}\right)\right)\right)$

Well, we don't even necessarily know it exists. Looking at this, in the $ϵ\to 0$ limit, if $q$ is such that $\forall i:q_i>0$, then $q^{\frac{ϵ}{1+ϵ}}$ will tend to 1 for all $i$. And so, $h$ of that will tend to 1, and ln of that will tend to 0 from below, and hopefully the really tiny negative number cancels out with the fact that we're also dividing by a really tiny negative number. To do our approximation work, we're going to need that $q$ is bounded above 0 by something. We can show that the limit exists if we were dealing with a family of $q$ that are bounded above 0.

Accordingly, our proof strategy is going to be getting some bounds (for all $ϵ$ sufficiently close to 0) on how much the results differ if we're taking the sup over all appropriate $q$, vs if we're looking purely at the $q$ that are bounded above 0 by some (small, but not varying with $ϵ$) number. Then, we can get some upper bounds and lower bounds, which we will be able to show converge in the $ϵ\to 0$ limit. The problem is that the bounds won't be tight enough to produce the same limit, because we're blowing things up with a division by $ϵ$. So, all we're going to be able to conclude is that the relevant $ϵ\to 0$ sequence has all of its limit points lying in an interval. However, the lower our "bound above 0" cutoff is, the tighter the interval will be. So, if we take the limit as our "bound above 0" cutoff shrinks to 0, the interval will shrink to a point, and we will have shown that the limit does in fact exist. 

Let's get started on our upper bounds and lower bounds, respectively. Fix some $\delta$ which, importantly, won't vary with $ϵ$ (yes, this will lead to a bit of weirdness where we start looking at behavior when $ϵ<<\delta$). For notation, ${sup}_{q\ge \delta }$ is maximizing $q$ which fulfill the relevant property of $\forall i:q_i\ge \delta$. Accordingly, $\delta$ should be less than 1 divided by the number of possible finite outcomes. So, we can start establishing our upper bound as:

${sup}_q\left(h\left(q^{\frac{ϵ}{1+ϵ}}\right)\right)\ge {sup}_{q\ge \delta }\left(h\left(q^{\frac{ϵ}{1+ϵ}}\right)\right)$

And the natural logarithm is monotonic, so

$\ln \left({sup}_q\left(h\left(q^{\frac{ϵ}{1+ϵ}}\right)\right)\right)\ge \ln \left({sup}_{q\ge \delta }\left(h\left(q^{\frac{ϵ}{1+ϵ}}\right)\right)\right)$

And then we multiply both sides by a negative number, flipping the sign, so:

$\frac{1+ϵ}{-ϵ}\ln \left({sup}_q\left(h\left(q^{\frac{ϵ}{1+ϵ}}\right)\right)\right)\le \frac{1+ϵ}{-ϵ}\ln \left({sup}_{q\ge \delta }\left(h\left(q^{\frac{ϵ}{1+ϵ}}\right)\right)\right)$

And bam, we have an upper bound. The lower bound is significantly more tricky. Let's start with our first question. Given a $q\ngeqq \delta$, how can we adjust it to a $q^{\prime }$ that fulfills that property? Well, just have:

$q_i^{\prime }:=\frac{q_i+\frac{\delta }{1-|X|\delta }}{1+|X|\frac{\delta }{1-|X|\delta }}$

We should check that A: this still adds up to 1, and B: that when $q_i=0$, $q_i^{\prime }\ge \delta$. For later, we'll also need to check C: what's the critical value where this transformation switches from increasing the value to decreasing the value? Let's hit A first.

${\sum }_i{q}_i^{\prime }={\sum }_i\frac{q_i+\frac{\delta }{1-|X|\delta }}{1+|X|\frac{\delta }{1-|X|\delta }}=\frac{1}{1+|X|\frac{\delta }{1-|X|\delta }}{\sum }_i(q_i+\frac{\delta }{1-|X|\delta })$

$=\frac{1}{1+|X|\frac{\delta }{1-|X|\delta }}({\sum }_i{q}_i+{\sum }_i\frac{\delta }{1-|X|\delta })=\frac{1}{1+|X|\frac{\delta }{1-|X|\delta }}(1+|X|\frac{\delta }{1-|X|\delta })=1$

Excellent. For B, we can quickly check that this function is still in range by inspection if $q_i$ is 1, because we're dividing a number by a slightly bigger number. For being above $\delta$, observe that:

$\frac{0+\frac{\delta }{1-|X|\delta }}{1+|X|\frac{\delta }{1-|X|\delta }}=\frac{\frac{\delta }{1-|X|\delta }}{\frac{1-|X|\delta +|X|\delta }{1-|X|\delta }}=\frac{\delta }{1-|X|\delta +|X|\delta }=\delta$

And finally, let's check the threshold where this starts moving the value of the function down instead of up. Instead of having to do a bunch of fancy equations, let $q$ be the uniform function, with $\frac{1}{|X|}$ function-mass on each outcome. We're adding an equal amount to everything, and then dividing by some amount, so we get another uniform function. Which, to sum up to 1, must be unchanged. so $\frac{1}{|X|}$ is the critical value where the value of our $q$ start decreasing in value (if they're above it), or increasing (if they're below it).

Armed with our way of translating functions so that they do indeed fulfill our desired $\delta$ bound, let's look at the difference between: $h\left(q^{\frac{ϵ}{1+ϵ}}\right)$ and $h\left(q^{\prime \frac{ϵ}{1+ϵ}}\right)$

To begin with, by monotonicity,

$h\left(q^{\frac{ϵ}{1+ϵ}}\right)\le h(sup(q^{\frac{ϵ}{1+ϵ}},q^{\prime \frac{ϵ}{1+ϵ}}))$

then, by the fact that we have a finite Lipschitz constant $L$ for infradistributions when the associated function is bounded above 0. Let $ϵ$ be small enough that $q^{\prime \frac{ϵ}{1+ϵ}}\ge 0.5$, this makes the Lipschitz constant not depend on $\delta$.

$h(sup(q^{\frac{ϵ}{1+ϵ}},q^{\prime \frac{ϵ}{1+ϵ}}))\le h\left(q^{\prime \frac{ϵ}{1+ϵ}}\right)+Ld(sup(q^{\frac{ϵ}{1+ϵ}},q^{\prime \frac{ϵ}{1+ϵ}}),q^{\prime \frac{ϵ}{1+ϵ}})$

Now, let's try to evaluate the distance between those two functions, and how it scales with $ϵ$. The distance between functions is the maximum difference in values they assign to input points. Remember, if $q_i\le \frac{1}{|X|}$, $q_i^{\prime }$ has an equal or higher value, so the supremum is gonna mimic $q^{\prime }$ there. But for everything else, $q_i$ is actually going to be higher, and the supremum will mimic $q$ instead. So, we have:

$d(sup(q^{\frac{ϵ}{1+ϵ}},q^{\prime \frac{ϵ}{1+ϵ}}),q^{\prime \frac{ϵ}{1+ϵ}})={sup}_{i:q_i>\frac{1}{|X|}}|q_i^{\frac{ϵ}{1+ϵ}}-q_i^{\prime \frac{ϵ}{1+ϵ}}|$

$={sup}_{i:q_i>\frac{1}{|X|}}(q_i^{\frac{ϵ}{1+ϵ}}-{\left(\frac{q_i+\frac{\delta }{1-|X|\delta }}{1+|X|\frac{\delta }{1-|X|\delta }}\right)}^{\frac{ϵ}{1+ϵ}})\le {sup}_{y\in (|X{|}^{-1},1]}(y^{\frac{ϵ}{1+ϵ}}-{\left(\frac{y+\frac{\delta }{1-|X|\delta }}{1+|X|\frac{\delta }{1-|X|\delta }}\right)}^{\frac{ϵ}{1+ϵ}})$

Now, what we really want to study is how that above quantity varies with $ϵ$. Fortunately, $a^{\frac{x}{1-x}}$ with $a\in (0,1]$ is an analytic function at $x=0$, so we can take the Taylor expansion of both terms to see what's happening around 0 in terms of $ϵ$.

$={sup}_{y\in (|X{|}^{-1},1]}\left(\right(1+ϵ\ln \left(y\right)+O\left({ϵ}^2\right))-(1+ϵ\ln \left(\frac{y+\frac{\delta }{1-|X|\delta }}{1+|X|\frac{\delta }{1-|X|\delta }}\right)+O({ϵ}^2\left)\right))$

$={sup}_{y\in (|X{|}^{-1},1]}\left(ϵ\ln \right(y)-ϵ\ln \left(\frac{y+\frac{\delta }{1-|X|\delta }}{1+|X|\frac{\delta }{1-|X|\delta }}\right)+O({ϵ}^2\left)\right)$

$=ϵ{sup}_{y\in (|X{|}^{-1},1]}\left(\ln \left(\frac{y}{\frac{y+\frac{\delta }{1-|X|\delta }}{1+|X|\frac{\delta }{1-|X|\delta }}}\right)\right)+O\left({ϵ}^2\right)$

And, graphing the function in the sup with Desmos, with $y$ as the variable, and $\delta$ and $|X|$ as sliders, it's always maximized at 1. So then we get:

$=ϵ\ln \left(\frac{1}{\frac{1+\frac{\delta }{1-|X|\delta }}{1+|X|\frac{\delta }{1-|X|\delta }}}\right)+O\left({ϵ}^2\right)=ϵ\ln \left(\frac{1+|X|\frac{\delta }{1-|X|\delta }}{1+\frac{\delta }{1-|X|\delta }}\right)+O\left({ϵ}^2\right)$

I should note something about the big-O notation. From trying it out on some test values, the coefficient gets larger as $y$ decreases. So we don't have to worry about the coefficient in the big-O blowing up unboundedly, the lower bound on our possible $y$ tames it. Putting it all together, we get (for $ϵ$ sufficiently close to 0),

$h\left(q^{\frac{ϵ}{1+ϵ}}\right)\le h\left(q^{\prime \frac{ϵ}{1+ϵ}}\right)+Lϵ\ln \left(\frac{1+|X|\frac{\delta }{1-|X|\delta }}{1+\frac{\delta }{1-|X|\delta }}\right)+O\left({ϵ}^2\right)$

And our big-O doesn't depend on what q happens to be. Given any q at all, when we rescale it to get our $q^{\prime }$, our analysis always works until the big-O terms start manifesting, but they're biggest for the smallest $y$'s, and the lowest our $y$ gets is $|X{|}^{-1}$, so we can pick a sufficiently large constant to make everything work regardless of the $q$. Also, our big-O absorbed the Lipschitz constant. Now, because our big-O doesn't care about what $q$ is, we have:

${sup}_q\left(h\right(q^{\frac{ϵ}{1+ϵ}}\left)\right)\le {sup}_{q\ge \delta }\left(h\right(q^{\frac{ϵ}{1+ϵ}}\left)\right)+Lϵ\ln \left(\frac{1+|X|\frac{\delta }{1-|X|\delta }}{1+\frac{\delta }{1-|X|\delta }}\right)+O\left({ϵ}^2\right)$

Pretty much, since the last two terms of our bound are uniform in $q$, and all our $q^{\prime }\ge \delta$ since we designed it that way, we get the above bound. Now, we can take the $\ln$ to get

$\ln \left({sup}_q\right(h\left(q^{\frac{ϵ}{1+ϵ}}\right)\left)\right)\le \ln \left({sup}_{q\ge \delta }\right(h\left(q^{\frac{ϵ}{1+ϵ}}\right))+Lϵ\ln \left(\frac{1+|X|\frac{\delta }{1-|X|\delta }}{1+\frac{\delta }{1-|X|\delta }}\right)+O({ϵ}^2\left)\right)$

and multiply to get:

$\frac{1+ϵ}{-ϵ}\ln \left({sup}_q\right(h\left(q^{\frac{ϵ}{1+ϵ}}\right)\left)\right)\ge \frac{1+ϵ}{-ϵ}\ln \left({sup}_{q\ge \delta }\right(h\left(q^{\frac{ϵ}{1+ϵ}}\right))+Lϵ\ln \left(\frac{1+|X|\frac{\delta }{1-|X|\delta }}{1+\frac{\delta }{1-|X|\delta }}\right)+O({ϵ}^2\left)\right)$

Thus, our upper bound on the sequence as a whole is:

$\frac{1+ϵ}{-ϵ}\ln \left({sup}_{q\ge \delta }\right(h\left(q^{\frac{ϵ}{1+ϵ}}\right)\left)\right)$

and our lower bound on the sequence as a whole for small $ϵ$ is

$\frac{1+ϵ}{-ϵ}\ln \left({sup}_{q\ge \delta }\right(h\left(q^{\frac{ϵ}{1+ϵ}}\right))+Lϵ\ln \left(\frac{1+|X|\frac{\delta }{1-|X|\delta }}{1+\frac{\delta }{1-|X|\delta }}\right)+O({ϵ}^2\left)\right)$

Let's show convergence for that top one, as it'll eventually let us crack the bottom one as well. Our task now is to show upper and lower bounds for the sequence (as $ϵ\to 0$)

$\frac{1+ϵ}{-ϵ}\ln \left({sup}_{q\ge \delta }\right(h\left(q^{\frac{ϵ}{1+ϵ}}\right)\left)\right)$

Augmented with our nice bounds on how low $q$ can be, let's see if we can find some other function that's close to $q^{\frac{ϵ}{1+ϵ}}$ for $ϵ$ near 0, so we can swap out for that.

Well... if we take the Taylor expansion of $y^{\frac{ϵ}{1+ϵ}}$ w.r.t. $ϵ$ around 0, then we get $1+ϵ\ln \left(y\right)+O\left({ϵ}^2\right)$. So what if we swapped out $q^{\frac{ϵ}{1+ϵ}}$ for $1+ϵ\ln \left(q\right)$? The second part of that is negative, so it's below 1. And, since, for all $i$, $q_i\ge \delta$, once we get to $ϵ<\frac{1}{-\ln \left(\delta \right)}$, it's guaranteed to never undershoot 0 and be a legit function. Let's assess the difference between the two functions:

${sup}_i|q_i^{\frac{ϵ}{1+ϵ}}-(1+ϵ\ln (q_i\left)\right)|$

$={sup}_i|(1+ϵ\ln (q\left)\right)+O\left({ϵ}^2\right)-(1+ϵ\ln (q\left)\right)|=O\left({ϵ}^2\right)$

Again, the reason this works is, because we have a uniform lower bound on our $q_i$, they're all in $[\delta ,1]$, which bounds how bad the big-O constants can be, so this difference is uniform across our $q$. The difference between $q^{\frac{ϵ}{1+ϵ}}$ and $1+ϵ\ln \left(q\right)$ is $O\left({ϵ}^2\right)$. By Lipschitzness of $h$ on functions bounded above $0.5$ (which happens for low enough $ϵ$), we can transfer this difference outside the $h$, and the Lipschitz constant absorbs into the big-O, so:

$h\left(q^{\frac{ϵ}{1+ϵ}}\right)\le h(1+ϵ\ln (q\left)\right)+O\left({ϵ}^2\right)$

and then, transferring this to all $q$ (the big-O is uniform), we have:

${sup}_{q\ge \delta }\left(h\right(q^{\frac{ϵ}{1+ϵ}}\left)\right)\le {sup}_{q\ge \delta }\left(h\right(1+ϵ\ln \left(q\right)\left)\right)+O\left({ϵ}^2\right)$

and so, we get a lower bound where

$\frac{1+ϵ}{-ϵ}\ln \left({sup}_{q\ge \delta }\right(h\left(q^{\frac{ϵ}{1+ϵ}}\right)\left)\right)\ge \frac{1+ϵ}{-ϵ}\ln \left({sup}_{q\ge \delta }\right(h(1+ϵ\ln (q\left)\right))+O({ϵ}^2\left)\right)$

Now, for the upper bound. This is easy, because by graphing, we can see that $1+ϵ\ln \left(q_i\right)\le q_i^{\frac{ϵ}{1+ϵ}}$ is always true if $ϵ\ge 0$ and $q_i\in [\delta ,1]$. Thus, by monotonicity,

$h\left(q^{\frac{ϵ}{1+ϵ}}\right)\ge h(1+ϵ\ln (q\left)\right)$

and, again, transferring this to all $q$, and then taking the $\ln$ and multiplying by our negative constant, we have:

$\frac{1+ϵ}{-ϵ}\ln \left({sup}_{q\ge \delta }\right(h\left(q^{\frac{ϵ}{1+ϵ}}\right)\left)\right)\le \frac{1+ϵ}{-ϵ}\ln \left({sup}_{q\ge \delta }\right(h(1+ϵ\ln (q\left)\right)\left)\right)$

Alright, we've got some bounds. We can keep poking more at reexpressing the bounds, but remember that since we still haven't shown that anything in particular converges, we're gonna keep getting bounds on our bounds on our bounds. At some point we need to ground out and get that some actual limit exists, and use that as a tool to solve all the rest of the bounds. 

Let's look at $h(1+ϵ\ln (q\left)\right)$ for inspiration. We can notice something interesting. For a particular $q$, we can perfectly reexpress this as $h(1-ϵf)$, where $f_i=-\ln \left(q_i\right)$. Our analogue of $q_i$ summing to 1 is ${\sum }_i{e}^{-f_i}=1$, and our analogue of $q$ being in $[\delta ,1{]}^{|X|}$ is that $f\in [0,-\ln (\delta ){]}^{|X|}$. In fact, all $f$ of this form correspond to a $q$, and vice-versa, just have $q=e^{-f}$. So, using ${sup}_{f\le -\ln \left(\delta \right)}$ as a shorthand for "we're selecting among $f$ that fulfill these properties as that's isomorphic to selecting a $q$", we would be able to go:

${sup}_{q\ge \delta }\left(h\right(1+ϵ\ln \left(q\right)\left)\right)={sup}_{f\le -\ln \left(\delta \right)}\left(h\right(1-ϵf\left)\right)$

Now, with this reexpression, fixing a particular $f^{\ast }$, are we able to solve the following equation?

${lim}_{ϵ\to 0}\frac{1+ϵ}{-ϵ}\ln \left(h\right(1-ϵf^{\ast }\left)\right)$

We're just slicing off the smallest nontrivial bit of the problem we can to hopefully get one of these damn bounds to converge to something. And it turns out, we actually can solve this one! The teensy little problem is that L'hopital's rule only applies to differentiable functions, and this... isn't exactly differentiable. So we have to dig deep into the guts of the proof behind L'hopital's rule in order to show that applying the L'hopital procedure pretty much solves this, even though our function isn't differentiable (remember, h is Lipschitz, not differentiable). Once we've solved this, we'll be able to start chaining backwards and solve everything.

Our first order of business is to show that $(1+ϵ)\ln \left(h\right(1-ϵf^{\ast }\left)\right)$, as a function of $ϵ$ is differentiable almost everywhere, concave, and monotonically decreasing. First, for concavity of $h(1-ϵf^{\ast })$, observe that:

$h(1-(pϵ+(1-p){ϵ}^{\prime }\left)f^{\ast }\right)=h(p-pϵf^{\ast }+(1-p)-(1-p\left){ϵ}^{\prime }{f}^{\ast }\right)\ge ph(1-ϵf^{\ast })+(1-p)h(1-{ϵ}^{\prime }{f}^{\ast })$

And, as $ϵ$ gets bigger, by monotonicity of $h$, $h(1-ϵf^{\ast })$ gets smaller. So, $h(1-ϵf^{\ast })$ is monotonically decreasing, and concave. Now, from math stackexchange, the composition of a concave function with a monotonically increasing concave function ($\ln$ in this case) is concave. Thus, $\ln \left(h\right(1-ϵf^{\ast }\left)\right)$ is monotonically decreasing in $ϵ$, and concave. It's 0 when $ϵ=0$, and slopes down into the negative.

Now, any line from a point on the graph of $\ln \left(h\right(1-ϵf^{\ast }\left)\right)$ to another point on it must have a very important property. It slopes down, since this function is monotonically decreasing in $ϵ$. So, given some $ϵ$ and ${ϵ}^{\prime }$, there's a linear function $a-bx$ with $a,b\ge 0$ where, regardless of $p$,

$a-b(pϵ+(1-p\left){ϵ}^{\prime }\right)=p\ln \left(h\right(1-ϵf^{\ast }\left)\right)+(1-p)\ln \left(h\right(1-{ϵ}^{\prime }{f}^{\ast }\left)\right)$

(this is just the line between two spots on our resulting concave composite function). And then we can go:

$\ln \left(h\right(1-(pϵ+(1-p\left){ϵ}^{\prime }\right)f^{\ast }\left)\right)\ge p\ln \left(h\right(1-ϵf^{\ast }\left)\right)+(1-p)\ln \left(h\right(1-{ϵ}^{\prime }{f}^{\ast }\left)\right)=a-b(pϵ+(1-p\left){ϵ}^{\prime }\right)$

The first inequality is by concavity for $\ln \left(h\right(1-ϵf^{\ast }\left)\right)$ in $ϵ$. Multiplying by $(1+pϵ+(1-p\left){ϵ}^{\prime }\right)$ produces:

$(1+pϵ+(1-p\left){ϵ}^{\prime }\right)\ln \left(h\right(1-(pϵ+(1-p\left){ϵ}^{\prime }\right)f^{\ast }\left)\right)\ge (1+pϵ+(1-p\left){ϵ}^{\prime }\right)(a-b(pϵ+(1-p){ϵ}^{\prime }\left)\right)$

and, then, I'm gonna explain this following inequality in a bit, where it came from.

$\ge p(1+ϵ)(a-bϵ)+(1-p)(1+{ϵ}^{\prime })(a-b{ϵ}^{\prime })$

$=p(1+ϵ)\ln \left(h\right(1-ϵf^{\ast }\left)\right)+(1-p)(1+{ϵ}^{\prime })\ln \left(h\right(1-{ϵ}^{\prime }{f}^{\ast }\left)\right)$

So, the equality makes sense, we just use the link between our line and ln of $h$, see above just under "net takeaway". The inequality... what the heck is that about? Well, $(1+x)(a-bx)$ is a parabola opening down, it's concave. So, plugging $pϵ+(1-p){ϵ}^{\prime }$ in for the $x$ produces a bigger value than $p(1+ϵ)(a-bϵ)+(1-p)(1+{ϵ}^{\prime })(a-b{ϵ}^{\prime })$.

Ok, so our equation as a whole is concave. It's also monotonically decreasing because (ln of $h$ of...) starts off at 0 and just heads down from there, and we're multiplying by bigger and bigger positive numbers as $ϵ$ increases.

And also, according to math stackexchange, concave functions can only be non-differentiable at countably many points! So,

$(1+ϵ)\ln \left(h\right(1-ϵf^{\ast }\left)\right)$

the above function is concave in $ϵ$, is monotonically decreasing in $ϵ$, and only has countably many non-differentiable points. So as not to rewrite this each time, we'll switch our variable from $ϵ$ to $x$, and abbreviate this as $\theta \left(x\right)$, unpacking as needed.

Now that we know our function is nice, we can turn to verifying the important core needed to apply L'hopital's rule to solve the limit. And once that's done, we can start chaining backwards to solve our whole problem.

The key part that works for our function in particular, though it may fail in the general case, is an analogue of Cauchy's mean value theorem. We're about to make a bit of a mathematical leap here. We're going to let the derivative be set-valued at nondifferentiable points. As a toy example, consider the function $|x|$. if $x\ne 0$, the derivative is well-defined. If $x=0$, then, even though we don't have a derivative here, there's a left-derivative and a right-derivative. So, we can consider the "derivative" at 0 for $|x|$ to be any number between -1 and 1. 

Now, the particular thing we need to go through the L'hopital proof for our specific case is: For $ϵ$ and $\tau \in (0,ϵ)$, there's a $\chi \in [\tau ,ϵ]$, and a possible choice of derivative (remember, we've got the set-valued derivatives now) where:

$\frac{\theta \left(ϵ\right)-\theta \left(\tau \right)}{(-ϵ)-(-\tau )}=\frac{\frac{d}{dx}\left(\theta \right(x\left)\right)\left(\chi \right)}{\frac{d}{dx}(-x)\left(\chi \right)}$

We can make the argument for this more intuitive by drawing the following picture.

Remember, our function \theta is concave, and note that that the left-hand-side of our equation is just going "what's the slope of the line" (with positive sign). From concavity, we can just translate said line up until it becomes a tangent line of our function, and that gets us our value of $\chi \in [\tau ,ϵ]$ where there's a possible derivative that induces the above equality (because $\frac{d}{dx}(-x)\left(\chi \right)=-1$ no matter what, and this also enforces the appropriate sign). So, we do indeed have our analogue of Cauchy's mean value theorem working here. Drawing a line segment between two points on the graph of $\theta \left(x\right)$, there's a point in between them where the possible derivative matches up with the slope of the line segment.

Now, define the following two functions:

$m\left(ϵ\right):={inf}_{\chi \in [0,ϵ]}\frac{\frac{d}{dx}\left(\theta \right(x\left)\right)\left(\chi \right)}{\frac{d}{dx}(-x)\left(\chi \right)}$

$M\left(ϵ\right):={sup}_{\chi \in [0,ϵ]}\frac{\frac{d}{dx}\left(\theta \right(x\left)\right)\left(\chi \right)}{\frac{d}{dx}(-x)\left(\chi \right)}$

The inf and sup is also taken over possible choices of derivative, by the way. And so, regardless of our choice of $ϵ$ and $\tau$, as long as $\tau <ϵ$, from our analogue of Cauchy's Mean Value Theorem,

$m\left(ϵ\right)\le \frac{\theta \left(ϵ\right)-\theta \left(\tau \right)}{(-ϵ)-(-\tau )}\le M\left(ϵ\right)$

Now that we've established this, lock $ϵ$ in place and let $\tau$ limit to 0.

${lim}_{\tau \to 0}\frac{\theta \left(ϵ\right)-\theta \left(\tau \right)}{(-ϵ)-(-\tau )}$

$={lim}_{\tau \to 0}\frac{(1+ϵ)\ln \left(h\right(1-ϵf^{\ast }\left)\right)-(1+\tau )\ln \left(h\right(1-\tau f^{\ast }\left)\right)}{(-ϵ)-(-\tau )}$

$={lim}_{\tau \to 0}\frac{(1+ϵ)\ln \left(h\right(1-ϵf^{\ast }\left)\right)}{(-ϵ)-(-\tau )}-{lim}_{\tau \to 0}\frac{(1+\tau )\ln \left(h\right(1-\tau f^{\ast }\left)\right)}{(-ϵ)-(-\tau )}$

$=\frac{1+ϵ}{-ϵ}\ln \left(h\right(1-ϵf^{\ast }\left)\right)$

That last equality was because $1-\tau f^{\ast }$ approaches 1, so by normalization for $h$, $h(1-\tau f^{\ast })$ approaches 1, so $\ln \left(h\right(1-\tau f^{\ast }\left)\right)$ approaches 0, and multiplying by $(1+\tau )$ dosn't change that, and the bottom doesn't limit to 0.

So, we have our result that, for all our relevant $ϵ$,

$m\left(ϵ\right)\le \frac{1+ϵ}{-ϵ}\ln \left(h\right(1-ϵf^{\ast }\left)\right)\le M\left(ϵ\right)$

And now we'll use the squeeze theorem. So, what's the limit as $ϵ$ heads to 0 for $m\left(ϵ\right)$ and $M\left(ϵ\right)$?

Well, the former is:

${lim}_{ϵ\to 0}m\left(ϵ\right)={lim}_{ϵ\to 0}{inf}_{\chi \in [0,ϵ]}\frac{\frac{d}{dx}\left(\theta \right(x\left)\right)\left(\chi \right)}{\frac{d}{dx}(-x)\left(\chi \right)}={lim}_{ϵ\to 0}{inf}_{\chi \in [0,ϵ]}\frac{\frac{d}{dx}\left(\right(1+x\left)\ln \right(h(1-x{f}^{\ast })\left)\right)\left(\chi \right)}{-1}$

$={lim}_{ϵ\to 0}{inf}_{\chi \in [0,ϵ]}(-\left(\ln \right(h(1-x{f}^{\ast }))+\frac{1+x}{h(1-x{f}^{\ast })}\frac{d}{dx}h(1-x{f}^{\ast }\left)\right)(\chi \left)\right)$

$={lim}_{ϵ\to 0}{inf}_{\chi \in [0,ϵ]}(-\left(\ln \right(h(1-\chi f^{\ast }))+\frac{1+\chi }{h(1-\chi f^{\ast })}\frac{d}{dx}(h(1-x{f}^{\ast })\left)\right(\chi \left)\right))$

and as $ϵ$ gets incredibly close to 0 (forcing $\chi$ to do so as well), the $\ln \left(h\right(1-\chi f^{\ast }\left)\right)$ turns into 0, and the $\frac{1+\chi }{h(1-\chi f^{\ast })}$ turns into 1. So, this produces:

$={lim}_{ϵ\to 0}{inf}_{\chi \in [0,ϵ]}(-\frac{d}{dx}(h(1-x{f}^{\ast })\left)\right(\chi \left)\right)$

And now, since $h(1-x{f}^{\ast })$ is concave in $x$ and monotonically decreasing... Well, no matter which slope we choose for the nondifferentiable points, the shallowest possible slope is at 0. The slope is gonna be negative. Multiplying it by a negative means that we're trying to minimize a positive number. So, we want the shallowest slope we can possibly get, which would mean plugging $\chi =0$ in. Bam, no dependence on $ϵ$ anymore.

$=-\frac{d}{dx}\left(h\right(1-x{f}^{\ast }\left)\right)\left(0\right)$

$=-{lim}_{\tau \to 0}\frac{h(1+\tau (-f^{\ast }\left)\right)-h\left(1\right)}{\tau }$

And, consulting the Wikipedia page for the Gateux Derivative, this is the Gateaux Derivative of $h$ at 1 in the direction of $-f^{\ast }$!

So, we finally have solved one of our limits, it's:$-dh(1;-f^{\ast })$. Now, what about $M\left(ϵ\right)$? Well, a similar analysis applies.

${lim}_{ϵ\to 0}M\left(ϵ\right)={lim}_{ϵ\to 0}{sup}_{\chi \in [0,ϵ]}\frac{\frac{d}{dx}\left(\theta \right(x\left)\right)\left(\chi \right)}{\frac{d}{dx}(-x)\left(\chi \right)}={lim}_{ϵ\to 0}{sup}_{\chi \in [0,ϵ]}\frac{\frac{d}{dx}\left(\right(1+x\left)\ln \right(h(1-x{f}^{\ast })\left)\right)\left(\chi \right)}{-1}$

$={lim}_{ϵ\to 0}{sup}_{\chi \in [0,ϵ]}(-\left(\ln \right(h(1-x{f}^{\ast }))+\frac{1+x}{h(1-x{f}^{\ast })}\frac{d}{dx}h(1-x{f}^{\ast }\left)\right)(\chi \left)\right)$

$={lim}_{ϵ\to 0}{sup}_{\chi \in [0,ϵ]}(-\left(\ln \right(h(1-\chi f^{\ast }))+\frac{1+\chi }{h(1-\chi f^{\ast })}\frac{d}{dx}(h(1-x{f}^{\ast })\left)\right(\chi \left)\right))$

and as $ϵ$ gets incredibly close to 0 (forcing $\chi$ to do so as well), the $\ln \left(h\right(1-\chi f^{\ast }\left)\right)$ turns into 0, and the $\frac{1+\chi }{h(1-\chi f^{\ast })}$ turns into 1. So, this produces:

$={lim}_{ϵ\to 0}{sup}_{\chi \in [0,ϵ]}(-\frac{d}{dx}(h(1-x{f}^{\ast })\left)\right(\chi \left)\right)$

And now, since $h(1-x{f}^{\ast })$ is concave in $x$ and monotonically decreasing... Well, the slope is shallowest at 0, and steepest at $ϵ$ itself. The slope is gonna be negative. Multiplying it by a negative means that we're trying to maximize a positive number. So, we want the steepest slope we can possibly get, which would mean plugging $\chi =ϵ$ in. So, we have:

$={lim}_{ϵ\to 0}sup(-\frac{d}{dx}(h(1-x{f}^{\ast })\left)\right(ϵ\left)\right)$

Now, the sup in this case is just sup over derivatives, we know which $\chi$ to put in. In particular, since $h(1-x{f}^{\ast })$ is concave in $x$ and monotonically decreasing, the steepest possible derivative we could have is the derivative where the nearby point approaches from higher $ϵ$.

Now, remember, $h(1-x{f}^{\ast })$ is a concave function and monotonically decreasing (in $x$). If we graphed the derivative (in $x$), it'd be monotonically decreasing and always at 0 or less. There's discontinuities in the graph of the derivative, the graph of the derivative would look like a staircase going down. But remember, there are only countably many discontinuities. We're taking the lowest value of the derivative (read: furthest away from 0), so we can turn it into a (discontinuous) function where, at the "stairstep" discontinuity points, we stay at the bottom of the stairstep. And so, the question is, "if we stick to the bottom of the step at points where there's a step jump, and travel towards 0 ie $ϵ$ goes to 0, do we have a limit?" Well, the value of that "staircase" derivative function is monotonically increasing (going from well below 0 to less below 0) as $ϵ$ goes to 0, and it's got an upper bound of 0, so yeah, there's a limit.

But, in order to identify the limit as $ϵ$ goes to 0 of the lowest possible derivative with just "the derivative at 0", we've got a bit of a problem. There's some free choice in which derivative value to assign at discontinuity points. Given free choice in the matter, do all those choices lead to hitting the same value at 0? Well, let's say we took the upper value of the staircase. Given any $ϵ$ where there's a discontinuity, there's a smaller $\tau \in [\frac{ϵ}{2},ϵ]$ where the derivative is well-defined (because there's only countably many points where there's a discontinuity), which attains a value closer to 0 than the closest-to-0 value on the stairstep, because our derivative function stairstep is monotonically increasing as $ϵ$ ticks down. So, even the "take the upper value for each stairstep discontinuity" function can have any particular value exceeded by a sufficiently low value for $ϵ$ when we take the lower value for the stairstep discontinuities. So, it has the same limiting value. Which, again, is the derivative at 0. So, we get:

$={lim}_{ϵ\to 0}sup(-\frac{d}{dx}(h(1-x{f}^{\ast })\left)\right(ϵ\left)\right)=-\frac{d}{dx}\left(h\right(1-x{f}^{\ast }\left)\right)\left(0\right)=-dh(1;-f^{\ast })$

Alright! We got the same value for an upper bound as a lower bound! Awesome! Now we can get started solving some limits, finally! From here on out, we'll do a lot of backing up to stuff we've already shown. First, we've already shown that:

$m\left(ϵ\right)\le \frac{1+ϵ}{-ϵ}\ln \left(h\right(1-ϵf^{\ast }\left)\right)\le M\left(ϵ\right)$

and, in the $ϵ\to 0$ limit, both the left-hand side and right-hand-side have the same limit. Namely, $-dh(1;-f^{\ast })$. The Gateaux derivative of $h$ at 1 in the direction of $-f^{\ast }$. So,

${lim}_{ϵ\to 0}\frac{1+ϵ}{-ϵ}\ln \left(h\right(1-ϵf^{\ast }\left)\right)=-dh(1;-f^{\ast })$

Alright, we've got our first toehold where we were actually able to solve a damn limit. Let's back up a bit and try somthing more ambitious. Let's attempt to solve

${lim}_{ϵ\to 0}\frac{1+ϵ}{-ϵ}\ln \left({sup}_{f\le -\ln \left(\delta \right)}\right(h(1-ϵf)\left)\right)$

Again, we're going to impose upper and lower bounds. The tricky part in this case is that the previous limit was just for a particular function. Once we start taking the supremum over a bunch of different functions, we can't necessarily guarantee that they all limit at the same rate. But, let's try to reduce it to the case of one particular function.

To begin with, regardless of $ϵ$ and $f$, $h(1-ϵf)\le 1+ϵdh(1;-f)$. Why is this the case? Well, the former is a concave function, monotonically decreasing, that starts at 1 where $ϵ=0$. And the latter is the tangent line to the former function at $ϵ=0$. So, the tangent line lies above the function. Thus, we can go:

$h(1-ϵf)\le 1+ϵdh(1;-f)$

${sup}_{f\le -\ln \left(\delta \right)}\left(h\right(1-ϵf\left)\right)\le {sup}_{f\le -\ln \left(\delta \right)}(1+ϵdh(1;-f\left)\right)$

$\ln \left({sup}_{f\le -\ln \left(\delta \right)}\right(h(1-ϵf)\left)\right)\le \ln \left({sup}_{f\le -\ln \left(\delta \right)}\right(1+ϵdh(1;-f)\left)\right)$

$\frac{1+ϵ}{-ϵ}\ln \left({sup}_{f\le -\ln \left(\delta \right)}\right(h(1-ϵf)\left)\right)\ge \frac{1+ϵ}{-ϵ}\ln \left({sup}_{f\le -\ln \left(\delta \right)}\right(1+ϵdh(1;-f)\left)\right)$

and then, since all the Gateux derivatives are 0 or less, we can move the sup inside (changes nothing), and get:

$\frac{1+ϵ}{-ϵ}\ln \left({sup}_{f\le -\ln \left(\delta \right)}\right(h(1-ϵf)\left)\right)\ge \frac{1+ϵ}{-ϵ}\ln (1+ϵ{sup}_{f\le -\ln \left(\delta \right)}(dh(1;-f)\left)\right)$

Ok, cool, we've got a lower bound. Now, what about an upper bound? Well, pick an $f^{\ast }$ where $dh(1;-f^{\ast })$ is extremely extremely close to ${sup}_{f\le -\ln \left(\delta \right)}\left(dh\right(1;-f\left)\right)$. We can get:

${sup}_{f\le -\ln \left(\delta \right)}\left(h\right(1-ϵf\left)\right)\ge h(1-ϵf^{\ast })$

$\ln \left({sup}_{f\le -\ln \left(\delta \right)}\right(h(1-ϵf)\left)\right)\ge \ln \left(h\right(1-ϵf^{\ast }\left)\right)$

$\frac{1+ϵ}{-ϵ}\ln \left({sup}_{f\le -\ln \left(\delta \right)}\right(h(1-ϵf)\left)\right)\le \frac{1+ϵ}{-ϵ}\ln \left(h\right(1+ϵf^{\ast }\left)\right)$

And bam, we have an upper bound.

Now, let's take the $ϵ\to 0$ limits of our lower bound and upper bound. Our upper bound limit is:

${lim}_{ϵ\to 0}\frac{1+ϵ}{-ϵ}\ln \left(h\right(1+ϵf^{\ast }\left)\right)=-dh(1;-f^{\ast })$

Our lower bound limit is:

${lim}_{ϵ\to 0}\frac{1+ϵ}{-ϵ}\ln (1+ϵ{sup}_{f\le -\ln \left(\delta \right)}(dh(1;-f)\left)\right)$

But fortunately, that supremum doesn't change with $ϵ$! It's just a constant. So the function inside the $\ln$ is continuous and differentiable, and so is everything, so we can solve this with vanilla L'hopital's rule.

$={lim}_{ϵ\to 0}\frac{\frac{d}{dx}\left(\right(1+x\left)\ln \right(1+x{sup}_{f\le -\ln \left(\delta \right)}\left(dh\right(1;-f\left)\right)\left)\right)\left(ϵ\right)}{\frac{d}{dx}(-x)\left(ϵ\right)}$

$={lim}_{ϵ\to 0}\frac{\ln (1+ϵ{sup}_{f\le -\ln \left(\delta \right)}(dh(1;-f)\left)\right)+\frac{1+ϵ}{1+ϵ{sup}_{f\le -\ln \left(\delta \right)}\left(dh\right(1;-f\left)\right)}{sup}_{f\le -\ln \left(\delta \right)}\left(dh\right(1;-f\left)\right)}{-1}$

$=-\left(\ln \right(1+0)+\frac{1+0}{1+0}{sup}_{f\le -\ln \left(\delta \right)}(dh(1;-f)\left)\right)$

$=-{sup}_{f\le -\ln \left(\delta \right)}\left(dh\right(1;-f\left)\right)$

Sadly, these two bounds are different. We only have that

${lim}_{ϵ\to 0}\frac{1+ϵ}{-ϵ}\ln \left({sup}_{f\le -\ln \left(\delta \right)}\right(h(1-ϵf)\left)\right)\in [-{sup}_{f\le -\ln \left(\delta \right)}(dh(1;-f)),-dh(1;-f^{\ast }\left)\right]$

Or, heck, the limit might not even exist! But all limit points must be in that interval. But... this argument worked independently of our choice of $f^{\ast }$. So, we can select it so the derivative is as close as we want to the supremum derivative! No matter how tight the interval is, we can always back up, pick a different $f^{\ast }$, and make the interval smaller! Thus, the limit must exist, and we have:

${lim}_{ϵ\to 0}\frac{1+ϵ}{-ϵ}\ln \left({sup}_{f\le -\ln \left(\delta \right)}\right(h(1-ϵf)\left)\right)=-{sup}_{f\le -\ln \left(\delta \right)}\left(dh\right(1;-f\left)\right)$

Bam, that's another limit out of the way. Going back in the proof, we showed earlier that

$\frac{1+ϵ}{-ϵ}\ln \left({sup}_{f\le -\ln \left(\delta \right)}\right(h(1-ϵf))=\frac{1+ϵ}{-ϵ}\ln ({sup}_{q\ge \delta }\left(h\right(1+ϵ\ln \left(q\right)\left)\right))$

(it was just a reexpression), so that nets us another limit,

${lim}_{ϵ\to 0}\frac{1+ϵ}{-ϵ}\ln \left({sup}_{q\ge \delta }\right(h(1+ϵ\ln (q\left)\right)\left)\right)=-{sup}_{f\le -\ln \left(\delta \right)}\left(dh\right(1;-f\left)\right)$

Now... let's back up to showing what

${lim}_{ϵ\to 0}\frac{1+ϵ}{-ϵ}\ln \left({sup}_{q\ge \delta }\right(h\left(q^{\frac{ϵ}{1+ϵ}}\right)\left)\right)$

is. From earlier work, our upper bound (for small enough $ϵ$) was:

$\frac{1+ϵ}{-ϵ}\ln \left({sup}_{q\ge \delta }\right(h(1+ϵ\ln (q\left)\right)\left)\right)$

and our lower bound was:

$\frac{1+ϵ}{-ϵ}\ln \left({sup}_{q\ge \delta }\right(h(1+ϵ\ln (q\left)\right))+O({ϵ}^2\left)\right)$

Well, we know what the upper bound limits to already. We do need to check that the $O\left({ϵ}^2\right)$ thing doesn't mess with anything. We're going to Taylor-expand $\ln$ about 1. The interval of convergence is $(0,2]$ so this Taylor expansion works for $ϵ$ a bit away from 1, not just in the limit. Taylor-expanding the ln for the lower bound produces:

$\frac{1+ϵ}{-ϵ}\left(\right({sup}_{q\ge \delta }\left(h\right(1+ϵ\ln \left(q\right)\left)\right)+O\left({ϵ}^2\right)-1)+\frac{1}{2}({sup}_{q\ge \delta }\left(h\right(1+ϵ\ln \left(q\right)\left)\right)+O\left({ϵ}^2\right)-1{)}^2...)$

Now, $\left({sup}_{q\ge \delta }\right(h(1+ϵ\ln (q\left)\right))-1)$ converges to 0 as $O\left(ϵ\right)$, so we can neglect all terms but the first (because any later term would converge to 0 as $O\left({ϵ}^2\right)$ or faster, so even after getting blown up by dividing by $ϵ$, they'd still shrink to 0). And the $O\left({ϵ}^2\right)$ error term in the lower bound, again, even after getting blown up, doesn't affect the $ϵ\to 0$ limit. So, since our error term is too small to affect the limit, both the upper bound and lower bound limit to the same thing, $-{sup}_{f\le -\ln \left(\delta \right)}\left(dh\right(1;-f\left)\right)$. And so, by the squeeze theorem,

${lim}_{ϵ\to 0}\frac{1+ϵ}{-ϵ}\ln \left({sup}_{q\ge \delta }\right(h\left(q^{\frac{ϵ}{1+ϵ}}\right)\left)\right)=-{sup}_{f\le -\ln \left(\delta \right)}\left(dh\right(1;-f\left)\right)$

Ok, cool. That's another limit we were able to show to exist. But what about our original thing, back from the start of the proof, that we wanted to show? We wanted to solve

${lim}_{ϵ\to 0}\frac{1+ϵ}{-ϵ}\ln \left({sup}_q\right(h\left(q^{\frac{ϵ}{1+ϵ}}\right)\left)\right)$

Well, our upper bound was:

$\frac{1+ϵ}{-ϵ}\ln \left({sup}_{q\ge \delta }\left(h\left(q^{\frac{ϵ}{1+ϵ}}\right)\right)\right)$

and our lower bound was:

$\frac{1+ϵ}{-ϵ}\ln \left({sup}_{q\ge \delta }\right(h\left(q^{\frac{ϵ}{1+ϵ}}\right))+Lϵ\ln \left(\frac{1+|X|\frac{\delta }{1-|X|\delta }}{1+\frac{\delta }{1-|X|\delta }}\right)+O({ϵ}^2\left)\right)$

Again, our upper bound limits to $-{sup}_{f\le -\ln \left(\delta \right)}\left(dh\right(1;-f\left)\right)$, and our lower bound... well, hang on, there's a $O\left(ϵ\right)$ additional term in there, which is large enough to affect the limit. Again, doing the Taylor-expansion of $\ln$ around 1, and dropping all terms but the first since they decline as $O\left({ϵ}^2\right)$ or faster and so don't affect the limit, our upper bound turns into:

$-{sup}_{f\le -\ln \left(\delta \right)}\left(dh\right(1;-f\left)\right)={lim}_{ϵ\to 0}\frac{1+ϵ}{-ϵ}\ln \left({sup}_{q\ge \delta }\left(h\left(q^{\frac{ϵ}{1+ϵ}}\right)\right)\right)$

$={lim}_{ϵ\to 0}\frac{1+ϵ}{-ϵ}({sup}_{q\ge \delta }\left(h\left(q^{\frac{ϵ}{1+ϵ}}\right)\right)-1)$

Ok, so we know what that limit is. But for our lower bound, when we do the Taylor expansion (neglecting higher-order terms), we get:

${lim}_{ϵ\to 0}\frac{1+ϵ}{-ϵ}\ln \left({sup}_{q\ge \delta }\right(h\left(q^{\frac{ϵ}{1+ϵ}}\right))+Lϵ\ln \left(\frac{1+|X|\frac{\delta }{1-|X|\delta }}{1+\frac{\delta }{1-|X|\delta }}\right)+O({ϵ}^2\left)\right)$

$={lim}_{ϵ\to 0}\frac{1+ϵ}{-ϵ}\left({sup}_{q\ge \delta }\right(h\left(q^{\frac{ϵ}{1+ϵ}}\right))+Lϵ\ln \left(\frac{1+|X|\frac{\delta }{1-|X|\delta }}{1+\frac{\delta }{1-|X|\delta }}\right)+O({ϵ}^2)-1)$

$={lim}_{ϵ\to 0}\frac{1+ϵ}{-ϵ}\left({sup}_{q\ge \delta }\right(h\left(q^{\frac{ϵ}{1+ϵ}}\right))-1)+{lim}_{ϵ\to 0}\frac{1+ϵ}{-ϵ}\left(Lϵ\ln \left(\frac{1+|X|\frac{\delta }{1-|X|\delta }}{1+\frac{\delta }{1-|X|\delta }}\right)\right)+{lim}_{ϵ\to 0}\frac{1+ϵ}{-ϵ}O\left({ϵ}^2\right)$

And then using our result above, and cancelling out some stuff, the lower bound limit is:

$=-{sup}_{f\ge -\ln \left(\delta \right)}\left(dh\right(1;-f\left)\right)-L\ln \left(\frac{1+|X|\frac{\delta }{1-|X|\delta }}{1+\frac{\delta }{1-|X|\delta }}\right)$

So all we have is that ${lim}_{ϵ\to 0}\frac{1+ϵ}{-ϵ}\ln \left({sup}_q\right(h\left(q^{\frac{ϵ}{1+ϵ}}\right)\left)\right)$ lies in

$[-{sup}_{f\le -\ln \left(\delta \right)}(dh(1;-f))-L\ln \left(\frac{1+|X|\frac{\delta }{1-|X|\delta }}{1+\frac{\delta }{1-|X|\delta }}\right),-{sup}_{f\le -\ln \left(\delta \right)}(dh(1;-f)\left)\right]$

Uuuugh. We weren't able to show that the limit exists, just that all limit points are in that interval. But wait a minute, we've got a finite width interval because we picked a $\delta$ ahead of time. What if we redo the argument with a much smaller $\delta$? Can we get this interval down to a single point if we pick smaller and smaller $\delta$? Well, yes.

To begin, our upper bound, $-{sup}_{f\le -\ln \left(\delta \right)}\left(dh\right(1;-f\left)\right)$, as $\delta$ gets bigger, is monotonically decreasing, and bounded below by $-{sup}_f\left(dh\right(1;-f\left)\right)$. So it does have a limit. The argument for this is that, as \delta gets smaller, $-\ln \left(\delta \right)$ is getting bigger, so we're picking amongst more functions. Thus, we've got more freedom to make the Gateaux derivative close to 0 (the derivatives are always 0 or negative), and flipping the sign around, we manage to move our positive quantity lower (or it stays the same). So that takes care of the "monotonically decreasing" part. And obviously, no matter the $\delta$, we have less freedom to pick a function make our derivative close to 0 than maximal freedom in picking said function. But is the limit point as $\delta$ shrinks to 0 actually equal to $-{sup}_f\left(dh\right(1;-f\left)\right)$? Well, we can pick a concrete function that attains a value arbitrarily close to that, and then get a $\delta$ that includes said function, so we do have:

${lim}_{\delta \to 0}-{sup}_{f\le -\ln \left(\delta \right)}\left(dh\right(1;-f\left)\right)=-{sup}_f\left(dh\right(1;-f\left)\right)$

Now, let's tackle our upper bound.

${lim}_{\delta \to 0}-{sup}_{f\le -\ln \left(\delta \right)}\left(dh\right(1;-f\left)\right)-L\ln \left(\frac{1+|X|\frac{\delta }{1-|X|\delta }}{1+\frac{\delta }{1-|X|\delta }}\right)$

$={lim}_{\delta \to 0}(-{sup}_{f\le -\ln \left(\delta \right)}(dh(1;-f)\left)\right)+{lim}_{\delta \to 0}(-L\ln \left(\frac{1+|X|\frac{\delta }{1-|X|\delta }}{1+\frac{\delta }{1-|X|\delta }}\right))$

$=-{sup}_f\left(dh\right(1;-f\left)\right)+(-L\ln \left(\frac{1+|X|\frac{0}{1-|X|0}}{1+\frac{0}{1-|X|0}}\right))$

$=-{sup}_f\left(dh\right(1;-f\left)\right)+(-L\ln \left(\frac{1}{1}\right))$

$=-{sup}_f\left(dh\right(1;-f\left)\right)$

Ah good, we get the same bound. Therefore, since we can narrow our window width to 0 with decreasing $\delta$, and regardless of $\delta$, the limit points of our original sequence of interest are in the window,

${lim}_{ϵ\to 0}\frac{1+ϵ}{-ϵ}\ln \left({sup}_q\right(h\left(q^{\frac{ϵ}{1+ϵ}}\right)\left)\right)=-{sup}_f\left(dh\right(1;-f\left)\right)=-{sup}_q\left(dh\right(1;\ln \left(q\right)\left)\right)$

Where the supremum is taken over $f$ that are in $[0,\infty {)}^{|X|}$ and ${\sum }_i{e}^{-f_i}=1$, or $q\in [0,1{]}^{|X|}$ and ${\sum }_i{q}_i=1$, related by $f=-\ln \left(q\right)$. We're finally done!

 

Proposition 53: For cohomogenous infradistributions,

$H\left(h\right)=-{sup}_{q}dh(1;\ln (q\left)\right)={inf}_q({sup}_{(\lambda \mu ,b)\in H^{min}}\lambda \cdot H(\mu ,q\left)\right)={sup}_{(\lambda \mu ,b)\in H^{min}:\lambda +b=1}\lambda \cdot H\left(\mu \right)$

 

So, we already know from Theorem 4 that

$H\left(h\right)=-{sup}_{q}dh(1;\ln (q\left)\right)$

So that just leaves the last inequality to show.

$-{sup}_{q}dh(1;\ln (q\left)\right)=-{sup}_q\left({lim}_{ϵ\to 0}\frac{h(1+ϵ\ln (q\left)\right)-h\left(1\right)}{ϵ}\right)$

$=-{sup}_q\left({lim}_{ϵ\to 0}\frac{h(1+ϵ\ln (q\left)\right)-1}{ϵ}\right)$

$=-{sup}_q\left({lim}_{ϵ\to 0}\frac{{inf}_{(\lambda \mu ,b)\in H^{min}}\left(\lambda \mu \right(1+ϵ\ln \left(q\right))+b)-1}{ϵ}\right)$

$=-{sup}_q\left({lim}_{ϵ\to 0}\frac{{inf}_{(\lambda \mu ,b)\in H^{min}}(\lambda +ϵ\lambda \mu (\ln \left(q\right))+b)-1}{ϵ}\right)$

And because the infradistribution is cohomogenous, $\lambda +b$ always equals 1, so we have

$=-{sup}_q\left({lim}_{ϵ\to 0}\frac{ϵ{inf}_{(\lambda \mu ,b)\in H^{min}}\lambda \mu \left(\ln \right(q\left)\right)}{ϵ}\right)$

$=-{sup}_q\left({inf}_{(\lambda \mu ,b)\in H^{min}}\lambda \mu \right(\ln \left(q\right)\left)\right)={inf}_q({sup}_{(\lambda \mu ,b)\in H^{min}}\lambda \cdot (-\mu \left(\ln \right(q\left)\right)\left)\right)$

$={inf}_q\left({sup}_{(\lambda \mu ,b)\in H^{min}}(\lambda \cdot (-{\sum }_i{\mu }_i\cdot \ln (q_i\left)\right))\right)$

$={inf}_q({sup}_{(\lambda \mu ,b)\in H^{min}}\lambda \cdot H(\mu ,q\left)\right)$

And we're done. Well, not quite, we still need that alternate characterization of the form:

${sup}_{(\lambda \mu ,b)\in H^{min}:\lambda +b=1}\lambda \cdot H\left(\mu \right)$

The way that this shakes out is that we'll be using Sion's minimax theorem on the characterization of Entropy as:

${inf}_q({sup}_{(\lambda \mu ,b)\in H^{min}}\lambda \cdot H(\mu ,q\left)\right)$

In order to invoke Sion's minimax theorem to swap the order of the inf and the sup, we have four things to check. $q\in \Delta X$ so we need to check that $\Delta X$ is a compact convex subset of a vector space. Yes, this is the case because $X$ only has finitely many points in it, that's one down, it's just a subset of $R^n$. Also, $(\lambda \mu ,b)\in H^{min}$, so we need to check that $H^{min}$ is a convex subset of a topological vector space. Convexity comes from convexity of infradistributions, and the minimal points of $H$ (due to cohomogenity being exactly those with $\lambda +b=1$) must form a convex set, because you can't decrease the $b$ value any more and stay in $H$, and the space of signed measures over $X$, as well as the $b$ term, is embedded in $R^n$ (for suitably large $n$).

That just leaves two things. We need to check that for all $q$,

$(\lambda \mu ,b)\mapsto \lambda H(\mu ,q)$

is continuous and concave (we'll actually show it's linear), and we need to check that for all $(\lambda \mu ,b)$, the function

$q\mapsto \lambda H(\mu ,q)$

is continuous and convex.

Continuity for both of these is obvious, because the cross-entropy is a continuous function. That leaves showing linearity for the first function, and convexity for the second one.

Use $\varphi$ for your function $(\lambda \mu ,b)\mapsto \lambda H(\mu ,q)$

It can be unpacked a bit more as:

$\varphi (\lambda \mu ,b)=-\lambda {\sum }_i{\mu }_i\ln \left(q_i\right)$

Then we can go:

$\varphi \left(p\right(\lambda \mu ,b)+(1-p\left)\right({\lambda }^{\prime }{\mu }^{\prime },b^{\prime }\left)\right)$

$=\varphi \left(\right(p\lambda +(1-p){\lambda }^{\prime })(\frac{p\lambda }{p\lambda +(1-p){\lambda }^{\prime }}\mu +\frac{(1-p){\lambda }^{\prime }}{p\lambda +(1-p){\lambda }^{\prime }}{\mu }^{\prime })+(pb+(1-p)b^{\prime }\left)\right)$

$=-(p\lambda +(1-p\left){\lambda }^{\prime }\right){\sum }_i(\frac{p\lambda }{p\lambda +(1-p){\lambda }^{\prime }}{\mu }_i+\frac{(1-p){\lambda }^{\prime }}{p\lambda +(1-p){\lambda }^{\prime }}{\mu }_i^{\prime })\ln \left(q_i\right)$

$=-{\sum }_i(p\lambda {\mu }_i+(1-p\left){\lambda }^{\prime }{\mu }_i^{\prime }\right)\ln \left(q_i\right)$

$=p(-\lambda {\sum }_i{\mu }_i\ln (q_i\left)\right)+(1-p)(-{\lambda }^{\prime }{\sum }_i{\mu }_i^{\prime }\ln (q_i\left)\right)$

$=p\varphi (\lambda \mu ,b)+(1-p)\varphi ({\lambda }^{\prime }{\mu }^{\prime },b^{\prime })$

And we're done with linearity there, linear functions are concave. Time for the next one.

Use $\psi$ for your function $q\mapsto \lambda H(\mu ,q)$

It can be unpacked a bit more as:

$\psi \left(q\right)=-\lambda {\sum }_i{\mu }_i\ln \left(q_i\right)$

Now, we can go:

$\psi (pq+(1-p\left)q^{\prime }\right)=-\lambda {\sum }_i{\mu }_i\ln (p{q}_i+(1-p\left)q_i^{\prime }\right)$

Now, $\ln$ is a concave function, not a convex one. However, the negative sign flips it around to be convex, so we have:

$\le -\lambda {\sum }_i{\mu }_i\left(p\ln \right(q_i)+(1-p\left)\ln \right(q_i^{\prime }\left)\right)$

$=p(-\lambda {\sum }_i{\mu }_i\ln (q_i\left)\right)+(1-p)(-\lambda {\sum }_i{\mu }_i^{\prime }\ln (q_i^{\prime }\left)\right)$

$=p\psi \left(q\right)+(1-p)\psi \left(q^{\prime }\right)$

So it's convex. We can now invoke Sion's minimax theorem and go:

${inf}_q({sup}_{(\lambda \mu ,b)\in H^{min}}\lambda \cdot H(\mu ,q\left)\right)$

$={sup}_{(\lambda \mu ,b)\in H^{min}}({inf}_q\lambda \cdot H(\mu ,q\left)\right)$

And cross-entropy is minimized when $q=\mu$, and equals the entropy of $\mu$ so we have:

$={sup}_{(\lambda \mu ,b)\in H^{min}}\lambda \cdot H\left(\mu \right)$

And that's the last bit we have for this.

 

Proposition 54: For all infradistributions, $0\le H\left(h\right)\le \ln \left(|X|\right)$, entropy is upper bounded by the logarithm of the number of states.

Looking back at the proof of Proposition 50, we can see that regardless of infradistribution, it holds up to here

$H\left(h\right)=-{sup}_q\left({lim}_{ϵ\to 0}\frac{{inf}_{(\lambda \mu ,b)\in H^{min}}(\lambda +ϵ\lambda \mu (\ln \left(q\right))+b)-1}{ϵ}\right)$

And note that, in an infradistribution, $\lambda +b\ge 1$ always for minimal points, but the inf enforces that $\lambda +b=1$ by taking the $ϵ\to 0$ limit, so the entropy for general infradistributions can be reexpressed as:

$=-{sup}_q\left({lim}_{ϵ\to 0}\frac{{inf}_{(\lambda \mu ,b)\in H^{min}:\lambda +b=1}(\lambda +ϵ\lambda \mu (\ln \left(q\right))+b)-1}{ϵ}\right)$

And going through the proof of Proposition 50 again, the final more general formulation of entropy we get for arbitrary infradistributions is:

${inf}_q({sup}_{(\lambda \mu ,b)\in H^{min}:\lambda +b=1}\lambda \cdot H(\mu ,q\left)\right)$

Now, cross-entropy is always non-negative, so that means

$H\left(h\right)\ge 0$

Further, the entropy is bounded above by $\ln \left(|X|\right)$, because, letting $U$ be the uniform distribution,

$H(\mu ,U)=-{\sum }_i{\mu }_i\ln \left(U_i\right)=-{\sum }_i{\mu }_i\ln \left(\frac{1}{|X|}\right)={\sum }_i{\mu }_i\ln \left(|X|\right)=\ln \left(|X|\right)$

Therefore,

$H\left(h\right)={inf}_q({sup}_{(\lambda \mu ,b)\in H^{min}:\lambda +b=1}\lambda \cdot H(\mu ,q\left)\right)$

$\le {sup}_{(\lambda \mu ,b)\in H^{min}:\lambda +b=1}\lambda \cdot H(\mu ,U)$

$={sup}_{(\lambda \mu ,b)\in H^{min}:\lambda +b=1}\lambda \cdot \ln \left(|X|\right)\le \ln \left(|X|\right)$

And we're done.

 

Proposition 55: For all infradistributions, entropy is concave.
$H(ph+(1-p\left)h^{\prime }\right)\ge pH\left(h\right)+(1-p)H\left(h^{\prime }\right)$

$H(ph+(1-p\left)h^{\prime }\right)=-{sup}_{q}d(ph+(1-p\left)h^{\prime }\right)(1;\ln (p\left)\right)$

$=-{sup}_q{lim}_{ϵ\to 0}\frac{(ph+(1-p\left)h^{\prime }\right)(1+ϵ\ln (q\left)\right)-(ph+(1-p\left)h^{\prime }\right)\left(1\right)}{ϵ}$

$=-{sup}_q{lim}_{ϵ\to 0}(p\frac{h(1+ϵ\ln (q\left)\right)-h\left(1\right)}{ϵ}+(1-p\left)\frac{h^{\prime }(1+ϵ\ln (q\left)\right)-h^{\prime }\left(1\right)}{ϵ}\right)$

$=-{sup}_q\left(pdh\right(1;\ln \left(q\right))+(1-p\left)d{h}^{\prime }\right(1;\ln \left(q\right)\left)\right)$

$\ge -{sup}_q\left(pdh\right(1;\ln \left(q\right)\left)\right)-{sup}_q\left(\right(1-p\left)d{h}^{\prime }\right(1;\ln \left(q\right)\left)\right)$

$=p(-{sup}_{q}dh(1;\ln \left(q\right)\left)\right)+(1-p)(-{sup}_{q}d{h}^{\prime }(1;\ln \left(q\right)\left)\right)=pH\left(h\right)+(1-p)H\left(h^{\prime }\right)$

 

Proposition 56: For all infradistributions, entropy doesn't increase after deterministic pushforward. $H\left(g_{\ast }\right(h\left)\right)\le H\left(h\right)$

To begin,

$H\left(h\right)=-{sup}_{q}dh(1;\ln (p\left)\right)=-{sup}_q{lim}_{ϵ\to 0}\frac{h(\lambda x.1+ϵ\ln (q_x\left)\right)-h\left(1\right)}{ϵ}$

$\ge -{sup}_q{lim}_{ϵ\to 0}\frac{h(\lambda x.1+ϵ\ln \left({\sum }_{x^{\prime }:g\left(x^{\prime }\right)=g\left(x\right)}{q}_{x^{\prime }}\right))-h\left(1\right)}{ϵ}$

The reason for that last inequality is that, regardless of $q$ and $x$,

$q_x\le {\sum }_{x^{\prime }:g\left(x^{\prime }\right)=g\left(x\right)}{q}_{x^{\prime }}$

so

$\ln \left(q_x\right)\le \ln \left({\sum }_{x^{\prime }:g\left(x^{\prime }\right)=g\left(x\right)}{q}_{x^{\prime }}\right)$

So, by monotonicity,

$h(\lambda x.1+ϵ\ln (q_x\left)\right)\le h(\lambda x.1+ϵ\ln \left({\sum }_{x^{\prime }:g\left(x^{\prime }\right)=g\left(x\right)}{q}_{x^{\prime }}\right))$

So then, regardless of $ϵ$,

$\frac{h(\lambda x.1+ϵ\ln (q_x\left)\right)-h\left(1\right)}{ϵ}\le \frac{h(\lambda x.1+ϵ\ln \left({\sum }_{x^{\prime }:g\left(x^{\prime }\right)=g\left(x\right)}{q}_{x^{\prime }}\right))-h\left(1\right)}{ϵ}$

so then this property transfers to the limit, and

${lim}_{ϵ\to 0}\frac{h(\lambda x.1+ϵ\ln (q_x\left)\right)-h\left(1\right)}{ϵ}\le {lim}_{ϵ\to 0}\frac{h(\lambda x.1+ϵ\ln \left({\sum }_{x^{\prime }:g\left(x^{\prime }\right)=g\left(x\right)}{q}_{x^{\prime }}\right))-h\left(1\right)}{ϵ}$

and then for the supremum,

${sup}_q{lim}_{ϵ\to 0}\frac{h(\lambda x.1+ϵ\ln (q_x\left)\right)-h\left(1\right)}{ϵ}$

$\le {sup}_q{lim}_{ϵ\to 0}\frac{h(\lambda x.1+ϵ\ln \left({\sum }_{x^{\prime }:g\left(x^{\prime }\right)=g\left(x\right)}{q}_{x^{\prime }}\right))-h\left(1\right)}{ϵ}$

And then multiplying by a negative flips the sign of the inequality. That's where it came from. So, we're currently up to:

$H\left(h\right)\ge -{sup}_q{lim}_{ϵ\to 0}\frac{h(\lambda x.1+ϵ\ln \left({\sum }_{x^{\prime }:g\left(x^{\prime }\right)=g\left(x\right)}{q}_{x^{\prime }}\right))-h\left(1\right)}{ϵ}$

Now, where to go from here? Well... given a $q$ that sums to 1 over all points in $X$, it's basically a probability distribution. We can define a $q^{\prime }$ that's supported over the image of $Y$ as $q^{\prime }=g_{\ast }\left(q\right)$, just the pushforward. Or, more prosaically, $q_{g\left(x\right)}^{\prime }={\sum }_{x^{\prime }:g\left(x^{\prime }\right)=g\left(x\right)}{q}_{x^{\prime }}$. Ah, there's what we were looking for. Also, by normalization, $h\left(1\right)=1$.

$=-{sup}_q{lim}_{ϵ\to 0}\frac{h(\lambda x.1+ϵ\ln (q_{g\left(x\right)}^{\prime }\left)\right)-1}{ϵ}$

Hm. Well, how many $q^{\prime }$ can we hit? Well, $q$ could be any probability distribution over $X$. so, we'd be able to induce any probability distribution as long as it's support is in the image of $g$. So, we can reexpress as:

$=-{sup}_{q^{\prime }:{\sum }_{y\in g\left(X\right)}{q}_y^{\prime }=1}{lim}_{ϵ\to 0}\frac{h(\lambda x.1+ϵ\ln (q_{g\left(x\right)}^{\prime }\left)\right)-1}{ϵ}$

and, by monotonicity, we can take the sup over more stuff since they'll always produce a lesser result.

$=-{sup}_{q^{\prime }:{\sum }_{y\in g\left(X\right)}{q}_y^{\prime }\le 1}{lim}_{ϵ\to 0}\frac{h(\lambda x.1+ϵ\ln (q_{g\left(x\right)}^{\prime }\left)\right)-1}{ϵ}$

Wait a second, these $q^{\prime }$ are only defined on the image of $g$. But the values produced by $h$ only depends on what functions do on the image of $g$. So, we should just be able to extend in an arbitrary way s.t. they still look like probability distributions over $Y$, that doesn't affect the values at all.

$=-{sup}_{q^{\prime }:{\sum }_y{q}_y^{\prime }\le 1}{lim}_{ϵ\to 0}\frac{h(\lambda x.1+ϵ\ln (q_{g\left(x\right)}^{\prime }\left)\right)-1}{ϵ}$

And, again, by monotonicity, we can just restrict back to "must sum up to 1".

$=-{sup}_{q^{\prime }:{\sum }_y{q}_y^{\prime }=1}{lim}_{ϵ\to 0}\frac{h(\lambda x.1+ϵ\ln (q_{g\left(x\right)}^{\prime }\left)\right)-1}{ϵ}$

Alright now, let's abbreviate this as:

$=-{sup}_{q^{\prime }}{lim}_{ϵ\to 0}\frac{h(\lambda x.1+ϵ\ln (q_{g\left(x\right)}^{\prime }\left)\right)-1}{ϵ}$

And then we notice something interesting. This can be viewed as a function that maps an $x$ to a $y$ via $g$, and then maps $y$ to $1+ϵ\ln \left(q_y^{\prime }\right)$. This composition form means we can reexpress it as:

$=-{sup}_{q^{\prime }}{lim}_{ϵ\to 0}\frac{g_{\ast }\left(h\right)(\lambda y.1+ϵ\ln (q_y^{\prime }\left)\right)-1}{ϵ}$

$=-{sup}_{q^{\prime }}{lim}_{ϵ\to 0}\frac{g_{\ast }\left(h\right)(\lambda y.1+ϵ\ln (q_y^{\prime }\left)\right)-g_{\ast }\left(h\right)\left(1\right)}{ϵ}$

$=-{sup}_{q^{\prime }}d\left(g_{\ast }\right(h\left)\right)(1;\ln (q^{\prime }\left)\right)=H\left(g_{\ast }\right(h\left)\right)$

And we're done!

$H\left(h\right)\ge H\left(g_{\ast }\right(h\left)\right)$

 

Proposition 57: For cohomogenous infradistributions, $H(h⋉K)\le H\left(h\right)+{sup}_{(\lambda \mu ,b)\in H^{min}}(\lambda \cdot E_{\mu }[H\left(K\right(x\left)\right)\left]\right)$

First, use our reexpression of what the entropy means for cohomogenous infrdistributions to go:

$H(h⋉K)={inf}_{q\in \Delta (X\times Y)}{sup}_{(\lambda \mu ,b)\in (H⋉K{)}^{min}}\lambda \cdot H(\mu ,q)$

$={inf}_{q\in \Delta (X\times Y)}\left({sup}_{(\lambda \mu ,b)\in (H⋉K{)}^{min}}(-\lambda {\sum }_{x,y}({\mu }_{x,y}\ln \left(q_{x,y}\right)\left)\right)\right)$

Now, from what the semidirect product looks like, the points in the semidirect product (or at least, this nabs all the minimal points) looks like selecting a $(\lambda \mu ,b)$ from $H$, and a selection function s that takes each $x$ and assigns it a minimal point from $K\left(x\right)$. Then just take $\mu ⋉s$ and add on the $b$ term. So, we can rewrite the inf as "pick a $(\lambda \mu ,b)$ from $H^{min}$, then pick a $s\left(x\right)$ from each $K(x{)}^{min}$, which we'll write as $({\lambda }^{s\left(x\right)}{\nu }^{s\left(x\right)},b^{s\left(x\right)})$"

So, the resulting measure (not probability distribution!!) produced by that has the measure on the point $(x,y)$ being:

$\lambda {\mu }_x{\lambda }^{s\left(x\right)}{\nu }_y^{s\left(x\right)}$

And so the total amount of measure present (our analogue of the $\lambda$ term) would be:

${\sum }_{x^{\prime },y^{\prime }}\lambda {\mu }_{x^{\prime }}{\lambda }^{s\left(x^{\prime }\right)}{\nu }_{y^{\prime }}^{s\left(x^{\prime }\right)}$

And the actual probability distribution on the point $(x,y)$, ignoring the $\lambda$ term, would be

$\frac{\lambda {\mu }_x{\lambda }^{s\left(x\right)}{\nu }_y^{s\left(x\right)}}{{\sum }_{x^{\prime },y^{\prime }}\lambda {\mu }_{x^{\prime }}{\lambda }^{s\left(x^{\prime }\right)}{\nu }_{y^{\prime }}^{s\left(x^{\prime }\right)}}$

Thus, we can rewrite our entropy as:

$={inf}_{q\in \Delta (X\times Y)}{sup}_{(\lambda \mu ,b)\in H^{min},({\lambda }^{s\left(x\right)}{\nu }^{s\left(x\right)},b^{s\left(x\right)})\in K(x{)}^{min}}$

$-\left({\sum }_{x^{\prime },y^{\prime }}\lambda {\mu }_{x^{\prime }}{\lambda }^{s\left(x^{\prime }\right)}{\nu }_{y^{\prime }}^{s\left(x^{\prime }\right)}\right)\left({\sum }_{x,y}\left(\frac{\lambda {\mu }_x{\lambda }^{s\left(x\right)}{\nu }_y^{s\left(x\right)}}{{\sum }_{x^{\prime },y^{\prime }}\lambda {\mu }_{x^{\prime }}{\lambda }^{s\left(x^{\prime }\right)}{\nu }_{y^{\prime }}^{s\left(x^{\prime }\right)}}\ln \right(q_{x,y}\left)\right)\right)$

We can cancel out and move the $\lambda$ outside to yield:

$={inf}_{q\in \Delta (X\times Y)}{sup}_{(\lambda \mu ,b)\in H^{min},({\lambda }^{s\left(x\right)}{\nu }^{s\left(x\right)},b^{s\left(x\right)})\in K(x{)}^{min}}-\lambda \left({\sum }_{x,y}\left({\mu }_x{\lambda }^{s\left(x\right)}{\nu }_y^{s\left(x\right)}\ln \right(q_{x,y}\left)\right)\right)$

And now we'll be abusing notation somewhat to economize on space, we'll be writing $(\lambda \mu ,b)\in H^{min}$ as $\left(\lambda \mu \right)\in H$ and writing $({\lambda }^{s\left(x\right)}{\nu }^{s\left(x\right)},b^{s\left(x\right)})\in K(x{)}^{min}$ as $(\lambda \nu {)}^{s\left(x\right)}\in K(x)$. With these space abbreviations, we have:

$={inf}_{q\in \Delta (X\times Y)}\left({sup}_{\left(\lambda \mu \right)\in H,(\lambda \nu {)}^{s\left(x\right)}\in K(x)}(-\lambda \left({\sum }_{x,y}{\mu }_x{\lambda }^{s\left(x\right)}{\nu }_y^{s\left(x\right)}\ln \right(q_{x,y}\left)\right))\right)$

and break up the sum to yield:

$={inf}_{q\in \Delta (X\times Y)}\left({sup}_{\left(\lambda \mu \right)\in H,(\lambda \nu {)}^{s\left(x\right)}\in K(x)}(-\lambda \left({\sum }_x{\mu }_x{\lambda }^{s\left(x\right)}\left({\sum }_y{\nu }_y^{s\left(x\right)}\ln \right(q_{x,y}\left)\right)\right))\right)$

And since $q$ is fixed (from the perspective of the inside), we can go "ah, the optimal $s\left(x\right)$ to pick doesn't depend at all on what $\mu$ or $\lambda$ is, our task is just to make the chunk associated with ${\mu }_x$ as negative as possible to make the negative sum as a whole as large as possible" so we can rewrite as:

$={inf}_{q\in \Delta (X\times Y)}\left({sup}_{\left(\lambda \mu \right)\in H}(-\lambda \left({\sum }_x{\mu }_x{inf}_{(\lambda \nu {)}^{s\left(x\right)}\in K(x)}\left({\lambda }^{s\left(x\right)}\left({\sum }_y{\nu }_y^{s\left(x\right)}\ln \right(q_{x,y}\left)\right)\right)\right))\right)$

And then, we can rewrite $\ln \left(q_{x,y}\right)$ as $\ln \left(\frac{q_{x,y}}{{\sum }_{y^{\prime }}{q}_{x,y^{\prime }}}\right)+\ln \left({\sum }_{y^{\prime }}{q}_{x,y^{\prime }}\right)$ to get:

$={inf}_{q\in \Delta (X\times Y)}\left({sup}_{\left(\lambda \mu \right)\in H}\right(-\lambda \left({\sum }_x{\mu }_x{inf}_{(\lambda \nu {)}^{s\left(x\right)}\in K(x)}\right($

${\lambda }^{s\left(x\right)}\left({\sum }_y{\nu }_y^{s\left(x\right)}(\ln \left(\frac{q_{x,y}}{{\sum }_{y^{\prime }}{q}_{x,y^{\prime }}}\right)+\ln \left({\sum }_{y^{\prime }}{q}_{x,y^{\prime }}\right))\right)\left)\right)\left)\right)$

And now, we can start breaking down the $q$ accordingly. We can select any probability distribution over $X\times Y$, so we could think of our choice of distribution as choosing a distribution $q^{\prime }$ over $X$, and a bunch of conditional distributions $\left(q|x\right)$ over $Y$ for each $x$. With this reexpression, we get:

$={inf}_{q^{\prime }\in \Delta X,\left(q|x\right)\in \Delta Y}\left({sup}_{\left(\lambda \mu \right)\in H}\right(-\lambda \left({\sum }_x{\mu }_x{inf}_{(\lambda \nu {)}^{s\left(x\right)}\in K(x)}\right($

${\lambda }^{s\left(x\right)}\left({\sum }_y{\nu }_y^{s\left(x\right)}\left(\ln \right(\left(q|x{)}_y\right)+\ln \left(q_x^{\prime }\right))\right)\left)\right)\left)\right)$

Now, since ${\nu }^{s\left(x\right)}$ is always a probability distribution and that second ln term is a constant and doesn't depend on $y$, we can pull it out and get:

$={inf}_{q^{\prime }\in \Delta X,\left(q|x\right)\in \Delta Y}\left({sup}_{\left(\lambda \mu \right)\in H}\right(-\lambda \left({\sum }_x{\mu }_x{inf}_{(\lambda \nu {)}^{s\left(x\right)}\in K(x)}\right($

${\lambda }^{s\left(x\right)}{\sum }_y\left({\nu }_y^{s\left(x\right)}\ln \right(\left(q|x{)}_y\right))+{\lambda }^{s\left(x\right)}\ln \left(q_x^{\prime }\right)\left)\right)\left)\right)$

Now we need to be really finicky about that last ln piece. It's negative. Swapping the constant in front of it for a 1 would make the inf chunk more negative, but then there's a negative sign in front, so the sup chunk would get bigger, and so would the inf chunk at the very start. So, we have:

$\le {inf}_{q^{\prime }\in \Delta X,\left(q|x\right)\in \Delta Y}\left({sup}_{\left(\lambda \mu \right)\in H}\right(-\lambda \left({\sum }_x{\mu }_x{inf}_{(\lambda \nu {)}^{s\left(x\right)}\in K(x)}\right($

${\lambda }^{s\left(x\right)}{\sum }_y\left({\nu }_y^{s\left(x\right)}\ln \right(\left(q|x{)}_y\right))+\ln \left(q_x^{\prime }\right)\left)\right)\left)\right)$

And now that there's no dependence on which point was picked from $K(x{)}^{min}$, we can pull it out of the inf to yield:

$={inf}_{q\in \Delta (X\times Y)}\left({sup}_{\left(\lambda \mu \right)\in H}\right(-\lambda ({\sum }_x\left({\mu }_x\ln \right(q_x^{\prime }\left)\right)$

$+{\sum }_x{\mu }_x{inf}_{(\lambda \nu {)}^{s\left(x\right)}\in K(x)}\left({\lambda }^{s\left(x\right)}{\sum }_y{\nu }_y^{s\left(x\right)}\ln \right(\left(q|x{)}_y\right))\left)\right))$

Moving the negative sign inwards,

$={inf}_{q^{\prime }\in \Delta X,\left(q|x\right)\in \Delta Y}\left({sup}_{\left(\lambda \mu \right)\in H}\right(\lambda (-{\sum }_x({\mu }_x\ln \left(q_x^{\prime }\right))$

$-{\sum }_x{\mu }_x{inf}_{(\lambda \nu {)}^{s\left(x\right)}\in K(x)}\left({\lambda }^{s\left(x\right)}{\sum }_y{\nu }_y^{s\left(x\right)}\ln \right(\left(q|x{)}_y\right))\left)\right))$

Moving the negative sign further inwards,

$={inf}_{q^{\prime }\in \Delta X,\left(q|x\right)\in \Delta Y}\left({sup}_{\left(\lambda \mu \right)\in H}\right(\lambda (-{\sum }_x({\mu }_x\ln \left(q_x^{\prime }\right))$

$+{\sum }_x{\mu }_x{sup}_{(\lambda \nu {)}^{s\left(x\right)}\in K(x)}\left({\lambda }^{s\left(x\right)}(-{\sum }_y{\nu }_y^{s\left(x\right)}\ln (\left(q|x{)}_y\right))\right)\left)\right))$

And abbreviating the cross-entropy, we have:

$={inf}_{q^{\prime }\in \Delta X,\left(q|x\right)\in \Delta Y}\left({sup}_{\left(\lambda \mu \right)\in H}\left(\lambda \left(H\right(\mu ,q^{\prime })+{\sum }_x{\mu }_x{sup}_{(\lambda \nu {)}^{s\left(x\right)}\in K(x)}\left({\lambda }^{s\left(x\right)}H\right({\nu }^{s\left(x\right)},\left(q|x\right)\left)\right))\right)\right)$

And now we can go "y'know, we can optimize the conditional probabilities individually when we see an x. Murphy's distribution and my distribution, once a particular x gets locked in, is disconnected from all the other x, so we can move that inf inwards". So, we can reexpress as:

$={inf}_{q^{\prime }\in \Delta X}\left({sup}_{\left(\lambda \mu \right)\in H}\left(\lambda \left(H\right(\mu ,q^{\prime })+{\sum }_x{\mu }_x{inf}_{\left(q|x\right)\in \Delta Y}\left({sup}_{(\lambda \nu {)}^{s\left(x\right)}\in K(x)}\left({\lambda }^{s\left(x\right)}H\right({\nu }^{s\left(x\right)},\left(q|x\right)\left)\right)\right))\right)\right)$

And now we use our form for the entropy of an infradistribution to yield:

$={inf}_{q^{\prime }\in \Delta X}\left({sup}_{\left(\lambda \mu \right)\in H}\left(\lambda \left(H\right(\mu ,q^{\prime })+{\sum }_x{\mu }_{x}H(K\left(x\right)\left)\right)\right)\right)$

$={inf}_{q^{\prime }\in \Delta X}\left({sup}_{\left(\lambda \mu \right)\in H}\left(\lambda H\right(\mu ,q^{\prime })+\lambda E_{\mu }[H\left(K\right(x\left)\right)\left]\right)\right)$

And then, by optimizing both components individually we can get

$\le {inf}_{q^{\prime }\in \Delta X}\left({sup}_{\left(\lambda \mu \right)\in H}\right(\lambda H(\mu ,q^{\prime }))+{sup}_{\left(\lambda \mu \right)\in H}(\lambda E_{\mu }\left[H\right(K\left(x\right)\left)\right]\left)\right)$

$={inf}_{q^{\prime }\in \Delta X}\left({sup}_{\left(\lambda \mu \right)\in H}\lambda H\right(\mu ,q^{\prime }\left)\right)+{sup}_{\left(\lambda \mu \right)\in H}\lambda E_{\mu }\left[H\right(K\left(x\right)\left)\right]$

And then, using our form of entropy for cohomogenous infradistributions, and unpacking a bit, we have

$=H\left(h\right)+{sup}_{(\lambda \mu ,b)\in H^{min}}\lambda E_{\mu }\left[H\right(K\left(x\right)\left)\right]$

Putting it all together, we have:

$H(h⋉K)\le H\left(h\right)+{sup}_{(\lambda \mu ,b)\in H^{min}}\lambda E_{\mu }\left[H\right(K\left(x\right)\left)\right]$

And we're done!

 

Proposition 58: For cohomogenous infradistributions, $H(h_1\times h_2)\le H\left(h_1\right)+H\left(h_2\right)$, with equality when the infradistributions are crisp.

By Proposition 57,

$H(h⋉K)\le H\left(h\right)+{sup}_{(\lambda \mu ,b)\in H^{min}}\lambda E_{\mu }\left[H\right(K\left(x\right)\left)\right]$

And then, $h1\times h_2$ is a special case of the semidirect product where $K\left(x\right)$ is always $h_2$, so this turns into:

$H(h_1\times h_2)\le H\left(h_1\right)+{sup}_{(\lambda \mu ,b)\in H_1^{min}}\lambda E_{\mu }\left[H\right(h_2\left)\right]=H\left(h_1\right)+{sup}_{(\lambda \mu ,b)\in H_1^{min}}\lambda H\left(h_2\right)$

And then, because there's points with $\lambda =1$ in a cohomogenous infradistribution, we have:

$H(h_1\times h_2)\le H\left(h_1\right)+H\left(h_2\right)$

This is only part of the proof however, we need to show that we have equality for crisp infradistributions, so we've gotta dig back through the proof of Proposition 57 and show that the two inequalities we have turn into equalities. Looking back through the proof, the first inequality we had was:

$H(h⋉K)={inf}_{q^{\prime }\in \Delta X,\left(q|x\right)\in \Delta Y}\left({sup}_{\left(\lambda \mu \right)\in H}\right(-\lambda \left({\sum }_x{\mu }_x{inf}_{(\lambda \nu {)}^{s\left(x\right)}\in K(x)}\right($

${\lambda }^{s\left(x\right)}{\sum }_y\left({\nu }_y^{s\left(x\right)}\ln \right(\left(q|x{)}_y\right))+{\lambda }^{s\left(x\right)}\ln \left(q_x^{\prime }\right)\left)\right)\left)\right)$

$\le {inf}_{q^{\prime }\in \Delta X,\left(q|x\right)\in \Delta Y}\left({sup}_{\left(\lambda \mu \right)\in H}\right(-\lambda \left({\sum }_x{\mu }_x{inf}_{(\lambda \nu {)}^{s\left(x\right)}\in K(x)}\right($

${\lambda }^{s\left(x\right)}{\sum }_y\left({\nu }_y^{s\left(x\right)}\ln \right(\left(q|x{)}_y\right))+\ln \left(q_x^{\prime }\right)\left)\right)\left)\right)$

There's two critically important things to note. First is that, in the crisp infradistribution case, all minimal points have $\lambda =1$. Second is that, for a direct product, the target we're selecting points from on the second stage is always $H_2$, and there's no dependence on $x$ in that selection. So, reexpressing the part immediately before the inequality, what we have is:

$H(h_1\times h_2)={inf}_{q^{\prime }\in \Delta X,\left(q|x\right)\in \Delta Y}\left({sup}_{\mu \in H_1}(-{\sum }_x{\mu }_x{inf}_{\nu \in H_2}({\sum }_y\left({\nu }_y\ln \right(\left(q|x{)}_y\right))+\ln (q_x^{\prime }\left)\right))\right)$

And then we can move the $\ln \left(q_x^{\prime }\right)$ out to get:

$={inf}_{q^{\prime }\in \Delta X,\left(q|x\right)\in \Delta Y}\left({sup}_{\mu \in H_1}(-{\sum }_x{\mu }_x{inf}_{\nu \in H_2}({\sum }_y\left({\nu }_y^{s\left(x\right)}\ln \right(\left(q|x{)}_y\right))+\ln (q_x^{\prime }\left)\right))\right)$

Which is exactly the reexpression of that second thing that we'd normally have an inequality for. So, the proof of Proposition 57, for crisp infradistributions and the direct product, proceeds with equalities past the first inequality, and stopping right before the second one in the proof of Proposition 57 we had the line:

$={inf}_{q^{\prime }\in \Delta X}\left({sup}_{\left(\lambda \mu \right)\in H}\left(\lambda H\right(\mu ,q^{\prime })+\lambda E_{\mu }[H\left(K\right(x\left)\right)\left]\right)\right)$

Reexpressing the first term for the direct product, and noting that we made it past the first inequality, it would be:

$H(h_1\times h_2)={inf}_{q^{\prime }\in \Delta X}\left({sup}_{\mu \in H_1}\left(H\right(\mu ,q^{\prime })+E_{\mu }[H\left(h_2\right)\left]\right)\right)$

But then, the entropy of $h_2$ is just a constant, so you can pull it out and get:

$={inf}_{q^{\prime }\in \Delta X}\left({sup}_{\mu \in H_1}\left(H\right(\mu ,q^{\prime })+H(h_2\left)\right)\right)$

$={inf}_{q^{\prime }\in \Delta X}\left({sup}_{\mu \in H_1}H\right(\mu ,q^{\prime }\left)\right)+H\left(h_2\right)$

$=H\left(h_1\right)+H\left(h_2\right)$

And we're done, we've shown our result for crisp infradistributions!

0 comments

Comments sorted by top scores.