5
$\begingroup$

Let $$ p = (p_1, \ldots, p_n) $$ be a finite probability distribution, which for convenience I'll assume to have no zeroes: thus, $p_i > 0$ for all $i$ and $\sum_i p_i = 1$.

Is the function $$ q \mapsto \biggl( \sum_{i = 1}^n p_i^q \biggr)^{1/(1 - q)} $$ ($q \geq 0$) necessarily convex?

Now let me give some context.

For each $t \in \mathbb{R}$ and $x = (x_1, \ldots, x_n) \in (0, \infty)^n$, we can form the power mean of $x_1, \ldots, x_n$, weighted by $p_1, \ldots, p_n$, of order $t$. When $t \neq 0$, this is defined by $$ M_t(p, x) = \biggl( \sum_{i = 1}^n p_i x_i^t \biggr)^{1/t}. $$ We define $M_0(p, x) = \lim_{t \to 0} M_t(p, x)$, which works out to be $$ M_0(p, x) = \prod_{i = 1}^n x_i^{p_i}. $$

It's a well-known classical fact that $M_t(p, x)$ is increasing in $t$, for fixed $p$ and $x$. (I mean "increasing" non-strictly; e.g. it's constant in $t$ if $x_1 = \cdots = x_n$.) For instance, the fact that $M_0(p, x) \leq M_1(p, x)$ is the famous theorem that the geometric mean is less than or equal to the arithmetic mean. My question is, in some sense, at one level higher.

For reasons that probably aren't relevant here, I've seen plots of the function $$ t \mapsto 1/M_t(p, p) \qquad (t \geq -1) $$ for many different distributions $p$. The fact above tells us that the graph is always decreasing. But in every case I've seen, it has also looked as if it's convex. Write $q = t + 1$ ($q \geq 0$), so that $$ 1/M_t(p, p) = \begin{cases} \Bigl( \sum p_i^q \Bigr)^{1/(1 - q)} &\text{if } q \neq 1 \\ \prod p_i^{-p_i} &\text{if } q = 1. \end{cases} $$ Then in every case I've seen, the graph has looked something like this:

Graph of reciprocal power means
(source: ed.ac.uk)

Notes:

  1. For $q \geq 0$, write $f(q) = \bigl( \sum p_i^q \bigr)^{1/(1 - q)}$. We know that $f \geq 0$ and $f' \leq 0$. I'm asking whether $f'' \geq 0$. If that's true, a natural conjecture is that $(-1)^k f^{(k)} \geq 0$ for all $k$: that is, $f$ is completely monotone. A theorem of Bernstein states that $f$ is completely monotone if and only if it's the Laplace transform of some finite measure on $[0, \infty)$.

  2. For an arbitrary $x \in (0, \infty)^n$, it's not necessarily true that $t \mapsto 1/M_t(p, x)$ is convex in the region $t \geq -1$. There are counterexamples.

  3. The quantity $\bigl( \sum p_i^q \bigr)^{1/(1 - q)}$ is the exponential of the Rényi entropy of $p$ of order $q$. That's why I've given this an "information theory" tag.

$\endgroup$
1
  • 3
    $\begingroup$ Some tests with extreme cases seem to indicate that the answer may be negative. The small negative part of the second derivative of the function for $n=3$ and values $p = [0.25\ 0.25\ 0.5]$ (see here) does not look like a numerical artifact. Other values that give suspicious results are tuples with a small number of entries (but more that two) that are close to the uniform distribution. $\endgroup$
    – Dirk
    Jul 21, 2014 at 13:28

1 Answer 1

7
$\begingroup$

To expand on Dirk's example: for $n=3$ and $p = [1/4, 1/4, 1/2]$ we have $$ f''(0) = 3\, \left( \ln \left( 3 \right) \right) ^{2}+6\,\ln \left( 3 \right) -10\,\ln \left( 2 \right) \ln \left( 3 \right) +9\, \left( \ln \left( 2 \right) \right) ^{2}-10\,\ln \left( 2 \right) < 0$$.

Added by Tom Leinster As a check, and to insure against any error in computing the 2nd derivative, I computed this: $$ \frac{1}{2}\bigl( f(0) + f(0.6) \bigr) - f(0.3) = -0.00018332\ldots < 0, $$ again proving non-convexity. (I chose $0.6$ because that's roughly the value that illustrates the non-convexity most vividly. But even so, notice how close to zero this is.)

$\endgroup$
5
  • 1
    $\begingroup$ Good! It still puzzles me, why the quantity is convex in almost every case. I would still believe if somebody told me that convexity is true for large $n$… $\endgroup$
    – Dirk
    Jul 21, 2014 at 18:45
  • $\begingroup$ Thanks very much, Dirk and Robert. I agree with Dirk: it's still a puzzle as to why it's so nearly true. E.g. in this particular example, the non-convexity is extremely subtle - I just plotted the graph and couldn't detect it by eye. $\endgroup$ Jul 21, 2014 at 19:05
  • 2
    $\begingroup$ You can get a counterexample for arbitrary $n$ by perturbing this slightly ($p = [1/4, 1/4, 1/2 - (n-3) \epsilon, \epsilon, \ldots, \epsilon]$). $\endgroup$ Jul 21, 2014 at 19:05
  • $\begingroup$ Ok, my believe is destroyed… Another interesting question could be. What are $n$ and $p$ such that the respective function has most negative value in its second derivative? $\endgroup$
    – Dirk
    Jul 21, 2014 at 20:32
  • 2
    $\begingroup$ If you take a large $N$, say $100$, and $n=N-1$ with $p=[1/N,1/N,\dots,1/N,2/N]$ then you get something that looks very non-convex. $\endgroup$ Jul 21, 2014 at 21:57

Your Answer

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

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