tightest upper bound of a rational function

Question

Consider a sequence $S=\{s_i\}^n_i$, where $s_i$ are integers s.t $\sum^n_{i=0}s_i\neq 0$.

Is it possible to find a polynomial upper bound on the ratio: $$\left|\frac{\sum^n_{i=1}i\cdot s_i}{\sum^n_{i=0}s_i}\right|$$

Answer 1

Writing $\|s\|_\infty = \max_i |s_i|$, you have the trivial upper bound $$ \left|\frac{\sum^n_{i=1}i\cdot s_i}{\sum^n_{i=0}s_i}\right| \leq \left|\sum^n_{i=1}i\cdot s_i\right| \leq n^2\|s\|_\infty. $$ Now let's look at a lower bound. Suppose for simplicity that $n$ is even, pick some $\|s\|_\infty$, and let $$ s_i = \begin{cases}1 &\text{if $i = 0$,}\\ -\|s\|_\infty &\text{if $1 \leq i \leq \frac n2$,}\\ \|s\|_\infty &\text{if $\frac n2 < i \leq n$.} \end{cases} $$ Then $$ \left|\frac{\sum^n_{i=1}i\cdot s_i}{\sum^n_{i=0}s_i}\right| = \|s\|_\infty \left(\sum_{i=n/2+ 1}^n i - \sum_{i = 1}^{n/2}i\right) = \|s\|_\infty \left(\frac n2\right)^2 = \frac14 \|s\|_\infty n^2. $$ This shows that up to a constant, this upper bound is the best you can do.