Question

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

Answer 1

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.

Answer 2

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.