0
$\begingroup$

Given the following:

  • $\sum_{i=1}^{n} a_i = 1, a_i \geq 0\;\forall i$,
  • $\sum_{i=1}^{n} b_i = 1, b_i \geq 0\;\forall i$,
  • $\sum_{i=1}^{n} |a_i - b_i| \leq e$ where $e \ll 1$,

what is the upper bound on:

\begin{equation*} \sum_{i,j=1}^{n} |a_i\cdot a_j - b_i\cdot b_j|? \end{equation*}

I am almost sure it is bounded by $2e$ but am not able to prove it.

  • 2
    Try to write $a_ia_j−b_ib_j as $a_ia_j−b_ia_j+b_ia_j - b_ib_j$ and use the triangle inequality.2010-08-08
  • 2
    Got it. Thanks a lot.2010-08-08

1 Answers 1

3

$\sum_{i,j=1}^{n} |a_i\cdot a_j - b_i\cdot b_j|$ = $\sum_{i,j=1}^{n} |a_i\cdot a_j - b_i.a_j + b_i.a_j - b_i\cdot b_j|$

$= \sum_{i,j=1}^{n} |(a_i - b_i).a_j + (a_j - b_j).b_i|$

$\leq \sum_{i,j=1}^{n} [|(a_i - b_i).a_j| + |(a_j - b_j).b_i|]$ ........ (using the triangle inequality ,i.e., $|x+y| \leq |x|+|y|$)

$= (\sum_{i,j=1}^{n} |(a_i - b_i).a_j|) + (\sum_{i,j=1}^{n} |(a_j - b_j).b_i|)$

$\leq (\sum_{i}^{n} |(a_i - b_i).1|) + (\sum_{i}^{n} |e.b_i|)$ .... (By solving the inner summation over j and using the given (in)equations).

$\leq e + e$
$= 2.e$

Hence Proved.