Let $\mathbf{p}=(p_1,p_2,…,p_n)$ be a probability distribution, and let $0\leq m<n$ 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!
Best Answer
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.