Entropy & difference between max and min values of probability mass

Question

Let $X$ be a random variable with probability mass function $p(x) = \mathbb{P}[X = x]$. I know entropy $H(X)$ of $X$ measures the uncertainty of $X$ and a large value of $H(X)$ means $p(x)$ is nearly uniform.

To me, it seems to be likely that $D(X) := \max_x p(x) - \min_x p(x)$ can be another measure of uncertainty; small $D(X)$ corresponds to $p(x)$ close to a uniform distribution.

So here is my question. Is there any connection (e.g. inequality) between $H(X)$ and $D(X)$?

I've tried this and that, and all I've got so far is the following:

For simplicity, let $p(x)$ be a Bernoulli distribution $\mathrm{Bin}(1, \theta)\ (\theta \in [0, 1])$: $$p(x) = \begin{cases} \hfill\theta &(x = 1) \\ \hfill1 - \theta &(x = 0)\end{cases}$$ and $\tilde{p}(x)$ be a "flipped" version of $p(x)$: $$\tilde{p}(x) = \begin{cases} \hfill1 - \theta &(x = 1) \\ \hfill\theta &(x = 0).\end{cases}$$

$D(X)$ is related to the $L^1$ (or total variation) divergence between $p$ and $\tilde{p}$ as follows: $$ \lVert p - \tilde{p} \rVert_1 = \lvert \theta - (1 - \theta) \rvert + \lvert (1 - \theta) - \theta \rvert = 2 D(X) . $$ From Pinsker's inequality, we have \begin{align*} D(X)^2 = \, & \frac{1}{4} \lVert p - \tilde{p} \rVert_1^2 \\ \leq \, & \frac{1}{2} \mathrm{KL}(p||\tilde{p}) \\ = \, & \frac{1}{2} \left( \theta \log \left( \frac{\theta}{1 - \theta} \right) + (1 - \theta) \log \left( \frac{1 - \theta}{\theta} \right) \right) \\ = \, & \frac{1}{2} \left\{ \left( \theta \log \theta + (1 - \theta) \log (1 - \theta) \right) - \left( \theta \log (1 - \theta) + (1 - \theta) \log \theta \right)\right\} \\ = \, & \frac{1}{2} \left\{ \left( \theta \log \theta + (1 - \theta) \log (1 - \theta) \right) + \left( (1 - \theta) \log (1 - \theta) + \theta \log \theta \right) - \left( \log (1 - \theta) + \log \theta \right) \right\} \\ = \, & \frac{1}{2} \left\{ -2 H(X) - \left( \log (1 - \theta) + \log \theta \right) \right\} \\ = \, & - H(X) - \frac{1}{2} \log \theta(1 - \theta). \end{align*}

This indeed represents the relationship between $H(X)$ and $D(X)$ (i.e. large $H(X)$ = small $D(X)$). However, it has several limitations:

• It is limited to cases where $X$ is a binary variable.
• I don't like the extra term $\log \theta(1 - \theta)$.

Does anyone have a more general & interpretable relationship between $H(X)$ and $D(X)$ (or some other measures similar to $D(X)$)?

Answer 1

As we are interested in cases when the "probability mass function [...] $p(x)$ is nearly uniform'' and we have $\min_x p(x)$ mentioned, it is reasonable to assume that the random variable $X$ takes only finitely many, say $k$, distinct values. Without loss of generality, these values are $1,\dots,k$ and \begin{equation*} p_1\ge\cdots\ge p_k\ge0, \tag{1}\label{1} \end{equation*} where $p_j:=p(j)$, so that \begin{equation*} d:=D(X)=p_1-p_k\in[0,1] \tag{2}\label{2} \end{equation*} and \begin{equation*} H:=H(X)=\sum_{j=1}^k h(p_j), \end{equation*} where \begin{equation*} h(p):=p\ln\frac1p \end{equation*} for $p\in(0,1]$, with $h(0):=0$.

The case $k=1$ is trivial, because then there is only one pmf. The case $k=2$ is also trivial, because then there is only one pmf with property \eqref{1} and with a given value of $D(X)$.

So, consider the case $k\ge3$. Then, by the concavity of $h$, \begin{equation*} \begin{aligned} H&\le h(p_1)+h(p_k)+(k-2)h\Big(\frac{1-p_1-p_k}{k-2}\Big) \\ &=H^+(p):=H^+(k,d,p):=h(p+d)+h(p)+(k-2)h\Big(\frac{1-2p-d}{k-2}\Big), \end{aligned} \end{equation*} where $p:=p_k$. Letting $u_+:=\max(0,u)$ for real $u$, it is easy to see that conditions \eqref{1} and \eqref{2} imply \begin{equation*} p\in I_{k,d}:=\Big[\frac{(1-(k-1)d)_+}k,\frac{1-d}k\Big], \end{equation*} and the bounds $\frac{(1-(k-1)d)_+}k$ and $\frac{1-d}k$ on $p$ are the best possible.

Note that $H^+(p)$ is strictly concave in $p$, and the equation $(H^+)'(p)=0$ can be rewritten as the quadratic equation \begin{equation*} (p+d)p=\Big(\frac{1-2p-d}{k-2}\Big)^2 \tag{3}\label{3} \end{equation*} for $p$. Moreover, by the strictly concavity of $H^+(p)$ in $p$, there is exactly one root of the quadratic equation \eqref{3} in the interval $I_{k,d}$. This root has different expressions depending on whether $k=3$, $k=4$, or $k\ge5$.

Consider the case $k\ge5$. Then the root of the quadratic equation \eqref{3} in the interval $I_{k,d}$ is \begin{equation*} \begin{aligned} &p_{k,d}:=\frac{-d k^2+4 d k-4}{2 (k-4) k} \\ &+\frac{1}{2} \sqrt{\frac{d^2 k^4-8 d^2 k^3+20 d^2 k^2-16 d^2 k+4 k^2-16 k+16}{(k-4)^2 k^2}} \end{aligned} \end{equation*} and hence \begin{equation*} H\le H^{++}(k,d):=H^+(k,d,p_{k,d}). \end{equation*} So, $H^{++}(k,d)$ is the exact upper bound on the entropy $H=H(X)$ in terms of $k$ and $d=D(X)$.

One has $p_{k,d}=\frac1k - \frac d2 + \frac{k-2}8\, d^2+O(d^4)$ and hence \begin{equation*} H^{++}(k,d)=\ln k-\frac{kd^2}4+O(d^4) \end{equation*} as $d\downarrow0$. So, if the difference $d=D(X)$ between the largest and smallest values of the pmf of $X$ is small, then $H(X)$ differs from the generally largest possible value $\ln k$ of the entropy by at least $\sim\frac{kd^2}4$.

(If $k\in\{3,4\}$, the expressions for the root of the quadratic equation are simpler.)

---

It is even easier to show that the best lower bound on the entropy $H=H(X)$ in terms of $k$ and $d=D(X)$ for $k\ge3$ is given by \begin{equation*} H\ge H^{--}(k,d):=(1-d) \ln\frac k{1-d}=\ln k-\Big(\ln\frac ke\Big)\,d-O_{d\downarrow0}(d^2). \end{equation*} So, if the difference $d=D(X)$ between the largest and smallest values of the pmf of $X$ is small, then $H(X)$ differs from the generally largest possible value $\ln k$ of the entropy by at most $\sim(\ln\frac ke)\,d$.

---

Here are the graphs $\{(d,H^{--}(k,d)-\ln k)\colon0<d<1\} =\{(d,H^{--}(k,d)-H^{--}(k,0))\colon0<d<1\}$ (blue) and $\{(d,H^{++}(k,d)-\ln k)\colon0<d<1\} =\{(d,H^{++}(k,d)-H^{++}(k,0))\colon0<d<1\}$ (golden) for $k=5$ (left) and $k=10$ (right):

Answer 2

In general, $D(X)$ will not convey much information about $H(X)$. Let $0<\varepsilon\ll1$ and consider two cases.

In case A, $X$ is Bernoulli with parameter $p$, with $p=1-\varepsilon\approx1$. Then $D(X)=1-2\varepsilon\approx1$ and $H(X)= -p\log p-\varepsilon\log\varepsilon\approx-\varepsilon\log\varepsilon$, the latter approaching $0$ as $\varepsilon\to0$.

In case B, the distribution of $X$ has 1 "heavy" mass of weight $1-\varepsilon$ and $d$ "light" masses of weight $\varepsilon/d$ each. As in case A, we have $D(X)=1-2\varepsilon\approx 1$. However, $$ H(X)= -(1-\varepsilon)\log(1-\varepsilon)-\varepsilon\log\frac{d}\varepsilon \approx-\varepsilon\log\frac{d}\varepsilon. $$ Choosing $d$ large enough -- say, $d=\exp(1/\varepsilon^2)$ -- will make $H(X)$ arbitrarily large.

So in both cases you have $D(X)\approx1$, while $H(X)$ can be either arbitrarily small or arbitrarily large. This should dash any hopes of obtaining (in general) any estimate on $H(X)$ in terms of $D(X)$.