1
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$ Nov 4, 2021 at 22:59
  • $\begingroup$ @stochasticboy321 Thank you! $\endgroup$
    – Amit Zach
    Nov 5, 2021 at 7:48
  • $\begingroup$ 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. $\endgroup$ Nov 5, 2021 at 16:49

1 Answer 1

2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ 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]$. $\endgroup$ Nov 6, 2021 at 16:02

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .