# Upper and Lower Bounds of Joint Entropy

Let $$\mathbf{p}=(p_1,p_2,...,p_n)$$ be a probability distribution, and let $$0\leq m be a given natural number. Define for every probability distribution $$\mathbf{x}\in[0,1]^N$$ the Joint Entropy:

$$H(\mathbf{x})\equiv-\sum_{k=1}^{N}x_k \log(x_k)$$

Also, define:

$$q_m\equiv1-\sum_{k=1}^{m}p_k\qquad \mathbf{q}\equiv (p_1,p_2,...,p_m,q_m)$$

Prove:

$$0\leq H(\mathbf{p})-H(\mathbf{q})\leq q_m\log(n-m)$$

And check when equality holds.

I was able to prove the lower bound ($$0$$) using the monotonicity of the logarithm, but I'm not sure when equality holds: I know it would hold if $$m=n-1$$, or if $$p_k=1$$ for some $$k\in[m+1,n]_\mathbb{N}$$. But I'm not sure these are the only cases. As for the upper bound - I'm not so sure what to do. I felt like Jensen's inequality could help, so I tried to do this trick when you define a random variable $$X$$ with one of the probability distributions $$\mathbf{p}$$ or $$\mathbf{q}$$ (and then the sum magically turns into an expected value), but it didn't work out eventually. (BTW - If Jensen's inequality were to work, then I'd also know when equality holds, as for the upper bound).

Thanks!

• This indeed follows from Jensen's, in particular using the concavity of $\log$. Start out by noting that $H(p) - H(q) = \sum_{k = m+1}^n p_k \log \frac{q_m}{p_k} = q_m \sum_{k = m+1}^n \frac{p_k}{q_m} \log \frac{q_m}{p_k}.$ Do you spot a distribution here? Does the sum remind you of something? Nov 4, 2021 at 22:59
• @stochasticboy321 Thank you! Nov 5, 2021 at 7:48
• You're welcome. If you think you've got it, please write an answer (and accept it) - this can serve as reference for someone that might have a similar question later. Nov 5, 2021 at 16:49

The upper bound is a direct consequence of the log-sum inequality (which is a consequence of Jensen's inequality)

Let $$t$$ be the number of striclty positive elements in $$(p_{m+1},p_{m+2},\cdots p_{n})$$ ; $$t\le n-m$$, with equality if all are positive.

The following sums are assumed to run over these $$t$$ positive elements.

Letting $$q_m=Q= \sum p_i$$ we have

\begin{align} H(\mathbf{q})-H(\mathbf{p}) &= \sum p_i \log p_i -Q \log Q \\ &=\sum p_i \log \frac{p_i}{Q} \\ & \ge Q \log \frac{Q}{t Q } \\ &= - Q \log(t) \\ & \ge - Q \log(n-m) \end{align}

Multiplying by $$-1$$ you get the upper bound.

We can use the same inequality for the lower bound:

\begin{align} H(\mathbf{p}) -H(\mathbf{q}) &=\sum p_i \log \frac{1}{p_i} +Q \log Q \\ &\ge (\sum p_i) \log(\frac{(\sum 1)}{(\sum p_i)})+Q \log Q \\ &= Q \log(t) \\ &\ge 0 \end{align} =

with equality iif $$t=1$$; or, equivalently if $$(p_{m+1},p_{m+2},\cdots p_{n})$$ has a single (or none) positive term.

• There's a slightly more operational way to write this - let $X \sim p,$ and $Y = \begin{cases} X & X \in [1:m] \\ * & X \in [m+1:n]\end{cases}.$ Then $Y \sim q,$ and is a deterministic function of $X$, so $H(Y) = I(X;Y) = H(X) - H(X|Y)$ and thus $H(p) - H(q) = H(X|Y)$. But $X$ is determined if $Y \neq *,$ so $H(X|Y) = P(Y = *) H(X|Y = *) \le Q\log(n-m),$ the latter because given $Y = *,$ $X$ is supported on $[m+1:n]$. Nov 6, 2021 at 16:02