2
$\begingroup$

I made the following claim, which I now see that I don't know how to prove. Can anyone prove it?

Claim. Let $f$ be a concave and non-negative function on $[0,1]$ with $$\int_0^1 f = 1,$$ $$\int_0^1 |f-1| > 2\varepsilon.$$ Then $$\min\left(\int_0^{1/4} f , \int_{3/4}^1 f\right) < \frac14 - \frac\varepsilon8.$$

In principle, this claim can be settled via computer algebra. For any $f$ satisfying the conditions, there is a piecewise-linear function $g$ of 10 pieces which satisfies the same conditions and has the same integrals as $f$ and $|f-1|$ on $[0,\frac14]$, $[\frac14,\frac34]$ and $[\frac34,1]$. The existence of such $g$ is just a matter of the existence of 9 $x$'s, 11 $y$'s, and 1 $\varepsilon$ satisfying some multilinear equalities and inequalities, and therefore is algorithmically solvable. In practice, my simplifications in Mathematica get overwhelmed before they finish.

Does anyone see a proof or a counterexample? I'd be happy to see a proof with $8$ replaced by any other small number.

Update: Distributions like $f(x)=\min(cx,c(1-x),\frac12(c-\sqrt{c^2-4c}))$ may provide extreme examples. The graph below shows $c=24$, with a maximum of $12-\sqrt{120}$, and a bound of $\frac14-\varepsilon/3.66$. For $f$ of this form with high $c$, the bound is $\min(\int_0^{1/4}f,\int_{3/4}^1f)<\frac14-\varepsilon/4$.

enter image description here

$\endgroup$

2 Answers 2

5
$\begingroup$

I claim the following result which implies what you are asking for.

Claim: Let $g$ be a convex function such that $\int_0^1 g=0$. Then one of $\int_0^{1/4}g$ and $\int_{3/4}^1 g$ is at least $\|g\|_1/18$.

The result implies what you are looking for (up to replacing 8 by 9) by setting $g=1-f$.

Proof: Since $\int_0^1 g=0$, we have $\int g^+=\int g^-=\|g\|_1/2$. Let $\{x\colon g(x)\le 0\}=[a,b]$.

First suppose that $b\le\frac 34$. In this case, since $g$ is increasing on $[b,1]$, $\int_{3/4}^1 g\ge \int_b^{b+\frac 14}g$. By convexity, $\int_b^{b+1/4}g\ge \frac1{32}g'(b^+)$ while $\int g^-=-\int_a^b g\le \frac 12(b-a)^2g'(b^+)\le \frac{9}{32}g'(b^+)$. It follows that $\int_{3/4}^1 g\ge \frac 19\int g^-=\frac 1{18}\|g\|_1$. By symmetry, the same applies if $a\ge \frac 14$.

In the other case, $g$ is negative on $[\frac 14,\frac 34]$. Since $\int g=0$, either $\int_0^{1/2}g\ge 0$ or $\int_{1/2}^1 g\ge0$. Without loss of generality, we assume that the first of these holds. Hence $\int_0^{1/4}g\ge -\int_{1/4}^{1/2}g$. We then apply the following lemma with $f=-g$, which gives $\int_{1/4}^{1/2}(-g)\ge \frac 19\int (-g)^+$, or $-\int_{1/4}^{1/2}g\ge \frac 1{18}\int\|g\|_1$, and the claim then follows.

Lemma: Let $f$ be concave on $[\frac 14,1]$ and positive on $[\frac 14,\frac 34]$ (at least). Then $\int_{1/4}^{1/2}f\ge \frac 19\int f^+$.

Proof: We are attempting to find a lower bound for $\int_{1/4}^{1/2}f\big / \int_0^1 f^+$. Given any $f$, this quantity is reduced if $f$ is replaced on $[\frac 14,\frac 12]$ by a linear function joining $(\frac 14,f(\frac 14))$ to $(\frac 12,f(\frac 12))$. It is then further reduced by extending that linear function to $[\frac 14,1]$. Now it is straightforward to see that the quantity is minimized if $f(x)=x-\frac 14$ on $[\frac 14,1]$, where the ratio is $\frac 19$ as required.

