Univariate trimmed-mean bound under sample replacement

Shifting every clean and observed coordinate by $-\mu$ shifts both order-statistic cutoffs, every clipped value, and the output by $-\mu$, so it suffices to analyze the centered data $Z$. By [F1], for each $p\in (0,1)$ the quantile $q_p=Q_p(Z)$ has $P(Z\le q_p)=p$ and $P(Z\ge q_p)=1-p$. Thus $\mathrm{\mid }{q}_p\mathrm{\mid }\le \sigma \mathrm{/}\sqrt{\min (p,1-p)}$: if $q_p\ge 0$, use ${\sigma }^2\ge q_p^{2}P(Z\ge q_p)$; if $q_p<0$, use ${\sigma }^2\ge q_p^{2}P(Z\le q_p)$. For any event $A$, $E[\mathrm{\mid }Z\mathrm{\mid }{\mathbf{1}}_A]\le \sigma \sqrt{P(A)}$: when $P(A)>0$, this follows by expanding $0\le E[(\mathrm{\mid }Z\mathrm{\mid }\mathrm{/}\sigma -{\mathbf{1}}_A\mathrm{/}\sqrt{P(A)}{)}^2]$, and the zero-probability case is immediate. Also $T$ is nondecreasing, since its tail sets expand with $u$, and $T(4\epsilon )\le \sigma \sqrt{2\epsilon }$ by [F1] and this inequality. For a lower clipping endpoint $a=q_p$ with $p\le 1\mathrm{/}2$, put $L=E[\mathrm{\mid }Z\mathrm{\mid }{\mathbf{1}}_{\{Z\le a\}}]$. If $a\le 0$, $E[(a-Z){\mathbf{1}}_{\{Z\le a\}}]\le L$. If $a>0$, centering implies $a(1-p)\le E[Z{\mathbf{1}}_{\{Z>a\}}]=-E[Z{\mathbf{1}}_{\{Z\le a\}}]\le L$; hence $ap\le L$ and the clipping excess is at most $2L$. The symmetric upper-endpoint argument is identical. For a deterministic clip $W={\varphi }_{a,b}(Z)$, $E[(W-c{)}^2]=\mathrm{Var}W+(EW-c{)}^2$ with $c={\varphi }_{a,b}(0)$, and $\mathrm{\mid }W-c\mathrm{\mid }\le \mathrm{\mid }Z\mathrm{\mid }$ because clipping is 1-Lipschitz. Thus $\mathrm{Var}W\le {\sigma }^2$; also $\mathrm{\mid }W-EW\mathrm{\mid }\le b-a$ since both values lie in $[a,b]$.

First use inner endpoints $q_{2\epsilon },q_{1-2\epsilon }$ and outer endpoints $q_{\epsilon \mathrm{/}2},q_{1-\epsilon \mathrm{/}2}$. Require each of the two inner clean $Y$ tail counts to exceed $N(\epsilon +2\eta )$ and each outer count to be less than $N(\epsilon -2\eta )$. Put $a=\eta \mathrm{/}t\ge 0$. Since $\epsilon =(8a+12)t$, [F3] for the binomial counts bounds each inner failure by $\exp [-36(a+2{)}^2\mathrm{\ell }\mathrm{/}(36a+56)]\le e^{-18\mathrm{\ell }\mathrm{/}7}$, and each outer failure by $\exp [-(2a+6{)}^2\mathrm{\ell }\mathrm{/}((28\mathrm{/}3)a+16)]\le e^{-9\mathrm{\ell }\mathrm{/}4}$. The two rational functions are increasing for $a\ge 0$, as direct differentiation shows, so their minima are their values at zero. Thus all four count conditions hold outside probability $4e^{-9\mathrm{\ell }\mathrm{/}4}\le \delta \mathrm{/}2$, since $\mathrm{\ell }>\log 4$. After $M\le 2\eta N$ changes the inner counts are still strictly greater than $\epsilon N$ and outer counts strictly less than $\epsilon N$. Integer counts and the ranks $r_{-}=\lceil \epsilon N\rceil$, $r_{+}=N-\lfloor \epsilon N\rfloor$ therefore give $q_{\epsilon \mathrm{/}2}\le \alpha -\mu \le q_{2\epsilon }$ and $q_{1-2\epsilon }\le \beta -\mu \le q_{1-\epsilon \mathrm{/}2}$. For example fewer than $\epsilon N$ values below an outer lower endpoint means at most $r_{-}-1$ such values, while more than $\epsilon N$ values above an inner upper endpoint means at least $\lfloor \epsilon N\rfloor +1$ such values. These strict inequalities cover noninteger ranks and the integral boundary without a rounding loss.

