Sum of square root of positive real numbers bounded away from the mean

189 Views Asked by At

I know that for $a_i \in (0,1)$ with $\sum^k_{i=1}a_i=1$ we have $\sum^k_{i=1}\sqrt{a_i}\leq \sqrt{k}$. The maximum value is attained when the terms are all equal.

I want to know what are the bounds if the terms are strictly away from the mean. In other words, suppose for $m>0$ and $\frac{1}{k}>|\alpha_i|>m$ with $\sum^k_{i=1}\alpha_i=0$ , we define $a_i := \frac{1}{k}+\alpha_i$. Is there a sharper bound for $\sum^k_{i=1}\sqrt{a_i}$ in this situation?

2

There are 2 best solutions below

0
On

I will prove a result which is true for all concave functions $f:(0,\infty)\rightarrow \mathbb{R}$ with the property that $f(1)=1$. This will automatically answer the original question as a corollary.

Theorem: Given a concave function $f:(0,\infty)\rightarrow \mathbb{R}$ with the property that $f(1)=1$ and a positive sequence $(a_i)_{i=1}^{k}$ of real numbers bounded away from one by a constant $m \in (0,1)$ such that $\sum_{i=1}^{k}a_i=k$, we have $$ \sum_{i=1}^{k}f(a_i)<\frac{k}{2}\left( f(1-m)+f(1+m)\right)\leq k$$ Corollary: For a situation as above with $f(x)=\sqrt{x}$, we have $$ \sum_{i=1}^{k}\sqrt{a_i}<\frac{k}{2}\left( \sqrt{1-m}+\sqrt{1+m}\right)\leq k$$ Proof of Theorem: Consider the line passing through the points $(1-m,f(1-m))$ and $(1+m, f(1+m))$. Then the line joining these two points lies below the function $f(x)$ for $x\in(1-m,1+m)$ but above it for $x\in (0,1-m)\cup (1+m,\infty)$ by its concavity. Therefore, $$f(x)<\frac{f(1+m)-f(1-m)}{2m}\left(x-(1+m)\right)+f(1+m)$$ Summing over the elements, we get: $\begin{aligned} \sum_{i=1}^{k}f(a_i)&<\sum_{i=1}^{k}\left[ \frac{f(1+m)-f(1-m)}{2m}\left(a_i-(1+m)\right)+f(1+m)\right]\\ &=k\frac{f(1+m)-f(1-m)}{2m}-k(1+m)\frac{f(1+m)-f(1-m)}{2m} + kf(1+m), \text{ as } \sum_{i=1}^{k}a_i=k\\ &=\frac{k}{2}\left( f(1-m)+f(1+m)\right) \end{aligned} $. $\square$

Note that $f(1-m)+f(1+m)\leq 2$ by concavity so we do indeed have a stricter bound.

4
On

We replace the constraints $m<|\alpha_i|<\frac{1}{k}$ with $m\le |\alpha_i|\le \frac{1}{k}$. This replacement does not alter the logics of our response, since even in the case of strict inequalities, one can tend to either of the bounds ($m$ or $\frac{1}{k}$) arbitrarily closely.

The problem can then be formulated as $$ {\max \sum_{i=1}^k\sqrt{\frac{1}{k}+\alpha_i} \\ m\le |\alpha_i|\le \frac{1}{k} } $$

Let an optimal solution to the latter problem be $\{\alpha_i^*\}_{i=1}^k$. We prove the following property for $\{\alpha_i^*\}_{i=1}^k$:

Claim: If there exist two distinct indices $i$ and $j$ for which $m<|\alpha_i^*|<\frac{1}{k}$ and $m<|\alpha_j^*|<\frac{1}{k}$, then $\alpha_i^*=\alpha_j^*$.

Proof: let two such indices $i,j$ exist. Then we have $$ \alpha_i^*+\alpha_j^*+\sum_{k=1,k\notin \{i,j\}}^K\alpha_k^*=0. $$ Since $m<|\alpha_i^*|<\frac{1}{k}$ and $m<|\alpha_j^*|<\frac{1}{k}$, it is possible to freely increase or decrease both the variables $\alpha_i^*$ and $\alpha_j^*$ as much as a small enough $\epsilon>0$. Keeping $C=\sum_{k=1,k\notin \{i,j\}}^K\alpha_k^*$ constant, the objective function can be written as $$ O= K+\sqrt{\frac{1}{k}+\alpha_i^*}+\sqrt{\frac{1}{k}-C-\alpha_i^*} $$where both $C$ and $K$ are constant. The derivative of $O$ w.r.t. $\alpha_i^*$ yields $${ \frac{\partial O}{\partial \alpha_i^*}=\frac{1}{2\sqrt{\frac{1}{k}+\alpha_i^*}}-\frac{1}{2\sqrt{\frac{1}{k}-C-\alpha_i^*}} \\= \frac{\sqrt{\frac{1}{k}-C-\alpha_i^*}-\sqrt{\frac{1}{k}+\alpha_i^*}}{2\sqrt{\frac{1}{k}+\alpha_i^*}\sqrt{\frac{1}{k}-C-\alpha_i^*}} \\= \frac{-C-2\alpha_i^*}{2\sqrt{\frac{1}{k}+\alpha_i^*}\sqrt{\frac{1}{k}-C-\alpha_i^*}(\sqrt{\frac{1}{k}-C-\alpha_i^*}+\sqrt{\frac{1}{k}+\alpha_i^*})}. } $$ First-order necessary condition (FONC) implies that the latter derivative be zero at the optimal point, such that no deviation yields a better result. Consequently, we should have $-C-2\alpha_i^*$ or $\alpha_i^*=\alpha_j^*$, and the proof is complete $\blacksquare$

Based on the proven claim, the optimal point $\{\alpha_i^*\}_{i=1}^k$ has the following form:

(1) A total of $n_1$ indices $i$ exist, where for each index we have $\alpha_i^*=\frac{1}{k}$.

(2) A total of $n_2$ indices $i$ exist, where for each index we have $\alpha_i^*=-\frac{1}{k}$.

(3) A total of $n_3$ indices $i$ exist, where for each index we have $\alpha_i^*=m$.

(4) A total of $n_4$ indices $i$ exist, where for each index we have $\alpha_i^*=-m$.

(5) A total of $n_5$ indices $i$ exist, where for each index we have $\alpha_i^*=\alpha$ where $m<\alpha<\frac{1}{k}$.

(6) $n_1+n_2+n_3+n_4+n_5=k$

Replacing these conditions into our problem, we achieve the following optimization problem $$ {\max n_1\sqrt{\frac{2}{k}}+n_3\sqrt{\frac{1}{k}+m}+n_4\sqrt{\frac{1}{k}-m}+n_5\sqrt{\frac{1}{k}+\alpha} \\ m< |\alpha|< \frac{1}{k} \\ n_1+n_2+n_3+n_4+n_5=k \\ \sum_{i=1}^k\alpha_i^*=\frac{n_1-n_2}{k}+m(n_3-n_4)+n_5\alpha=0 } $$ equivalently $$ {\max n_1\sqrt{\frac{2}{k}}+n_3\sqrt{\frac{1}{k}+m}+n_4\sqrt{\frac{1}{k}-m}+n_5\sqrt{\frac{1}{k}+\alpha} \\ m< |\alpha|< \frac{1}{k} \\ n_1+n_2+n_3+n_4+n_5=k \\ 2n_1+n_3(1+mk)+n_4(1-mk)+n_5(1+\alpha k)=k. } $$ Since $n_2$ is now a free-running variable, another form of the problem is $$ {\max n_1\sqrt{\frac{2}{k}}+n_3\sqrt{\frac{1}{k}+m}+n_4\sqrt{\frac{1}{k}-m}+n_5\sqrt{\frac{1}{k}+\alpha} \\ m< |\alpha|< \frac{1}{k} \\ n_1+n_3+n_4+n_5\le k \\ 2n_1+n_3(1+mk)+n_4(1-mk)+n_5(1+\alpha k)=k. } $$

An intuitive upper bound is then $$ \max \{\sqrt{2k},\sqrt{k+mk^2},\sqrt{k-mk^2}\}=\sqrt{2k}. $$