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

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

2 Answers 2


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):

enter image description here


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

  • $\begingroup$ 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]$. $\endgroup$ Jul 31, 2022 at 12:50
  • $\begingroup$ 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? $\endgroup$ Jul 31, 2022 at 12:50
  • $\begingroup$ Yes, you're right. I missed the "nearly uniform" part; my examples are quite the opposite of that. $\endgroup$ Jul 31, 2022 at 13:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.