8
$\begingroup$

Let $S_{n,k}=\sum_{S\subset[n],|S|=k}\prod_{i\in S} x_i$ be the elementary symmetric polynomial of degree $k$ on $n$ variables. Consider this polynomial as a function, in particular a function on probability distributions on $n$ items. It is not hard to see that this function is maximized at the uniform distribution. I am wondering if there is a "convexity"-based approach to show this. Specifically, is $S_{n,k}$ concave on probability distributions on $n$ items?

$\endgroup$
  • $\begingroup$ Specifically, if it is concave on probability distributions, then applying this to a uniform convex combination of a probability distribution and its rotations would yield the above maximization at the uniform distributions. $\endgroup$ – miforbes Jul 9 '13 at 12:50
6
$\begingroup$

(I know this question is ancient, but I happened to run into it while looking for something else.)

While I am not sure if $S_{n,k}$ is concave on the probability simplex, you can prove the result you want and many other similar useful things using Schur concavity. A sketch follows.

A vector $y\in \mathbb{R}_+^n$ majorizes $x \in \mathbb{R}_+^n$ if the following inequalities are satisfied:

$$ \sum_{j=1}^i{x_{(j)}} \leq \sum_{j=1}^i{y_{(j)}} $$ for all $i$, and $\sum_{i=1}^n x_i = \sum_{i=1}^n y_i$. Here $x_{(j)}$ is the $j$-th largest coordinate of $x$ and similarly for $y$. Let's write this $x \prec y$. For intuition it's useful to know that $x \prec y$ if and only if $x$ is in the convex hull of vectors you get by permuting the coordinates of $y$.

A function is Schur-concave if $x \prec y \implies f(x) \geq f(y)$. A simple sufficient condition for Schur concavity is that $\partial f(x)/\partial x_i \ge \partial f(x)/\partial x_j$ whenever $x_i \le x_j$. It is easy to verify that $S_{n,k}$ satisfies this condition for any $n$,$k$.

Notice that $x=(1/n, \ldots, 1/n)$ is majorized by every vector $y$ in the probability simplex. You can see this for example by noticing that the sum of $i$ random coordinates of $y$ is $i/n$, so surely the sum of the $i$ largest coordinates is at least as much. Equivalently, $x$ is the average of all permutations of $y$. This observation, and the Schur concavity of $S_{n,k}$ imply $S_{n,k}(x) \ge S_{n,k}(y)$.

In fact, $S_{n,k}^{1/k}$ is concave on the positive orthant, and this implies what you want. This is itself a special case of much more powerful results about the concavity of mixed volumes. But the Schur concavity approach is elementary and pretty widely applicable.

$\endgroup$
  • $\begingroup$ Thanks Sasho. My hope was for a slick Jensen-type proof, as is done with maximizing Shannon entropy. At some point since my original question, I did come across Schur-convexity (see "Majorization and the Birthday Inequality" by Clevenson and Watkins, jstor.org/stable/2691301 ). I guess this answer is probably this slickest I'll find (assuming that the proof about $S^{1/k}_{n,k}$ being concave you mention is less easy.) $\endgroup$ – miforbes Jul 4 '15 at 11:10
  • $\begingroup$ I have seen two kinds of proofs that $S_{n,k}^{1/k}$ is concave. Some are elementary (i.e. use little to no heavy machinery) but are long and messy. On the other hand there is a slick proof by Khovanskii math.toronto.edu/askold/1984-Doklady-6-English.pdf of the Alexandrov-Fenchel inequalities for mixed discriminants (and even mixed hyperbolic forms) using hyperbolic polynomials. $\endgroup$ – Sasho Nikolov Jul 4 '15 at 12:22
  • $\begingroup$ To clarify my comment above: $S_{n,k}$ is a special case of a mixed discriminant, and Alexandrov-Fenchel is equivalent to a concavity property of mixed discriminants that implies the concavity of $S_{n,k}^{1/k}$. Alexandrov-Fenchel for hyperbolic forms is vastly more general than concavity of $S_{n,k}$, but Khovanskii's proof is the only one I have seen that doesn't involve long tedious calculations. Here is one of the elementary proofs I have found: cms.math.ca/cjm/a144993. BTW, cute article about the birthday paradox! $\endgroup$ – Sasho Nikolov Jul 4 '15 at 14:44
  • $\begingroup$ Thanks! I'll take a look. (Indeed, the birthday paradox was what got into this.) $\endgroup$ – miforbes Jul 5 '15 at 19:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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