Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

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.

share|improve this question
3  
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. –  Dirk Jul 21 at 13:28

1 Answer 1

up vote 7 down vote accepted

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

share|improve this answer
1  
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$… –  Dirk Jul 21 at 18:45
    
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. –  Tom Leinster Jul 21 at 19:05
2  
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]$). –  Robert Israel Jul 21 at 19:05
    
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? –  Dirk Jul 21 at 20:32
2  
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. –  Simon Willerton Jul 21 at 21:57

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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