Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

If the sequence $x_1,x_2,\dots$ is periodic, the unweighted averages $(\sum_{i=1}^n x_i)/n$ converge to the asymptotic average of the $x_n$'s with error $O(1/n)$, but the weighted averages $(\sum_{i=1}^n i(n+1-i)x_i)/(n(n+1)(n+2)/6))$ converge even more quickly, with error $O(1/n^2)$.

This fact is easy to prove (e.g. first prove it for $(x_n) = (\zeta^n)$ with $\zeta$ an arbitrary root of unity and then appeal to linearity), but it's something I stumbled upon on my own, and I don't really understand what's going on. Can anyone provide a context for this fact? My guess is that it must be well-known to people who study series-convergence (and acceleration thereof), and also well-known to Fourier analysts, though possibly in disguised form. (Speaking of disguises: This question is related to my earlier question A specific Dedekind-esque sum ; in my earlier post, the relevant sequence is almost-periodic rather than periodic, and the discrepancy goes down like $O((\log n)/n^2)$ rather than $O(1/n^2)$.)

I suspect that $O(1/n^2)$ is the end of the line, in the sense that no weighted average of $x_1,\dots,x_n$ with fixed coefficients will differ from the asymptotic average of the $x_n$'s by $O(1/n^c)$ for any $c>2$, and I might even try to give a proof using the geometry of numbers, but I suspect this is old stuff and would appreciate some pointers.

Thanks!

Jim Propp

share|improve this question

2 Answers 2

up vote 3 down vote accepted

Just think a bit of what the Poisson summation formula gives you for the function $\varphi_n(x)=\varphi(x/n)$ where $\varphi$ is some not too bad compactly supported function (you can view the weighted $n$-th sum for the periodic sequence as the finite weighted sum of several infinite sums of values of $\varphi_n$ over arithmetic progressions). The real end of line is almost exponential in $n$.

Edit: Suppose that $\varphi$ is reasonably smooth and has integral $1$ (the characteristic function of an interval is not falling under this argument formally but the function $[x(1-x)]_+$ already is). Now, let $P$ be the period and let the sequence be $a_0,a_1,\dots,a_{P-1},a_0,a_1,\dots$. Then the $\varphi$ weighted sum $$ S_n=\frac 1n \sum_k\varphi_n(k)a_k=\frac 1P\sum_{k=0}^{P-1}a_k\sigma_k $$ where $$ \sigma_k=\frac Pn\sum_m\varphi_n(k+mP)= \sum_m\widehat\varphi(mn/P)e^{2\pi i mk/P} $$ by the Poisson summation formula. Now, $|\sigma_k-1|\le\sum_{m\ne 0}|\widehat\varphi(mn/P)|$ and, if $\widehat\varphi$ decays fast (which you can always achieve by making $\varphi$ smooth enough), this bound decays fast with $n$.

You may object that one has to divide not by $n$ but by $\sum_k \varphi_n(k)$ but it is close to $n$ with the same relative precision (just run the same argument for the sequence consisting of all ones).

share|improve this answer
    
Thanks, Fedja! I am having a little trouble unpacking your answer, though. I tried taking $\phi$ to be the indicator function of an interval, but did not gain enlightenment (maybe your stricture "not too bad" rules out discontinuities?). If Fedja or anyone else can give me a less terse answer to the first part of my question, I would be grateful. Pointers to the literature would also be appreciated. Also, regarding the second part of my question, I would like to know whether the weights $i(n+1-i)/(n(n+1)(n+2)/6)$ are indeed optimal. –  James Propp Aug 29 '10 at 1:06
    
Sorry, James. I didn't mean to be cryptic but I decided that you would appreciate a quick but terse answer more than a delayed but expanded one (quick and expanded would be the best, of course, but it was out of question at that moment). See if you have enough details now. –  fedja Aug 29 '10 at 2:00
    
Yes, that helps a lot! –  James Propp Sep 2 '10 at 0:55

My original suspicion that $O(1/n^2)$ was "the end of the line" was wrong: smoothing the sequence of multipliers gives improvements beyond $O(1/n^2)$. For instance, $(\sum_{i=1}^n [i(n+1-i)]^2 x_i)/(\sum_{i=1}^n [i(n+1-i)]^2)$ converges to the asymptotic average of the $x_i$'s with error $O(1/n^3)$.

Fedja's post gave me the right point of view. Thanks, Fedja!

(I'd still appreciate references to the literature, if anyone knows of anything relevant.)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.