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?


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.

  • $\begingroup$ 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. $\endgroup$ Dec 16 '11 at 3:49
  • 2
    $\begingroup$ 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. $\endgroup$
    – fedja
    Dec 16 '11 at 5: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.

Should be $\sum a_i/b_i \ge \sum_i \left(a_i/\sum_j b_j\right) = \sum_i a_i / \sum_i b_i$.

  • $\begingroup$ 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$. $\endgroup$ Dec 15 '11 at 16:08
  • 1
    $\begingroup$ I think the tight bound is $\sum_ia_i/(\sum_ib_i-(n-1))$. $\endgroup$ Dec 15 '11 at 16:18
  • $\begingroup$ Well, that’s tight if $\sum_ib_i< 2n-1$. If $\sum_ib_i$ is larger, it is more tricky. $\endgroup$ Dec 15 '11 at 16:24
  • $\begingroup$ 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. $\endgroup$ Dec 15 '11 at 16:24
  • 3
    $\begingroup$ Shouldn't that be $\ge$ rather than $\le$? $\endgroup$ May 16 '13 at 19:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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