Upper bound on the sum of means.

116 Views Asked by At

I was looking at a previous post, and was curious to the following extension:

Suppose I have positive integers $x_1,\dots,x_n$, and another positive integer $m<n$. If we were to arbitrarily group the indices into two disjoint sets $\mathcal{A}$ and $\mathcal{B}$, such that $|\mathcal{A}|=m$ and $|\mathcal{B}|=n-m$ (also $A\cup B=\{1,\dots,n\}$), is there an upper bound as a function of $\frac{1}{n}\sum_{i=1}^nx_i$ (or $\frac{1}{n-m}\sum_{i=1}^nx_i$) for the following sum of means when $m=o(n)$? \begin{align*} \frac{1}{m}\sum_{i\in\mathcal{A}}x_i+\frac{1}{n-m}\sum_{j\in\mathcal{B}}x_j. \end{align*} For example, if $n=m-n$ (i.e., $m=\frac{n}{2}$), then \begin{align*} \frac{1}{m}\sum_{i\in\mathcal{A}}x_i+\frac{1}{n-m}\sum_{j\in\mathcal{B}}x_j =\frac{2}{n}\sum_{i=1}^nx_i. \end{align*} I'm curious about the upper bound for the more general case of $m=o(n)$.

Clarification: I'm considering the scenario where the groups are already given to us (we can't choose what to put in each group). I was wondering if we can get an upper bound of constant * $\frac{1}{n}\sum_{i=1}^nx_i$ (or $\frac{1}{n-m}\sum_{i=1}^nx_i$), i.e., something similar to the case of $m=n-m$.

2

There are 2 best solutions below

0
On BEST ANSWER

There is certainly no constant $C$ for which there is an upper bound of the form $Cn^{-1}\sum_1^nx_i$. Take $m=n-1$, take $x_1,x_2,\dots,x_{n-1}$ to be small, say, $x_1=x_2=\cdots=x_{n-1}=1$, and $x_n$ to be some large number $L$. Then $n^{-1}\sum_1^nx_i=(n-1+L)/n=(L/n)+1-(1/n)$, while the other sum is $1+L$, which is almost $n$ times as big.

4
On

Assume $m\lt n-m$. Put the $m$ largest in A and the rest in B. This will give you the upper bound. Proof: obvious - any switch will make the sum lower.

Detail of proof: $x_k \in A$ and $x_j\in B$ $\frac{x_k}{m}+\frac{x_j}{n-m}\gt \frac{x_j}{m}+\frac{x_k}{n-m}$ since $\frac{x_k-x_j}{m}\gt \frac{x_k-x_j}{n-m}$.

Obvious note: $m\gt n-m$, switch roles.