Let $a\_n$ be a nonnegative sequence that Cesaro converges to $K > 0$. We recall this means


$$\frac{1}{N} \sum\_{n = 1}^N a\_n \to K$$


as $N \to \infty$.


Suppose $a\_{\phi\_n}$ with $\phi: \mathbb N \to \mathbb N$ is a rearrangement of the $a\_n$ such that for some $\varepsilon > 0$, we have


$$|\phi(n) - n| \leq \varepsilon n$$


for all $n \in \mathbb N.$


Is it true that there exists some $C\_\varepsilon$ depending only on $\varepsilon$ (and not $a\_n$ or $K$) with $C\_\varepsilon \to 0$ as $\varepsilon \to 0$ such that the partial averages of $a\_{\phi\_n}$ satisfy


$$(1-C\_\varepsilon) K \leq \liminf\_{N \to \infty} \frac{1}{N} \sum\_{n = 0}^{N-1} a\_{\phi\_n} \ \leq \limsup\_{N \to \infty} \frac{1}{N} \sum\_{n = 0}^{N-1} a\_{\phi\_n} \ \leq (1 + C\_\varepsilon)K?$$



Does control on the “magnitude” of the rearrangement give control of the rearranged Cesaro sums?
$\newcommand\ep\varepsilon$We have $\{\phi\_0,\dots,\phi\_{N-1}\}\subseteq\{0,\dots,\lfloor(N-1)(1+\ep)\rfloor\}$. Therefore and because $a\_n\ge0$ for all $n$,  

$$\sum\_{n=0}^{N-1} a\_{\phi\_n}\le \sum\_{0\le n\le(N-1)(1+\ep)} a\_n.$$
So,
$$\limsup\_{N\to\infty}\frac{1}{N}\sum\_{n = 0}^{N-1} a\_{\phi\_n} \le (1+\ep)K.$$


Similarly,
$$\{\phi\_0,\dots,\phi\_{N-1}\}\supseteq\{0,\dots,\lfloor(N-1)(1-\ep)\rfloor\}; \tag{1}\label{1}$$
see details on this at the end of this answer.
Therefore and because $a\_n\ge0$ for all $n$,  

$$\sum\_{n=0}^{N-1} a\_{\phi\_n}\ge \sum\_{0\le n\le(N-1)(1-\ep)} a\_n.$$
So,
$$\liminf\_{N\to\infty}\frac{1}{N}\sum\_{n = 0}^{N-1} a\_{\phi\_n} \ge (1-\ep)K.$$


**Details on \eqref{1}:** We have $|\phi\_n-n|\le\ep n$ for all $n$, which can be rewritten as $|k-\psi\_k|\le\ep\psi\_k$ for all $k$, where $\psi$ is the inverse of $\phi$, so that $\phi\_{\psi\_k}=k$ for all $k$. So, $\psi\_k\le\dfrac k{1-\ep}$ for all $k$. So, if $k\le (1-\ep)(N-1)$, then $\psi\_k\le N-1$. That is, $\{\psi\_0,\dots,\psi\_{\lfloor(N-1)(1-\ep)\rfloor}\}\subseteq\{0,\dots,N-1\}$. That is, $\{0,\dots,\lfloor(N-1)(1-\ep)\rfloor\}\subseteq\{\phi\_0,\dots,\phi\_{N-1}\}$, so that \eqref{1} holds.


