2
$\begingroup$

Let $S=\{(x_i, y_i)\}_{i=1...n} \in [0,1]^{2n}$ bet a tuple of ordered pairs, and let $A, H$ denote the arithmetic and harmonic mean. Then $$ \sup_S (H(\underset{i}{A}(x_i),\underset{i}{A}(y_i)) - \underset{i}{A}(H(x_i, y_i))) = \begin{cases} 0.5,n\text{ is even}\\ 0.5 - \frac{1}{2n^2},\text{else} \end{cases} $$ We found a proof (Opitz and Burst, 2019: Macro F1 and Macro F1) by showing that the difference can be increased by intelligently swapping variables and then setting them to either 0 or 1. The proof is fairly long, and we are wondering: Is there a simple way to show this bound?

$\endgroup$
1
  • $\begingroup$ I have a very simple proof for the even case but the odd case is a bit trickier (although I think the main ideas can be adapted with patience). $\endgroup$ Commented Nov 27, 2019 at 3:24

2 Answers 2

1
$\begingroup$

$ \newcommand{\R}{\mathbb{R}} \newcommand{\la}{\lambda} \newcommand{\p}{\partial} \newcommand{\PP}{\mathcal{P}}$ Let $x:=(x_1,\dots,x_n)\in[0,1]^n$, $y:=(y_1,\dots,y_n)\in[0,1]^n$, $h:=(h_1,\dots,h_n)$, \begin{equation*} h_i:=H(x_i,y_i),\quad H(u,v):=\frac2{\frac1u+\frac1v}=\frac{2uv}{u+v} \end{equation*} for $u>0$ and $v>0$, and, by continuity, $H(u,v):=0$ for $u\ge0$ and $v\ge0$ with $u v=0$. Let $Az:=\frac1n\sum_1^n z_i$ for $z:=(z_1,\dots,z_n)$. Then the result in question can written as \begin{equation*} L:=L(x,y):=H(Ax,Ay)-Ah\le L^*_n:= \left\{ \begin{alignedat}{2} &\frac12&&\text{ if $n$ is even}\\ & \frac12-\frac1{2n^2}&&\text{ if $n$ is odd}, \end{alignedat} \right. \tag{0} \end{equation*} with equality for some $x,y$ in $[0,1]^n$.

The maximum of $L(x,y)$ over all $(x,y)\in[0,1]^n\times[0,1]^n$ is attained. In what follows, let $(x,y)$ be such a maximizer.

With $[n]:=\{1,\dots,n\}$, $p$ and $q$ in $\{0,1\}$, and $|K|:=(\text{cardinality of $K$)}$, let
\begin{gather*} I:=\{i\in[n]\colon 0<x_i<1\},\quad J:=\{i\in[n]\colon 0<y_i<1\},\\ I_p:=\{i\in[n]\colon x_i=p\},\quad J_q:=\{i\in[n]\colon y_i=q\},\\ s_{pq}:=\tfrac1n|I_p\cap J_q|, \end{gather*} so that $s_{00}+s_{01}+s_{10}+s_{11}\le1$.

If $Ax=0$, then $x=0$ and hence $h=0$ and $L=0$, which makes the inequality in (0) trivial. So, without loss of generality (wlog), $Ax>0$. Similarly, wlog $Ay>0$. So, \begin{equation*} r:=Ay/Ax\in(0,\infty). \tag{1} \end{equation*}

Let $\p_u$ denote the partial derivative with respect to a variable $u$. Then
\begin{equation*} \p_u H(u,v)=2\Big(\frac v{u+v}\Big)^2 \end{equation*} for $u>0$ and $v>0$. So, for any $i\in I$ \begin{equation*} \frac n2\,\p_{x_i}L =\Big(\frac r{r+1}\Big)^2-\Big(\frac{y_i}{x_i+y_i}\Big)^2=0, \end{equation*} because $(x,y)$ is a maximizer of $L$. So, $y=rx>0$ on $I$. Similarly, $y=rx>0$ on $J$, and hence $y=rx>0$ on $I\cup J$. So, with $\xi:=\frac1n\,\sum_{i\in I\cup J}x_i$, \begin{alignat*}{5} &Ax=&& &&s_{10}&+&s_{11}&&+\xi, \tag{Ax}\\ &Ay=&&s_{01}&& &+&s_{11}&&+\xi r, \tag{Ay}\\ &Ah=&& && &&s_{11}&&+\xi\frac{2r}{1+r}. \end{alignat*} So, \begin{align*} L&=\frac{2 Ax\,Ay}{Ax+Ay}-Ah \\ &=Ax\frac{2r}{1+r}-\Big(s_{11}+\xi\frac{2r}{1+r}\Big) \\ &=(s_{10}+s_{11})\frac{2r}{1+r}-s_{11}. \tag{2} \end{align*} It also follows from (Ax) and (Ay) that the equality in (1) can be rewritten as \begin{equation*} s_{01}+s_{11}=r(s_{10}+s_{11}). \end{equation*} So, if $s_{10}+s_{11}=0$, then $s_{11}=0$ and hence, by (2), $L=0$. So, wlog $s_{10}+s_{11}>0$ and hence $r=\frac{s_{01}+s_{11}}{s_{10}+s_{11}}$. Using this expression for $r$, we get from (2): \begin{align*} L=M:=\frac{2 s_{01} s_{10} + (s_{01}+ s_{10})s_{11}}{s_{01} + s_{10} + 2 s_{11}}. \end{align*} Next, \begin{equation*} \p_{s_{11}}M:=\frac{(s_{01}-s_{10})^2}{(s_{01} + s_{10} + 2 s_{11})^2}\ge0. \end{equation*} So, wlog one may replace $s_{11}$ by its largest possible value, $1-s_{01}-s_{10}$: \begin{equation*} L=M\le N:=M|_{s_{11}=1-s_{01}-s_{10}}= \frac{(1-s_{01})s_{01}+(1-s_{10})s_{10}}{2-s_{01}- s_{10}}. \end{equation*} Further, \begin{equation*} (\p_{s_{01}}+\p_{s_{10}})N= \frac{4(1-s_{01})(1-s_{10})}{(2-s_{01}-s_{10})^2}\ge0. \end{equation*} So, if we increase $s_{01}$ and $s_{10}$ by the same amount, while keeping $s_{01}+s_{10}\le1$, the value of $N$ may only increase. So, \begin{equation*} L\le N|_{s_{10}=1-s_{01}}=2(1-s_{10})s_{10} \le2(1-\tfrac mn)\tfrac mn=L^*_n, \end{equation*} where $m:=\lfloor n/2\rfloor$; the latter inequality follows because $(1-u)u$ is decreasing in $|u-1/2|$ for $u\in[0,1]$.

The inequality in (0) turns into the equality if $(x_i,y_i)=(1,0)$ for $i=1,\dots,m$ and $(x_i,y_i)=(0,1)$ for $i=m+1,\dots,n$.

The entire proof is now complete.

$\endgroup$
1
  • $\begingroup$ I have added a couple of details to the proof, and also fixed a couple of typos. $\endgroup$ Commented Nov 27, 2019 at 4:20
0
$\begingroup$

I will give you a short proof for the even case. I think it may be possible to imitate the steps for $n$ odd.

Restating your problem in a math-olympiad fashion, one has to prove that for $0< x_i,y_i\leq 1$, $1\leq i\leq n$, the following holds:

$$ \frac{1}{n} \cdot \frac{2\left(\sum_{i=1}^n x_i\right) \left(\sum_{i=1}^n y_i\right)}{\left(\sum_{i=1}^n x_i\right) + \left(\sum_{i=1}^n y_i\right)} - \frac{2}{n} \sum_{i=1}^n \frac{x_iy_i}{x_i+y_i} \leq \frac{1}{2}$$

Which in turn, using the inequalities between harmonic and arithmetic means in the first summand, means that it is enough to prove:

$$ \frac{1}{2n} \left(\sum_{i=1}^n x_i + \sum_{i=1}^n y_i\right) - \frac{2}{n} \sum_{i=1}^n \frac{x_iy_i}{x_i+y_i} \leq \frac{1}{2}$$

And this is equivalent to this:

$$ \sum_{i=1}^n (x_i + y_i) - 4 \sum_{i=1}^n \frac{x_iy_i}{x_i+y_i} \leq n$$

Which, rewriting is just to prove:

$$ \sum_{i=1}^n \frac{(x_i-y_i)^2}{x_i+y_i} \leq n$$

And it is sufficient to verify that each summand is $\leq 1$, which is pretty simple given that $(x_i-y_i)^2\leq x_i+y_i$, since this is just equivalent to $x_i^2+y_i^2 \leq x_i+y_i + 2x_iy_i$, and the last inequality follows directly from the fact that $x_i^2\leq x_i$ and $y_i^2\leq y_i$, for $x_i,y_i\in [0,1]$.

Interestingly, the case of equality is straightforward to construct, since we only need that $(x_i-y_i)^2= x_i+y_i$ which is easy to see only can happen for $x_i=1$ and $y_i=0$ or viceversa, and that $\sum x_i = \sum y_i$.

$\endgroup$
1
  • $\begingroup$ Interesting! It would probably have never occurred to me that simply bounding the harmonic mean (of the arithmetic means) by the corresponding arithmetic mean would work, even for even $n$. However, after that, you are only rewriting the bound on the difference, and I don't see how this could be made work for odd $n$. $\endgroup$ Commented Nov 27, 2019 at 22:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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