# Maximize $\int_{0}^{1} \mathbb{E} |X-\mathbb{P}(X\ge u)|^3\,\mathrm du$ over $[0,1]$ valued $X$.

Find the maximal value of

$$\int_{0}^{1} \mathbb{E} |X-\mathbb{P}(X\ge u)|^3\,\mathrm du$$

over $$[0,1]$$ valued random variables $$X$$.

I believe that optimal $$X$$ takes exactly two different values, but I have a hard time trying to actually prove it. I will be glad for any help or insight.

I also wonder if a pair $$(X,\mathbb{P}[X\ge U])$$, where $$U\sim\mathcal{U}[0,1]$$, is a more widely known or studied.

• why the power 3? what is the motivation behind ? Dec 28 '19 at 20:16
• in this case, you could perhaps mention the solution for k=2 in your question; this could be of interest to solve the other cases. Dec 28 '19 at 20:42
• I understand you're asking for general $X$, but if we restrict to binary-valued (indicator) $X$, the max still happens at $P(X=1)=\frac12$ for $k=3$, but more interestingly for $k=4$ the max(es) now happen at $P(X=1)=\frac12 \pm {1 \over 2\sqrt{3}}$ (assuming I didn't make any mistake with math and typing things into wolfram alpha.) Dec 28 '19 at 23:29
• One can easily show that the maximizer is always a discrete random variable with at most $C(k)$ values with some explicit $C(k)$. Unfortunately, as of now, it is of little practical value since I can only show that $C(3)\le 66$, say, and I see no reason why the number of values should not grow to infinity as $k\to\infty$. Would you be interested in some upper bounds that are only not too far from the true maxima for large $k$ as well? Jan 5 '20 at 3:45
• @fedja - I would be highly interested in $C(3)\le 66$ bound. I have been trying to find any such bound by myself and did not succeed. I think it would be quite eyeopening to see it. Jan 5 '20 at 11:06

The equivalent reformulation of the problem is to maximize $$\mathbb E|X-Y|^k$$ under the condition that $$X,Y$$ are independent and the functions $$F_X(u)=\mathbb P\{X\ge u\}$$ and $$F_Y(u)=\mathbb P\{Y\ge u\}$$ are inverse to each other in the sense that their graphs are symmetric (as usual, we connect the jumps in the graph by vertical intervals and consider vertical intervals as jumps).
Now I want to show two things: the upper bound $$\frac 2{k+1}$$ (which should be compared with the example $$X=\frac{k+1}{k+2}\chi_ A, \mathbb P(A)=\frac{k+1}{k+2}$$ giving the value $$\frac 2{k+2}(\frac{k+1}{k+2})^{k+1}\ge \frac 2{e(k+2)}$$) and the claim that the maximizer exists and is a discrete random variable with at most $$C(k)$$ values (though I'll not try to squeeze the best $$C(k)$$ the method can give: it is still too large for practical purposes even when $$k=3$$).
The first claim is rather straightforward: $$\mathbb E|X-Y|^k=\int_0^1 kt^{k-1}(\mathbb P\{X>Y+t\}+\mathbb P\{Y>X+t\})dt.$$ Now define $$s\in[0,1-t]$$ by $$F_X(s+t)=s$$. Notice that if $$X>Y+t$$, then either $$X>s+t$$, the probability of which is $$F_X(s+t)=s$$ or $$Y, the probability of which is $$1-F_Y(s)=1-F_X^{-1}(s)=1-s-t$$, so we always have $$\mathbb P\{X>Y+t\}\le \mathbb P\{X>s+t\}+\mathbb P\{Y and the same inequality holds for the other probability whence the integral in question is at most $$2\int_0^1 kt^{k-1}(1-t)dt=\frac 2{k+1}.$$
The second claim is a bit longer to prove. We fix $$m$$ and consider all discrete random variables with at most $$m$$ values. This is a compact set and we have a continuous functional, so the maximum over that family is attained for some $$X$$ with, say, $$M$$ values. If we bound $$M$$ independently of $$m$$, we will be done. Suppose that $$M$$ is large. Then the graph of $$F_X$$ is a descending stairway with many steps. In particular, there is a value $$x$$ of $$X$$ that is neither $$0$$, nor $$1$$, and the associated probability $$p_{x}=\mathbb P\{X=x\}\le\frac 1{M-2}$$ is very small. Let's try to move $$x$$ to a close value $$x'$$ without changing the probabilities. Our functional then can be written as $$L(x')+\sum_y p_x q_y|x'-y|^k+p_x[|x'-y_+|^k-|x'-y_-|^k](x'-x)$$ where $$L(x')$$ is linear in $$x'$$ and $$y_+-y_-=p_x$$ (i.e., $$y_{\pm}$$ are the levels of the top and the bottom of the step on the stairway graph of $$F_X$$ whose vertical side is $$p_x$$). Taking the second derivative in $$x'$$ at $$x'=x$$ and dividing by $$p_x$$, we get $$k(k-1)\sum_y q_y|x-y|^{k-2}\\+2k[|x-y_+|^{k-1}{\rm sgn}(x-y_+)- |x-y_-|^{k-1}{\rm sgn}(x-y_-)]\le 0$$ (otherwise our configuration cannot be a maximizer). Since the second derivative $$k(k-1)|x-y|^{k-2}$$ is a convex function of $$y$$ for integer $$k\ge 2$$, we can replace the increment of the first derivative by the half-sum of the second derivatives at the endpoints times $$y_+-y_-=p_x$$ and derive the inequality $$\sum_y q_y|x-y|^{k-2}\le p_x[|x-y_+|^{k-2}+|x-y_-|^{k-2}]\tag{*}$$ This should actually hold for every $$x\ne 0,1$$ and I feel that there must be a more efficient way to use $$(*)$$ than the one I'm following below but, at the very least, the RHS is $$\le 2p_x$$, so if $$p_x$$ is very small, then $$Y$$ is concentrated near $$x$$ and, thereby, near its mean $$EY$$. Similarly, choosing small $$q_y$$ with $$y\ne 0,1$$, we see that $$X$$ is concentrated near $$EX$$. But $$EX=EY$$ (both represent the area under the stairway), so in this case $$X-Y$$ is concentrated near $$0$$ and $$E|X-Y|^k$$ is very small. However, we have a maximizer, so we have an a priori lower bound on that expectation for every fixed $$k$$, which tells us that $$M$$ cannot be too large, finishing the argument.
• @StanTuwim Yes, but the problem is that the minimum may occur at an end and the sequence of $p$'s and $q$'s may be unimodal with maximum near the middle or increasing all the way to the other end, so the desired inequality never occurs for $p_x$ or $q_y$. Jan 6 '20 at 12:31