$\endgroup$
2
  • $\begingroup$ Thanks! Is there an example to show that this $1/18$ is sharp? And is there a name for inequalities like this? $\endgroup$
    – user44143
    Commented Jun 12, 2021 at 13:14
  • $\begingroup$ It's definitely not sharp: for that you would need the extremal example for one inequality to be extremal for the other also. I don't know a name for this kind of inequality. $\endgroup$ Commented Jun 12, 2021 at 14:12
2
$\begingroup$

$\newcommand{\ep}{\varepsilon}\newcommand{\de}{\delta}$Instead of $\int_0^1|f-1|>2\ep$, let us write \begin{equation*} \ep:=\frac12\int_0^1|f-1|. \end{equation*} We want to show that \begin{equation*} \min\Big(\int_0^{1/4}f,\int_{3/4}^1 f\Big)\le\frac14-\frac\ep8. \tag{!} \end{equation*}

Without loss of generality (wlog), $\ep>0$. By approximation, wlog the function $f\in C^2[0,1]$ with $f''>0$ on $(0,1)$ and the set $\{x\in[0,1]\colon f(x)\ge1\}$ is an interval $[a,b]$ such that $0<a<b<1$, with $f(a)=f(b)=1$.

So, \begin{equation*} \ep=\ep_1+\ep_2, \end{equation*} where \begin{equation*} \ep_1:=\int_0^a(1-f),\quad\ep_2:=\int_b^1(1-f). \end{equation*} Let \begin{equation*} \de_1:=\frac14-\int_0^{1/4}f=\int_0^{1/4}(1-f),\quad \de_2:=\frac14-\int_{3/4}^1 f=\int_{3/4}^1(1-f). \end{equation*} It suffices to show that \begin{equation*} \max(\de_1,\de_2)\overset{\text{(?)}}\ge\frac{24}{121}\,\ep, \tag{*} \end{equation*} which will improve the constant factor in (!) from $1/8=0.125$ to $\frac{24}{121}=0.19834\dots$. Moreover, the factor $\frac{24}{121}=0.19834\dots$ in the lower bound $\frac{24}{121}\,\ep$ in (*) is the best possible.

Our main tool here will be the following lemma.

Lemma 1: Suppose that $g\in C^2[0,1]$ with $g''<0$ on $(0,1)$ and $g(u)=0$ for some $u\in(0,1)$. Then the function $h\colon[0,1]\to\mathbb R$ defined by \begin{equation*} h(x):=\frac1{(x-u)^2}\,\int_u^x g \end{equation*} for $x\in[0,1]\setminus u$, with $h(u):=g'(u)/2$, is nonincreasing. Here, $\int_u^x:=-\int_x^u$ if $x<u$.

The proof of this lemma consists in a triple application of the special-case l'Hospital-type rule for monotonicity given by Proposition 4.1.

In particular, it follows from Lemma 1 (applied to $g:=f-1$) that \begin{equation*} b-a\ge1/2. \tag{0} \end{equation*} Indeed, suppose (0) is false. Then there are $l_1\in(0,a)$ and $l_2\in(0,1-b)$ such that $l_1+l_2=b-a$ (e.g., let $l_1:=\frac{b-a}{a+1-b}\,a$ and $l_1:=\frac{b-a}{a+1-b}\,(1-b)$). By Lemma 1 (it helps to draw a picture), \begin{equation*} \int_a^{a+l_1}(f-1)\le\frac{l_1^2}{a^2}\,\int_a^0(f-1)=\frac{l_1^2}{a^2}\,\int_0^a(1-f) =\frac{l_1^2}{a^2}\,\ep_1\le\ep_1, \tag{0.5} \end{equation*} so that $\int_a^{a+l_1}(f-1)\le\ep_1$, and the latter inequality is strict if $\ep_1>0$. Similarly, $\int_{a+l_1}^b(f-1)=\int_{b-l_2}^b(f-1)\le\ep_2$, and the latter inequality is strict if $\ep_2>0$. So, \begin{equation*} \ep=\int_a^b(f-1)=\int_a^{a+l_1}(f-1)+\int_{a+l_1}^b(f-1)\le\ep_1+\ep_2=\ep, \end{equation*} and the latter inequality is strict, since $\ep>0$ and hence either $\ep_1>0$ and $\ep_2>0$. Thus, we have $\ep<\ep$, a contradiction, which proves (0).

In view of (0) and by symmetry, it is enough to consider the following two cases: \begin{equation*} 0<a\le1/4,\quad 3/4\le b<1 \tag{i} \end{equation*} and \begin{equation*} 1/4<a\le1/2,\quad 3/4\le b<1 \tag{ii} \end{equation*}

Consider now case (i). Then, letting \begin{equation*} \eta_1:=\int_a^{1/4}(f-1),\quad\eta_2:=\int_{3/4}^b(f-1), \end{equation*} we have \begin{equation*} \de_1=\ep_1-\eta_1,\quad\de_2=\ep_2-\eta_2. \tag{1.5} \end{equation*} Let now \begin{equation*} c:=f(1/4)-1[\ge0],\quad d:=f(3/4)-1[\ge0], \end{equation*} \begin{equation*} p(x):=c+(x-1/4)\frac{d-c}{1/2}=\frac{3c-d}2+2x(d-c). \end{equation*} Then $p(1/4)=c=f(1/4)-1$ and $p(3/4)=d=f(3/4)-1$. So, by the concavity of $f$, we have $p\le f-1$ on $[1/4,3/4]$ and $p\ge f-1$ on $[0,1]\setminus[1/4,3/4]$. So, \begin{equation*} \eta_1=\int_a^{1/4}(f-1)\le\int_a^{1/4}p=\frac{5c-d}{16}; \end{equation*} similarly, $\eta_2\le\int_a^{1/4}p=\frac{5d-c}{16}$, whence \begin{equation*} \eta_1+\eta_2\le\frac{5c-d}{16}+\frac{5d-c}{16}=\frac{c+d}4, \end{equation*} whence, by (1.5), \begin{equation*} \de_1+\de_2=\ep_1+\ep_2-(\eta_1+\eta_2)=\ep-(\eta_1+\eta_2)\ge\ep-(c+d)/4; \end{equation*} and \begin{equation*} \int_{1/4}^{3/4}(f-1)\ge\int_{1/4}^{3/4}p=\frac{c+d}4, \end{equation*} so that \begin{equation*} \ep_1+\ep_2=\ep=\int_a^b(f-1)=\int_a^{1/4}(f-1)+\int_{1/4}^{3/4}(f-1)+\int_{3/4}^b(f-1) \ge\eta_1+\frac{c+d}4+\eta_2, \end{equation*} whence, by (1.5), $\de_1+\de_2\ge(c+d)/4$. So, \begin{equation*} \max(\de_1,\de_2)\ge\frac12\,(\de_1+\de_2) \ge\frac12\,\max((c+d)/4,\ep-(c+d)/4)\ge\frac\ep4. \end{equation*} So, (*) holds if case (i) takes place.

Consider now case (ii). By Lemma 1 (cf. (0.5)), \begin{equation*} \ep=\int_a^b(f-1)\le\frac{(b-a)^2}{a^2}\,\int_0^a(1-f)\le\frac{(1-a)^2}{a^2}\,\int_0^a(1-f) =\frac{(1-a)^2}{a^2}\,\ep_1, \end{equation*} \begin{equation*} \ep-\eta_2=\int_a^{3/4}(f-1) \ge\frac{(3/4-a)^2}{(b-a)^2}\,\int_a^b(1-f)=\frac{(3/4-a)^2}{(b-a)^2}\,\ep\ge\frac{(3/4-a)^2}{(1-a)^2}\,\ep, \end{equation*} and, similarly, \begin{equation*} \ep_1-\de_1=\int_a^{1/4}(f-1)\le\frac{(a-1/4)^2}{a^2}\int_a^0(f-1) =\frac{(a-1/4)^2}{a^2}\,\ep_1, \end{equation*} which implies \begin{equation*} \de_1\ge n(a)\ep_1\ge m(a)\ep, \tag{4} \end{equation*} where \begin{equation*} n(a):=1-\frac{(a-1/4)^2}{a^2},\quad m(a):=\frac{a^2}{(1-a)^2}n(a). \end{equation*} So, \begin{equation*} \de_2=\ep_2-\eta_2=-\ep_1+(\ep-\eta_2)\ge-\de_1/n(a)+\frac{(3/4-a)^2}{(1-a)^2}\,\ep. \tag{5} \end{equation*}

