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$
  • $\begingroup$ Are there any restrictions on $A_k$ and $B_k$ ? $\endgroup$ – learner Mar 3 '19 at 4:50
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$
  • $\begingroup$ Sorry for missing the multiplier. I meant $\frac{1}{M}$ instead of M. Just updated the question. $\endgroup$ – Scott Guan Mar 3 '19 at 5:21
  • $\begingroup$ @ScottGuan I have updated the answer. $\endgroup$ – Kavi Rama Murthy Mar 3 '19 at 5:37
  • $\begingroup$ Thank you for your answer. Appreciate it. $\endgroup$ – Scott Guan Mar 3 '19 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$
  • $\begingroup$ Sorry for missing the multiplier. I meant $\frac{1}{M}$ instead of M. Just updated the question. $\endgroup$ – Scott Guan Mar 3 '19 at 5:20
  • $\begingroup$ Updated the answer. $\endgroup$ – forgottenarrow Mar 3 '19 at 6:03
  • $\begingroup$ Thanks for the answer. It helped a lot. $\endgroup$ – Scott Guan Mar 3 '19 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$

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.