4
$\begingroup$

Let $Z$ be a standard normal distribution.

I am trying to find a solution to the following problem: \begin{align} &\max_{ x_1,x_2 \in \mathbb{R}, t\in[0,1]} (1-t) E[|x_1+Z|^m]+t E[|x_2+Z|^m]\\ &\text{ s.t. } (1-t) |x_1|^k+t|x_2|^k=c \end{align} where $0\le m\le k$.

This problem can also be cast as the following problem: \begin{align} &\max_{X} E[|X+Z|^m] \quad (*)\\ &\text{ s.t. } X \text{ has two mass points}, E[|X|^k]=c, X \text{ is indpendent of } Z \end{align}

My conjecture is that the above problem is maximized by a deterministic random variable $X= c^{\frac{1}{k}}$ and \begin{align} \max_{X} E[|X+Z|^m]= E[|c^{\frac{1}{k}}+Z|^m]. \end{align}

While we are restrict $Z$ to be standard normal it would be nice to have a proof that works for all symmetric and absolutely continuous distributions.

I feel like the proof should be using Jensen's inequality but not sure how to use it. The reason is the following. Suppose we remove $Z$ and seek to optimize

\begin{align} &\max_{X} E[|X|^m]\\ &\text{ s.t. } X \text{ has two mass points}, E[|X|^k]=c, X \text{ is indpendent of } Z \end{align} Since, $m \le k$ by Jensen's inequality \begin{align} E[|X|^m] \le ( E[|X|^k] )^{\frac{m}{k}}. \end{align} Note, that Jensen's inequality is equality iff $X$ is a constant. So, the optimization problem $\max_{X} E[|X|^m]$ is solve by deterministic random variable.

Edit 1: It appears that my conjecture is only true in some cases. See a very nice approach of kimchilover.

Edit 2: It also appears that in $(*)$ the $\max$ should be replaced with $\sup$. This was also pointed out by kimchilover.