Minimizing now $\max(\de_1,\de_2)$ over all $\de_1,\de_2,a$ such that $1/4\le a<1$, $\de_1\ge m(a)\ep$ (cf. (4)), and $\de_2\ge-\de_1/n(a)+\frac{(3/4-a)^2}{(1-a)^2}\,\ep$ (cf. (5)), we get $\max(\de_1,\de_2)\ge\frac{24}{121}\,\ep$ in case (ii), so that (*) holds in case (ii) as well. This calculation takes about 0.11 sec with Mathematica:

enter image description here

$\Box$

Remark 1: To show without Mathematica that $\max(\de_1,\de_2)\ge\frac{24}{121}\,\ep$ in case (ii), one can do as follows. Rewrite the conditions $\de_1\ge m(a)\ep$ and $\de_2\ge-\de_1/n(a)+\frac{(3/4-a)^2}{(1-a)^2}\,\ep$ as \begin{equation} \de_1/\ep\ge\max(A,(B-\de_2/\ep)K), \end{equation} where $A:=m(a)$, $B:=\frac{(3/4-a)^2}{(1-a)^2}$, and $K:=n(a)$. If $\de_2\ge\frac{24}{121}\,\ep$, we are done. Otherwise, \begin{equation} \de_1/\ep\ge \max(m(a),M(a)), \end{equation} where \begin{equation} M(a):=(B-\tfrac{24}{121})K=\Big(\frac{(3/4-a)^2}{(1-a)^2}-\frac{24}{121}\Big)n(a). \end{equation} Note that $m$ is increasing on $[0,1]$, $M$ is decreasing on $[1/4,1/2]$, and $m(\frac 5{16})=\frac{24}{121}=M(\frac 5{16})$. It follows that for all $a\in[1/4,1/2]$ \begin{equation} \de_1/\ep\ge\max(m(a),M(a))\ge\tfrac{24}{121}, \end{equation} as was proved by Mathematica.

Remark 2: Following the lines of the consideration of case (ii) (with $a=5/16$, $\ep\downarrow0$, and $b\uparrow1$), one can see that the factor $\frac{24}{121}=0.19834\dots$ in the lower bound $\frac{24}{121}\,\ep$ in (*) is the best possible.

More explicitly, for $k\in(0,1)$ and $x\in[0,1]$, let \begin{equation} f(x):=\left\{ \begin{aligned} k \left(x-5/16\right)+1 & \text{ if }x\le\frac{5 k+16}{11 k+16} \\ \frac{(25 k^2+352 k+256) (1-x)}{96 k} & \text{ if }x\ge\frac{5 k+16}{11 k+16}. \end{aligned} \right. \end{equation} Then $f$ satisfies all the conditions. Moreover, then \begin{equation} a=5/16,\quad b=\frac{25 k^2+256 k+256}{25 k^2+352 k+256}, \end{equation} and \begin{equation} \frac{\de_1}\ep=\frac{\de_2}\ep=\frac{24 \left(25 k^2+352 k+256\right)}{(25 k+176)^2}\to\frac{24}{121} \end{equation} as $k\downarrow0$.

Here is the plot of this particular $f$ for $k=1/2$:

enter image description here

$\endgroup$
7
  • $\begingroup$ Thanks, Iosif. I deleted my previous comments. Can you give an explicit example of a distribution which attains this factor, or some factor better than $1/4$? $\endgroup$
    – user44143
    Commented Jun 13, 2021 at 15:19
  • 1
    $\begingroup$ @MattF. : Such an explicit example is now given. $\endgroup$ Commented Jun 13, 2021 at 16:09
  • $\begingroup$ Now Mathematica does not have to be used at all. $\endgroup$ Commented Jun 13, 2021 at 21:17
  • 1
    $\begingroup$ Nice! To make this self-contained, Lemma 1 can be proved by noting that if $g$ is convex and $g(u)=0$, then $k(x)=\frac 12g(x)/(x-u)$ is increasing. The function $h$ is $\int_u^x k(x)(x-u)\big / \int_u^x (x-u)$, which is an average of an increasing function, and hence increasing. $\endgroup$ Commented Jun 14, 2021 at 5:06
  • $\begingroup$ @AnthonyQuas : Thank you for your comment. $\endgroup$ Commented Jun 14, 2021 at 13:29

You must log in to answer this question.