Given a sequence of nonnegative numbers $t_1,\ldots, t_n\geq 0$,it satisfies that $\sum_{i=1}^n t_i=1$, and $$\left|t_1-\frac{t_n+t_2}{2}\right|+\left(\sum_{i=2}^{n-1}\left|t_i-\frac{t_{i-1}+t_{i+1}}{2}\right|\right)+\left|t_n-\frac{t_{n-1}+t_1}{2}\right|=\epsilon\leq 1,$$ where $\epsilon$ is a small constant. What is the best upper bound on $$\left(\sum_{i=1}^{n-1}\left|t_{i+1}-t_i\right|\right)+\left|t_n-t_1\right|?$$ Can we have an upper bound only depends on $\epsilon$? I tried several examples, the upper bounds are $O(\sqrt{\epsilon})$.


Consider a triangle wave with step size $\frac\epsilon2$. Then $\left|t_i-\frac{t_{i-1}+t_{i+1}}{2}\right|=0$ for all $i$ except at the top and bottom of the wave, where that value equals $\frac\epsilon2$. We then have $$\left(\sum_{i=1}^{n-1}\left|t_{i+1}-t_i\right|\right)+\left|t_n-t_1\right| = n\frac\epsilon2.$$

Illustration: enter image description here

  • $\begingroup$ What do you mean triangle waves? Note that $t_i\geq 0$. If $|t_i-\frac{t_{i-1}+t_{i+1}}{2}|=0$ for $i=2\ldots, n-1$, then $t_1,\ldots, t_n$ are monotone. $\endgroup$ – user07001129 Dec 21 '15 at 22:29
  • $\begingroup$ I mean something like $$t_i = \frac1n + \frac{n\epsilon}8 - \frac\epsilon2\left|i-\left(\frac n2+1\right)\right|.$$ Then $\left|t_i-\frac{t_{i-1}+t_{i+1}}{2}\right| = 0$ only when $i=1$ (the trough) and $i=\frac n2+1$ (the peak). $\endgroup$ – Théophile Dec 21 '15 at 23:00
  • $\begingroup$ I see. In this case, $\epsilon=O(\frac{1}{n^2})$ as $\sum_i t_i=1$, then the bound $\frac{n}{2}\epsilon=O(\sqrt{\epsilon})$. $\endgroup$ – user07001129 Dec 21 '15 at 23:12
  • $\begingroup$ Yes, that seems right. $\endgroup$ – Théophile Dec 21 '15 at 23:24

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.