# Inequality Involving Concave Functions

Assume that $$f: \mathbb{R} \to \mathbb{R}_+$$ is a concave, non-decreasing and positive function. Let $$\mathbb{X}$$ be a finite set consisting of $$0\leq x_1 \leq x_2 \leq x_3 \leq \ldots \leq x_n$$. Further, let $$X$$ be a random variable supported on $$\mathbb{X}$$.

I am interested in the following inequality:

$$\frac{ f(x_n) - \mathbb{E}[f(X)] }{ \sqrt{ \mathbb{E}\left[ \left(f(X) - \mathbb{E}[f(X)]\right)^2 \right] } } \leq \frac{ x_n - \mathbb{E}[X] }{ \sqrt{ \mathbb{E}\left[ \left(X - \mathbb{E}[X]\right)^2 \right] } }$$

Is this inequality always true under the given conditions? If so, can you provide a proof or some intuition behind why this inequality holds? If not, can you provide a counterexample or conditions under which it might fail?

• May I know the source of the problem?
– Amir
Commented Aug 4 at 20:57

It is true, fairly simple, and reasonably well-known (to people who know it well) in a slightly different form.

Shifting $$x_n$$ and $$f(x_n)$$ to $$0$$, flipping both axes and the fraction, squaring, writing the variance as $$E[Y^2]-E[Y]^2$$ and adding $$1$$, we arrive at the following (classical?) version of this inequality:

Let $$X\ge 0$$ be a random variable, and let $$f:[0,+\infty)\to [0,+\infty)$$ be a convex increasing function with $$f(0)=0$$. Then $$\frac{E[f(X)^2]}{E[f(X)]^2}\ge \frac{E[X^2]}{E[X]^2}\,.$$

The proof is a three-liner. First, note that the LHS is invariant under multiplication of $$f$$ by a positive constant, so we can normalize so that $$E[f(X)]=E[X]$$. Then $$E[(f(X)-X)_+]=E[(X-f(X))_+]$$ (here $$a_+=\max(0,a)$$). Note that due to the convexity of $$f$$ and the condition $$f(0)=0$$, we have $$f(x)\le x$$ for $$x\le x_0$$ and $$f(x)\ge x$$ for $$x\ge x_0$$ with some $$x_0>0$$.

Hence $$E[(f(X)^2-X^2)_+]\ge E[2x_0(f(X)-X)_+] \\ =E[2x_0(X-f(X))_+]\ge E[(X^2-f(X)^2)_+]\,,$$ whence $$E[f(X)^2]\ge E[X^2]$$ and we are done.

• There is another bounty with some hours left (there is an answer but not sure if it really solves the question) that I feel it could be solved with a version of the inequality you used because what wants to be proved $\sum (p-\frac{1}{n})^2\ge\sum(\frac{p\log 1/p}{\sum p\log 1/p} -\frac{1}{n})^2$ reduces to $\sum p^2\ge\sum(\frac{p\log 1/p}{\sum p\log 1/p})^2$ or $\frac{\sum p^2}{(\sum p)^2}\ge\frac{\sum f(p)^2}{(\sum f(p))^2}$, if you want to look at it. Commented Aug 5 at 5:15
• @Dabed $f(p)=-p \log p$ is concave but not increasing, which makes it challenging (see the existing answer for more details).
– Amir
Commented Aug 5 at 6:54
• @Amir Ah right did follow the proof but put my attention was drawn just to the similitude of the inequalities and didn't think this much trough, thanks. Commented Aug 5 at 7:28
• @Amir Of course, $f(p)=-p\log p$ is not increasing on $(0,1)$ but $-cp\log p+p$ (where $c\in(0,1)$ is the normalizing factor such that $\sum cf(p)=1$) is increasing on the set of $p$'s involved (though it is not at all obvious), and that suffices. Can you finish it from here or should I post the full solution? Commented 2 days ago
• @fedja Thank you! If you are not busy now, you may post it as a full solution so that I can award the bounty (it expires shortly).
– Amir
Commented 2 days ago