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?$$
Best Answer
$\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.