Lower bound on the sum of square roots of probabilities that are upper and lower bounded

Question

Let $p_i$ with $i=1,\ldots,n$ be probabilities, that is $\sum_i p_i =1$. Moreover each term is bounded according to $$ \frac{1}{n}-\epsilon \leq p_i \leq \frac{1}{n}+\epsilon $$ I want to find the minimum in terms of $\epsilon$ of the following function $$ f(\vec{p}) = \sum_{i=1}^{n} \sqrt{\frac{p_i}{n}} $$ Is it true that this occurs when one term is exactly $\frac{1}{n}-\epsilon$, one is $\frac{1}{n}+\epsilon$ and the rest are just $\frac{1}{n}$? So, in other words can I show that $$ f(\vec{p}) \geq \frac{1}{\sqrt{n}}\left(n-2+ \sqrt{\frac{1}{n}+\epsilon}+\sqrt{\frac{1}{n}-\epsilon}\right) $$ One can explicitly show that this is true in the case $n=2$ but I am not sure how/if this generalizes for arbitrary $n$?

Answer 1

If $n$ is even:

From the given condition, we have $$\sqrt{\frac{1}{n}\left(\frac{1}{n}-\epsilon\right)}\le \sqrt{\frac{p_i}{n}}\le \sqrt{\frac{1}{n}\left(\frac{1}{n}+\epsilon\right)} \hspace{1cm} \text{for all }1\le i\le n $$ $$\Longrightarrow \left(\sqrt{\frac{p_i}{n}} -\sqrt{\frac{1}{n}\left(\frac{1}{n}-\epsilon\right)} \right) \left(\sqrt{\frac{p_i}{n}} -\sqrt{\frac{1}{n}\left(\frac{1}{n}+\epsilon\right)} \right)\le0 \hspace{1cm} \text{for all }1\le i\le n $$ $$\Longrightarrow\frac{p_i}{n} -\sqrt{\frac{1}{n}} \left(\sqrt{\frac{1}{n}-\epsilon}+\sqrt{\frac{1}{n}+\epsilon} \right) \sqrt{\frac{p_i}{n}}+\frac{1}{n}\sqrt{\frac{1}{n^2}-\epsilon^2} \le 0 \hspace{1cm} \text{for all }1\le i\le n \tag{1}$$

Make the sum of $(1)$ for all $i\in\{1,..,n \}$, and use the condition $\sum_i^np_i=1$, we deduce $$\frac{1}{n} -\sqrt{\frac{1}{n}} \left(\sqrt{\frac{1}{n}-\epsilon}+\sqrt{\frac{1}{n}+\epsilon} \right)\color{red}{\sum_{i=1}^n \sqrt{\frac{p_i}{n}} }+\sqrt{\frac{1}{n^2}-\epsilon^2} \le 0$$

$$\iff \color{red}{\sum_{i=1}^n \sqrt{\frac{p_i}{n}} \ge \frac{\frac{1}{n}+\sqrt{\frac{1}{n^2}-\epsilon^2}}{\sqrt{\frac{1}{n}} \left(\sqrt{\frac{1}{n}-\epsilon}+\sqrt{\frac{1}{n}+\epsilon} \right)} }$$

The equality occurs if and only if $p_i = \frac{1}{n}-\epsilon$ or $p_i = \frac{1}{n}+\epsilon$.

If $n$ is odd : still don't know how to do, I guess we can do as follows:

The first condition is equal to $$\sum_{i=1}^{n-1}p_i = 1-p_{n}$$

Apply the same method above, we may deduce that $$\sum_{i=1}^{n} \sqrt{\frac{p_i}{n}} =\sqrt{\frac{p_n}{n}}+ \sum_{i=1}^\color{red}{n-1} \sqrt{\frac{p_i}{n}} \ge \sqrt{\frac{p_n}{n}} + \frac{\frac{\color{red}{1-p_n}}{n}+\sqrt{\frac{1}{n^2}-\epsilon^2}}{\sqrt{\frac{1}{n}} \left(\sqrt{\frac{1}{n}-\epsilon}+\sqrt{\frac{1}{n}+\epsilon} \right)} $$

Answer 2

I am just going to add another approach, even though @NN2 's answer is better. One can use a reverse Cauchy-Schwartz inequality, namely the Pólya–Szegő inequality, $$ \left(\sum_{k=1}^{n} a_k b_k \right)^2 \geq \frac{1}{C} \sum_{k=1}^{n} a_k^2 \sum_{k=1}^{n} b_k^2 $$ with $$ C=\frac{1}{4}\left(\sqrt{\frac{M_1 M_2}{m_1 m_2}} +\sqrt{\frac{m_1 m_2}{M_1 M_2}}\right)^2 $$ and $0<m_1\leq a_i \leq M_1$,$0<m_2\leq b_i \leq M_2$.

Taking $a_i=\sqrt{p_i}$ and $b_i=\frac{1}{\sqrt{n}}$, we find $$ f(\vec{p})^2 \geq \frac{2\sqrt{\frac{1}{n^2}-\epsilon^2}}{\frac{1}{n}+\sqrt{\frac{1}{n^2}-\epsilon^2}} \,, $$ which seems to give the same bound as in @NN2's answer. However, the derivation is not elegant as it depends on the knowledge of that particular inequality.

In fact, in the following reference there are more reverse Cauchy-Schwartz-type inequalities but I haven't checked if all bounds coincide in this case. https://rgmia.org/papers/v7n1/ReverseSchwarz.pdf

EDIT: I made a mistake and even though the bounds are pretty similar when $n << 1/\epsilon$, for $n\sim 1/\epsilon$ my bound is smaller and less tight. I have added a plot where I compare the two for values of $n$ up to 1000 and with $\epsilon=1/1000$. The curve in blue is my bound while in red the one from @NN2's answer.

Answer 3

For odd $n$:

Problem: Let $n\ge 3$ be a fixed odd number. Let $0 < \epsilon\le \frac{1}{n}$ be fixed. Let $p_i\ge 0, i = 1, 2, \cdots, n$ with $\sum_{i=1}^n p_i = 1$ and $\frac{1}{n} - \epsilon \le p_i \le \frac{1}{n} + \epsilon$. Find the minimum of $$f(p) := \frac{1}{\sqrt n}\sum_{i=1}^n \sqrt{p_i}.$$

Answer: The minimum of $f(p)$ is given by $$\frac{1}{\sqrt n} \left(\frac{n-1}{2}\sqrt{\frac{1}{n} - \epsilon} + \frac{n-1}{2}\sqrt{\frac{1}{n} + \epsilon} + \sqrt{\frac{1}{n}}\right)$$ when $p_1 = p_2 = \cdots = p_{(n-1)/2} = \frac{1}{n} - \epsilon$ and $p_{(n+1)/2} = \frac{1}{n}$ and $p_{(n+1)/2 + 1} = p_{(n+1)/2 + 2} = \cdots = p_n = \frac{1}{n} + \epsilon$.

Proof:

WLOG, assume that $p_1 \le p_2 \le \cdots \le p_n$.

Note that if $\frac{1}{n} - \epsilon < x \le y < \frac{1}{n} + \epsilon$, then there exists $t > 0$ such that $\frac{1}{n} - \epsilon < x - t < y + t < \frac{1}{n} + \epsilon$ and $$\sqrt{x - t} + \sqrt{y + t} < \sqrt{x} + \sqrt{y}.$$ (Note: $\iff 2\sqrt{(x - t)(y+t)} < 2\sqrt{xy} \iff t(t - x + y) > 0$.)
In other words, if there exist $i\ne j$, $p_i, p_j \in (1/n - \epsilon, 1/n + \epsilon)$, then $(p_1, p_2, \cdots, p_n)$ is not optimal. Thus, at minimum, there exists at most one $p_j \notin \{1/n - \epsilon, 1/n + \epsilon\}$

Thus, at minimum, there exists $k\in \{0, 1, 2, \cdots, n\}$ such that $$p_1 = p_2 = \cdots = p_k = \frac{1}{n} - \epsilon$$ and $$p_{k+2} = p_{k+3} = \cdots = p_n = \frac{1}{n} + \epsilon.$$

From $\sum_{k=1}^n p_i = 1$, we have $$k(1/n - \epsilon) + (n - k - 1)(1/n + \epsilon) + p_k = 1$$ which results in $p_k = \frac{1}{n} + \epsilon(2k + 1 - n)$.

From $\frac{1}{n} - \epsilon \le p_k \le \frac{1}{n} + \epsilon$, we have $n/2 - 1\le k \le n/2$. Since $n$ is odd, we have $k = \frac{n-1}{2}$. Thus, $p_{(n-1)/2} = \frac{1}{n}$, and $p_1 = p_2 = \cdots = p_{(n-1)/2} = \frac{1}{n} - \epsilon$, and $p_{(n-1)/2+1} = p_{(n-1)/2+2} = \cdots = p_n = \frac{1}{n} + \epsilon$.

We are done.