accelerated convergence to the mean using quadratic weights

Question

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

Answer 1

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).

Answer 2

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.)