Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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$?

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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.

share|improve this answer
    
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
2  
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.

share|improve this answer
    
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
1  
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
1  
Shouldn't that be $\ge$ rather than $\le$? –  Dan Stahlke May 16 '13 at 19:21

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.