On the count event, monotonicity of clipping endpoints bounds the clean first-half clipped average above by the average of $W^{+}={\varphi }_{q_{2\epsilon },q_{1-\epsilon \mathrm{/}2}}(Z)$ and below by the average of $W^{-}={\varphi }_{q_{\epsilon \mathrm{/}2},q_{1-2\epsilon }}(Z)$. Step 1.1 bounds $E{W}^{+}\le 2T(4\epsilon )$ and $E{W}^{-}\ge -2T(4\epsilon )$, their variances by ${\sigma }^2$, and their interval widths by $2\sqrt{2}\sigma \mathrm{/}\sqrt{\epsilon }$. These comparison variables have fixed endpoints, so their deviation events are functions of the clean $X$ half and do not rely on the corrupted cutoffs being independent of it. Apply [F3] at $a=\mathrm{\ell }$ separately to the two comparisons. As $t\mathrm{/}\epsilon \le 1\mathrm{/}12$, each deviation is at most $\sigma \sqrt{t}[\sqrt{2}+(4\sqrt{2}\mathrm{/}3)\sqrt{t\mathrm{/}\epsilon }]\le 2\sigma \sqrt{t}$. Their total exceptional probability is $2e^{-\mathrm{\ell }}=\delta \mathrm{/}2$.

Write $A=q_{\epsilon \mathrm{/}2}$, $B=q_{1-\epsilon \mathrm{/}2}$. Replacing at most $M$ first-half points changes the clipped average by at most $2\eta (B-A)\le (\epsilon \mathrm{/}4)(B-A)$. If $A\le 0\le B$, $(\epsilon \mathrm{/}4)(B-A)\le \max \{(\epsilon \mathrm{/}2)\mathrm{\mid }A\mathrm{\mid },(\epsilon \mathrm{/}2)\mathrm{\mid }B\mathrm{\mid }\}\le T(\epsilon )$. If both endpoints are positive, use $B-A\le B$ and the same upper-tail bound; if both are negative, use $B-A\le \mathrm{\mid }A\mathrm{\mid }$ and its lower-tail bound. By monotonicity $T(\epsilon )\le T(4\epsilon )$. Combining this with step 2.1 and the two exceptional probabilities proves the first displayed bound with its exact constants $3$ and $2$, uniformly over every admissible sample-dependent replacement.

For the second bound put $s=\epsilon N\mathrm{/}12\ge \mathrm{\ell }>\log 4$ and keep the same inner quantiles but use wider outer endpoints $q_{\epsilon \mathrm{/}4},q_{1-\epsilon \mathrm{/}4}$. Use the same count thresholds $N(\epsilon \pm 2\eta )$. Since $2\eta \le \epsilon \mathrm{/}4$, the inner downward gap is at least $3\epsilon \mathrm{/}4$ from mean $2\epsilon$, and the outer upward gap is at least $\epsilon \mathrm{/}2$ from mean $\epsilon \mathrm{/}4$. The function $u^2\mathrm{/}(2(p+u\mathrm{/}3))$ increases for $u>0$, so [F3] bounds each inner failure by $e^{-\epsilon N\mathrm{/}8}=e^{-3s\mathrm{/}2}$ and each outer failure by $e^{-3\epsilon N\mathrm{/}10}=e^{-18s\mathrm{/}5}$. The same strict rank argument of step 1.2 brackets the corrupted cutoffs. For the fixed comparison clips, step 1.1 gives directional bias at most $2T(4\epsilon )\le 2\sqrt{2}\sigma \sqrt{\epsilon }$, variance at most ${\sigma }^2$ and width at most $4\sigma \mathrm{/}\sqrt{\epsilon }$. Bernstein at $a=s$ therefore bounds each directional clean-average noise by $(1\mathrm{/}\sqrt{6}+2\mathrm{/}9)\sigma \sqrt{\epsilon }$. The replacement shift is at most $2\eta \cdot 4\sigma \mathrm{/}\sqrt{\epsilon }\le \sigma \sqrt{\epsilon }$. The total error is consequently at most $(2\sqrt{2}+1\mathrm{/}\sqrt{6}+2\mathrm{/}9+1)\sigma \sqrt{\epsilon }<10\sigma \sqrt{\epsilon }$. Its exceptional probability is at most $2e^{-3s\mathrm{/}2}+2e^{-18s\mathrm{/}5}+2e^{-s}\le 4e^{-s}$, because the first two terms sum to at most $4e^{-3s\mathrm{/}2}\le 2e^{-s}$. This proves the second assertion.