$\endgroup$
8
  • $\begingroup$ So look at the set of points $\{(x^k, E|Z+x|^m):x\in\mathbb R\}$, or better, its convex hull. $\endgroup$ Jul 24, 2017 at 14:02
  • $\begingroup$ @kimchilover Thank for the hint, but can you give more details. I don't follow at this point. $\endgroup$
    – Boby
    Jul 24, 2017 at 14:25
  • $\begingroup$ So let $H\subset \mathbb R^2$ be that convex hull. Every point in $H$ comes from some putative distribution for $X$. You want to look at the intersection of $H$ with the vertical line $L=\{(c,y):y\in\mathbb R\}.$ In particular, you want the maximal $y$ such that $(c,y)\in L\cap H$. It is an extreme point of $L\cap H$, and, it turns out (by Dubins's theorem), a convex combo of at most $2$ extreme points of $H.$ I have not worked out $H$ so don't know what to expect. $\endgroup$ Jul 24, 2017 at 14:25
  • $\begingroup$ @kimchilover Wow. Thanks for pointing this out. Looks like this question needs some very advanced tools. There is no simpler way of showing this? $\endgroup$
    – Boby
    Jul 24, 2017 at 15:29
  • $\begingroup$ I am sure there is a simple solution to the problem, and my off-the-cuff remarks is just a high-brow way of describing it. $\endgroup$ Jul 24, 2017 at 15:34

1 Answer 1

6
+100
$\begingroup$

This problem is harder, and more interesting, than I originally thought. The OP's conjecture is sometimes true and sometimes not, depending on the values $k$ and $m.$

For given $m$ let $g(x) = E|Z+x|^m,$ where $Z\sim N(0,1).$ The symmetry of the distribution of $Z$ implies $g(x)=g(-x)$. If $m\ge 1$ the function $g$ is convex on $\mathbb R.$ But $g$ is concave on $[0,\infty)$ if $m<1$. As outlined in a comment, let $\Gamma=\{(x^k,g(x)): x\ge 0\} = \{(u, g(u^{1/k})): u\ge 0\}.$ (Note the comment did not restrict $x\ge0,$ but it should have.) Let $H\subset \mathbb R^2$ be the closed convex hull of $\Gamma.$ The closure of the set of possible $(E|X|^k, E|X+Z|^m)$ values attainable as we vary the probability law of $X$ is exactly the set $H$. Let $L=\{(x,y)\in\mathbb R^2: x=c\}$. The intersection $H\cap L$ is a closed interval in the plane; the OP's question concerns the upper end point of that interval.

There are two cases to consider. In the easy case, the function $\gamma: u\mapsto g(u^{1/k})$ is concave. Then the desired maximum is $\gamma(c^{1/k})$, attained at $(c,g(c))\in\Gamma$ when $P(X=c^{1/k})=1$, as the OP conjectured.

In the harder case $g$ is not concave. Let $\gamma^*$ be the upper concave envelope of $\gamma$, that is, the pointwise infimum of all concave functions pointwise greater than $\gamma$. By Dubins's theorem, or by Rockafellar's Corollary 17.1.5 (transposing his convex to our concave, etc.) we know that $(c,\gamma^*(c))$ is a convex combination of at most two points on $\Gamma$, which is what the original problem statement wanted. Note also that this $(c,\gamma^*(c))$ is in the closure of the hull of $\Gamma$ and itself might be only a limit of 2 point mixtures, not a 2 point mixture itself. And there might be technical conditions needed to apply these theorems.

So what distinguishes the easy case from the hard? First, if $m$ is an even integer, $g(x)$ works out to an even polynomial with nonnegative coefficients, of degree $m$. Thus $\gamma(u)$ is a nonnegative combination of terms $u^{j/k}$ for $0\le j\le m$, each of which is concave, so long as $k\ge m$. Another case to consider is $m=1.$ Then it can be checked that $\gamma$ is not concave unless $k\ge 2$. In general, for $\gamma$ to be concave the function $u\mapsto g'(u^{1/k})u^{1/k-1}$ must be decreasing in $u\in\mathbb R_+$) which is to say, $g'(x)x^{1-k}$ is decreasing in $x\in \mathbb R_+$.

ADDED 26 July. In the non concave case the sought-after maximum of $E|X+Z|^m$ need not be attained, but only approximated by 2-point distributions for $X$. In the $k=m=1$ case the function $\gamma$ is convex and increasing, and the set $H$ is $\{(x,y): x\ge 0, g(x)\le x \le x+g(0)\},$ but the points of form $(x,x+g(0))$ for $x>0$ are not in the convex hull of $\Gamma$ but only in its closure. They cannot be attained by any distribution on $X$. Thus the original statement of the problem should have asked for $\sup E|X+Z|^m$ instead of $\max E|X+Z|^m.$

ADDED & edited (to cope with $k\ne1$) 29 July. In hindsight I could have picked notations a bit better. Let $\gamma(x) = g(x^{1/k}).$ Let $\Gamma=\{(x,\gamma(x)): x\ge0\}$ be the graph of $\gamma$. Let $S$ be the convex hull of $\Gamma$, and let $\overline S$ be the closure of $S$. Let $\gamma^*$ be the upper concave envelope of $\gamma$. The problem of optimizing $E\gamma(X)$ over all $X\ge$ such that $E|X|^k=c$ is solved by $\gamma^*(c)$ in one of these senses: If $(c,\gamma^*(c))\in \Gamma$ the optimum is attained, as the OP conjectured, by a 1-point distribution for which $P(X=c)=1.$ If instead $(c,\gamma^*(c))\in S \setminus \Gamma,$ the optimum is attained by a 2-point distribution. But if $(c,\gamma^*(c))\in \overline S \setminus S,$ the optimum is not attained, but only approximated by 2-point distributions.

Added 3 August: The example $m=k=1$ is instructive. One finds that $g(x)= E|Z+x| = 2\varphi(x) + x(2\Phi(x)-1)$, a convex function on $[0,\infty)$. (Here $\varphi$ and $\Phi$ are the standard normal density and c.d.f.) The upper concave envelope is evidently $g^*( x) = g(0)+x.$ The convex hull, $S,$ of the graph $\Gamma=\{(x,g(x)): x\ge 0\}$ is given by $S=\Gamma \cup \{(x,y): x>0, g(x)\le y < g(0)+x\}$; it is seen to be the union of $\Gamma$ and all chords connecting pairs of points on $\Gamma$; it is also the set of all pairs $(EX,Eg(x))$ attainable by 1 or 2 point mass distributions for $X$. The point $(1,g(0)+1)$ is not in $S$, and cannot be represented by two point masses. The sequence of 2 point distributions $\mu_n = (1-1/n)\delta_0 + \delta_n/n$ obeys $\int x\mu_n(dx) = 1$ and $\int g(x) \mu_n(dx) = (1-1/n)g(0)+ 2\phi(n)/n + n(2\Phi(n)-1)/n \to g(0)+1$. (Claims in the comments to the effect that the set of measures $\mu$ such that $E|x|\le c$ is compact are besides the point: because $\mathbb R_+$ is unbounded, the map $\mu\mapsto \int x \mu(dx)$ is not continuous. The sequence $\mu_n$ might converge weakly to $\delta_0$ but the sequence $\int g(x) \mu_n(dx)$ goes not converge to $g(0)$.)

$\endgroup$
22
  • $\begingroup$ Thanks. Very nice answer. It will probably take me some time to understand all of your arguments, so I hope you don't mind if I bombard you with questions. First I wanted to summarize the conclusion of your findings. So, the conclusion is: if $\gamma(u)=g(u^{1/k})$ is concave then the solution is given by a single point mass. If $\gamma(u)$ is not concave then the solution is given by two mass points which we still have to determine. Is this correct? $\endgroup$
    – Boby
    Jul 25, 2017 at 18:38
  • $\begingroup$ Yes, that's how I see it. Please send your questions along; I'll try to answer them as I can. $\endgroup$ Jul 25, 2017 at 19:25
  • $\begingroup$ Very interesting. So, for the case when the solution is given by two point masses, any conjecture as to what the optimal distribution is? $\endgroup$
    – Boby
    Jul 25, 2017 at 19:35
  • $\begingroup$ Not really. I don't have an intuition about the shape of $\Gamma$ when $\gamma$ is not convex. One project might be to use a computer to draw a good diagram in the case $k=m=1$. $\endgroup$ Jul 25, 2017 at 19:42
  • $\begingroup$ Ok. Thanks. I can try doing that once I get through all the details. If you don't mind I will try to post a bounty on this question tomorrow. I want to see if other people have other ideas. $\endgroup$
    – Boby
    Jul 25, 2017 at 19:45

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .