Let $n_1,\ldots,n_k$ be positive integers summing to $N$. What's an upper bound for $\sum_{i=1}^k1/\sqrt{n_i}$?

Question

Disclaimer. Sorry, I haven't looked into this one in any detail (as I should have). I was just thinking there out-of-be an elementary principle out here (pigeon-hole, Cauchy-Schwarz, Jensen, etc.). Which settles it in one line or so...

So, let $n_1,\ldots,n_k$ be positive integers summing to $N$.

Question

What's a good upper bound for $\sum_{i=1}^k\dfrac{1}{\sqrt{n_i}}$ in terms of $k$ and $N$?

Generalization

Let $p_1,\ldots,p_k \ge 0$ with $\sum_{i}^k p_i = 1$.

What's a good upper bound for $\sum_{i=1}^k \dfrac{1}{\sqrt{n_i}}p_i$ ?

---

Edit

Ok, I just figured out I've asking the wrong question all along. I won't get very far trying to bound each term of an entangled sum individually...

So, here is the full business: Let $T$ and $k$ be positive integers. A each round $t=1,2,\ldots$, exactly one item from $\{1,\ldots,k\}$, say $i_t$, is observed. Let $n_t(i)$ be the total number of times object was $i$ observed upto (and including) time $t$.

Question. For a positive integer $T$, what is a good upper bound for $S_T := \sum_{t=1}^T\dfrac{1}{\sqrt{n_t(i_t)}}$.

My rough guess is that this should be something like $C\sqrt{kT}$.

---

Edit

Below, I solve the restated question (the first Edit).

By the pigeon-hole principle,

$$ \begin{split} S_T:=\sum_{t=1}^Tf(n_t(i_t))&=\sum_{t=1}^T\sum_{i=1}^k 1_{\{i_t=i\}}f(n_t(i))=\sum_{i=1}^k\sum_{t=1}^T1_{\{i_t=i\}}f(n_t(i)) = \sum_{i=1}^k\sum_{n=1}^{n_T(i)} f(n) \end{split} $$

Case 1: $f$ nonnegative and concave.

By Jensen's inequality, one has $$ \begin{split} S_T=\sum_{i=1}^k\sum_{n=1}^{n_T(i)} f(n) \le kT\sum_{i=1}^k\sum_{n=1}^Tf(n)\frac{1}{kT} \le kTf(kT), \end{split} $$

Case 2: $f(x) := x^{-\alpha}$, $0 < \alpha \le 1$ It is an elementary result that

If $f(x)$ is a continuous positive decreasing function and $a_n =f(n)$ then $$ a_n + \int_1^n f(x)dx \le a_1+a_2+\cdots+a_n \le a_1+\int_1^nf(x)dx. $$

Thus, if $f(x) = x^{-\alpha}$ with anti-derivative $g_\alpha(x) := (1-\alpha)^{-1}x^{1-\alpha}$ if $0 < \alpha < 1$ and $g_1(x):=\log(x)$, we can compute the above integral to get $$ \sum_{n=1}^{n_T(i)} f(n) \le 1 + g_\alpha(n_T(i))-g_\alpha(1). $$

Now, using the theory of Lagrange multipliers, it's not hard to arrive at the fact that $\sum_{i=1}^kg_\alpha(n_T(i))$ is maximized when the $n_T(i)$ are equal for all $i$. Thus

$$ \begin{split} S_T &= \sum_{i=1}^k \sum_{n=1}^{n_T(i)} f(n) \le \underset{\sum_{i=1}^kn_T(i) = T}{\max}\;\sum_{i=1}^k (g_\alpha(n_T(i)+1-g_\alpha(1))\\ &\le \begin{cases}\frac{1}{1-\alpha}(k^\alpha T^{1-\alpha}+(\alpha-1)k)=\mathcal O(k^\alpha T^{1-\alpha}),&\mbox{ if }0 < \alpha < 1,\\ \log(T) + k=\mathcal O(\log(T)),&\mbox{ if }\alpha = 1.\end{cases} \end{split} $$

Thus if $f(n):=1/\sqrt{n}$ as in the original question, we get $S_T \le 2\sqrt{kT}$ as claimed.

Answer 1

To maximize your sum you would want the denominators to be as small as possible; since each $n_k$ is a natural number we know that they are all at least $1$, and so the trivial upper bound of your sum is $k$.

I would wager that we can do better, though I am not really in a mood to try and prove this. What compositions of $N$ into $k$ parts are good candidates for maximization of this sum? Presumably it is the composition $(1,1,\ldots,N-k+1)$ and others resulting from permuting those entries around. This would give you an upper bound of $k-1+\frac{1}{\sqrt{N-k+1}}$, which should be tight.

For your generalization, we have a trivial upper bound of $1$, which follows by the same reasoning for the trivial upper bound above. A tight upper bound is probably going to be something like the following: $$ 1-\min\{p_{k}\}+\frac{\min\{p_k\}}{\sqrt{N-k+1}} $$

If the trivial bounds are not good enough, then I would probably try and prove these tight bounds with some multidimensional optimization techniques; you have some function defined on fairly nice bounded region of $\mathbb{R}^k$, so something probably works nicely.