2
$\begingroup$

I wanted to use the following inequality in my research, but I cannot prove whether it is correct or not.

$\frac{\sum_{k=1}^{M} A_{k}}{\sum_{k=1}^{M} B_{k}} \leq \frac{1}{M} \sum_{k=1}^{M} \frac{A_{k}}{B_{k}}$, where $A_{k}, B_{k} \geq 0$

I tested this inequality on random numbers generated by MATLAB and the inequality seemed to hold. Anyone has some ideas, how to prove or disprove it? Thank you guys in advance.

$\endgroup$
1
  • $\begingroup$ Are there any restrictions on $A_k$ and $B_k$ ? $\endgroup$
    – learner
    Mar 3, 2019 at 4:50

3 Answers 3

4
$\begingroup$

The edited version is false: take $M=2$ and let $A_1 \to 0$. The inequality becomes $\frac {A_2} {B_1+B_2} \leq \frac 1 2\frac {A_2} {B_2}$. But this is false if $B_1 <B_2$.

Answer for the old version: assuming that $A_k$'s and $B_k$'s are positive there is a stronger inequality: let $C$ be the maximum of the numbers $\frac {A_k} {B_k}$. Then $\sum A_k \leq C\sum b_k$ so $\frac {\sum A_k} {\sum B_k} \leq C \leq \sum \frac {A_k} {B_k}$.

$\endgroup$
3
  • $\begingroup$ Sorry for missing the multiplier. I meant $\frac{1}{M}$ instead of M. Just updated the question. $\endgroup$ Mar 3, 2019 at 5:21
  • $\begingroup$ @ScottGuan I have updated the answer. $\endgroup$ Mar 3, 2019 at 5:37
  • $\begingroup$ Thank you for your answer. Appreciate it. $\endgroup$ Mar 3, 2019 at 15:06
1
$\begingroup$

It's false generally, but true in some cases. I don't have a full characterization of when it's true. Consider Titu's Lemma (a consequence of the Cauchy-Schwartz inequality. See the Cauchy-Schwartz wikipedia page).

$$\frac{(\sum_{k=1}^M u_k)^2}{\sum_{k=1}^M v_k} \leq \sum_{k=1}^M\frac{u_k^2}{v_k}.$$

If $A_k = u_k = 1$ and $B_k = v_k$ for all $k$, then we're done. This implies

$$M\frac{M}{\sum_{k=1}^M B_k} \leq \sum_{k=1}^M \frac{1}{B_k}.$$

Now for a specific counterexample. Let $A_1 = 20200$ and $A_k=1$ for $k=2,\dots,11$. Let $B_1 = 10000$ and $B_k = 10$ for $k=2,\dots,11$. Of course, $M=11$. Then,

\begin{align*} &\frac{\sum_{k=1}^M A_k}{\sum_{k=1}^M B_k} = \frac{20210}{10100} \geq 2.\\ &\frac{1}{M}\sum_{k=1}^M\frac{A_k}{B_k} = \frac{1}{11}\left(2.02 + 10*0.1\right) = \frac{3.02}{11} < 1. \end{align*}

I just chose some extreme numbers to make an example. You could probably construct a cleaner counterexample later. Here's how I constructed it. Start with arbitrary positive $B_k$ (assume the $B_k$ are not all equal to each other.) and let $A_k = 1$ for all $k$. In this case, we know the inequality holds. Then take the partial derivatives with respect to $A_k$ for some $k$ such that $B_k > \overline{B}:=\frac{1}{M}\sum_{k=1}^M B_k$. Then the derivative on the left side of the inequality is $\frac{1}{M\overline{B}}$ and the derivative on the right side of the inequality is $\frac{1}{MB_k} < \frac{1}{M\overline{B}}$. So for a counterexample, make $A_k$ large if $B_k$ is large.

$\endgroup$
3
  • $\begingroup$ Sorry for missing the multiplier. I meant $\frac{1}{M}$ instead of M. Just updated the question. $\endgroup$ Mar 3, 2019 at 5:20
  • $\begingroup$ Updated the answer. $\endgroup$ Mar 3, 2019 at 6:03
  • $\begingroup$ Thanks for the answer. It helped a lot. $\endgroup$ Mar 3, 2019 at 15:06
1
$\begingroup$

Just complementing the other answers. When it works, it is known as Chebyshev's inequality. For example $A_1\geq A_2\geq ... \geq A_M \geq 0$ and $\color{red}{B_M\geq B_{M-1}\geq ... \geq B_1>0}$ then $$\frac{1}{B_1}\geq \frac{1}{B_2}\geq ... \geq \frac{1}{B_M}>0\Rightarrow \color{red}{\frac{A_1}{B_1}\geq \frac{A_2}{B_2}\geq ... \geq \frac{A_M}{B_M}}$$ as a result $$0\leq M\left(\sum\limits_{k=1}^M A_k\right)= \color{blue}{M\left(\sum\limits_{k=1}^M \frac{A_k}{B_k}\cdot B_k\right)\overset{Ch.in.}{\leq} \left(\sum\limits_{k=1}^M \frac{A_k}{B_k}\right)\left(\sum\limits_{k=1}^M B_k\right)}$$ and finally $$\frac{\sum\limits_{k=1}^M A_k}{\sum\limits_{k=1}^M B_k} \leq \frac{1}{M}\left(\sum\limits_{k=1}^M \frac{A_k}{B_k}\right)$$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .