Why is Entropy maximised when the probability distribution is uniform?

Question

I know that entropy is the measure of randomness of a process/variable and it can be defined as follows. for a random variable $X \in$ set $A$ :- $H(X)= \sum_{x_i \in A} -p(x_i) \log (p(x_i)) $. In the book on Entropy and Information Theory by MacKay, he provides this statement in Ch2

Entropy is maximized if p is uniform.

Intuitively, I am able to understand it, like if all datapoints in set $A$ are picked with equal probability $1/m$ ($m$ being cardinality of set $A$), then the randomness or the entropy increases. But if we know that some points in set $A$ are going to occur with more probability than others (say in the case of normal distribution, where the maximum concentration of data points is around the mean and small standard deviation area around it, then the randomness or entropy should decrease.

But is there any mathematical proof for this ? Like the equation for $H(X)$ I differentiate it with respect to $p(x)$ and set it to 0 or something like that.

On a side note, is there any connnection between the entropy that occurs information theory and the entropy calculations in chemistry (thermodynamics) ?

Answer 1

Heuristically, the probability density function on $\{x_1, x_2,..,.x_n\}$ with maximum entropy turns out to be the one that corresponds to the least amount of knowledge of $\{x_1, x_2,..,.x_n\}$, in other words the Uniform distribution.

Now, for a more formal proof consider the following:

A probability density function on $\{x_1, x_2,..,.x_n\}$ is a set of nonnegative real numbers $p_1,...,p_n$ that add up to 1. Entropy is a continuous function of the $n$-tuples $(p_1,...,p_n)$, and these points lie in a compact subset of $\mathbb{R}^n$, so there is an $n$-tuple where entropy is maximized. We want to show this occurs at $(1/n,...,1/n)$ and nowhere else.

Suppose the $p_j$ are not all equal, say $p_1 < p_2$. (Clearly $n\neq 1$.) We will find a new probability density with higher entropy. It then follows, since entropy is maximized at some $n$-tuple, that entropy is uniquely maximized at the $n$-tuple with $p_i = 1/n$ for all $i$.

Since $p_1 < p_2$, for small positive $\varepsilon$ we have $p_1 + \varepsilon < p_2 -\varepsilon$. The entropy of $\{p_1 + \varepsilon, p_2 -\varepsilon,p_3,...,p_n\}$ minus the entropy of $\{p_1,p_2,p_3,...,p_n\}$ equals

$$-p_1\log\left(\frac{p_1+\varepsilon}{p_1}\right)-\varepsilon\log(p_1+\varepsilon)-p_2\log\left(\frac{p_2-\varepsilon}{p_2}\right)+\varepsilon\log(p_2-\varepsilon)$$ To complete the proof, we want to show this is positive for small enough $\varepsilon$. Rewrite the above equation as $$-p_1\log\left(1+\frac{\varepsilon}{p_1}\right)-\varepsilon\left(\log p_1+\log\left(1+\frac{\varepsilon}{p_1}\right)\right)-p_2\log\left(1-\frac{\varepsilon}{p_2}\right)+\varepsilon\left(\log p_2+\log\left(1-\frac{\varepsilon}{p_2}\right)\right)$$

Recalling that $\log(1 + x) = x + O(x^2)$ for small $x$, the above equation is $$-\varepsilon-\varepsilon\log p_1 + \varepsilon + \varepsilon \log p_2 + O(\varepsilon^2) = \varepsilon\log(p_2/p_1) + O(\varepsilon^2)$$ which is positive when $\varepsilon$ is small enough since $p_1 < p_2$.

A less rigorous proof is the following:

Consider first the following Lemma:

Let $p(x)$ and $q(x)$ be continuous probability density functions on an interval $I$ in the real numbers, with $p\geq 0$ and $q > 0$ on $I$. We have $$-\int_I p\log p dx\leq -\int_I p\log q dx$$ if both integrals exist. Moreover, there is equality if and only if $p(x) = q(x)$ for all $x$.

Now, let $p$ be any probability density function on $\{x_1,...,x_n\}$, with $p_i = p(x_i)$. Letting $q_i = 1/n$ for all $i$, $$-\sum_{i=1}^n p_i\log q_i = \sum_{i=1}^n p_i \log n=\log n$$ which is the entropy of $q$. Therefore our Lemma says $h(p)\leq h(q)$, with equality if and only if $p$ is uniform.

Also, wikipedia has a brief discussion on this as well: wiki

Answer 2

Entropy in physics and information theory are not unrelated. They're more different than the name suggests, yet there's clearly a link between. The purpose of entropy metric is to measure the amount of information. See my answer with graphs here to show how entropy changes from uniform distribution to a humped one.

The reason why entropy is maximized for a uniform distribution is because it was designed so! Yes, we're constructing a measure for the lack of information so we want to assign its highest value to the least informative distribution.

Example. I asked you "Dude, where's my car?" Your answer is "it's somewhere in USA between Atlantic and Pacific Oceans." This is an example of the uniform distribution. My car could be anywhere in USA. I didn't get much information from this answer.

However, if you told me "I saw your car one hour ago on Route 66 heading from Washington, DC" - this is not a uniform distribution anymore. The car's more likely to be in 60 miles distance from DC, than anywhere near Los Angeles. There's clearly more information here.

Hence, our measure must have high entropy for the first answer and lower one for the second. The uniform must be least informative distribution, it's basically "I've no idea" answer.

Answer 3

The mathematical argument is based on Jensen inequality for concave functions. That is, if $f(x)$ is a concave function on $[a,b]$ and $y_1, \ldots y_n$ are points in $[a,b]$, then: $n \cdot f(\frac{y_1 + \ldots y_n}{n}) \geq f(y_1) + \ldots + f(y_n)$

Apply this for the concave function $f(x) = -x \log(x)$ and Jensen inequality for $y_i = p(x_i)$ and you have the proof. Note that $p(x_i)$ define a discrete probability distribution, so their sum is 1. What you get is $log(n) \geq \sum_{i=1}^n - p(x_i) log(p(x_i))$, with equality for the uniform distribution.

Answer 4

On a side note, is there any connnection between the entropy that occurs information theory and the entropy calculations in chemistry (thermodynamics) ?

Yes, there is! You can see the work of Jaynes and many others following his work (such as here and here, for instance).

But the main idea is that statistical mechanics (and other fields in science, also) can be viewed as the inference we do about the world.

As a further reading I'd recommend Ariel Caticha's book on this topic.

Answer 5

Main idea: take partial derivative of each $p_i$, set them all to zero, solve the system of linear equations.

Take a finite number of $p_i$ where $i=1,...,n$ for an example. Denote $q = 1-\sum_{i=0}^{n-1} p_i$.

\begin{align} H &= -\sum_{i=0}^{n-1} p_i \log p_i - (1-q)\log q\\ H*\ln 2 &= -\sum_{i=0}^{n-1} p_i \ln p_i - (1-q)\ln q \end{align} \begin{align} \frac{\partial H}{\partial p_i} &= \ln \frac{q}{p_i} = 0 \end{align} Then $q = p_i$ for every $i$, i.e., $p_1=p_2=...=p_n$.

Answer 6

There are already several good answers. Another argument uses the fact that H is a symmetric, strictly concave function. More precisely, consider the unit simplex $\Delta_n=\{(p_1,\dots,p_n): p_i\ge 0,\sum_i p_i=1\}$.Then $H$ may be considered a function $H: \Delta_n\to \mathbb{R}$, and it is easy to show that it is strictly convex.

To explain symmetry, we first introduce some notation. Given a permutation $\sigma: \{1,\dots, n\}\to\{1,\dots,n\}$, and a point $p\in \Delta_n$, define $\sigma p=(p_{\sigma(1)},\dots, p_{\sigma(n)})$. It is clear that $H(\sigma p)=H(p)$ for any $\sigma$ and p, and this is what it means to say that H is a symmetric function.

Now, we can show that the uniform distribution maximizes $H$. Since $H$ is strictly convex, it has a unique maximizer, call it $p_{max}$. On the other hand $H(\sigma p_{max})=H(p_{max})$ for any $\sigma$, so $\sigma p_{max}$ is also a maximizer. Since $p_{max}$ is the only maximizer, we conclude $p_{max}=\sigma p_{max}$ for each $\sigma$, and the only point in $\Delta_n$ with this property is $p_{max}=(1/n,\dots, 1/n)$.

Answer 7

Calculus of Variations

To handle varying functions, we will make use of the Calculus of Variations. The variation $\delta f(x)$ refers to a rate of change of $f(x)$ with respect to "time". That is, $\delta$ works like a partial derivative with respect to "time". For example, $$ \begin{align} \delta(\log(f(x))f(x)) &=\left(\frac1{f(x)}f(x)+\log(f(x))\right)\delta f(x)\\ &=(1+\log(f(x)))\,\delta f(x) \end{align} $$ simply says that the rate of change of $\log(f(x))f(x)$ is $(1+\log(f(x)))$ times the rate of change of $f(x)$.

---

Maximize Entropy

Consider the family of continuous probability distributions $f$ on $[a,b]$; that is, positive $f$ where $$ \int_a^bf(x)\,\mathrm{d}x=1\tag1 $$ Define the entropy of $f$ to be $$ -\int_a^b\log(f(x))f(x)\,\mathrm{d}x\tag2 $$ If we wish to maximize $(2)$ for all distributions satisfying $(1)$, we need to find all $f$ so that $(2)$ is stationary; that is, $\delta$ of the integral in $(2)$ vanishes: $$ -\int_a^b(1+\log(f(x))\,\delta f(x)\,\mathrm{d}x=0\tag3 $$ for all variations, $\delta f$, where $(1)$ is stationary; that is, $\delta$ of the integral in $(1)$ vanishes: $$ \int_a^b\color{#C00}{1}\,\delta f(x)\,\mathrm{d}x=0\tag4 $$ $(3)$, $(4)$, and orthogonality (equations $(3)$ and $(4)$ say that $\color{#C00}{1}$ and $1+\log(f(x))$ are orthogonal to all the same variations; see the link for details) require that there be a $c_0$ so that $$ 1+\log(f(x))=c_0\cdot\color{#C00}{1}\tag5 $$ That is, the desired distribution is constant; that is, $$ \bbox[5px,border:2px solid #C0A000]{f(x)=\frac1{b-a}}\tag6 $$

---

Vanishing Densities

Note that in $(3)$, $-(1+\log(f(x)))\to\infty$ as $f(x)\to0$. This doesn't cause a problem in $(2)$ since $-\log(f(x))f(x)$ is bounded by $\frac1e$. There are a few simple ways to overcome the problem in $(3)$.

1. We can use $\delta f(x)=f(x)\,\delta\log(f(x))$ and use variations of $\log(x)$. Then $(5)$ becomes $$ (1+\log(f(x)))f(x)=c_0f(x) $$ and both sides vanish when $f(x)=0$.

2. We can restrict $f(x)\gt0$ and only consider $f(x)=0$ as a limiting case in the closure.

3. Note that for $f(x)\approx0$, $-(1+\log(f(x)))$ is huge. That means that to maximize $(2)$, any place where $f(x)\approx0$ we want $\delta f(x)$ to be positive, so that $-\int_a^b(1+\log(f(x)))\delta f(x)\,\mathrm{d}x$ increases. That is, no maximizing function will have $f(x)=0$.

Answer 8

An intuitive explanation:

If we put more probability mass into one event of a random variable, we will have to take away some from other events. The one will have less information content and more weight, the others more information content and less weight. Therefore the entropy being the expected information content will go down since the event with lower information content will be weighted more.

As an extreme case imagine one event getting probability of almost one, therefore the other events will have a combined probability of almost zero and the entropy will be very low.