Upper bound on discrepancy of two sums

86 Views Asked by At

Can you help upper bounding this? \begin{equation} \left|\frac{\sum_{i=1}^{m} a_i}{\sum_{i=1}^{m} t_i} - \frac{\sum_{i=1}^{m} b_i}{\sum_{i=1}^{m} s_i}\right| \leq ? \end{equation} where for each $i$ we have: \begin{equation} \left| \frac{a_i}{t_i} - \frac{b_i}{s_i} \right| \leq \mathcal{D}_i \leq 1 \end{equation} $$0 \leq \frac{a_i}{t_i} \leq 1$$ $$0 \leq \frac{b_i}{s_i} \leq 1$$

My conjecture is something $\mathcal{O}(D_i)$ based on some special cases, but generally, I cannot prove it.

Basically, each element of the pair ($a_i/t_i$, $b_i/s_i$) is a normalized value in $[0,1]$, and we have the discrepancy of these two elements. Now we want to bound the discrepancy of the cumulative (not the right term for this, what to use instead?) version of the discrepancy.

1

There are 1 best solutions below

5
On BEST ANSWER

The bound is $1$, even if $D_i=0$. To be specific, let $n=2, \frac {a_1}{t_1}=\frac {b_1}{s_1}=1, \frac {a_2}{t_2}=\frac {b_2}{s_2}=0$ Now if we let $a_1=t_1=1000$ while $b_1=s_1=1$ and $b_2=0, s_2=1000$ while $a_1=0,t_2=1$ we will have $$\begin{equation} \left|\frac{\sum_{i=1}^{m} a_i}{\sum_{i=1}^{m} t_i} - \frac{\sum_{i=1}^{m} b_i}{\sum_{i=1}^{m} s_i}\right| =\left|\frac{1000+0}{1000+1}-\frac{1+0}{1+1000}\right|=\frac {999}{1001} \end{equation}$$ We can clearly get as close to $1$ as we would like by this approach even though $D_i=0$.