# Entropy & difference between max and min values of probability mass

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)$$)?

• Do you have a response to the answers on this page? Aug 1, 2022 at 14:11

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 (blue) and $$\{(d,H^{++}(k,d)-\ln k)\colon0 (golden) for $$k=5$$ (left) and $$k=10$$ (right): 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)$$.

• It seems to me that the OP is particularly interested in the case when "$p(x)$ is nearly uniform", with "small $D(X)$". The case $D(X)\approx1$ is the opposite of that. When $D(X)$ is indeed small, it is clear (from my answer or otherwise) that $H(X)$ will be close to the entropy $\ln k$ of the uniform distribution on the set $[k]:=\{1,\dots,k\}$, which is the largest possible value of the entropy over all distributions on $[k]$. Jul 31, 2022 at 12:50
• Previous comment continued: So, it should be clear that we can only get reasonable bounds on the entropy if the size $k$ of the set is taken into account. In contrast, in one of your two examples $k=2$ and in the other example $k$ is very large. Is this a fair comparison? Jul 31, 2022 at 12:50
• Yes, you're right. I missed the "nearly uniform" part; my examples are quite the opposite of that. Jul 31, 2022 at 13:58