<![CDATA[An Entropy Challenge]]>

<![CDATA[An Entropy Challenge]]>If you like computer calculations, here’s a little challenge for you. Oscar Dahlsten may have solved it, but we’d love for you to check his work. It’s pretty important for the foundations of thermodynamics, but you don’t need to know any physics or even anything beyond a little algebra to tackle it! First I’ll explain it in really simple terms, then I’ll remind you a bit of why it matters.

We’re looking for two lists of nonnegative numbers, of the same length, listed in decreasing order:

$p_1 \ge p_2 \ge \cdots \ge p_n \ge 0$

$q_1 \ge q_2 \ge \cdots \ge q_n \ge 0$

that sum to 1:

$p_1 + \cdots + p_n = 1$

$q_1 + \cdots + q_n = 1$

and that obey this inequality:

$\displaystyle{ \frac{1}{1 - \beta} \ln \sum_{i=1}^n p_i^\beta \le \frac{1}{1 - \beta} \ln \sum_{i=1}^n q_i^\beta }$

for all $0 < \beta < \infty$ (ignoring $\beta = 1$ ), yet do not obey these inequalities:

$p_1 + \cdots + p_k \ge q_1 + \cdots + q_k$

for all $1 \le k \le n.$

Oscar’s proposed solution is this:

$p = (0.4, 0.29, 0.29, 0.02)$

$q = (0.39, 0.31, 0.2, 0.1)$

Can you see if this works? Is there a simpler example, like one with lists of just 3 numbers?

This question came up near the end of my post More Second Laws of Thermodynamics. I phrased the question with a bit more jargon, and said a lot more about its significance. Suppose we have two probability distributions on a finite set, say $p$ and $q.$ We say $p$ majorizes $q$ if

$p_1 + \cdots + p_k \ge q_1 + \cdots + q_k$

for all $1 \le k \le n,$ when we write both lists of numbers in decreasing order. This means $p$ is ‘less flat’ than $q$ , so it should have less entropy. And indeed it does: not just for ordinary entropy, but also for Rényi entropy! The Rényi entropy of $p$ is defined by

$\displaystyle{ H_\beta(p) = \frac{1}{1 - \beta} \ln \sum_{i=1}^n p_i^\beta }$

where $0 < \beta < 1$ or $1 < \beta < \infty$ . We can also define Rényi entropy for $\beta = 0, 1, \infty$ by taking a limit, and at $\beta = 1$ we get the ordinary entropy

$\displaystyle{ H_1(p) = - \sum_{i = 1}^n p_i \ln (p_i) }$

The question is whether majorization is more powerful than Rényi entropy as a tool to to tell when one probability distribution is less flat than another. I know that if $p$ majorizes $q,$ its Rényi entropy is less than than that of $q$ for all $0 \le \beta \le \infty.$ Your mission, should you choose to accept it, is to show the converse is not true.

]]>