# Ratio of Sequences Sum Inequality

I have two real sequences $a_1,a_2,\dots,a_n$ and $b_1, b_2, \dots, b_n$, with $a_i > 0$ and $1 \leq b_i < n$, and I'm looking for a lower bound of $\sum_i \frac{a_i}{b_i}$ in terms of $\sum_i a_i$ and $\sum_i b_i$. There is also an extra contraint that if $b_i$ is large then $a_i$ is small (something like $a_i < b_i/e^{b_i})$

They're not necessarily monotonic, so I can't use Chebyshev's inequality. Is there something else that I'm missing?

Edit:

After thinking a bit more about the problem I get that, as stated, there are instances where $\sum \frac{a_i}{b_i} = \frac{\sum a_i}{\sum b_i - (n-1)}$.

That is if $a_i = \epsilon$ for $1 \leq i \leq n-1$ and $a_n = \sum a_i - (n-1)\epsilon$, and $b_i = 1$ for $1 \leq i \leq n-1$ and $b_n = \sum b_i - (n-1)$. Then, as long as $\sum a_i < \frac{\sum b_i - (n-1)}{e^{\sum b_i - (n-1)}} + (n-1)\epsilon$, we get the above as $\epsilon$ goes to $0$. Is this tight as long as the inequality is satisfied? If it isn't satisfied, then $\sum a_i$ is larger than $\frac{\sum b_i - (n-1)}{e^{\sum b_i - (n-1)}}$, implying that the lower bound should be larger.

So to tweak the problem a bit more, what if the inequality isn't satisfied (for small $\epsilon$)? Say for $\sum a_i = 1$ and $\sum b_i = 2n$?

-

Here is an old cheap trick that may be helpful. Assume that $\sum_i a_i=A$, $\sum_i b_i=B$ and $a_i\le b_if(b_i)$ where $f$ is a decreasing function tending to $0$. Choose $b$ so that $f(b)=\frac{A}{2B}$. Then $\sum_{i:b_i>b}a_i\le f(b)\sum_{i:b_i>b}b_i\le f(b)B\le\frac A2$, so $\sum_i\frac{a_i}{b_i}\ge \frac A{2b}$.

For $f(x)=e^{-x}$, this results in the estimate $\sum_i\frac{a_i}{b_i}\ge \frac A{2\log\tfrac{2B}A}$. It is not optimal, of course, but may suffice for your purposes. If it doesn't, then tell in what range you'd like to improve it.

-
Thanks, that looks useful. Ideally, I'd like a bound that doesn't tend to $0$ with large $n$ and constant $A$, but that may not be possible. –  Michael Biro Dec 16 '11 at 3:49
That's totally out of question: take large $M>0$, choose $n/M$ b's to be $M$ and the rest $1$ (so that $B$ is just about $2n$). Choose $n/M$ a's to be $AM/n$ and the rest $0$. Then, if $n$ is large enough, all restrictions hold but the sum of ratios is just $A/M$. Either you add some additional restrictions, or you'll have to live with some decay. –  fedja Dec 16 '11 at 5:19
OK, I see. Thanks for the help. –  Michael Biro Dec 16 '11 at 8:19

You have $\sum a_i/b_i \le \sum_i \left(a_i/\sum_j b_j\right) = \sum_i a_i / \sum_i b_i$.

This is basically sharp: if you take $a_1=\epsilon$, $a_i=\epsilon^3$ for $i>1$, $b_1=1$ and $b_i=\epsilon$ for $i>1$. Then your constraint is satisfied; $\sum a_i/b_i=\epsilon+(n-1)\epsilon^2$, while $\sum a_i=\epsilon+(n-1)\epsilon^3$ and $\sum b_i=1+(n-1)\epsilon$.

For $\epsilon$ sufficiently close to 0, the two expressions are close.

-
Thanks for the answer. I have that bound already, but I don't think it's tight. One of the bounds is that $b_i \geq 1$, so we can't have $b_i = \epsilon$ and $\epsilon$ close to $0$. –  Michael Biro Dec 15 '11 at 16:08
I think the tight bound is $\sum_ia_i/(\sum_ib_i-(n-1))$. –  Emil Jeřábek Dec 15 '11 at 16:18
Well, that’s tight if $\sum_ib_i< 2n-1$. If $\sum_ib_i$ is larger, it is more tricky. –  Emil Jeřábek Dec 15 '11 at 16:24
Yes, I have an instance of $\sum_i a_i/(\sum_i b_i - (n-1))$, but I haven't been able to show that it's tight. I'm going to edit the question to show this. –  Michael Biro Dec 15 '11 at 16:24
Shouldn't that be $\ge$ rather than $\le$? –  Dan Stahlke May 16 '13 at 19:21